Research On Multicast Algorithms In WDM Optical Networks

With the development of network technologies and the variety of user's requirements, multicast applications such as video conferencing, high-definition television, interactive distance learning, and distributed games become widely popular. On the other hand, the emergence of wavelength-division multiplexing (WDM) technology has made it possible for a single fiber to provide vast amount of bandwidths and opened the gates for bandwidth-intensive multicast applications. Therefore, the problem of supporting multicasting in WDM networks has become a research topic in recent years. In order to realize the optical layer multicasting, various techniques are required from both the data plane and control plane. Currently, there are still a lot of open issues for both of the data plane and control plane in multicast capable WDM networks. This dissertation investigates multicast algorithms in the control plane. Specifically, we mainly focus on the following aspects: constrained multicast routing in WDM networks, dedicated multicast protection, shared multicast protection, and multicast traffic grooming.In real networks, physical layer properties may set some constraints on the multicast routing problem. Chapter 2 of this dissertation studies the constrained multicast routing problem in WDM networks. The main contributions include: (1) to reduce network construction cost, it is desirable to configure light-splitting nodes sparsely in WDM networks. However, existing sparse-splitting constrained multicast routing algorithms have different pitfalls in terms of consumed cost, the number of established light-trees, and the computation complexity. To address these problems, this thesis proposes an efficient sparse-splitting constrained multicast routing algorithm and conducts extensive simulations to evaluate the performance of the algorithm. (2) It has been widely recognized that physical layer constraints, including wavelength continuity constraint and transmission impairments, must be taken into account when routing multicast connections in all-optical networks. To the best of our knowledge, the problem of multicast routing under wavelength continuity and transmission impairments (polarization mode dispersion and amplifier spontaneous emission) constraints has not been studied. This dissertation studies this problem and proposes a multicast routing algorithm. The simulation results prove that the proposed algorithm can find a multicast tree with minimum cost under these constraints.In WDM optical networks, any single fiber failure may lead to multiple destinations of a multicast session fail to receive data. Therefore, it is important to provide protection for multicast sessions. Chapter 3 of this dissertation investigates the dedicated multicast protection algorithms for multicast sessions. The main contributions are summarized as follows. (1) The survivable multicast route derived by most of the existing algorithms may include some redundant links. To reduce protection resource, this dissertation first improves existing ILP (Integer Linear Programming) formulation for the dedicated multicast protection problem, and then proposes two algorithms. The two algorithms can remove the redundant links and avoid redundant links in the process of building survivable multicast route, respectively. The simulation results show that the two algorithms have better performance than other existing algorithms. Furthermore, the solutions generated by the two proposed algorithms are quite close to the solutions generated by ILP. (2) With sparse-splitting constraint, the backup paths derived by existing algorithms can not share wavelength channels with primary tree. On the other hand, with wavelength continuity constraint, some of the existing algorithm even can not find link-disjoint backup paths. To address these problems, this dissertation proposes a multicast protection algorithm under sparse-splitting and wavelength continuity constraints. The backup paths derived by the proposed algorithm can share wavelength channels with primary tree in sparse-splitting networks. Due to wavelength channels sharing among primary tree and backup paths, the blocking probability caused by failures of finding link-disjoint backup paths is reduced. Simulation results show that the algorithm can improve wavelength utilization ratio and blocking probability.As we know, backup resource sharing within different multicast sessions can reduce consumed backup resources and enhance wavelength utilization ratio. Currently, only a few of literatures studied the shared multicast protection problem. Chapter 4 of this dissertation investigates the shared multicast protection algorithms for multicast sessions. The main contributions are summarized as follows. (1) This dissertation studies the shared multicast protection problem under SRLG (Shared Risk Link Group) constraints. With SRLG constraints, it is possible that we can't find a link-disjoint backup path for a primary path. This is the so-called "trap" problem. Segment protection scheme is regarded as an efficient scheme to avoid traps. However, most of the existing segment multicast protection algorithms use fixed approaches to divide segments for a multicast tree. These fixed approaches have two pitfalls. First, these fixed approaches can't avoid traps in some cases. Secondly, these fixed approaches can't guarantee the optimization of wavelength utilization ratio. Therefore, this dissertation proposes an efficient shared segment multicast protection algorithm, which divide segments for a primary tree according to the network status and the SRLGs traversed by the primary tree. The proposed algorithm can avoid traps and enhance the wavelength utilization ratio efficiently. (2) As far as we know, the problem of shared multicast protection under sparse-splitting constraints has not been studied. This dissertation investigates the problem of shared multicast protection in sparse-splitting WDM networks, and proposes an efficient algorithm for shared multicast protection with sparse-splitting constraints. The proposed algorithm can achieve self-sharing and spare-capacity sharing (backup wavelength channels sharing within different multicast sessions) in sparse-splitting networks. Simulation results show that through wavelength channels sharing, the performance of wavelength utilization ratio and blocking probability is improved.In WDM networks, each wavelength channel has a transmission rate on the order of tens of Gigabits per second. However, most multicast applications have bandwidth requirements that are far less than that provided by a wavelength channel. Therefore, in order to efficiently utilize resources, multiple sub-wavelength traffic requirements are groomed onto a single wavelength channel. Currently, only a few of literatures investigated the dynamic multicast traffic grooming problem. The existing dynamic multicast traffic grooming algorithms can be divided into two categories. The algorithms in the first category use auxiliary graph to groom dynamic multicast traffics. And the algorithms in the second category try to use established light-trees to accommodate a new multicast traffic. Due to the large number of nodes in the auxiliary graph constructed by the algorithms in first category, the computation complexity of the algorithms in first category is very high. And the wavelength utilization ratio of the algorithms in the second category is very low. To address these problems in existing algorithms, this dissertation proposes two dynamic multicast traffic grooming algorithms. In the two proposed algorithms, an existing light-tree can be reconfigured or extended when a route is to be established for a new request, and the residual bandwidth can be used by the new request. The simulation results show that the proposed algorithms can improve the network resource utilization ratio and blocking probability.