On survivable access network design: Complexity and algorithms

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.