On the Resiliency of Randomized Routing Against Multiple Edge Failures

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A3 Kirjan tai muun kokoomateoksen osa
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2016
Major/Subject
Mcode
Degree programme
Language
en
Pages
15
1-15
Series
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics, Volume 55
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.
Description
Keywords
Arborescenses, Connectivity, Randomized, Resilience, Routing
Other note
Citation
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) . , 134 , Leibniz International Proceedings in Informatics , vol. 55 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-15 , International Colloquium on Automata, Languages and Programming , Rome , Italy , 12/07/2016 . https://doi.org/10.4230/LIPIcs.ICALP.2016.134