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 u003e 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 u003c 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link. |
Year | Venue | Field |
---|---|---|
2016 | ICALP | Discrete mathematics,Link-state routing protocol,Combinatorics,Multipath routing,Equal-cost multi-path routing,Dynamic Source Routing,Path vector protocol,Computer science,Static routing,Destination-Sequenced Distance Vector routing,Routing Information Protocol |
DocType | Citations | PageRank |
Conference | 5 | 0.41 |
References | Authors | |
0 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marco Chiesa | 1 | 101 | 8.20 |
Andrei Gurtov | 2 | 1326 | 109.52 |
Aleksander Mądry | 3 | 961 | 45.38 |
Slobodan Mitrović | 4 | 30 | 7.68 |
Ilya Nikolaevskiy | 5 | 38 | 4.38 |
Michael Schapira | 6 | 13 | 2.73 |
Scott Shenker | 7 | 29892 | 2677.04 |