Designing Hierarchical Survivable Networks

Anantaram Balakrishnan, Thomas L. Magnanti and Prakash Mirchandani
Additional contact information
Anantaram Balakrishnan: The Pennsylvania State University, University Park, Pennsylvania
Thomas L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
Prakash Mirchandani: University of Pittsburgh, Pittsburgh, Pennsylvania

Operations Research, 1998, vol. 46, issue 1, 116-136

Abstract: As the computer, communication, and entertainment industries begin to integrate phone, cable, and video services and to invest in new technologies such as fiber-optic cables, interruptions in service can cause considerable customer dissatisfaction and even be catastrophic. In this environment, network providers want to offer high levels of service—in both serviceability (e.g., high bandwidth) and survivability (failure protection)—and to segment their markets, providing better technology and more robust configurations to certain key customers. We study core models with three types of customers (primary, primary but critical, and secondary) and two types of services/technologies (primary and secondary). The network must connect all primary customers using primary (high bandwidth) services and, additionally, contain a back-up path connecting the critical primary customers. Secondary customers require only single connectivity to other customers and can use either primary or secondary facilities. We propose a general multi-tier survivable network design model to configure cost effective networks for this type of market segmentation. When costs are triangular, we show how to optimally solve single-tier subproblems, with two critical customers, as a matroid intersection problem. We also propose and analyze the worst-case performance of tailored heuristics for several special cases of the two-tier model. Depending upon the particular problem setting, the heuristics have worst-case performance ratios ranging between 1.25 and 2.6. We also provide examples to show that the performance ratios for these heuristics are the best possible.

Keywords: Networks/graphs; heuristics; analysis for hierarchical; survivable applications; Networks/graphs; tree algorithms; hierarchical; survivable networks; Programming; integer; heuristics; multifacility; reliable telecommunications networks (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.1.116 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:1:p:116-136

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().