Skip to Main content Skip to Navigation
Journal articles

Load-Optimal Local Fast Rerouting for Dense Networks

Abstract : Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures however is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper introduces a general framework to reason about and design local failover algorithms which minimize the resulting load after failover on dense networks, beyond destination-based routing. We show that due to the inherent locality of the failover decisions at runtime, the problem is fundamentally related to the field of distributed algorithms without coordination. We derive an intriguing lower bound on the inherent network load overhead any local fast failover scheme will introduce in the worst-case, even though globally seen, much more balanced traffic allocations exist. We then present different randomized and deterministic failover algorithms and analyze their overhead load. In particular, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory which tolerates a maximal number of link failures while ensuring low loads.
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download
Contributor : Gilles Tredan Connect in order to contact the contributor
Submitted on : Thursday, February 21, 2019 - 11:20:30 AM
Last modification on : Tuesday, October 19, 2021 - 11:18:06 PM
Long-term archiving on: : Wednesday, May 22, 2019 - 1:58:59 PM


Files produced by the author(s)



Michael Borokhovich, Yvonne-Anne Pignolet, Stefan Schmid, Gilles Trédan. Load-Optimal Local Fast Rerouting for Dense Networks. IEEE/ACM Transactions on Networking, IEEE/ACM, 2018, 26 (6), pp.2583-2597. ⟨10.1109/TNET.2018.2871089⟩. ⟨hal-02043798⟩



Record views


Files downloads