An improved Lower Bound for Local Failover in Directed Networks via Binary Covering Arrays
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908855757176832 |
|---|---|
| author | Akker, Erik van den Foerster, Klaus-Tycho |
| author_facet | Akker, Erik van den Foerster, Klaus-Tycho |
| contents | Communication networks often rely on some form of local failover rules for fast forwarding decisions upon link failures. While on undirected networks, up to two failures can be tolerated, when just matching packet origin and destination, on directed networks tolerance to even a single failure cannot be guaranteed. Previous results have shown a lower bound of at least $\lceil\log(k+1)\rceil$ rewritable bits to tolerate $k$ failures.
We improve on this lower bound for cases of $k\geq 2$, by constructing a network, in which successful routing is linked to the \textit{Covering Array Problem} on a binary alphabet, leading to a lower bound of $Ω(k + \lceil\log\log(\lceil\frac{n}{4}\rceil-k)\rceil)$ for $k$ failures in an $n$ node network. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23860 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An improved Lower Bound for Local Failover in Directed Networks via Binary Covering Arrays Akker, Erik van den Foerster, Klaus-Tycho Data Structures and Algorithms Networking and Internet Architecture Communication networks often rely on some form of local failover rules for fast forwarding decisions upon link failures. While on undirected networks, up to two failures can be tolerated, when just matching packet origin and destination, on directed networks tolerance to even a single failure cannot be guaranteed. Previous results have shown a lower bound of at least $\lceil\log(k+1)\rceil$ rewritable bits to tolerate $k$ failures. We improve on this lower bound for cases of $k\geq 2$, by constructing a network, in which successful routing is linked to the \textit{Covering Array Problem} on a binary alphabet, leading to a lower bound of $Ω(k + \lceil\log\log(\lceil\frac{n}{4}\rceil-k)\rceil)$ for $k$ failures in an $n$ node network. |
| title | An improved Lower Bound for Local Failover in Directed Networks via Binary Covering Arrays |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2602.23860 |