On the Resiliency of Randomized Routing Against Multiple Edge Failures
We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s t...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2018
|
| Online Access: | http://hdl.handle.net/1721.1/113892 https://orcid.org/0000-0003-0536-0323 |
| _version_ | 1826203273613279232 |
|---|---|
| author | Chiesa, Marco Gurtov, Andrei Madry, Aleksander Mitrovic, Slobodan Nikolaevskiy, Ilya Shapira, Michael Shenker, Scott |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chiesa, Marco Gurtov, Andrei Madry, Aleksander Mitrovic, Slobodan Nikolaevskiy, Ilya Shapira, Michael Shenker, Scott |
| author_sort | Chiesa, Marco |
| collection | MIT |
| description | We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link. Keywords: Randomized, Routing, Resilience, Connectivity, Arborescenses |
| first_indexed | 2024-09-23T12:34:02Z |
| format | Article |
| id | mit-1721.1/113892 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:34:02Z |
| publishDate | 2018 |
| publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
| record_format | dspace |
| spelling | mit-1721.1/1138922022-09-28T08:40:39Z On the Resiliency of Randomized Routing Against Multiple Edge Failures Chiesa, Marco Gurtov, Andrei Madry, Aleksander Mitrovic, Slobodan Nikolaevskiy, Ilya Shapira, Michael Shenker, Scott Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Madry, Aleksander We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link. Keywords: Randomized, Routing, Resilience, Connectivity, Arborescenses 2018-02-26T21:36:27Z 2018-02-26T21:36:27Z 2016 Article http://purl.org/eprint/type/ConferencePaper 1868-8969 http://hdl.handle.net/1721.1/113892 Chiesa, Marco et al. "On the Resiliency of Randomized Routing Against Multiple Edge Failures." Leibniz International Proceedings in Informatics (LIPIcs), 55 (2016). pp. 134:1--134:15. https://orcid.org/0000-0003-0536-0323 en_US http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.134 Leibniz International Proceedings in Informatics (LIPIcs) Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ application/pdf Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Dagstuhl Publishing |
| spellingShingle | Chiesa, Marco Gurtov, Andrei Madry, Aleksander Mitrovic, Slobodan Nikolaevskiy, Ilya Shapira, Michael Shenker, Scott On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title | On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title_full | On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title_fullStr | On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title_full_unstemmed | On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title_short | On the Resiliency of Randomized Routing Against Multiple Edge Failures |
| title_sort | on the resiliency of randomized routing against multiple edge failures |
| url | http://hdl.handle.net/1721.1/113892 https://orcid.org/0000-0003-0536-0323 |
| work_keys_str_mv | AT chiesamarco ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT gurtovandrei ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT madryaleksander ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT mitrovicslobodan ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT nikolaevskiyilya ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT shapiramichael ontheresiliencyofrandomizedroutingagainstmultipleedgefailures AT shenkerscott ontheresiliencyofrandomizedroutingagainstmultipleedgefailures |