Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the resiliency of randomized routing against multiple edge failures
Université catholique du Louvain, Belgium.ORCID iD: 0000-0002-9675-9729
Show others and affiliations
2016 (English)In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016, Vol. 55, article id 134Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016. Vol. 55, article id 134
Series
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969 ; 55
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222324DOI: 10.4230/LIPIcs.ICALP.2016.134Scopus ID: 2-s2.0-85012897010ISBN: 9783959770132 (print)OAI: oai:DiVA.org:kth-222324DiVA, id: diva2:1180769
Conference
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 12 July 2016 through 15 July 2016
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chiesa, Marco
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 3 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf