On the Resiliency of Randomized Routing Against Multiple Edge Failures

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Chiesa, Marco
dc.contributor.author Gurtov, Andrei
dc.contributor.author Madry, Aleksander
dc.contributor.author Mitrović, Slobodan
dc.contributor.author Nikolaevskiy, Ilya
dc.contributor.author Shapira, Michael
dc.contributor.author Shenker, Scott
dc.contributor.editor Chatzigiannakis, Ioannis
dc.contributor.editor Mitzenmacher, Michael
dc.contributor.editor Rabani, Yuval
dc.contributor.editor Sangiorgi, Davide
dc.date.accessioned 2017-05-11T08:20:56Z
dc.date.available 2017-05-11T08:20:56Z
dc.date.issued 2016
dc.identifier.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 fur Informatik GmbH, Dagstuhl Publishing , pp. 1-15 , International Colloquium on Automata, Languages, and Programming , Rome , Italy , 11-15 June . DOI: 10.4230/LIPIcs.ICALP.2016.134 en
dc.identifier.isbn 978-3-95977-013-2
dc.identifier.issn 1868-8969
dc.identifier.other PURE UUID: 6a0a0894-01e0-4cd1-8648-1e8f9665ddd6
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/on-the-resiliency-of-randomized-routing-against-multiple-edge-failures(6a0a0894-01e0-4cd1-8648-1e8f9665ddd6).html
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/11504284/LIPIcs_ICALP_2016_134.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/25575
dc.description.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. en
dc.format.extent 15
dc.format.extent 1-15
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartof International Colloquium on Automata, Languages, and Programming en
dc.relation.ispartofseries 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) en
dc.relation.ispartofseries Leibniz International Proceedings in Informatics en
dc.relation.ispartofseries Volume 55 en
dc.rights openAccess en
dc.subject.other 113 Computer and information sciences en
dc.title On the Resiliency of Randomized Routing Against Multiple Edge Failures en
dc.type A3 Kirjan tai muun kokoomateoksen osa fi
dc.description.version Peer reviewed en
dc.contributor.department Universite Catholique de Louvain
dc.contributor.department Department of Computer Science
dc.contributor.department Massachusetts Institute of Technology
dc.contributor.department Swiss Federal Institute of Technology Lausanne
dc.contributor.department Hebrew University of Jerusalem
dc.contributor.department University of California at Berkeley
dc.subject.keyword Arborescenses
dc.subject.keyword Connectivity
dc.subject.keyword Randomized
dc.subject.keyword Resilience
dc.subject.keyword Routing
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201705113959
dc.identifier.doi 10.4230/LIPIcs.ICALP.2016.134
dc.type.version publishedVersion


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account