DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.20

Fast Rerouting Against Dynamic Failures: 2-Resilience via Ear-Decomposition and Planarity

Authors: Wenkai Dai, Klaus-Tycho Foerster, and Stefan Schmid

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract

Modern communication networks employ local fast failover mechanisms in the data plane, swiftly reacting to link failures through pre-installed rerouting rules. This paper investigates resilient routing schemes that guarantee packet delivery under up to k link failures, provided the source and destination remain connected in the degraded network. While prior theoretical studies have mainly addressed static failures, where multiple links fail simultaneously and permanently, real networks often experience dynamic failures, such as transient link flapping caused by short-lived faults. We study the limits of basic and source-matched failover routing with packet-header rewriting against dynamic failures in general graphs. In basic routing, forwarding depends only on active links, incoming ports, and the destination, whereas source-matched routing additionally incorporates the source, requiring more memory (and logic) at the router. The 2-resilient source-matched routing for static failures is shown to fail under permanent but non-simultaneous failures. Moreover, even with source matching, we prove that in planar graphs k ≥ 2 resilience is impossible without bit rewriting, and in general graphs, perfect k-resilience is unachievable by only rewriting O(log k) bits. For planar graphs, we introduce ear-decomposition into basic routing and develop novel local rerouting mechanisms that tolerate dynamic failures. These yield tight 2-resilient basic routing by rewriting only one or two bits, closing the gap between lower bounds and practical routing scheme.

Cite as

Wenkai Dai, Klaus-Tycho Foerster, and Stefan Schmid. Fast Rerouting Against Dynamic Failures: 2-Resilience via Ear-Decomposition and Planarity. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.OPODIS.2025.20,
  author =	{Dai, Wenkai and Foerster, Klaus-Tycho and Schmid, Stefan},
  title =	{{Fast Rerouting Against Dynamic Failures: 2-Resilience via Ear-Decomposition and Planarity}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.20},
  URN =		{urn:nbn:de:0030-drops-251930},
  doi =		{10.4230/LIPIcs.OPODIS.2025.20},
  annote =	{Keywords: Resilience, Local Failover, Routing, Dynamic Link Failures, Link Flapping}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2022.42

Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies

Authors: Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities.

Cite as

Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.DISC.2022.42,
  author =	{Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan},
  title =	{{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.42},
  URN =		{urn:nbn:de:0030-drops-172330},
  doi =		{10.4230/LIPIcs.DISC.2022.42},
  annote =	{Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity}
}

Search Results

Documents authored by Dai, Wenkai

Fast Rerouting Against Dynamic Failures: 2-Resilience via Ear-Decomposition and Planarity

Abstract

Cite as

Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies

Abstract

Cite as

Thanks for your feedback!

Could not send message