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. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/7980 |
| Date | 24 April 2017 |
| Creators | Pu, Jian |
| Contributors | Shoja, Gholamali C |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0026 seconds