Routing Bandwidth Guaranteed Paths with Restoration in Label Switched Networks (Download)

In Proceedins of IEEE ICNP2001, Riverside, CA, Nov 11-14, 2001.

Samphel Norden, Washington University in St. Louis

Milind M. Buddhikot, Dept. of Network Software Research, Lucent Bell Labs.

Marcel Waldvogel, Washington University in St. Louis

Subhash Suri, Department of Computer Science, Washington University in St. Louis


Label Switching (LS) paradigm encompasses optical technologies such as wavelength switching, and packet switching technologies, such as ATM and Multi Protocol Label Switching (MPLS). A Network Service Provider (NSP) that operates such label switched networks sets up end-to-end bandwidth guaranteed Label Switched Paths (LSPs) to satisfy the connectivity requirements of its client networks. To make such a service highly available, for every active LSP, the NSP may setup a backup LSP that is activated when the corresponding active LSP fails. Given this, the problem of LSP routing with and without restoration backup has received some attention in the recent past. In case of packet networks, solutions to this problem need to account for a new dimension of reconfigurable topologies. Specifically, the Bandwidth-On-Demand (BOD) capability of WDM networks on which such packet networks will be overlayed, will allow addition/deletion of virtual links of specified bandwidth and make the network topology reconfigurable.

In this paper, we investigate distributed algorithms for routing of LSPs with backup restoration in the context of static and dynamically reconfigurable label switched networks. Specifically, we propose a new concept of Backup Load Distribution (BLD) Matrix that captures partial network state and eliminates the problems of bandwidth wastage and pessimistic link selection. We describe two new distributed routing algorithms that utilize the BLD matrix and require bounded amount of run time. We can realize these algorithms in the current Intenet architecture using the OSPF extensions for Quality-of-Service (QoS) routing \cite{ospf-extensions} to exchange the proposed BLD matrix among peer routers/switches. Our simulation results for sample realistic topologies show excellent (30-50\%) improvement in number of rejected requests and 30-40\% savings in total bandwidth used for backup connections.