Source-linked AI summary
Constant Factor Optimal 2-Resilient Local Failover Routing Scheme on Directed Graphs
Kaito Harada, Naoki Kitamura, Yuki Kawashima, Yuya Terashima
TL;DR
Local failover routing seeks to deliver packets in directed graphs using local precomputed rules and a rewritable header despite link failures, but optimal header sizes remained unresolved for two failures and some larger failure counts. The paper develops improved routing schemes and lower bounds, bringing the k=2 bounds within 3 bits and establishing asymptotic tightness for a stated range of k.
Problem
In directed graphs, prior routing schemes had not achieved optimal header size for two failures or failure counts roughly greater than the number of vertices.
Source: §1.1 · pp. 1–2Method
The paper separates the final failure from the first k−1 in Ck, specializes a path-based scheme D to k=2, and uses cascaded path gadgets for lower bounds.
Source: §1.1 · p. 3, §4 · p. 12, §5 · p. 13Results
For k=2, the upper and lower bounds differ by at most 3 bits; for k=Θ(n) with ⌊k/2⌋≤(n−1)/8, both bounds are Θ(n).
Source: §1.1 · p. 3, §5 · p. 13Takeaways & Limitations
The k=2 header-size bounds are within 3 bits, and the bounds are asymptotically tight for k=Θ(n) within the stated range.
Source: §1.1 · p. 3, §5 · p. 13The exact k=2 header size remains open, and for k>n the known Ω(n)-bit lower bound and Ck’s O(n log(k/n))-bit upper bound leave a gap.
Source: §5 · p. 13
Abstract
from arXiv · showhide
Local failover routing delivers a packet from a source $s$ to a destination $t$ using only pre-computed, per-node forwarding rules together with a small rewritable packet header, remaining correct even when up to $k$ arcs of the network fail. We study this problem on directed graphs with $n$ nodes, measuring efficiency by the number of rewritable bits carried in the header, and focus on the case of $k \ge 2$ failures. Our first contribution is an improved upper bound for general $k$. We design a scheme using at most $\lceil \log\!\binom{2n+k-4}{k-1} \rceil+1$ bits, improving the best previously known $\lceil \log \binom{2n+k-3}{k} \rceil$ bit scheme for every $k < 2n-3$. For the special case $k=2$, we further improve this to a scheme using at most $\left\lceil \log\!\left(1+2\lfloor 2(n-1)/3 \rfloor\right)\right\rceil$ bits. Our second contribution is a family of improved lower bounds, obtained via a new path-gadget construction. For $k=2$, we prove a lower bound of $\left\lceil \log \lfloor n/3 \rfloor \right\rceil$ bits, and for general $k$, writing $k_2 = \lfloor k/2 \rfloor$, a lower bound of $\left\lceil k_2 \log \left\lfloor (n-1+k_2)/(3k_2) \right\rfloor \right\rceil$ bits, improving on the best previously known bound. In particular, for $k=2$, our upper bound of $\left\lceil \log\!\left(1+2\lfloor 2(n-1)/3 \rfloor\right)\right\rceil$ bits and our lower bound of $\left\lceil \log \lfloor n/3 \rfloor \right\rceil$ bits differ by at most $3$ bits.
1 Introduction
The introduction frames local failover routing as delivery over directed graphs using precomputed local rules and rewritable headers, then presents improved upper and lower bounds. Its results narrow the k=2 gap to at most 3 bits and establish asymptotically tight bounds in a stated general-k range.
1.1 Background and Our Results
- Local failover routing uses precomputed per-node forwarding rules and rewritable headers to deliver packets despite failures, provided the source and destination remain connected after up to k link failures.The scheme operates without network-wide recalculation.Source: §1.1 · p. 1
- Earlier directed-graph results left the optimal header size unresolved for two failures and for failure counts roughly greater than the number of vertices.Prior work had established an optimal scheme only for a single failure, while gaps remained for multiple failures.Source: §1.1 · p. 2
- The paper introduces scheme Ck for general k and a further-improved scheme D for k=2, alongside a path-gadget construction that strengthens lower bounds.D restricts the construction to a single well-chosen s–t path; the lower-bound construction cascades copies of its gadget for general k.Source: §1.1 · pp. 2–3
- For k=2, the new upper and lower bounds differ by at most 3 bits, and for k=Θ(n) they are both Θ(n) within the stated lower-bound range.The latter range is ⌊k/2⌋≤(n−1)/8.Source: §1.1 · p. 3
1.2 Related Work
- Prior work studied failover routing extensively on undirected graphs, while directed-graph studies developed bounds and schemes but left multi-failure cases short of optimality.Earlier directed-graph work included simulations and real-topology analyses, as well as theoretical upper and lower bounds.Source: §1.1 · p. 2, §1.2 · p. 4
2 Preliminaries
The preliminaries define directed-graph routing and its local failover model, then present a one-bit scheme for tolerating one arc failure. The scheme uses two in-arborescences and switches paths when the first fails.
2.1 Notation
- A directed path follows arcs from source to destination; the outgoing cut of a vertex set contains arcs leaving that set, and an in-arborescence routes each vertex toward its root.The paper measures shortest-path distance by total arc weight when weights are used.Source: §2.1 · pp. 4–5
2.2 Model
- Local forwarding rules use the incoming arc, locally detected failed outgoing arcs, source and destination, and a rewritable header; the header-size measure counts its rewritable bits.A scheme is k-resilient when it delivers packets for node pairs that remain connected after up to k arc failures.Source: §2.2 · pp. 5–6
2.3 1-Resilient Scheme A1 by van den Akker et al. [vdAWF26]
- A1 precomputes two in-arborescences rooted at the destination and uses one rewritable bit to switch from the first tree to the second after a failure.The trees are arc-disjoint except for non-failable arcs, and A1 tolerates one failure in at most 2n − 2 hops.Source: §2.3 · pp. 6–7
3 Our Algorithms
The algorithms improve header bounds for multiple arc failures by separating the last failure from earlier ones, and further improve the two-failure case using a carefully chosen path. The resulting two-failure upper bound is within 3 bits of the lower bound.
3.1 An Improved Scheme for Multi Failures
- Ck combines Bk−1's failure profile for earlier failures with A1's one-bit mechanism for the remaining failure, improving on Bk's header bound for k < 2n − 3.The profile records failures among at most 2n + k − 4 attempted arcs; the final failure is handled separately.Source: §3.1 · pp. 8–9
3.2 More Efficient 2-Resilient Scheme
- Scheme D restricts B1 in C2 to a weighted shortest s–t path whose number of failable arcs is at most ⌊2(n −1)/3⌋.The path is computed in a multigraph formed from two in-arborescences, with shared non-failable arcs weighted 0 and other arcs weighted 1.Source: §3.2 · p. 9
- When the first failed arc on the chosen path is detected, D switches to precomputed trees for the graph with that arc removed and tolerates one additional failure.The header records the path-failure index and a bit for the tree choice; at most 1 + 2⌊2(n −1)/3⌋ states are needed.Source: §3.2 · p. 10
- ⌈log(1 + 2⌊2(n −1)/3⌋)⌉ bits suffice for scheme D to tolerate two arc failures, and its bound is within 3 bits of the lower bound.For every n ≥ 3, D's bound is strictly smaller than C2's, saving at least 1 bit.Source: §3.2 · p. 10
4 Improved Lower Bound for Multi Failures at Least 2
A path gadget forces the packet header to encode which cross-arc remains usable. Cascading gadgets extends this information requirement to general k, while a single gadget yields the k=2 lower bound.
4 Improved Lower Bound for Multi Failures at Least 2
- A gadget can force every surviving s–t path through a chosen cross-arc, making at least ceil(log ℓ) header bits necessary to distinguish the possible paths.The forwarding rule must choose whether to use that cross-arc without observing a local failure, so the choice must be made using the packet header.Source: §4 · pp. 11–12
- For k=2, the construction requires at least ceil(log floor(n/3)) rewritable bits.It uses one gadget with ℓ=floor(n/3), padding any remaining vertices with unreachable isolated nodes.Source: §4 · pp. 11–12
- For general k, cascading k′=floor(k/2) gadgets makes the required header information grow with the number of connected gadgets.Each gadget requires ceil(log N) bits to remember which cross-arc carries the s–t path; the construction uses N=floor((n−1+k′)/(3k′)).Source: §4 · p. 12
- The construction applies only when k′≤(n−1)/8, because each gadget must contain at least eight nodes.Source: §4 · p. 12
- The adversary independently chooses an index in each gadget and removes at most two arcs there, leaving only the path through that index’s cross-arc able to reach t.The routing strategy must select the correct route using the packet header; otherwise the packet is returned to s.Source: §4 · p. 13
5 Concluding Remarks
The paper establishes improved upper and lower bounds for resilient local failover routing. For k=2, the bounds are within three bits, while the exact header size and the gap for k>n remain open.
5 Concluding Remarks
- The paper establishes improved upper and lower bounds on rewritable header bits for resilient local failover routing in directed graphs.Source: §5 · p. 13
- For k=2, the upper bound ⌈log(1 + 2⌊2(n −1)/3⌋)⌉ bits and lower bound ⌈log⌊n/3⌋⌉ bits differ by at most 3 bits.Source: §5 · p. 13
- The exact header size for 2-resilient routing remains open, as does the gap for k>n between an Ω(n)-bit lower bound and Ck’s O(n log(k/n))-bit scheme.The authors identify closing the latter gap, particularly when k is substantially larger than n, as future work.Source: §5 · p. 13