Fault-tolerance-oriented topology, routing and wavelength assignment optimization for WDM all-optical networks.

摘要

Wavelength-routed all-optical communication technologies have immense potential to become a qualified solution to next-generation communication networks satisfying both long-haul networking and special local communication requirements, as in avionic communication systems, due to its efficient one-shot data delivery, wide bandwidth provision, magneto-electrical interference resistance, light-weight signal carrying medium (fibers), etc. However, fiber optic components are susceptible to a range of operating faults, such as stability issues in both mechanical placements and electro-optic operations, especially under hazardous operating conditions. Therefore, it becomes more than desirable to propose efficient fault-tolerant network architectures and protocols to meet varied fault-tolerance requirements under certain resource provision limits.;This dissertation is dedicated to studying optimal resource (in form of wavelengths and optical links) allocation problems in designing different types of fault-tolerant Wavelength Division Multiplexing (WDM) network architectures and then searching for best solutions. A range of classic topologies, such as torus and circulant graphs, are studied on which optimal fault-tolerant routing algorithms are developed. The Wavelength Assignment (WA) problem is investigated in depth and a Wavelength Allocation and Reuse (WAR) algorithm for the two-dimensional N x N torus of arbitrary sizes is developed which performs close to the best possible solution (lower bound). Spare sharing technology, in favor of reducing redundant resource utilization, is also studied in fault-tolerant architecture design and different levels of spare sharing are proposed on the torus topology to evaluate the tradeoff between network connection reliability and resource utilization. Circulant graph, featuring scalable network sizes and flexible connectivity, is exploited and a node-disjoint routing algorithm for arbitrary sizes and connectivity degrees of the circulant graph is proposed to facilitate the multi-level fault-tolerant implementation of all-optical Local Area Networks (LANs).;From another perspective of fault-tolerant WDM architecture design, topological optimization under certain resource provision constraints is studied, in which a number of Integer Linear Programs (ILPs) are developed to model the problem in varied granularities. Based on the drawbacks analysis of the greedy approach, a two-phase heuristic algorithm is proposed that jointly considers the routing and wavelength assignment problems. Numerical simulations show that the proposed heuristic algorithm performs much better than the traditional method for the Routing and Wavelength Assignment (RWA) problems in which the routing and wavelength assignment are treated consecutively in a separate fashion.;This dissertation also touches upon a fundamental problem: ordered path enumeration (or k-shortest path enumeration). Based on a series of graph-theoretical derivation, a new ordered path enumeration algorithm is proposed to help form a pool of possible paths for the flow requests. Then a problem-aware candidate routing scheme is developed to select candidate routes from the pool of enumerated paths. This ordered-path-enumeration-based candidate routing method is examined on two shared-path-protection RWA problems and the numerical results indicate its great performance advantage over the traditional k-shortest disjoint routing based method. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html )