On survivable access network design: Complexity and algorithms

Dahai Xu, Elliot Anshelevich, Mung Chiang

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

8 Scopus citations

Abstract

With economic constraints and limited routing capability, the structure of an access network is typically a "fat tree", where the terminal has to relay the traffic from another terminal of the same or higher level. New graph theory problems naturally arise from such features of access network models, different from those targeted towards survivable backbone (mesh) networks. We model the important problem of provisioning survivability to an existing single-level fat tree through two graph theory problem formulations: the Terminal Backup problem and the Simplex Cover problem, which we show to be equivalent. We then develop two polynomial-time approaches, indirect and direct, for the Simplex Cover problem. The indirect approach of solving the matching version of Simplex Cover is convenient in proving polynomial-time solvability though it is prohibitively slow in practice. In contrast, leveraging the special properties of Simplex Cover itself, we demonstrate that the direct approach can solve the Simplex Cover problem very efficiently even for large networks. Extensive numerical results of applying our algorithms are also reported for designing survivable access networks over different types of topologies.

Original languageEnglish (US)
Title of host publicationINFOCOM 2008
Subtitle of host publication27th IEEE Communications Society Conference on Computer Communications
Pages709-717
Number of pages9
DOIs
StatePublished - Sep 15 2008
EventINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States
Duration: Apr 13 2008Apr 18 2008

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
CountryUnited States
CityPhoenix, AZ
Period4/13/084/18/08

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'On survivable access network design: Complexity and algorithms'. Together they form a unique fingerprint.

  • Cite this

    Xu, D., Anshelevich, E., & Chiang, M. (2008). On survivable access network design: Complexity and algorithms. In INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications (pp. 709-717). [4509641] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2007.46