【作者】 张颢；

【导师】 王行刚；

【作者基本信息】 中国科学院研究生院（计算技术研究所） ， 计算机系统结构， 2004， 博士

【摘要】 随着光通信技术的快速发展,光纤通信已从单纯的传输技术逐步演化为重要的组网手段。以波长路由为基础的光网络设计,对于提高设备利用率,降低网络建设成本有着至关重要的意义。本文研究了优化光网络系统设计的方法,主要有以下贡献:1).在分路由和单一路由策略下的流量路由优化问题利用势函数将网络拥塞优化目标转换为连续可微的数学表达式,使得目标函数能够反映整个网络中各链路负载状况。讨论了如何调整势函数构造参数,控制不同负载链路在目标函数中的权重表达,缩短算法的收敛时间。根据一定的数学分析,利用微分方法设计了以当前解为基础的最佳优化操作。提出了虚拟链路利用率λe’的概念,用来松弛可行解的限制条件,动态调节λe’可以灵活适配流量需求矩阵和链路带宽设定之间的差异,并使得搜索算法可以在更大的广度上选择初始方案。2).光通道路由优化问题对光通道路由优化进行了详细的数学分析,将其分解为特定边权值下的最短路径问题和可控规模的线性规划模型,在此基础上,设计了一个基于当前解邻域变换的快速搜索算法。考虑波长一致性限制条件,将RWA问题转换为更大规模拓扑上的单纯的通道路由问题,使得以降低网络拥塞为目标的光通道优化路由算法可以很好的应用于RWA问题的求解。3).在逻辑拓扑设计方面设计了一个遗传算法来优化设计,同其他此类方法相比,该算法不同之处在于以高质量的初始解群为基础,通过在遗传操作中引入较多的启发规则,加快“劣质”基因的淘汰,提高算法的收敛速度。为了在逻辑网络设计中体现物理光网络的影响,提出了源宿节点对之间光通道友好度ξij的概念,并利用公式“rs′d =rsd+β?ξsd”生成加权后的流量矩阵R,有效避免了在优化算法中引入新的独立参数。4).在物理光网络设计中,以前述高效的路由方案求解算法为基础,根据对网络拓扑的快速评估,提出了一个由高连接度的基准拓扑逐步进化为目的拓扑的物理光网络设计方法。通过基准拓扑确定、冗余链路删除等规则的设置,可以在求解过程中方便的引入工程设计经验,引导算法进行高效搜索,避免考察工程上“无效(或低效)”的解空间。更多还原

【Abstract】 The rapid development in WDM is making the transformation of fiber communication from a transmission method to the networking technology. The optimal design of optical networks, which are based on lightpaths routing, is becoming a very important issue to Internet Service Providers. In this paper, the methods for optical network designing are researched, the main contributions are listed below:1). The problems of traffic optimal bifurcated and non-bifurcated routingThrough potential function, the objective - minimization of network congestion - is converted to a continue, differential expression in which loads of all links in the network are considered. We also present the way to tune potential construction arguments to control different loaded links’“voice”in the objective function and accelerate the convergence process. Based on the flow deviation method, optimal operations, which are the main part of the optimal processes, are designed for the two traffic routing problems.The virtual bandwidth usage is presented to loose the constraints for valid solutions and smooth the difference between requirement matrix and link bandwidth.2). The problem of lightpaths optimal routingLightpaths optimal routing is analyzed mathematically and divided into two sub-problems, shortest path problem and small-scale linear programming model. A bifurcated routing algorithm is developed and the sub-problems are solved to find an optimal solution in minute-scale running time.Considering the wavelength continuity constraint, the RWA (Routing and Wavelength Assignment) problem is transformed into lightpaths routing problem over a larger-scale network that consist of many copies of the original network. So, it is natural and reasonable to apply lightpaths optimal routing algorithm to RWA problem.3). Logical topology designWe present a genetic algorithm to realize the optimization. The algorithm, different from other similar methods, gets excellent convergence characteristic from high-quality initial population, and more heuristic genetic operators that quicken the elimination of“bad”genes. To make the logical topology design to take the consideration of physical network, we present lightpath liabilityξij, which is incorporated into requirement matrix using equation“rs′d =rsd+β?ξsd”.更多还原