Designing Hierarchical Survivable Networks
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, netwo...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5115 |
| _version_ | 1811077004713263104 |
|---|---|
| author | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_facet | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_sort | Balakrishnan, Anantaram |
| collection | MIT |
| description | 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 servicein 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 (critical, primary, and secondary) and two types of services/technologies (primary and secondary). The network must connect primary customers using primary (high bandwidth) services and, additionally, contain a back-up path connecting certain 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. |
| first_indexed | 2024-09-23T10:34:55Z |
| format | Working Paper |
| id | mit-1721.1/5115 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:34:55Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51152019-04-12T08:15:32Z Designing Hierarchical Survivable Networks Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash 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 servicein 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 (critical, primary, and secondary) and two types of services/technologies (primary and secondary). The network must connect primary customers using primary (high bandwidth) services and, additionally, contain a back-up path connecting certain 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. 2004-05-28T19:23:49Z 2004-05-28T19:23:49Z 1994-01 Working Paper http://hdl.handle.net/1721.1/5115 en_US Operations Research Center Working Paper;OR 291-94 3675196 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash Designing Hierarchical Survivable Networks |
| title | Designing Hierarchical Survivable Networks |
| title_full | Designing Hierarchical Survivable Networks |
| title_fullStr | Designing Hierarchical Survivable Networks |
| title_full_unstemmed | Designing Hierarchical Survivable Networks |
| title_short | Designing Hierarchical Survivable Networks |
| title_sort | designing hierarchical survivable networks |
| url | http://hdl.handle.net/1721.1/5115 |
| work_keys_str_mv | AT balakrishnananantaram designinghierarchicalsurvivablenetworks AT magnantithomasl designinghierarchicalsurvivablenetworks AT mirchandaniprakash designinghierarchicalsurvivablenetworks |