Dissertation/Thesis Abstract

Solutions to constrained path computation in multi-layer networks
by Gong, Shujia, Ph.D., George Mason University, 2008, 128; 3289663
Abstract (Summary)

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 (Constrained 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 practice1.

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.

Indexing (document details)
Advisor: Jabbari, Bijan
Commitee:
School: George Mason University
School Location: United States -- Virginia
Source: DAI-B 68/11, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Electrical engineering
Keywords: Channel graph solutions, Common vector solutions, Constrained path computation, Multilayer networks, Path computation
Publication Number: 3289663
ISBN: 9780549331575
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest