1 Introduction↩︎

The local failover routing is a mechanism that delivers a message from \(s\) to \(t\) 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 \(s\) to \(t\) in a directed graph is impossible even in the case of a single arc failure unless the packet has rewritable bits in its header [1]. 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 as the number of faulty edges, the properties of the graph structure, and the upper limit of the rewritable bits in the packet header [1], [2]. For the upper bound \(k\) on the number of failing arcs, Van et al. showed that a rewritable header of \(k \lceil \log |E| \rceil\) bits suffices to deliver messages between any nodes, here \(|E|\) is the number of arcs in the graph. On the other hand, the state-of-the art lower bound for header size is \(\lceil\log (k+1)\rceil\) bits [1], which has a large gap with the upper bound of Van et al.

In this paper, we further investigate the upper and lower bounds of the 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:

Table 1 summarizes the previous results and our new contributions. For one failure, our upper bound replaces the worst-case path length \(n-1\) with the diameter \(D\). Since the diameter \(D\) is at most \(n - 1\), our result of \(\lceil \log (D + 1) \rceil\) is better than the existing \(\log n\).

For multiple failures, the improvement over the previous upper bound \(k\lceil \log |E| \rceil\) is seen by comparing it with the two terms in Theorem [thm:upper95k]. The first term is roughly \[k\log\frac{n+k}{k}=k\log\left(1+\frac{n}{k}\right),\] which replaces the factor \(\log |E|\) by \(\log(1+n/k)\). Thus, when \(k\) is small or moderate compared with \(n\), the cost is about \(k\log(n/k)\) rather than \(k\log |E|\); the saving becomes larger as \(k\) increases. When \(k\) is large, the second term, \[n\log\frac{n+k}{n}=n\log\left(1+\frac{k}{n}\right),\] can be smaller, so the minimum prevents the bound from growing linearly with \(k\log |E|\). On the lower bound, Theorems [thm:lower95k3]–[thm:lower95max] improve the previous lower bound \(\lceil\log(k+1)\rceil\) by showing that some graphs require a header size that grows with \(n\). Thus, for a wide range of \(k\), the known upper and lower bounds become much closer.

The theorems above successfully narrow the gap between the upper and lower bounds on the number of rewritable bits required for packet headers.

1.1 Related Works↩︎

There has been a lot of research on failover routing, in both directed and undirected networks. First, we will introduce some results on undirected graphs. Feigenbaum et al. first presented theoretical study on local failover routing [3]. They showed that, without header information, single-edge failures are always tolerable, but tolerating multiple failures is generally impossible. Dai et al. investigated the limitation by Feigenbaum et al. in more details. Precisely, they showed that the routing without rewriting packet headers is possible for two-edge failures, but impossible for three or more failures [4]. Chiesa et al. proposed a routing method that can tolerate \(k\)-\(1\) failures using \(\log k\) bits in \(k\)-edge-connected graphs for any \(k \leq 5\) [5]. Foerster et al. studied fault tolerance in two variants of the models in which vertices can and cannot identify the source of a packet. They showed that perfect fault tolerance is impossible for nonplanar graphs. They also proposed algorithms achieving perfect fault tolerance for all outerplanar graphs and related settings, as well as for nonouterplanar graphs where the destination is within two hops of the source [6]. Dai et al. classified link failures into three types: static (i.e., links which permanently and simultaneously fail), semi-dynamic (removing the assumption that links fail simultaneously), and dynamic (removing the assumption that links fail permanently), and examined the fault tolerance of failover routing for each type, clarifying its capabilities and limitations [2]. As a result, they showed a routing method which tolerates \(k-1\) dynamic link failures in \(k\)-edge-connected graphs for \(k \leq 5\). Furthermore, they showed that this result can be extended to any \(k\) by providing \(\log k\)-rewritable bits in the packet header. They also showed that rewriting \(3\) bits suffices to cope with \(k\) semi-dynamic failures. However, on general graphs, tolerating \(2\) dynamic failures becomes impossible without rewritable bits. Even by rewriting \(\log k\) bits, fault tolerance is impossible for \(k\) dynamic failures.

