Research On Hose-model-based Robust Routing And Survivability In WDM Optical Networks

On planning optical WDM (Wavelength Division Multiplexing) networks, traditional routing and survivable algorithms are based upon an explicit knowledge of traffic matrix. However, with the explosive incease of Internet traffic and unceasingly emerged broadband services in recent years, the packet flows running over the optical layer drastically fluctuate over time. This arouses significant difficulty in predicting/ estimating the actual pattern of each point-to-point demand. As a result, it becomes far beyond necessary to solve the robust routing and survivability with uncertain demand information, so as to keep pace with the booming and dynamially varing services in the network.Hose uncertain traffic model was firstly proposed in the research of virtual private networks (VPNs). In this model, the known traffic information is confined to the total rates entering and leaving each network node (i.e., the"row sums"and"column sums"of a traffic matrix) other than a full demand matrix. Immune from depicting the accurate traffic distributions in the network, the model dramatically facilitates the traffic estimation and is more flexible for design. This dissertation devotes to the optimization of WDM optical networks under the hose model constraints, and the author's work includes two perspectives: (1)the hose-model-based robust routing; (2)the robust survivability design on the basis of hose model. The major innovations of this paper could be summarized as the following 5 points. Firstly, the static robust routing is investigated under the hose uncertain traffic model. In stead of focusing on how to reduce link cost as the previous work did, the author explores the factors (including the link cost and node switching cost) that impact the network cost in a more comprehensive manner, and then proposes more cost-saving heuristic algorithms than the existed solutions. Secondly, the author studies how to work out the optimal robust routing under the hose model constraints, using partially known point-to-point traffic information. Here, a new routing strategy, as well as an algorithm based on it, is presented. Compared with the existed robust routing schemes, the algorithm can effectively mitigate network delay and jitter. Thirdly, the dynamic QoS robust routing under the hose model is discussed. To solve this issue, the author puts forward a heuristic algorithm. This algorithm dynamically adjusts the routes according to the LoS (level of service) of current connection request, the traffic being transmitted and the number of unused wavelengths in the network. Compared with the existed dynamic robust routing algorithms, the proposed algorithm provides better performance. Fourthly, the author studies single-link failure robust protection in the WDM mesh networks, and proposes two shared protection heuristic algorithms. Simulation results show that, the two algorithms achieve distinct improvement in cost and failure recovery time, compared with the previous robust protection algorithms. Finally, the author explores the multiple failure survivability on the basis of dynamic hose model. The ideas to solve this issue includes: (1) differentiated protection; (2) introduction of the concept of"Criticality", i.e., to bypass the network component with high criticality when computing the work path and backup path of each connection request. In pursuit of these two ideas, the author proposes two heuristic algorithms and evaluates them by simulations.Chapter 2 addresses robust routing in WDM mesh networks under the hose demand specifications, and the study includes three perspectives: (1) hose-model- based static robust routing; (2) robust routing with partially known traffic matrix (i.e., the awareness of point-to-point demands between a portion of node pairs); (3) dynamic robust routing under the hose traffic model. As for the first issue, the author puts forward two mathematical programming (MP) formulations respectively for both single path routing (SPR) and Valiant load-balancing, with the objective of minimizing total network cost. By solving the formulations, we can arrive at an optimal resource provisioning such as wavelengths channels, optical transceivers and wavelength converters, etc. As the optimization problem of robust routing in WDM networks is NP-complete, two heuristic algorithms, IBFS (Iterative Breadth-first Search) and MNC (Maximizing Network Capability) are proposed, on the basis of SPR and VLB, respectively. Simulation results show that both algorithms provide nice performance, and MNC exhibits more desirable scalability and performs much better than previous solutions in large networks. To sovle the second issue, the author puts forward adaptive load-balancing (ALB) routing strategy based on VLB, in terms of the observation for traffic. Then following the idea of ALB, a heuristic algorithm ADT (Adding Direct Traffic) is also proposed. The basic idea of ALB and its algorithm ADT is to use this known point-to-point traffic information to adjust as least as possible the two-hop virtual topology built by VLB, so as to carry more traffic load in single hop and thus reduce the delay and jitter. Simulation indicates that ALB approaches nice throughput while provides better QoS than the VLB. In the study of the third issue, the author considers the full-meshed virtual topology, and proposes DDALB (Differentiated Dynamic Adaptive Load-balancing) heuristic algorithm.From chapter 3 to chapter 5, the author dwells on the issue of hose-model-based robust survivability in WDM mesh networks. Chapter 3 and chapter 4 investigate single-link failure protection and correlated-link failure protection, respectively; while chapter 5 explores the survivability design under the failures of multiple network components. In chapter 3, the author proposes two shared segment protection (SSP) heuristic algorithms, one VPN-tree-based (called Tree-based Shared-segment Protection, TSSP), one VLB-based (called VLB-based Shared-segment Protection, VLB-SSP), to deal with single-link failure. As for resource provisioning, TSSP aims to minimize the number of leaf nodes (i.e., the node whose in-degree and out-degree are both 1) on the work tree, so as to reduce the number of work paths and backup paths. Therefore, it achieves a desirable resource utilization ratio. While in VLB-SSP, the work wavelengths and backup wavelengths are provisioned through the minimization of total network cost so that the cost budget gets close to optimal. As for failure recovery, both TSSP and VLB-SSP adopt shared segment protection. Therefore, they can maintain a rational recovery time.The research of correlated-link failure protection includes two perspectives. (1) For the problem of double-link failure protection, the author proposes DVLBSP (Differentiated VLB Shared Protection) heuristic algorithm. Complying with the idea of differentiated protection, the algorithm only computes backup paths for the work paths that fails to satisfy the given reliability requirement. Moreover, it also adopts shared protection for wavelength assignment, with the traffic model and network topology being considered. Simulation results show that DVLBSP receives a nice trade-off between cost and reliability. (2) As for shared risk link group (SRLG) failure protection, a heuristic algorithm called PSPPKT (Partial SRLG-disjoint Protection with Partially Known Traffic) is proposed and evaluated by simulations.For surviving multiple failures, the author proposes an ALB-based heuristic algorithm (called CAL, Criticality Avoidance Load-balancing), by blending the two major approaches that accommodate survivability—protection and restoration. According to the simulation results, CAL is a practical solution to robust survivability against multiple failures under the dynamic hose traffic model.To verify and evaluate the proposed algorithms in this dissertation, simulation platform is developed. Chapter 6 introduces this platform, and gives important pseudo codes. Chapter 7 concludes this dissertation.