Research On Multicasting Algorithms In WDM Optical Networks

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.