Reliability in layered networks with random link failures
We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multi-la...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/66124 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1811092008368865280 |
|---|---|
| author | Lee, Kayi Lee, Hyang-Won Modiano, Eytan H. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Lee, Kayi Lee, Hyang-Won Modiano, Eytan H. |
| author_sort | Lee, Kayi |
| collection | MIT |
| description | We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multi-layer setting. Using random sampling techniques, we develop polynomial time approximation algorithms for the failure polynomial. Our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. Furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. We show that maximizing the min cut of the (layered) network maximizes reliability in the low failure probability regime. Based on this observation, we develop algorithms for routing the logical topology to maximize reliability. |
| first_indexed | 2024-09-23T15:11:27Z |
| format | Article |
| id | mit-1721.1/66124 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:11:27Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/661242022-09-29T13:15:40Z Reliability in layered networks with random link failures Lee, Kayi Lee, Hyang-Won Modiano, Eytan H. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Modiano, Eytan H. Lee, Kayi Lee, Hyang-Won Modiano, Eytan H. We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multi-layer setting. Using random sampling techniques, we develop polynomial time approximation algorithms for the failure polynomial. Our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. Furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. We show that maximizing the min cut of the (layered) network maximizes reliability in the low failure probability regime. Based on this observation, we develop algorithms for routing the logical topology to maximize reliability. National Science Foundation (U.S.) (Grant CNS-0626781) National Science Foundation (U.S.) (Grant CNS-0830961) United States. Defense Threat Reduction Agency (Grant HDTRA1-07-1-0004) United States. Defense Threat Reduction Agency (Grant HDTRA-09-1-005) 2011-09-29T22:26:24Z 2011-09-29T22:26:24Z 2010-03 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-5836-3 0743-166X INSPEC Accession Number: 11286922 http://hdl.handle.net/1721.1/66124 Lee, Kayi, Hyang-Won Lee, and Eytan Modiano. “Reliability in Layered Networks with Random Link Failures.” IEEE INFOCOM, 2010. 1-9. Web. 29 Sept. 2011. https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/INFCOM.2010.5461985 IEEE INFOCOM proceedings 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Lee, Kayi Lee, Hyang-Won Modiano, Eytan H. Reliability in layered networks with random link failures |
| title | Reliability in layered networks with random link failures |
| title_full | Reliability in layered networks with random link failures |
| title_fullStr | Reliability in layered networks with random link failures |
| title_full_unstemmed | Reliability in layered networks with random link failures |
| title_short | Reliability in layered networks with random link failures |
| title_sort | reliability in layered networks with random link failures |
| url | http://hdl.handle.net/1721.1/66124 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT leekayi reliabilityinlayerednetworkswithrandomlinkfailures AT leehyangwon reliabilityinlayerednetworkswithrandomlinkfailures AT modianoeytanh reliabilityinlayerednetworkswithrandomlinkfailures |