cispa_all_3974.pdf (872.28 kB)

Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults

Download (872.28 kB)
Version 2 2023-12-14, 13:28
Version 1 2023-11-29, 18:07
journal contribution
posted on 2023-12-14, 13:28 authored by Moti Medina, Mehrdad Saberi, Stefan Schmid, Christoph LenzenChristoph Lenzen
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important that they rely on robust routing algorithms which ensure connectivity despite such failures. While most modern communication networks feature robust routing mechanisms, these mechanisms are often fairly complex to design and verify, as they need to account for the effects of failures and rerouting on communication. This paper conceptualizes the design of robust routing mechanisms, with the aim to avoid such complexity. In particular, we showcase simple and generic blackbox transformations that increase resilience of routing against independently distributed failures, which allows to simulate the routing scheme on the original network, even in the presence of non-benign node failures (henceforth called faults). This is attractive as the system specification and routing policy can simply be preserved. We present a scheme for constructing such a reinforced network, given an existing (synchronous) network and a routing scheme. We prove that this algorithm comes with small constant overheads, and only requires a minimal amount of additional node and edge resources; in fact, if the failure probability is smaller than 1/n, the algorithm can come without any overhead at all. At the same time, it allows to tolerate a large number of independent random (node) faults, asymptotically almost surely. We complement our analytical results with simulations on different real-world topologies.


Preferred Citation

Christoph Lenzen, Moti Medina, Mehrdad Saberi and Stefan Schmid. Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults. In: IEEE/ACM Transactions on Networking. 2023.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Legacy Posted Date



IEEE/ACM Transactions on Networking



Open Access Type

  • Green


@article{cispa_all_3974, title = "Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults", author = "Lenzen, Christoph and Medina, Moti and Saberi, Mehrdad and Schmid, Stefan", journal="{IEEE/ACM Transactions on Networking}", year="2023", }

Usage metrics


    No categories selected


    Ref. manager