| In the information age, human has been heavily depended on reliable operation of communication networks, especially on the continuous operation of backbone networks. With recent advances in WDM (Wavelength Division Multiplexing) technologies, the potential for enormous bandwidth in a single optical fiber has been exploited and WDM will become the core of the next generation backbone networks. Since each wavelength channel has the transmission rate over several gigabits per second, the failures of fiber links or nodes may lead a lot of services to be blocked. Therefore, the network survivability has become more urgent. Since the techniques of protection have faster failures recovery time, many researches are based on protection. A path in a directed graph that begins and ends at the same node is called a cycle. The cyclic structures of optical communication networks can provide fast restoration and high utilization of resources. The protection algorithms based on the cyclic structures in the mesh networks are practicable. With the concept of protection, this dissertation investigates the protection design in WDM mesh networks, including: designs for the simple link p-Cycles (Pre-configuration Cycles), finding the node-encircling p-Cycles, optimal capacity allocation for p-Cycles, diverse routing and p-Cycles designs with the SRLG (Shared Risk Link Group) constraints.A fault recovery system that is fast and reliable is essential in survivability design in the mesh networks. Pre-configuration Cycle (p-Cycle) benefits both the fast recovery time and the efficient resource utilization. Therefore, in chapter 2, the author studies the designs for link p-Cycles in WDM mesh networks from three perspectives. (1) Finding good candidate p-Cycles is the first and very important step in p-Cycles design. Three basic node-operations Node-Add, Node-Expand and Node-Grow are performed on the cycle to get more efficient p-Cycles. Based on the designs for simple p-Cycles, the authors propose a new algorithm called Fast Cycles Mining Algorithm (FCMA), which can design the simple efficient p-Cycles in WDM networks. The algorithm is also flexible in that the number and the length of cycles generated are controlled by several input parameters. (2) Considering the k-shortest-routing algorithms, the authors propose a new algorithm of finding cycles based on the improved metaDijkstra algorithm. Comparisons are made between this algorithm and the other k-shortest-routing algorithm, the result is that the improved metaDijkstra algorithm can find more candidate p-Cycles with good efficiency in optical mesh networks. (3) The definition of the local-map is first introduced. Considering that the expanding algorithms of cycles can be performed in a local-map, the authors propose a new heuristic algorithm called Local-map Cycles Mining Algorithm (LCMA), for finding simple link candidate p-Cycles. Comparisons are made between this algorithm and Depth First Search (DFS) algorithm and the result shows that the LCMA can find more candidate p-Cycles with good efficiency in optical mesh networks.The node-encircling p-Cycles can protect not only the on-cycle links and the straddling links but also the central node and the straddling flows. The node-encircling cycle must traverse all adjacent neighbor nodes of a central node. Therefore, the algorithms to construct the node-encircling candidate p-Cycles are special. In chapter 3, the author investigates the algorithms of finding the node-encircling p-Cycles in mesh networks from three perspectives. (1) In order to obtain the minimal-cost cycle, the Contraction algorithm is proposed. Three basic span-operations SP-Add, SP-Expand and SP-Grow are performed on the minimal-cost cycle to generate more efficient p-Cycles. Based on finding simple node-encircling p-Cycles, the author proposes a novel algorithm called Node-encircling p-Cycles Mining Algorithm (NCMA), which can efficiently find the simple node-encircling p-Cycles in WDM mesh networks. The qualities of p-Cycles generated by NCMA are controlled by several input parameters. NCMA is also suitable for finding some special link p-Cycles which must contain some fixed nodes. (2) Based on the definition of the local-map and several algorithms for finding node-encircling cycles. A new heuristic algorithm, called Local-map Cycles Mining Algorithm (LCMA), for finding simple node-encircling p-Cycles based on the local-map is proposed. Comparisons are made between LCMA and DFS algorithm and the result shows that the LCMA can find more candidate p-Cycles with good efficiency in optical mesh networks without enumerating all cycles. (3) Considering that the expanding algorithms in different level local-maps can fast generate more efficient candidate simple node-encircling p-Cycles, the author proposes a new heuristic algorithm called Local-map-based Finding p-Cycles Algorithm (LFCA), for finding candidate p-Cycles in different level local-maps. Differing from the previous algorithms of finding cycles, LFCA can find node-encircling p-Cycles and some special link p-Cycles which must contain some fixed nodes.Before providing protection for any link whose end nodes are both on the p-Cycles, the spare capacity allocation for the p-Cycles is the very important step for p-Cycles design in WDM networks. In chapter 4, the author studies the optimal capacity allocation for p-Cycles from three perspectives. (1) p-Cycle is a promising approach for protecting working capacities in optical mesh networks. The p-Cycles network design is the optimization assignment of the candidate p-Cycles. In order to get more efficient p-Cycles, the expanding algorithms are performed on the cycle in the spare capacity. The authors propose a novel heuristic algorithm of the p-Cycles assignment based on spare capacity. Comparisons are made between (a) and (b) strategies of this algorithm, the result is that our algorithm can optimize assignment of p-Cycles. (2) Considering the working capacity constraints, the expanding algorithms based on Local-map are performed on the cycle to get more efficient p-Cycles. The author proposes a novel heuristic capacity allocation algorithm, called the p-Cycle Capacity Assignment Algorithm (CCAA), to achieve an optimal capacity assignment of p-Cycles in WDM networks without using Integer Linear Programming (ILP). CCAA can configure the p-Cycles with good actual efficiency and first consume the spare capacity of the links with more spare capacity in the networks. Comparisons are made between the heuristic algorithm of the p-Cycles assignment based on spare capacity and this algorithm, the result shows that the performance of our algorithm is better. (3) The p-Cycles design in WDM mesh networks is to determine a set of p-Cycles requiring near-minimal spare capacity to fully protect the working capacity of a network. The p-Cycles are formed in the spare capacity of the network, so a spare capacity allocation of the p-Cycles can be done without affecting the working traffic. The author proposes a heuristic method, called the Joint p-Cycles capacity allocation (JCCA), for p-Cycles spare capacity allocation in WDM mesh networks. This method can allocate optimal spare capacity for p-Cycles and ensure 100% restorability without using ILP. JCCA configures the p-Cycles with considering the capacity distribution of the networks and first assigns p-Cycles with good actual efficiency. In real-world networks, different fiber links have the relationship of risks if they traverse the same physical resources. The relationship of risks can be defined as the Shared-Risk Link Groups (SRLG). Under the SRLG constraints, in chapter 5, the author investigates the diverse routing with SRLG constraints and the p-Cycles designs with SRLG constraints. (1) Multiple link failure models, in the form of SRLG are becoming critical in survivable optical network design. Avoiding SRLG failures in path determination will cause the failure of finding two SRLG-disjoint paths. In that case, the approximately SRLG-disjoint routing is needed. The importance of a SRLG can be evaluated by the impact of this SRLG failure on the max-flows of the networks. The author proposes a heuristic method, called the Multiple Importance Diverse Routing (MIDR), which can find two approximately SRLG-disjoint paths in WDM mesh networks. The working path is more reliable and the protection path can first consume the spare capacity of the links with more spare capacity. Comparisons are made between MIDR and the Active Path First (APF) algorithm. Simulation results show that MIDR can effectively reduce the required spare capacity and enhance the network resources utilization. (2) Based on the concept of SRLG, introduces the definition of SRLG diverse p-Cycles. The expanding cycle algorithms with the SRLG constraints can get more SRLG diverse p-Cycles. The author proposes a new heuristic method, called the SRLG Diverse p-Cycles Assignment (SRLG-DCA) algorithm, for the SRLG diverse p-Cycles optimum assignment in WDM mesh networks. The minimal capacity allocation method of SRLG-DCA need little reserved resources and the optimum capacity allocation method of SRLG-DCA can fast finish the p-Cycles assignment. SRLG-DCA configures the SRLG diverse p-Cycles with considering the capacity distribution and first assigns p-Cycles with good actual efficiency. The SRLG failures can be restorable in such networks.To verify and evaluate the proposed algorithms in this dissertation, simulation platform software is developed. Based on the platform, the performances of all proposed algorithms are evaluated. The final section of this dissertation is the conclusion.
|
PDF Full Text Request