Skip to Main content Skip to Navigation
Conference papers

Bonsai: Efficient Fast Failover Routing Using Small Arborescences

Abstract : To provide high availability despite link failures, many modern communication networks feature fast failover mechanisms in the data plane, which operates orders of magnitude faster than the control plane. While the configuration of highly resilient data planes using the shortest possible backup routes is known to be a difficult combinatorial problem, over the last years, much progress has been made in the design of algorithms which provably guarantee connectivity even under many concurrent link failures. However, while these algorithms provide connectivity, the resulting routes after failures can be very long, which in turn can harm performance. In this paper, we propose, analyze, and evaluate methods for fast failover algorithms which account for the quality of the routes after failures, in addition to connectivity. In particular, we revisit the existing approach to cover the to-be-protected network with arc-disjoint spanning arborescences to define alternative routes to the destination, aiming to keep the stretch imposed by these trees low (hence the name of our method: Bonsai). We show that the underlying problem is NP-hard on general topologies and present lower bound results that are tight for various topologies, for any class of fast failover algorithms. We also present heuristics for general networks and demonstrate their performance benefits in extensive simulations. Finally, we show that failover algorithms using low-stretch arborescences, as a side effect, can provide connectivity under more general failure models than usually considered in the literature.
Document type :
Conference papers
Complete list of metadata
Contributor : Gilles Tredan <>
Submitted on : Wednesday, December 9, 2020 - 4:45:13 PM
Last modification on : Thursday, June 10, 2021 - 3:01:31 AM
Long-term archiving on: : Wednesday, March 10, 2021 - 7:46:44 PM


Files produced by the author(s)



Klaus-Tycho Foerster, Andrzej Kamisiński, Yvonne-Anne Pignolet, Stefan Schmid, Gilles Trédan. Bonsai: Efficient Fast Failover Routing Using Small Arborescences. 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), Jun 2019, Portland, United States. pp.276-288, ⟨10.1109/DSN.2019.00039⟩. ⟨hal-03049100⟩



Record views


Files downloads