# On the Resiliency of Randomized Routing Against Multiple Edge Failures

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific › peer-review

### Standard

**On the Resiliency of Randomized Routing Against Multiple Edge Failures.** / Chiesa, Marco; Gurtov, Andrei; Madry, Aleksander; Mitrović, Slobodan; Nikolaevskiy, Ilya; Shapira, Michael; Shenker, Scott.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific › peer-review

### Harvard

*43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).*, 134, Leibniz International Proceedings in Informatics, vol. 55, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 1-15, International Colloquium on Automata, Languages and Programming, Rome, Italy, 12/07/2016. https://doi.org/10.4230/LIPIcs.ICALP.2016.134

### APA

*43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)*(pp. 1-15). [134] (Leibniz International Proceedings in Informatics; Vol. 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.134

### Vancouver

### Author

### Bibtex - Download

}

### RIS - Download

TY - CHAP

T1 - On the Resiliency of Randomized Routing Against Multiple Edge Failures

AU - Chiesa, Marco

AU - Gurtov, Andrei

AU - Madry, Aleksander

AU - Mitrović, Slobodan

AU - Nikolaevskiy, Ilya

AU - Shapira, Michael

AU - Shenker, Scott

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Arborescenses

KW - Connectivity

KW - Randomized

KW - Resilience

KW - Routing

U2 - 10.4230/LIPIcs.ICALP.2016.134

DO - 10.4230/LIPIcs.ICALP.2016.134

M3 - Chapter

SN - 978-3-95977-013-2

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 15

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

A2 - Chatzigiannakis, Ioannis

A2 - Mitzenmacher, Michael

A2 - Rabani, Yuval

A2 - Sangiorgi, Davide

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

ID: 9910041