Reliable routing and its applications in MPLS and admission control.

摘要

Reliable routing using alternate paths is investigated in this dissertation. We propose precalculated alternate paths as a method for fast recovery from link and node failures in IP 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 on the fly. However, to be effective, the alternate paths should share a minimal set of links and nodes---preferably none---with the failed path. As shared links are considered in this work, we give a reliability model for this situation (non-disjoint alternate paths) and develop estimates of reliability as a function of the number of shared links. Alternate path finding algorithms to calculate suitable alternate paths subject to predefined constraints are also developed.; Implementation of these techniques for improving routing reliability is shown to be straightforward for explicit routing protocols such as Multi-Protocol Label Switching (MPLS) with Explicit Routing mode. This mode is expected to be the protocol of choice for applications requiring guaranteed Quality of Service (QoS) carried on the coming generation of wavelength-switched networks (Internet II, CA Net III, etc.). We propose a Reliable MPLS (R-MPLS) protocol by applying alternate path routing to MPLS, using our new algorithms to precalculate appropriate alternate paths. Simulation results show that R-MPLS can achieve fast recovery from failures.; We also address reliability issues for the problem of optimal Service Level Agreement (SLA) admission control. To achieve reliable admission control, we apply alternate path routing to an existing SLA-based admission controller called SLAOpt. In the existing Utility Model, SLA admission control is mapped to the Multiple-Choice Multi-Dimension Knapsack Problem (MMKP), where the aim is to maximize system utility (i.e., revenue). However, SLAOpt is static in terms of network topology and does not 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-SLAOpt selects an appropriate path group containing two or three paths for each admitted session and performs resource reservation on all paths in the group. In the event of node or link failure, a session can be quickly switched to one of the alternate paths, maintaining the guaranteed QoS without having to run the full admission algorithm again. In this way, we have obtained a unified treatment of routing reliability and optimal SLA admission control.; Finally, simulations are presented which investigate R-SLAOpt's impact on system performance and the gains made in reliability.