TY - GEN

T1 - On survivable access network design

T2 - INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications

AU - Xu, Dahai

AU - Anshelevich, Elliot

AU - Chiang, Mung

PY - 2008/9/15

Y1 - 2008/9/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51349132800&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51349132800&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2007.46

DO - 10.1109/INFOCOM.2007.46

M3 - Conference contribution

AN - SCOPUS:51349132800

SN - 9781424420261

T3 - Proceedings - IEEE INFOCOM

SP - 709

EP - 717

BT - INFOCOM 2008

Y2 - 13 April 2008 through 18 April 2008

ER -