In contrast to undirected networks, the local failover routing for directed networks is just at the beginning. Grobe et al. carefully examined whether existing methods for undirected graphs can be applied to directed graphs, and compared the existing methods with their proposed method through simulations. As a result, they showed that their application is superior to the existing algorithms in most topologies [7]. Van et al. analyzed real-world topologies and showed that two-edge failure tolerance is possible in many real networks using two additional bits [8]. However, these two earlier results do not provide any theoretical analyses. Van et al. investigated local failover routing in directed graphs and gave upper and lower bounds on the number of bits required in the packet header [1]. They showed that at least one bit is required for one failure in the packet header and that \(\log n\) bits are sufficient to tolerate one failure. They also showed that at least \(\log (k+1)\) bits are required for \(k > 1\) failures, and \(k\log|E|\) bits are sufficient to tolerate \(k\) failures.

Therefore, previous work on local failover routing in directed graphs leaves a large gap between the upper and lower bounds on the number of rewritable bits in the packet header. This paper focuses on this gap in the static failure model. Compared with the known upper bound of Van et al., our routing schemes reduce the required header size by encoding failure information more compactly. On the lower bound, our constructions show that substantially more than the known lower bound are sometimes necessary. These upper and lower bounds show how many rewritable header bits are sufficient, and how many can be necessary, for storing failure information in directed local failover routing.

1.2 Organization↩︎

In Section 2, we explain the routing model. In Section 3, we prove the upper bounds on header size for local failover routing. In Section 4, we prove the lower bounds on header size for local failover routing. Finally, in Section 5, we explain the conclusion and open problems.

2 Model↩︎

We consider a simple directed graph \(G = (V, E), |V|=n\), where nodes represent routers and arcs represent communication links. Each node is assigned a unique identifier. Each arc is also assigned with a unique identifier represented by the pair of its endpoints’ IDs. The diameter of the graph \(G\) is denoted by \(D\). A local failover routing \(R(G,k)\) for \(G = (V, E)\) and \(k\) is defined as a collection of \(|V|\) local forwarding rules assigned to vertices in \(V\). A local forwarding rule \(R_v\) at \(v\) is defined as the following function: \[\begin{align} & R_v:E \times 2^{|\delta(v)|} \times V \times V \times \{0,1\}^{\ast} \to E \times \{0,1\}^{\ast}. \\ \end{align}\] Here, \(\delta(v)\) is the set of outgoing arcs of \(v\) (i.e., \(\delta(v) = \{(v, u) \in E:u \in V\}\)). \(R_v\) determines how to process a packet arriving at the node. For \(R_v(\mathit{in}, F_v, s, t, b) = (\mathit{out}, b')\), the given arguments and returned values mean:

• \(in\) : The incoming arc from which the packet arrived (or \(\varepsilon\) if the packet is originated at the node).

• \(F_v\) : The set of locally faulty outgoing arcs. Note that if the node \(v\) sends a message through a faulty arc, it finds the arc failed. Then that arc is added to \(F_v\).

• \(s\) : The ID of the source node of the packet. This information is stored in the packet header.

• \(t\) : The ID of the target node of the packet. This information is stored in the packet header.

• \(b\) : A rewritable bit string carried in the packet header.

• \(out\) : The outgoing arc to which the packet is sent.

• \(b'\) : The updated bit string carried in the header of the packet sent out.

Note that the IDs of \(s\) and \(t\) in the packet header are never rewritten. When a packet arrives at a node other than its destination \(t\), the node decides the neighboring node to which that packet is forwarded following the rule \(R_v\). After that, it sends the packet to the next node. When a node fails to send a packet, it stores the faulty arc in \(F_v\) and rewrites the packet header. Then it retries the packet forwarding according to the forwarding rules. We model the directed local failover routing as a two-player game between player 1 (the designer) and player 2 (the adversary):

1. The players are given a simple directed graph \(G = (V, E)\) with \(n = |V|\) nodes and a failure parameter \(k\).

2. The player 1 defines a set of local forwarding rules for each node, which must be able to route packets from a given source \(s\) to a target \(t\) as long as a \(s\)-\(t\) path exists in the current graph.

3. Let \(F\) be a subset of \(E\) that contains at most \(k\) arcs. The player 2 removes \(F\) from \(G\).

4. For any \(s\) and \(t\) such that every node reachable from \(s\) in \(G - F\) is reachable to \(t\) in \(G - F\), verify if the predefined local forwarding rules can successfully guides the packet from \(s\) to\(t\) or not. If it succeeds for all those pairs, then player 1 wins. Otherwise player 2 wins.

A local failover routing scheme \(\mathcal{A}\) is an algorithm of outputting a local failover routing for a given network \(G\) and a threshold parameter \(k\). The efficiency of a local forwarding rule is measured by the size of rewritable bits used in designed forwarding rules (referred to as header size). When the header size of any packet that can be sent in routing \(R(G,k)\) is less than or equal to \(B\), we say that the header size of \(R(G, k)\) is at most \(B\). For any \(n\)-node directed graph \(G\) and the failure parameter \(k\), if the header size of \(R(G,k)\) outputted by the scheme \(\mathcal{A}\) is bounded by a function \(f(n,k)\), the header size of the \(\mathcal{A}\) is said to be \(f(n,k)\).

3 Upper Bounds on Header Size for Local Failover Routing↩︎

In this section, we present local failover routing schemes \(\mathcal{A}_1\) and \(\mathcal{A}_2\) respectively providing the upper bounds of Theorem [thm:upper95k1] and [thm:upper95k].

Since any packet contains the information of its source and destination, one can apply different forwarding rules for packets with different source-destination pairs. Hence in the following argument we focus on the construction of the forwarding rule for a fixed pair \((s, t)\). The combination of the constructed rules for all \((s, t)\) obviously deduces whole forwarding rule. The baseline strategy common among \(\mathcal{A}_1\) and \(\mathcal{A}_2\) is stated as follows: The routing algorithm tries to send the packet via a path from \(s\) to \(t\). If the packet encounters a faulty arc in the transfer along the path, it records the arc ID in its header. After that, the packet is transferred along a predetermined route in the input graph, provided that the set of faulty arcs carried in the packet header are all removed. Since we assume that \(v\) must be reachable to \(t\) if the packet is reachable to a vertex \(v\) from \(s\), there necessarily exists a path to \(t\) avoiding all faulty arcs. Hence one can always design a correct failover routing scheme following this strategy. The design factor lying in this strategy is twofold: First, how the information of faulty arcs written to the packet header is encoded. Second, which path from \(v\) to \(t\) is chosen when a set of (identified) faulty arcs is given.

3.1 Upper Bound for a Single Failure↩︎

In this section, we show Theorem [thm:upper95k1]. Since explicitly storing faulty arc IDs requires \(k \log n\) bits in the worst case, we need to encode the information of the set of faulty arcs more compactly. Our key technical idea is to store the “time” when the node fails to send the packet¹. That is, instead of remembering the arc ID, the packet header remembers when the packet forwarding failed, counting from the origination of the packet. We refer to the time when packet transfer fails as a failing time. Because packet transmission is deterministic, it is possible to determine the route where a packet was transferred by using the header information. In addition, it is possible to restore the set of the faulty arcs the packet encounters from its header.

3.2 Upper Bound for Multiple Failures↩︎

In this section, we show Theorem [thm:upper95k]. The strategy for \(\mathcal{A}_2\) is close to \(\mathcal{A}_1\). The key idea behind \(\mathcal{A}_1\) is the packet passes through at most \(D\) arcs, and thus it can encounter at most \(D\) different positions in its transfer. Hence \(\log D +1\) bits suffices to store the information of the faulty arc (note that each forwarding rule is designed in advance with full information of \(G\), and thus the information of \(s\)-\(t\) shortest path (i.e., \(P\) in the proof of Theorem [thm:upper95k1]) and other failure-avoiding paths \(P_i\) are available). The scheme \(\mathcal{A}_2\) generalizes this approach to the multiple failure case.

If the length of the path delivering packets from \(s\) to \(t\) is bounded by \(g(k)\), then it can store the information of all failing times by using \((\log \binom{g(k)}{k})\)-rewritable bits. Unfortunately, a routing strategy that always tries to send the packet along a shortest path to \(t\) in the remaining graph (i.e., the graph after removing all encountered faulty arcs) may traverse the \(\Omega(kn)\) arcs in the worst case. To reduce the number of required bits, we consider the following strategy: An arc that succeeded to send the packet can be safely reused in the subsequent packet routing. Hence we do not have to count up the time when reusing such an arc into account, to identify encountered faulty arcs via failing times. This observation allows us to shrink the range of failing times into a value smaller than the transferred path length. To maximize this benefit, when encountering a faulty arc, we select the path from the current node to \(t\) that uses the fewest untraversed arcs, in the graph with removing all encountered faulty arcs.

We explain our scheme in more details. Our scheme (for each \(s\)-\(t\) pair) consists of the two components \(\mathrm{dec}(b, v)\) and the set of paths \(P_{F, v}\) for any \(F \subseteq E\) of \(|F| \leq k\) and \(v \in V\). The routing of the packet with information \(b\) at \(v\) first decodes the rewritable bits \(b\) using \(\mathrm{dec}(\cdot)\), which returns the set of faulty arcs \(F'\) the packet encountered up to \(v\). Then the algorithm forwards its packet along the specified path \(P_{F', v}\). In our scheme, the packet header stores the optimally compressed form of the failure profile \(c\), which is defined as follows: Let \(P = e_1, e_2, \dots, e_h\) be the forwarding edge sequence such that the packet is sent through \(e_i\) at its \(i\)-th forwarding (note that \(e_i\) might be faulty and thus it is not guaranteed that \(P\) forms a path from \(s\) to \(v\)). The first edge sequence \(\tau(P)\) of \(P\), which is the one obtained from \(P\) by extracting the first appearance of each edge. For example, given \(P = e_1, e_3, e_2, e_1, e_3, e_4\), \(\tau(P)\) becomes \(e_1, e_3, e_2, e_4\). The failure profile \(c\) is defined as the bit string of length \(|\tau(P)|\) such that the \(i\)-th bit of \(c\) is one if and only if the \(i\)-the edge of \(\tau(P)\) is faulty.

The function \(\mathrm{dec}(b, v)\) first uncompresses \(b\) into \(c\), and simulates the packet forwarding from \(s\) to \(v\) under the condition of the failure events represented by \(c\). This simulation is possible because \(v\) knows whole information on \(G\). Obviously, it also reconstructs \(P\), and thus provides the information on \(F'\). To minimize the size of header information, our scheme chooses \(P_{F',v}\) such that the length of \(\tau(P \circ P_{F',v})\) is minimized (where \(\circ\) means the concatenation of two sequences). More precisely, we choose \(P_{F',v}\) as the shortest \(v\)-\(t\) path in the graph \(G - F'\) where weight zero is given to edge \(e\) if it is contained in \(P\), or one otherwise. When the packet is sent through edge \(e''\), if \(e''\) is not contained in \(P\), an additional bit 1 is appended to \(c\), and its header is rewritten by the compressed form of \(c\) after appending. If the packet transfer fails, \(e''\) is added to the reconstructed \(F'\), and the appended bit is changed to zero. Then the new route \(P_{F', e''}\) is chosen. If \(e''\) is the edge in \(P\) (and not in \(F\)), the packet is transferred without any modification.

Now, we show the number of required bits for the rewritable bits under our strategy. Here, we show the following lemma.

Now we show Theorem [thm:upper95k].

4 Lower Bound for bit-string length↩︎

In this section, we show the lower bounds on the number of rewritable bits in the packet header for \(k\geq 3\). To prove this, we construct a graph in which packet headers must encode a large number of failure patterns which must be distinguished for correct delivery of packets. First, we show the construction of a gadget \(A_{\ell}\) as follows:

• Create two paths \((u_0,u_1,\dots,u_{\ell-1})\) and \((v_{0},v_1,\dots,v_{\ell-1})\).

• Add an arc \((u_j,v_j)\) for each \(0\leq j \leq \ell -1\).

An example of \(A_\ell\) is illustrated in Figure 2.

Here, we show the following lemma.

Next, we construct a lower bound graph for general \(k\) by cascading multiple copies of the gadget \(A_{\ell}\). By Lemma 2, we can limit the number of paths from \(u_0\) to \(v_{\ell -1}\) in the gadget \(A_{\ell}\) to only one by removing three arcs. In this case, \(\log \ell\) bits are required to remember which \((u_j,v_j)\) in the gadget is the path from \(u_0\) to \(v_{\ell-1}\). Thus, the total amount of information that must be encoded in the packet header grows in proportion to the number of connected gadgets. Now, we show Theorem [thm:lower95k].

5 Conclusion and Open Problems↩︎

This study shows the upper and lower bounds of the number of rewritable bits required in the packet header for the local failover routing on directed graphs. As a result, we presented the local failover routing scheme that can route packets using only \(\min(k \log ( \frac{e(2n+k-3)}{k},2n \log ( \frac{e(2n+k-3)}{2n})))\) rewritable bits. Moreover, any local failover routing scheme needs \(\Omega(k\lceil\log\frac{n}{k}\rceil)\) rewritable bits when the number of faulty arcs is equal to or less than \(\frac{3(n-1)}{8}\) and \(\frac{n-1}{4}\) rewritable bits when the number of faulty arc is more than \(\frac{3(n-1)}{8}\). Our results proposed a near optimal routing scheme when the number of faulty arcs is approximately less than the number of nodes. However, we have not yet shown the optimal routing scheme in which most of arcs are faulty. It is also interested in considering whether routing is possible for each graph property and type of failures.

References↩︎