Improved Algorithms for Local Failover Routing on Directed Graphs

Jul 16, 2026

Local failover routing forwards packets using only pre-calculated routing tables even when several directed arcs fail. The paper studies local failover schemes on directed graphs with up to k arc failures, focusing on minimizing the number of rewritable header bits. It closes the gap between known upper and lower bounds by providing a scheme that tolerates k faulty arcs with header size min(…) rewritable bits. Matching lower bounds show any local failover routing needs Ω(…) bits across different failure regimes.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages17

Reading Time43 min

Abstract

Introduction

Problem statement and background

Main contributions and theorems

Discussion and comparison with prior bounds

Theorems overview

arXiv :2607 . 1 1229v 1 [ cs .DS] 13 Jul 2026 Improved Algorithms for Local Failover Routing on Directed Graphs Yuki Kawashima Naoki Kitamura Taisuke Izumi July 14, 2026 Abstract The local failover routing is a mechanism that routes a packet from a source to a destination only using pre-calculated routing tables, even when several edges fail. In this paper, we study local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with 􀀺-arc failures. There are many studies of failover routing on undirected graphs, and it has been investigated whether routing is possible depending on the number of bits in the packet header, the type of failure, the graph properties, etc. In contrast, there is not much research on directed graphs. Van et al. first showed the upper and lower bounds of rewritable bits in the packet header on directed graphs. However, their results showed a large gap between the upper and lower bounds. The main contribution of this paper is to close the gap between the upper and lower bounds. Specifically, we show that our scheme can route packets with 􀀺 faulty arcs if the packet header has min (􀀺 log( 􀀴~~ ~~(2􀀽􀀺−3) , 2􀀽 log( 􀀴~~ ~~(2􀀽􀀺−3) ))) rewritable bits, where 􀀽 is the number of nodes. Moreover, any local failover routing scheme needs Ω (􀀺 ⌈log ~~􀀽~~􀀺 ⌉) rewritable bits when the number of faulty arcs is equal to or less than 3~~ ~~(􀀽8−~~ ~~1) and ~~􀀽 ~~−41 rewritable bits when the number of faulty arc is more than 3~~ ~~(􀀽8−~~ ~~1) . This result means our scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes. 1 Introduction The local failover routing is a mechanism that delivers a message from 􀁂 to 􀁃 only using pre-calculated routing tables, even when several edges fail (i.e., deleted from the network) . It is known that static local failover routing from 􀁂 to 􀁃 ina directed graph is impossible even in the case of a single arc failure unless the packet has rewritable bits in its header [8] . Hence, as prior results, we also focus on the local failover routing with packet headers. Several studies have investigated whether message transmission is possible with respect to some parameters such asthe number of faulty edges, the properties of the graph structure, and the upper limit of the rewritable bits in the packet header [4, 8] . For the upper bound 􀀺 on the number of failing arcs, Van et al. showed that a rewritable header of 􀀺 ⌈log |􀀚 |⌉ bits suffices to deliver messages between any nodes, here |􀀚 | is the number of arcsin the graph. On the other hand, the state-of-the art lower bound for header size is ⌈log(􀀺 + 1)⌉ bits [8], which has a large gap with the upper bound of Van et al. In this paper, we further investigate the upper and lower bounds ofthe rewritable bits required for static local failover routing in a directed graph. Precisely, our main contributions present tighter upper and lower bounds on packet header sizes in several settings, which are stated as follows: Theorem 1. Let 􀀜 = (􀀫 , 􀀚 ) be a directed graph with 􀀽 nodes and 􀀙 be its diameter of 􀀜 . Assuming at most one arc failure, there exists a local failover routing scheme A that uses ⌈log(􀀙 + 1)⌉ -rewritable bits in the packet header. Theorem 2. For any 􀀺, let 􀀜 = (􀀫 , 􀀚 ) be a directed graph with 􀀽 nodes. Assuming at most 􀀺 arc failure, there exists a local failover routing scheme B that uses at most min (􀀺 ⌈log 􀀴~~ ~~(2􀀽~~ ~~􀀺~~ ~~−~~ ~~3) ⌉ , 2􀀽⌈log 􀀴~~ ~~(2􀀽~~ ~~+2􀀽􀀺~~ ~~−~~ ~~3) ⌉) rewritable bits in the packet header. Theorem 3. There exists a lower bound graph 􀀜 of 􀀽 nodes such that any local failover routing tolerates at least three arc failures requires at least ⌈log(􀀽 −1)⌉ − 1 and ⌈log(􀀽 − 2)⌉ − 1 rewritable bits in the packet header when 􀀽 is odd and even, respectively. Theorem 4. For any integer 3 ≤ 􀀺 ≤ 3~~ ~~(􀀽8−~~ ~~1) , there exists a lower bound graph 􀀜 of 􀀽 nodes such that any local failover routing to

FAQs

What problem does local failover routing address on directed graphs?

It delivers packets using pre-calculated routing tables even when one or multiple directed arcs are deleted due to failures.

How does the paper improve on prior results for rewritable header bits?

It provides tighter upper and lower bounds on the number of rewritable bits needed to tolerate k arc failures, reducing the gap between previously known extremes on directed graphs.

What do the main theorems establish about the required packet-header size?

Theorems give an achievable header size for limited failures (including the single-failure case) and prove lower bounds showing that any local failover routing requires at least certain Ω(...) numbers of rewritable bits depending on k.

Jul 16, 2026

Upload by Evangeline