节点文献

WDM光网络中的多播算法研究

Research on Multicasting Algorithms in WDM Optical Networks

【作者】 鲁才

【导师】 李乐民;

【作者基本信息】 电子科技大学 , 通信与信息系统, 2007, 博士

【摘要】 随着光网络的迅速普及,作为未来Internet骨干支撑的WDM(Wavelength Division Multiplexing)光网络组网技术和业务提供技术受到了越来越多的关注。另一方面,随着光学技术的日益成熟,功能越来越完善的各种光通信器件/设备大批涌现,使得许多原来需要在业务交换层面完成的工作被更多地移植到了光层,一个典型的例子就是近年来广受关注的光网络多播技术。分光器的出现为实现光网络中多播传输提供了硬件基础,利用分光器可以设计出支持光层多播路由的光交叉连接器MC-OXC(Multicast Capable-OXC)。在单播连接中,光层路由是一个路状结构,而多播连接是一种点对多点的连接请求,需要在光层上构建全光的树状路由——光树或者光林(多棵光树)。与光层的单播路由,光层树状多播路由问题更加复杂。本文主要研究光层多播的算法设计问题,主要包括WDM光网络多播的网络静态规划问题、多约束条件下光树的优化设计问题、光层多播的保护问题以及光层多播的业务疏导问题。与光层的单播连接和IP层的多播技术相比,光层多播路由的计算问题存在一些特殊的约束条件,主要包括波长连续性约束、稀疏分光器配置约束和能量损伤约束。在实际的光网络中,不是每个节点都配置波长转换器。这就导致了光网络中的波长连续性约束。在这种下,多播选路与波长选择密切相关。对于单播请求,波长连续性约束下的光路计算问题被称为RWA(Routing and Wavelength Assignment)问题,而相应光树的计算问题被称为MC-RWA(Multicasting RWA)问题。此外,考虑到网络建设成本,在实际的光网络中,不是所有的网络节点都配置了分光器。这就形成了光网络中多播路由的稀疏分光器约束。在稀疏分光器配置约束下,光树的计算问题不再是一个传统的Steiner Tree(有文献译为施泰纳树,即求覆盖网络节点集合的一个子集的最佳生成子树)问题。在光树路由结构中,光信号从源点输出经过树状路由传输到每个目的节点。信号能量经过了传输衰减损伤和分光器的分光损伤。传输损伤主要是由于光信号在光纤系统中信号能量的吸收、散射等原因造成的。分光器引入的信号能量损伤是由于光信号通过分光器后,将输入的信号能量分成了多份并通过不同的光树分支输出,从而导致了每条分支上信号能量的损伤。但是为了保证每个目的节点接收到的信号能量都能超过接收器的接收门限,光树的计算必须考虑光树的能量损伤约束条件。这三个约束条件在计算光树的过程中同时存在,所以一个可行的多播树必须满足上述所有约束条件。光网络多播的静态规划可用于网络建设初期的规划设计或者网络中较大周期的虚拓扑重配置中。本文第二章主要从两个方面研究了光网络多播的静态规划问题:(1)在稀疏波长转换器和分光器配置的网络中,波长转换器和分光器的最佳放置问题;(2)在光纤波长通道数受限情况下,研究如何利用最少的网络资源承载给定业务矩阵的多播连接。这两个问题解决都是在波长连续性约束、稀疏分光器配置约束和能量损伤约束条件下进行的。在第二章,通过一个混合线性规划MILP(Mixed Integer Linear Programming)模型,将光网络中多播的静态规划问题转化为一个优化问题。通过求解此模型的最优解,可以获得分光器和波长转换器的最佳放置位置,并且可以得到满足所有约束条件的网络虚拓扑设计。由于光网络中多播路由的能量损伤约束是一个乘性约束。利用多播树上节点的能量守恒规律,在第二章,用一组线性的关系式准确描述了光层多播的能量损伤约束条件。给定网络资源配置(包括波长转换器和分光器的放置位置、光纤链路上的波长通道数),第三章研究了在动态多播业务环境中的多播树构建问题。如果没有约束条件,最佳多播树的计算问题就是一个传统的Steiner Tree问题。由于Steiner Tree问题是一个NP完全问题,约束条件下多播树的计算问题要比Steiner Tree问题更为复杂,所以约束条件下多播树的计算问题也是一个NP完全问题。在动态连接环境中,只能通过启发式算法来求解一个近似解。在图论中,树是一个不含圈的简单连通图。但是光层多播的约束条件下,一个可行的多播路由可以包含圈。针对这一特点,第三章提出的NMO(Novel-Member-Only)算法是对Member-Only的改进算法,提高了算法的性能。对于能量损伤约束条件下的多播树计算问题,提出了基于多播树扩张的选路算法MRST(Multicast Routing Basing on Spanning Tree)和基于重路由的选路算法MRRR(Multicast Routing Basing on Re-Route)。此外,一个可行的多播树算法必须满足所有约束条件,第三章还提出了多约束条件下的多播树构建算法。WDM技术可以大大提高链路的传输容量,同时也使网络的生存性问题日渐突出。在WDM光网络中,网络部件失效时可能遭受比传统网络更大的损失,比如一根光纤断裂将导致所有经过该光纤的光路或者光树都失效,而每条全光通道都能以Gbps的速率传输数据,这样的失效对网络中业务的影响是非常严重的。本文的第四章和第五章研究WDM网络多播的保护问题。第四章主要研究多播专用保护技术,第五章主要研究了多播的共享保护技术。在第四章,首先将多播专用保护问题用一个最优化数学模型进行描述。给定多播请求和网络配置,通过求解最优化模型,可以得到最佳的多播专用保护通路由,并为动态多播业务环境下的启发式算法提供一个理论上的参考。与单播保护问题类似,光网络中多播保护可以采用分段保护的机制。在分段多播保护中,一个关键的问题是如何将给定多播树进行分段。分段机制的不同将会对算法性能产生很大的影响。在第四章提出的自适应分段保护ASSP(Adaptive Segment Shared Protection)机制中,算法将多播树上的枝叶节点作为分段的起始节点,同时为其构建一条保护通路,重复这一过程直到多播树上没有枝叶节点为止,从而实现了多播树的保护。同时,在网络稀疏配置(稀疏波长转换器配置和稀疏分光器配置)约束下,现有的多播保护算法在波长连续性限制约束下将会失效。第四章还提出了网络稀疏配置下的双路多播保护TPMP(Two-Paths Multicast Protection)算法。为了提高资源利用率,第五章研究了光网络多播的共享保护机制。首先通过一个ILP模型将共享保护机制描述成一个最优化问题,通过ILP模型的求解可以得到共享保护机制下的多播虚拓扑设计。并提出了混合共享的多播保护算法MSSP(Mixed Segment Shared Protection)。根据仿真结果,MSSP算法提高了网络资源的利用率。在WDM网络中,波长路由的巨大带宽和单个连接请求的小粒度带宽不匹配。为了提高传输效率,可以将低速的多播业务连接汇聚起来在一棵光树上进行传输。第六章研究了WDM网络多播的业务疏导技术,并提出了多播树分解的业务疏导算法MTD(Multicasting Tree Decompose)。MTD业务疏导算法的基本思想是尽量通过网络上现有的光树进行业务疏导,每一次业务疏导都会导致新建多播树目的节点数的减少,从而改善网络的多播吞吐能力。此外,第六章还研究了WDM网络多播业务疏导的生存性问题,并提出了两种分析模型:多播混合带宽保护的业务疏导分析模型TG-MBP(Traffic Grooming with Mixed Bandwidth Protection)和多播共享保护的业务疏导分析模型TG-SP(Traffic Grooming with Shared Protection)。在TG-MBP模型中,一个专用保护的多播路由SMR(Survivable Multicasting Route)可以分解成为两棵“对偶”树结构。在网络正常情况下,连接都可以传输到SMR上的任意节点,从而保证了到SMR上任意节点的业务都可以进行业务疏导。利用TG-MBP提出了专用分段保护的多播业务疏导算法MTG-SP(Multicast Traffic with Segment Protection)。在TG-SP模型中,多播保护采用的是共享保护机制。在共享保护模型中,只有到工作树上节点的业务才可以进行业务疏导。基于这一模型,提出了共享分段保护的多播业务疏导算法MTG-SSP(Multicast Traffic Grooming with Shared Segment Protection)。最后进行了全文总结。

