两层光网络规划的优化算法研究

【作者】 王丽；

【导师】 李乐民；

【作者基本信息】 电子科技大学 ， 通信与信息系统， 2009， 硕士

【摘要】 随着波分复用(WDM, Wavelength Division Multiplexing)、光交叉连接(OXC, Optical Cross-Connect)以及光分插复用(OADM, Optical Add-drop Multiplexing)等技术的飞速发展,使得WDM技术可以提供巨大的带宽,从而成为下一代骨干网络的核心技术。由于MPLS技术具有良好的QoS、TE等功能及其在统一控制平面上的应用,使得MPLS成为了适配IP和WDM网络的最佳选择,MPLS over WDM网络得到了迅速发展。WDM光网络中每个波长可以提供高达上吉比特(如OC-48、OC-192、OC-768)的传输容量,而在实际应用中,很多业务请求的通信速率都小于一个波长粒度,例如OC-1、OC-3、OC-12(51.84Mb/s、155.52Mb/s、622.08Mb/s)。显然,为每个带宽小于一个波长粒度的业务请求分配一个独立的波长信道,会降低网络资源利用率且不经济。并且,由于光纤中波长数目的限制、网络节点中光收发器数目以及光交叉连接容量的限制等,不可能为每个业务请求分配一个独立的波长信道。显然,有必要将多个低速的业务请求汇集起来用一个波长信道传输或者某个业务请求通过多跳光路(Multihop Lightpath)的相续汇集最终到达目的节点,这就是所谓的业务量疏导(Traffic Grooming)技术。WDM光网络以其巨大的带宽满足海量的需求,但巨大传输带宽也面临挑战,即一旦网络部件失效,大量业务数据将会丢失,将导致巨大的损失。因此在网络设计时需要将网络的抗毁能力纳入考虑,因此,多层WDM光网络的生存性研究已经成为热点。本文研究MPLS over WDM两层光网络中的优化设计问题,主要研究带共享风险链路组(Shared Risk Link Groups, SRLG)的网络可生存性业务量疏导问题。可生存性业务量疏导问题可以如此描述:给定一个网络配置,包括物理链路、每个网络节点的光收发器数目、每根光纤的波长数目以及波长容量,可生存性业务量疏导就是为一组具有各种低速带宽粒度的业务连接建立光路并提供保护,以有效地安排这些连接请求,同时优化网络的性能。本文主要研究了两种问题:(1)针对网络资源配置足够、需要最小化已用的物理资源(即波长)的问题,作者分别提出了一种基于链路-路径(Link-Path)的整数线性规划(integer linear programming, ILP)数学模型和一种名为层间信息路由&多层业务量疏导(Cross Layer Information Routing & Multi-layer Traffic Grooming, CLIR-MLTG)的启发式算法。相比于一般的基于节点-链路(Node-Link)的ILP模型,本文提出的ILP模型大大的降低了问题规模,减少了求解时间;相比于已经存在的启发式算法,CLIR-MLTG算法避免了在不必要的情况下增加光路,从而避免了增加物理资源。(2)针对物理网络资源受限的情况下,最大化网络吞吐量的同时最大化网络收益的问题,提出了一种基于拉格朗日松弛(Lagrangian Relaxation)的层间迭代ILP算法,将整个优化问题分解成MPLS和WDM层的两个子问题,然后通过两层数据交互迭代的方式得到整个问题的上、下界,从而精确的估算出整个优化问题的最优解。更多还原

【Abstract】 With the rapid development of WDM (wavelength division multiplexing), OXC (optical cross-connect) and OADM (optical add-drop multiplexing) technology, WDM optical network can provide huge bandwidth and has become the core technology of next generation networks. Due to the excellent functions (QoS, TE) together with the implementation in the unified control plane, MPLS technology becomes the best choice to integrate IP and WDM networks, and MPLS over WDM network developed rapidly.The wavelength of WDM optical networks can provide up to more than G bits transmission capacity (for example), but in real applications, the granularity of low-speed demands is much smaller, such as OC-1, OC-3, OC-12(51.84Mb/s、155.52Mb/s、622.08Mb/s). Obviously, to accommodate such kind of low-rate traffic demands (or connections) with one lightpath will lead to inefficient resource utilization. At the same time, it is impossible to establish end-to-end lightpaths for all the traffic demands, due to the limits of the number of wavelengths per fiber and the number of receivers per node. So it is necessary to combine the low-speed demands onto high-speed lightpaths in multi-layer optical networks, this scheme is the so called traffic grooming technology.WDM optical networks transmit large number of traffic demands with its huge bandwidth, but this also brings great challenges. A single failure of any network equipments may affect large amount of demands and cause great loss. So it is necessary to take the fault recovery abilities of optical networks into account. Hence, survivable study has been playing more and more important roles in the multi-layer network design.In this paper, the author focuses on the survivable traffic grooming problem under SRLG (Shared Risk Link Groups) constraints in MPLS over WDM mesh networks. Survivable traffic grooming problem can be described as follows: Given the network configuration, including the physical links and nodes, the number of transceivers and receivers, the number of wavelength in each fiber and the wavelength capacity, survivable traffic grooming can effectively grooming low-speed demands onto high-capacity lightpaths as well as provide protection to demands, and improve the network throughput or reduce the network cost.This paper studies the following two problems: (1) Given enough network resources, the objective is to minimize the total used wavelengths in physical networks. Here the author proposes a novel Link-Path based ILP model and a novel heuristics algorithm named CLIR-MLTG (Cross Layer Information Routing & Multi-layer Traffic Grooming). Compared with the Node-Link based ILP formulation, the proposed Link-Path based ILP model reduced problem size and execution time. Comapared with the traditional heusistic methods, CLIR-MLTG heuristic algorithm avoids adding lightpaths when unnecessary, and then minimizes the total used physical resource. (2) With limited network resources, the objective is to maximize the network throughput as well as maximize the network revenue. In order to solve this problem, the author proposes a cross layer iteration ILP algorithm based on Lagrangian Relaxation (LR), and decomposes the total optimization problem into two sub-problems in MPLS and WDM layer, and get the upper and lower bounds through interactive iteration of the two-layer data, and then estimate the optimized results of the whole optimization problem.更多还原