Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks

The emerging label switched networks such as Multi Protocol Label Switching (MPLS) and Wavelength Division Multiplexing (WDM) 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. Given that the backup LSPs are activated only in the event of a failure and multiple simultaneous failures are uncommon, bandwidth reserved on links that protect the primary LSP can be shared among requests. Also, the latency of restoration can be minimized if the restoration paths originate closer or local to the node which detects the link failure. A routing algorithm must optimize the restoration latency and the amount of bandwidth used. In this paper, we introduce the concept of ``backtracking'' to bound the bandwidth used and 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 available link state information. We first show that joint optimization of primary and backup paths is NP-hard in the three cases of backtracking. We then consider two-step algorithms where primary path and backup paths are computed in two separate steps. Using our link cost model, we devise approximation algorithms for each case. We also report simulation results that characterize the performance of our algorithms.