Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • 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
Vise andre og tillknytning
2016 (engelsk)Inngår i: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016, Vol. 55, artikkel-id 134Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016. Vol. 55, artikkel-id 134
Serie
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969 ; 55
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-222324DOI: 10.4230/LIPIcs.ICALP.2016.134Scopus ID: 2-s2.0-85012897010ISBN: 9783959770132 (tryckt)OAI: oai:DiVA.org:kth-222324DiVA, id: diva2:1180769
Konferanse
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 12 July 2016 through 15 July 2016
Merknad

QC 20180207

Tilgjengelig fra: 2018-02-06 Laget: 2018-02-06 Sist oppdatert: 2018-02-07bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Søk i DiVA

Av forfatter/redaktør
Chiesa, Marco

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 8 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf