Name Independent Fault Tolerant Routing Scheme

Abstract

We consider the problem of routing in presence of faults in undirected weighted graphs. More specifically, we focus on the design of compact name-independent fault-tolerant routing schemes, where the designer of the scheme is not allowed to assign names to nodes, i.e., the name of a node is just its identifier. Given a set $F$ of faulty (or forbidden) edges, the goal is to route from a source node $s$ to a target $t$ avoiding the forbidden edges in $F$. Given any name-dependent fault-tolerant routing scheme and any name-independent routing scheme, we show how to use them as a black box to construct a name-independent fault-tolerant routing scheme. In particular, we present a name-independent routing scheme able to handle any set $F$ of forbidden edges in $|F|+1$ connected graphs. This has stretch $O(k^2|F{|}^3(|F|+{\log }^{2}n)\log D)$, where $D$ is the diameter of the graph. It uses tables of size $\tilde{O}(k{n}^{1/k}(k+deg(v)))$ bits at every node $v$, where $deg(v)$ is the degree of node $v$. In the context of networks that suffer only from occasional failures, we present a name-independent routing scheme that handles only $1$ fault at a time, and another routing scheme that handles at most $2$ faults at a time. The former uses $\tilde{O}(k^2{n}^{1/k}+kdeg(v))$ bits of memory per node, with stretch $O(k^3\log D)$. The latter consumes in average $\tilde{O}(k^2{n}^{1/k}+deg(v))$ bits of memory per node, with stretch $O(k^2\log D)$.

arXiv commentThe stretch analysis is faulty, so the whole idea does not work