On the Resiliency of Randomized Routing Against Multiple Edge Failures

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

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.

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). toim. / Ioannis Chatzigiannakis; Michael Mitzenmacher; Yuval Rabani; Davide Sangiorgi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. s. 1-15 134 (Leibniz International Proceedings in Informatics; Vuosikerta 55).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Harvard

Chiesa, M, Gurtov, A, Madry, A, Mitrović, S, Nikolaevskiy, I, Shapira, M & Shenker, S 2016, On the Resiliency of Randomized Routing Against Multiple Edge Failures. julkaisussa I Chatzigiannakis, M Mitzenmacher, Y Rabani & D Sangiorgi (toim), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)., 134, Leibniz International Proceedings in Informatics, Vuosikerta. 55, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Sivut 1-15, Rome, Italia, 12/07/2016. https://doi.org/10.4230/LIPIcs.ICALP.2016.134

APA

Chiesa, M., Gurtov, A., Madry, A., Mitrović, S., Nikolaevskiy, I., Shapira, M., & Shenker, S. (2016). On the Resiliency of Randomized Routing Against Multiple Edge Failures. teoksessa I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Toimittajat), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Sivut 1-15). [134] (Leibniz International Proceedings in Informatics; Vuosikerta 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.134

Vancouver

Chiesa M, Gurtov A, Madry A, Mitrović S, Nikolaevskiy I, Shapira M et al. On the Resiliency of Randomized Routing Against Multiple Edge Failures. julkaisussa Chatzigiannakis I, Mitzenmacher M, Rabani Y, Sangiorgi D, toimittajat, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. s. 1-15. 134. (Leibniz International Proceedings in Informatics). https://doi.org/10.4230/LIPIcs.ICALP.2016.134

Author

Chiesa, Marco ; Gurtov, Andrei ; Madry, Aleksander ; Mitrović, Slobodan ; Nikolaevskiy, Ilya ; Shapira, Michael ; Shenker, Scott. / On the Resiliency of Randomized Routing Against Multiple Edge Failures. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Toimittaja / Ioannis Chatzigiannakis ; Michael Mitzenmacher ; Yuval Rabani ; Davide Sangiorgi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. Sivut 1-15 (Leibniz International Proceedings in Informatics).

Bibtex - Lataa

@inbook{6a0a089401e04cd186481e8f9665ddd6,
title = "On the Resiliency of Randomized Routing Against Multiple Edge Failures",
abstract = "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 = "Arborescenses, Connectivity, Randomized, Resilience, Routing",
author = "Marco Chiesa and Andrei Gurtov and Aleksander Madry and Slobodan Mitrović and Ilya Nikolaevskiy and Michael Shapira and Scott Shenker",
year = "2016",
doi = "10.4230/LIPIcs.ICALP.2016.134",
language = "English",
isbn = "978-3-95977-013-2",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--15",
editor = "Chatzigiannakis, {Ioannis } and Mitzenmacher, {Michael } and Rabani, {Yuval } and Sangiorgi, {Davide }",
booktitle = "43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)",
address = "Germany",

}

RIS - Lataa

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