A Caltech Library Service

Algorithms for Computing QoS Paths With Restoration

Bejerano, Yigal and Breitbart, Yuri and Orda, Ariel and Rastogi, Rajeev and Sprintson, Alexander (2005) Algorithms for Computing QoS Paths With Restoration. IEEE/ACM Transactions on Networking, 13 (3). pp. 648-661. ISSN 1063-6692. doi:10.1109/TNET.2005.850217.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


There is a growing interest among service providers to offer new services with Quality of Service (QoS) guarantees that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology, i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guarantees to find a restoration topology with low cost when one exists.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2005 IEEE. Manuscript received February 20, 2003; revised April 21, 2004; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor Z. Zhang.
Subject Keywords:Approximation algorithms, QoS routing, restoration, restricted shortest path
Issue or Number:3
Record Number:CaltechAUTHORS:20160516-165524235
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67143
Deposited By: Kristin Buxton
Deposited On:17 May 2016 16:48
Last Modified:11 Nov 2021 00:27

Repository Staff Only: item control page