MPLS Local Restoration Routing

• L. Li, M. Buddhikot, C. Chekuri, and K. Guo, Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks, IEEE Journal on Selected Areas in Communications (JSAC) Special Issue on Intelligent Services and Applications in Next Generation Networks, Jan 2005.
  • Download Paper (PDF)

   

• Li Li, Milind M. Buddhikot,  Chandra Chekuri and Katie Guo, Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks (Download) , In Proceedins of IEEE ICNP 2002, Paris, France, Nov 12-15, 200.
  • Download PDF  

Abstract

The emerging Multi-Protocol Label Switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites \cite{davie-mpls-book, rfc1918,mpls-recovery-draft,rfc3212}. This basic Label Switched Path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. In this paper, we address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used.

In this paper, we introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance $D$: (1) no backtracking ($D=0$), (2) limited backtracking ($D=k$), and (3) unlimited backtracking ($D=\infty$). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.