@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",
}