### 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 > 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.

Original language | English |
---|---|

Title of host publication | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |

Editors | Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 1-15 |

Number of pages | 15 |

ISBN (Print) | 978-3-95977-013-2 |

DOIs | |

Publication status | Published - 2016 |

MoE publication type | A3 Part of a book or another research book |

Event | International Colloquium on Automata, Languages and Programming - Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016 Conference number: 43 |

### Publication series

Name | Leibniz International Proceedings in Informatics |
---|---|

Volume | 55 |

ISSN (Electronic) | 1868-8969 |

### Conference

Conference | International Colloquium on Automata, Languages and Programming |
---|---|

Abbreviated title | ICALP |

Country | Italy |

City | Rome |

Period | 12/07/2016 → 15/07/2016 |

### Keywords

- Arborescenses
- Connectivity
- Randomized
- Resilience
- Routing

## Fingerprint Dive into the research topics of 'On the Resiliency of Randomized Routing Against Multiple Edge Failures'. Together they form a unique fingerprint.

## Cite this

Chiesa, M., Gurtov, A., Madry, A., Mitrović, S., Nikolaevskiy, I., Shapira, M., & Shenker, S. (2016). On the Resiliency of Randomized Routing Against Multiple Edge Failures. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.),

*43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)*(pp. 1-15). [134] (Leibniz International Proceedings in Informatics; Vol. 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.134