Sökning: id:"swepub:oai:DiVA.org:kth-222324" >
On the resiliency o...
-
Chiesa, Marco,1987-Université catholique du Louvain, Belgium
(författare)
On the resiliency of randomized routing against multiple edge failures
- Artikel/kapitelEngelska2016
Förlag, utgivningsår, omfång ...
-
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing,2016
-
printrdacarrier
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:kth-222324
-
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-222324URI
-
https://doi.org/10.4230/LIPIcs.ICALP.2016.134DOI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:kon swepub-publicationtype
Anmärkningar
-
QC 20180207
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Gurtov, A.
(författare)
-
Madry, A.
(författare)
-
Mitrovic, S.
(författare)
-
Nikolaevskiy, I.
(författare)
-
Schapira, M.
(författare)
-
Shenker, S.
(författare)
-
Université catholique du Louvain, Belgium
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing9783959770132
Internetlänk
Hitta via bibliotek
Till lärosätets databas