On the Resiliency of Randomized Routing Against Multiple Edge Failures

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

  • Marco Chiesa
  • Andrei Gurtov

  • Aleksander Madry
  • Slobodan Mitrović
  • Ilya Nikolaevskiy
  • Michael Shapira
  • Scott Shenker

Organisaatiot

  • Universite Catholique de Louvain
  • Massachusetts Institute of Technology
  • Swiss Federal Institute of Technology Lausanne
  • Hebrew University of Jerusalem
  • University of California at Berkeley

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
ToimittajatIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
TilaJulkaistu - 2016
OKM-julkaisutyyppiA3 Kirjan osa tai toinen tutkimuskirja
TapahtumaInternational Colloquium on Automata, Languages, and Programming - Rome, Italia
Kesto: 12 kesäkuuta 201615 kesäkuuta 2016
Konferenssinumero: 43

Julkaisusarja

NimiLeibniz International Proceedings in Informatics
Vuosikerta55
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages, and Programming
LyhennettäICALP
MaaItalia
KaupunkiRome
Ajanjakso12/06/201615/06/2016

Lataa tilasto

Ei tietoja saatavilla

ID: 9910041