Abstracts Category : Other

Reliable routing and its application in MPLS and admission control

by Jian Pu

Reliable routing using alternate paths is investigated in this dissertation. We proposeprecalculated alternate paths as a method for fast recovery from link and node failures inIP networks. We demonstrate that path switching time, and thus failure recovery time are,as expected, considerably faster than the standard method of recalculating a new path onthe fly. However, to be effective, the alternate paths should share a minimal set of linksand nodes - preferably none - with the failed path. As shared links are considered in thiswork, we give a reliability model for this situation (non-disjoint alternate paths) anddevelop estimates of reliability as a function of the number of shared links. Alternate pathfinding algorithms to calculate suitable alternate paths subject to predefined constraintsare also developed.Implementation of these techniques for improving routing reliability is shown to bestraightforward for explicit routing protocols such as Multi-Protocol Label Switching(MPLS) with Explicit Routing mode. This mode is expected to be the protocol of choicefor applications requiring guaranteed Quality of Service (QoS) carried on the cominggeneration of wavelength-switched networks (Internet II, CA Net III, etc.) We propose aReliable MPLS (R-MPLS) protocol by applying alternate path routing to MPLS, using our new algorithms to precalculate appropriate alternate paths. Simulation results showthat R-MPLS can achieve fast recovery from failures.We also address reliability issues for the problem of optimal Service LevelAgreement (SLA) admission control. To achieve reliable admission control, we applyalternate path routing to an existing SLA-based admission controller called SLAOpt. Inthe existing Utility Model, SLA admission control is mapped to the Multiple-ChoiceMulti-Dimension Knapsack Problem (MMKP), where the aim is to maximize systemutility (i.e., revenue). However, SLAOpt is static in terms of network topology and doesnot consider reliability. Motivated by this, we propose a Reliable SLAOpt (R-SLAOpt), in which utility optimization is subject to the additional constraint of reliability. A new algorithm was also developed to calculate multiple groups of alternate paths that meet the desired QoS demands and reliability requirement. After QoS adaptation, R-SLAOptselects an appropriate path group containing two or three paths for each admitted sessionand performs resource reservation on all paths in the group. In the event of node or linkfailure, a session can be quickly switched to one of the alternate paths, maintaining theguaranteed QoS without having to run the full admission algorithm again. In this way, wehave obtained a unified treatment of routing reliability and optimal SLA admissioncontrol.Finally, simulations are presented which investigate R-SLAOpt's impact on systemperformance and the gains made in reliability.Advisors/Committee Members: Shoja, Gholamali C (supervisor).