Building edge-failure resilient networks

Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the design of resilient networks that are fault tolerant against single link failures. Resilience against single link failures can be built into the network by providing backup paths, which are used when an edge failure occurs on a primary path. We consider several network design problems in this context: the goal is to provision primary and backup bandwidth while minimizing cost. Our models are motivated by current high speed optical networks and we provide approximation algorithms for the problems below. The main problem we consider is that of backup allocation. In this problem, we are given an already provisioned (primary) network, and we want to reserve backup capacity on the edges of the underlying network so that all the demand can be routed even in the case of a single edge failure. We also consider a variant where the primary network has a tree topology and it is required that the restored network retains the tree topology. We then address the problem of simultaneous primary and backup allocation, in which we are given specifications of the traffic to be handled, and we want to both provision the primary as well as the backup network. We also investigate the online model where the primary network is not known in advance. Demands between source-sink pairs arrive online and the goal is to provide a primary path and set of backup edges that can be used for restoring a failure of any of the primary edges.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings
EditorsWilliam J. Cook, Andreas S. Schulz
PublisherSpringer
Pages439-456
Number of pages18
ISBN (Print)9783540478676
DOIs
StatePublished - 2002
Externally publishedYes
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002
Country/TerritoryUnited States
CityCambridge, MA
Period5/27/025/29/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Cite this