Solutions to Constrained Path Computation in Multi-layer Networks
Date
2007-12-17T21:03:11Z
Authors
Gong, Shujia
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Traffic Engineering methods as applied to traditional IP networks rely on link attributes advertised by link state protocols, such as Open Shortest Path First (OSPF) or Intermediate System to Intermediate System (IS-IS). Extending link state protocols to include heterogeneous transport layer attributes brings a more comprehensive view of networks for path computation. A unified control plane, which enables horizontal cooperation between peer layers and vertical integration across layers, facilitates the optimization of network resource and instantiation of cross-layered paths, yet brings to path computation additional challenges. These include but are not limited to Generalized Label Continuity Constraints, such as wavelength continuity and VLAN (Virtual Local Area Network) tag continuity and Interface Specific Adaptation Constraints such as switching type adaptation constraints when a cross-layered path needs to be setup. These constraints cannot be satisfied by traditional CSPF (Con- strained Shortest Path First) or integer linear programming. Moreover, the network graph may not be enough to describe the connectivity of network resources associated with wavelength, VLAN tag or switching type adaptation capabilities. Furthermore, the dynamic nature of the networks makes all exhaustive search or other NP-hard algorithms practically unattractive. In this dissertation, we provide the Common Vector solution to the Generalized Label Continuity Constraints. Mathematical analysis and simulation results demonstrate that the algorithm addresses the scalability problem of the existing wavelength graph solution, yet only with minor performance degradation from blocking perspective when the traffic load is not high. Especially, when the label space grows fast, the blocking caused by the lack of common labels is further reduced. Link performance bounds in a ring topology, which can help evaluate the performance degradation of common vector solution more accurately, is also discussed. For Interface Specific Adaptation Constraints, we provide the Channel Graph solution, which transforms the network graph to channel graph. We prove that this solution addresses both the optimality and scalability problems of path computation in multi-layer networks. We also prove that with assumption that the connectivity and cost of adaptation depends on switching type associated with an interface, the Channel Graph solution is most efficient. In a sparse network, the Channel Graph solution has the same order of computational complexity as running CSPF on network graph. Simulation results that corroborate those from the analytical models are presented in this dissertation. The solutions to path computation, as discussed here, lend themselves as good candidates for Internet of future. The proposed solutions for switching type adaptation and VLAN tag have also been implemented and verified in practice 1. 1This is done as a part of path computation in Dynamic Resource Allocation in GMPLS Optical Networks (DRAGON) project, an NSF sponsored project, to create dynamic, deterministic, and manageable end-to-end network transport services for high-end e-Science applications.
Description
Keywords
Path Computation, Multi-layer Networks, Common Vector Solution, Channel Graph Solution