【Abstract】 With the popularization of optical networks, the technology of wavelength division multiplexing (WDM) optical networks becomes the core technology of next generation Internet backbone networks. On the other hand, with the maturity of optics technology, there emerge more and more optical communication equipments/apparatus with perfect function. We can transplant some operations to the optical layer which are carried out on layer of service switching originally, for example, the technology of optical multicasting which absorbs attention widely in recent years. The emergence of the light splitters provides the hardware support for optical multicast technology. With the light splitters, we can design the multicast capable OXC--MC-OXC. In the case of unicast in the optical networks, the route of request has a "path" structure. The multicast service is the communication of one point to multiple points. So the route of the multicast request has a "tree" structure, called light trees or light forest (multiple light trees). Comparing with the technology of the unicast in optical layer, the problem of computing the optical multicasting routes is more complex. In this paper, we study the algorithm of optical multicasting, including the static programming of multicast in the WDM optical networks, the optimal design of the multicast trees with multiple constraints, the survivability of the optical multicasting and the traffic grooming of optical multicasting.The problem of computing optical multicast tree is more complex than that of unicast, for the optical multicast tree must satisfy some especial constraints: wavelength continuity constraints, sparse light splitter configuration constraints and power budge constraints. With the constraints of wavelength continuity, the multicast routing is correlative with the wavelength assignment. The problem of light path with wavelength continuity constraints is named RWA (Routing and wavelength assignment). In the same way, problem of computing the light tree with wavelength continuity is named MC-RWA (Multicast RWA). If there are none of wavelength converters in the network, the light tree must be assigned same wavelength channel to each optical fiber on the tree. In the practical optical communication system, we need not place a light splitter to every node in view of the network cost. With the constraints of sparse light splitter configuration, the computing of light tree is not a Steiner Tree problem. In the route of light tree, the optical signal is transmitted from the source node to every destination node. The optical signals suffer losses as they travel from source to destination node. We distinguish two types of losses: signal attenuation and splitting loss. The loss of signal attenuation is due to the absorbing and dispersing when the optical signal travel along the light tree. When the optical signals pass by the MC-OXC, the power will be split several parts and then switched to according outputs, which introduces the splitting loss of the optical signal. In order to ensure every destination node receive the data, the power of received by each receiver must above a threshold. So the light tree must satisfy the constraints of power budge. The three constraints coexist for a light tree, so a feasible light tree must satisfy all the constraints.The static programming of multicast optical network can be used for the layout design of network or the reconfiguration of virtual topology after a long period. Chapter 2 studies the static programming problem from two perspectives: (1) the placement of wavelength converters and light splitters in the sparse configuration networks; (2) with the limits of wavelength number per fiber, the network resource provisioning for given multicast traffic matrix. We formulate the two problems as a mixed integer linear programming (MILP) model. By this mean, the problem of static programming is transferred to an optimal problem. When we solve the MILP and achieve the optimal solutions, we can attain the placement of wavelength converters and light splitters. What’s more, we can achieve the design of virtual topology of the networks. Especially, the constraints of power budge are multiplicative. Usually, we can not formulate a multiplicative constraint problem with linear equations precisely. In chapter 2, we use linear programming to solve optimal multicast routing and wavelength assignment with power budget constraints by using the relation of power conservation at every node on the light tree.Chapter 3 studies the problem of dynamic multicast routing for given the configuration of network (including the placement of wavelength converters and light splitters, the wavelength number on each fiber link and the physical topology of network). With none constraints, the problem of optimal multicast tree is a Steiner Tree problem, which is NP hard. The problem of multicast tree with constraints is not less hard than that of the problem of Steiner Tree. So the multicast tree with constraints is NP hard. Under the environment of dynamic multicast traffic, we can only propose some heuristic algorithms to compute the multicast tree with constraints. In graph theory, a tree is a simple graph with no circles. With the constraints of the optical multicast, a feasible light tree may contain some circles. In chapter 3, we propose a heuristic algorithm (NMO) to compute the light tree with sparse light splitters configuration constraint according to the character of light tree. What’s more, we propose an algorithm for compute the light tree with all the constraints at the rest of chapter 3.WDM technology provides the tremendous bandwidth, while poses the survivability issue urgent. In WDM network, the failure of a network component can lead to tremendous loss than in other traditional networks. For example, a failed fiber link can lead to the failure of all the lightpaths that traverse the failed link, since each lightpath is expected to operate at a rate of several gigabytes per second, a failure can lead to a severe data loss. Chapter 4 and 5 study the protection of optical multicast in the mesh WDM networks. Chapter 4 mainly studies the scheme of dedicated multicast protection and chapter 5 focuses on the scheme of shared multicast protection. In chapter 4, we formulate the problem of dedicated multicast protection into a ILP model. Given a batch of multicast requests and the configuration of networks, we can achieve the virtual topology design by solving the ILP. Similar to the case of unicast, we can adopt the segment protection for the multicast request. The critical problem of segment multicast protection is how to identify the segments of a multicast tree. The scheme of segment will affect the performance of algorithm seriously. In chapter 4, adaptive segment shared protection (ASSP) algorithm is proposed. In the scheme of ASSP, we establish a light path to protect each segment between two leaf nodes on the multicast tree. With the constraints of sparse wavelength converters configuration, almost all the algorithms will be invalid. In chapter 4, we propose two paths multicast protection (TPMP) algorithm for sparse wavelength converters configuration constraints. In order to improve the network resource utilization efficiency, chapter 5 studies the scheme of shared multicast protection. The problem is formulated into an ILP model. We can solve the ILP model to achieve the virtual topology design. And then we propose mixed shared segment protection (MSSP) algorithm to protect multicast requests. The numerical results show that MSSP algorithm provides significant capacity savings.In the WDM optical networks, it is mismatch for the enormous bandwidth of wavelength channel and that of single server. It is necessary to investigate how to efficiently set up connections for these traffic streams. Traffic grooming can meet this problem. Chapter 6 studies the technology of multicast traffic grooming in the WDM mesh networks. An algorithm of Multicast Tree Decompose (MTD) is proposed for dynamic multicast traffic grooming. The main idea of MTD is try to decrease the destination number of multicast request by grooming the traffic on the existing multicast trees. Then we study the problem of survivability multicast traffic grooming and propose two model, named multicast traffic grooming with mixed bandwidth protection (TG-MBP) and multicast traffic grooming with shared protection (TG-SP). In TG-MBP, a dedicated protected survivable multicast route (SMR) route can be partitioned into two "dual-trees". Under normal operation, the traffic can be transferred to any node on the SMR, which ensures that we can groom the traffic on the SMR for every node on the SMR. According to the model of TG-MBP, multicast traffic grooming with segment protection (MTG-SP) algorithm is proposed. In the model of TG-SP, the protection resource can be shared by different multicast requests. Under normal operation, the traffic can only be transferred to the node on the working tree. So the traffic can be groomed on the working tree for the node on the tree. Based on the model of MTG-SP, the algorithm of multicast traffic grooming with shared segment protection is proposed.

节点文献中: