A Caltech Library Service

Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information

Bejerano, Yigal and Naor, Joseph (Seffi) and Sprintson, Alexander (2006) Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information. Journal of Combination Optimization, 12 (1-2). pp. 17-34. ISSN 1382-6905. doi:10.1007/s10878-006-8902-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study efficient algorithms for establishing reliable connections with bandwidth guarantees in communication networks. In the normal mode of operation, each connection uses a primary path to deliver packets from the source to the destination. To ensure continuous operation in the event of an edge failure, each connection uses a set of backup bridges, each bridge protecting a portion of the primary path. To meet the bandwidth requirement of the connection, a certain amount of bandwidth must be allocated the edges of the primary path, as well as on the backup edges. In this paper, we focus on minimizing the amount of required backup allocation by sharing backup bandwidth among different connections. We consider efficient sharing schemes that require only partial information about the current state of the network. Specifically, the only information available for each edge is the total amount of primary allocation and the cost of allocating backup bandwidth on this edge. We consider the problem of finding a minimum cost backup allocation together with a set of bridges for a given primary path. We prove that this problem is NP-hard and present an approximation algorithm whose performance is within O(log n) of the optimum, where n is the number of edges in the primary path. We also consider the problem of finding both a primary path and backup allocation of minimal total cost.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2006 Springer Verlag. This research is supported in part by a foundational and strategical research grant from the Israeli Ministry of Science, and by a US-Israel BSF Grant 2002276. A preliminary version of this paper appears in the Proceedings of 13th Annual European Symposium on Algorithms - ESA 2005, Mallorca, Spain.
Funding AgencyGrant Number
Israeli Ministry of ScienceUNSPECIFIED
US-Israel Binational Science Foundation (BSF)2002276
Subject Keywords:Approximation algorithms; Combinatorial optimization; Quality of service; Fault resilience; Restoration; Resource sharing
Issue or Number:1-2
Record Number:CaltechAUTHORS:20110602-125133028
Persistent URL:
Official Citation:Efficient algorithms for shared backup allocation in networks with partial information Yigal Bejerano, Joseph (Seffi) Naor and Alexander Sprintson
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23880
Deposited By: Ruth Sustaita
Deposited On:02 Jun 2011 20:41
Last Modified:09 Nov 2021 16:18

Repository Staff Only: item control page