On the Resiliency of Randomized Routing Against Multiple Edge Failures

Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrović, Ilya Nikolaevskiy, Michael Shapira, Scott Shenker

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

13 Citations (Scopus)
17 Downloads (Pure)

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.
Original languageEnglish
Title of host publication43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
EditorsIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-15
Number of pages15
ISBN (Print)978-3-95977-013-2
DOIs
Publication statusPublished - 2016
MoE publication typeA3 Part of a book or another research book
EventInternational Colloquium on Automata, Languages and Programming - Rome, Italy
Duration: 12 Jul 201615 Jul 2016
Conference number: 43

Publication series

NameLeibniz International Proceedings in Informatics
Volume55
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming
Abbreviated titleICALP
CountryItaly
CityRome
Period12/07/201615/07/2016

Keywords

  • Arborescenses
  • Connectivity
  • Randomized
  • Resilience
  • Routing

Fingerprint Dive into the research topics of 'On the Resiliency of Randomized Routing Against Multiple Edge Failures'. Together they form a unique fingerprint.

  • Cite this

    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. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 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