2.1 Network Model

We make the following assumptions.

(A1) A given network topology is a connected graph, and it remains so even if at most two components fail.

(A2) When a node fails, it does not send packets, and the opposite node of every link of the failed node does not use the link for packet forwarding.

(A3) When a node fails, packets destined for it must be removed from the network; that is, we must consider a reroute method that can remove such packets.

2.2 Method using Multiple Routing Configurations

The MRC method generates several BCs from a given network topology. Although each BC has the same nodes and links as those of the given network topology, the nodes are classified into two types (normal and isolated) and the links are classified into three types (normal, restricted, and isolated). The BCs must satisfy the following conditions.

(C1) Each node is an isolated node in only one BC, and each link is an isolated link in only one BC.

(C2) For a BC, when the topology that is created by removing all restricted and isolated links and isolated nodes is still a connected graph, we call it the backbone of the BC. For every BC, the backbone must exist.

(C3) Each isolated node has no normal links, only restricted and isolated ones. The number of restricted links is at least one An isolated node connects to a normal node in the backbone of the BC using a restricted link. An isolated node can have any number of isolated links, including zero.

Fig. 1 shows examples of BCs. Fig. 1(a) shows a given network topology, Figs. 1(b) and 1(c) show BCs obtained from Fig. 1(a), and Figs. 1(d) and 1(e) show backbones of the BCs. It is easily confirmed that the BCs in Fig. 1 satisfy the above conditions.

In the MRC method, packets are forwarded using the normal routing table based on a given network topology when the network has no failures. When a packet reaches a node and its next hop link cannot be used because of failure of either the link or the node to which the link connects (we call such a node the target node), the packet is rerouted using the BC where the link is isolated if the target node is the final destination node of the packet, or the packet is rerouted using the BC where the target node is isolated if the target node is not the final destination node of the packet.

Isolated nodes and links in a BC are ones that cannot be used to reroute packets in that BC. Restricted links in a BC are ones that can only be used as the first or last hop link of a reroute path, and they cannot be used as intermediate links of a reroute path. Normal nodes and links in a BC are ones that can be used at all times when packets are being rerouted.

If a packet that is rerouted at a node encounters another failure, it means that the assumption of single component failure does not hold; that is, multiple network components fail. Therefore, such a packet is removed from the network.

2.3 Method using Node-Independent Spanning Trees

For a given network topology $G$, its two spanning trees $T^d_1$ and $T^d_2$ rooted at node $d$ are called NISTs if path $P^d_1$ from arbitrary node $v$ to $d$ in $T^d_1$ does not include any node that is included as an intermediate node of path $P^d_2$ from $v$ to $d$ in $T^d_2$, that is, paths $P^d_1$ and $P^d_2$ are independent of each other (if $P^d_1$ and $P^d_2$ do not have intermediate nodes, then $T^d_1$ and $T^d_2$ are not NISTs of each other).

Fig. 2 shows examples of NISTs. Fig. 2(a) is identical to Fig. 1(a), and Figs. 2(c) and 2(d) are NISTs rooted at node 1 that is obtained from Fig. 2(a).

Assume that for every node $d$ in $G$, there exist two NISTs $T^d_1$ and $T^d_2$ rooted at node $d$. Then we can reroute packets with destination node $d$ using $T^d_1$ and $T^d_2$ as follows (see Fig. 3).

When the network has no failures, packets are forwarded using the normal routing table obtained from a shortest spanning tree (say $T^d_0$).

Next, in Fig. 3, assume that a packet from its source node $s$ reaches node $u$ using $T^d_0$ and it encounters a failure of link $u$-$v$ because of a failure of either link $u$-$v$ itself or node $v$. The packet is then rerouted from $u$ using $T^d_1$ or $T^d_2$. Without loss of generality, we assume that $T^d_1$ is used and that the packet encounters a failure of link $a$-$v$ at node $a$ due to a failure of $v$. The packet is then again rerouted from node $a$ using another NIST $T^d_2.$ Because $T^d_1$ and $T^d_2$ are NISTs of each other, the path from $a$ to $d$ in $T^d_2$ does not include node $v$, and consequently the packet can reach node $d$ without encountering any failure. In $T^d_1$, if the path from $u$ to $d$ does not include node $v$, then the packet can reach $d$ without using $T^d_2$. If $v$ is identical to $d$, then the packet encounters failures twice in $T^d_1$ and $T^d_2$. Therefore, the packet is removed from the network, which is a reasonable operation satisfying assumption (A3) because the destination node fails.

3.1 Idea

In the MRC method, each BC guarantees that packets can reach an arbitrary node from another arbitrary node without passing through isolated links or nodes as intermediate links and nodes using the BC. Thus, as described in the previous section, when a packet encounters a component failure, it can reach its destination using the BC where the failure component is isolated.

On the other hand, we consider the topology that is obtained from a BC by removing all the isolated links of the BC (we call this a shrunken topology). Fig. 4 show examples of shrunken topologies. Fig. 4(a) is a given topology that is identical to the ones in Figs. 1(a) and 2(a). Figs. 4(b)-4(e) show examples of BCs obtained from Fig. 4(a), and Figs. 4>(f)-4(i) show shrunken topologies obtained from Figs. 4(b)-4(e), respectively. Note that isolated links (orange dotted lines) in Figs. 4(b)-4(e) are removed in Figs. 4(f)-4(i).

Assume that we can construct the following two NISTs $T^d_1$ and $T^d_2$ rooted at node $d$ from the shrunken topology of the BC.

(1) If root node $d$ is an isolated node in the BC, then all the isolated nodes except $d$ in the BC are leaf nodes of $T^d_1$ and $T^d_2$.

(2) If root node $d$ is not an isolated node in the BC, then all the isolated nodes in the BC are leaf nodes of $T^d_1$ and $T^d_2$.

Then, it is trivial from Section 2.3 that packets can reach node $d$ from an arbitrary node if at most one component fails in the shrunken topology of the BC. Hereafter, we describe NIST $T_i$ ($i=1$, $2$) rooted at node $d$ that is constructed from the shrunken topology of ${\mathrm{BC}}_j$ as $T^d_i({\mathrm{BC}}_j)$.

From the discussion above, we propose the following IP reroute method for dealing with two network component failures (see Fig. 5).

(1) If a packet with destination node $d$ encounters a component failure, then we select a BC (say ${\mathrm{BC}}_j$) according to the BC selection policy of the MRC method, and the packet is rerouted using $T^d_1$(${\mathrm{BC}}_j$).

(2) If the packet encounters another failure, then it is again rerouted using $T^d_2$(${\mathrm{BC}}_j$).

3.2 Generation of NISTs for Rerouting against Double Network Component Failures

In our proposed method, we generate two NISTs rooted at every node from a given network topology $G$ using the following algorithm.

NIST generation algorithm

(Step 0) Let $n$ be the number of BCs starting from $n=2$.

(Step 1) If $n\le N$ ($N$ is the number of nodes in $G$), then proceed to Step 2; otherwise terminate the algorithm (which means that we fail to generate NISTs).

(Step 2) Using our BC generation algorithm described later, if ${\mathrm{BC}}_1$, ${\mathrm{BC}}_2$, ... ,$\mathrm{\ }{\mathrm{BC}}_n$ can be generated from $G$ such that each BC satisfies the following conditions (i) and (ii), then proceed to Step 3; otherwise return to Step 1 after incrementing the value of $n$ by one.

(i) Each isolated node must have at least two restricted links.

(ii) Each normal node must have at least two normal links.

(Step 3) Create the shrunken topology from each ${\mathrm{BC}}_i$ generated in Step 2.

(Step 4) For each destination node $d$ in each shrunken topology $T_s$, generate two NISTs ($T^d_1$, $T^d_2$) using the following steps in this order.

(Step 4-1) If $d$ is an isolated node in $T_s$, remove all isolated nodes except $d$ in $T_s$; otherwise (if $d$ is not an isolated node), remove all isolated nodes.

(Step 4-2) Let ${T_s}^{'}$ be $T_s$ after the execution of Step 4-1. If two NISTs ($T^d_1$, $T^d_2$) can be created from ${T_s}^{'}$ using the algorithm in ^[16] (which is an algorithm for creating two NISTs from a given connected graph), proceed to Step 4-3; otherwise return to Step 1 after incrementing the value of $n$ by one.

(Step 4-3) Using the isolated node connecting algorithm described later, connect every isolated node that was removed in Step 4-1 to the two NISTs ($T^d_1$, $T^d_2$) created in Step 4-2 so that they can remain NISTs.

Note that in the NIST generation algorithm described above, we try to generate ${\mathrm{BC}}_1$, ${\mathrm{BC}}_2$, ... ,$\mathrm{\ }{\mathrm{BC}}_n$ from $G$ such that each BC satisfies conditions (i) and (ii) in Step 2 because we must generate two NISTs rooted at each node in Step 4. Figs. 4(b)-4(e) are BCs obtained from Fig. 4(a) by Step 2 that satisfy conditions (i) and (ii).

We describe our BC generation algorithm in Step 2.

To attain condition ($\mathrm{i}$) described above, we modify the BC generation algorithm in ^[11]. That algorithm tries to isolate each node in only one BC as described in (C1) and decides whether node $u$ can be isolated in a BC (say ${\mathrm{BC}}_i$) by executing the following steps in order.

BC generation algorithm of ^[11]

(P0) Set a given network topology to the initial topology of $\mathrm{each\ }{\mathrm{BC}}_j\ \left(1\le j\le n\right).$

(P1) Select a node $u$ randomly among all nodes.

(P2) Set a variable $i=1$, and set a variable $start\_i=i$.

(P3) Try to isolate node $u$ in ${\mathrm{BC}}_i$ by executing the following steps (P3-0) to (P3-5) in this order.

(P3-0) If $u$ has a restricted link in ${\mathrm{BC}}_i$, then the isolation of $u$ in ${\mathrm{BC}}_i$ fails, and proceed to (P4).

(P3-1) All links of $u$ that are currently isolated links in ${\mathrm{BC}}_i$ remain isolated links in ${\mathrm{BC}}_i$.

(P3-2) We temporarily change all links of $u$ in ${\mathrm{BC}}_i$ to isolated links in ${\mathrm{BC}}_i$ if they are currently restricted links in other BCs.

(P3-3) We temporarily change all links of $u$ in ${\mathrm{BC}}_i$ to restricted links in ${\mathrm{BC}}_i$if they are currently isolated links in other BCs.

(P3-4) After (P3-3), if $u$ in ${\mathrm{BC}}_i$ has a restricted link, then we temporarily change all the remaining links of $u$ in ${\mathrm{BC}}_i$, which are normal links, to isolated links in ${\mathrm{BC}}_i$; otherwise if $u$ has normal links in ${\mathrm{BC}}_i$, we randomly select one arbitrary link, and temporarily change it to a restricted link in ${\mathrm{BC}}_i$, and temporarily change the remaining normal links to isolated links.

(P3-5) After (P3-4), if $u$ in ${\mathrm{BC}}_i$ has a restricted link, then the isolation of $u$ is successful, the temporary settings of links of $u$ in ${\mathrm{BC}}_i$ are fixed, $u$ becomes an isolated node in ${\mathrm{BC}}_i$ and proceed to (P5); otherwise the isolation of $u$ fails, the temporary settings are canceled and proceed to (P4).

(P4) If $i=n$, then $i=1$, otherwise $i=i+1$. If $i=start\_i$, then the isolation of node $u$ fails and terminate the algorithm; otherwise proceed to (P3).

(P5) If there is a node which has not been isolated yet, then go to (P6); otherwise (i.e. all nodes have been isolated) terminate the algorithm.

(P6) If there is an isolated node $v$ which connects to node $u$ in ${\mathrm{BC}}_i$ by a restricted link and has not been isolated yet, then select the node $v$; otherwise randomly select a node $v$ which has not been isolated yet. And set $start\_i=i+1$ and $i=i+1$, then proceed to (P3) considering node $v$ as node $u$ in (P3).

As described above, the algorithm of ^[11] tries to isolate node $u$ in ${\mathrm{BC}}_{start\_i}$, ${\mathrm{BC}}_{start\_i+1}$, ..., ${\mathrm{BC}}_n$, ${\mathrm{BC}}_1$, ..., ${\mathrm{BC}}_{start\_i-1}$ in this order in (P3) and (P4), and if $u$ has been isolated in ${\mathrm{BC}}_i$, then the algorithm tries to isolate a node $v$ selected in (P6) in ${\mathrm{BC}}_{i+1}$, ..., ${\mathrm{BC}}_n$, ${\mathrm{BC}}_1$, ..., ${\mathrm{BC}}_i$ in this order by setting $start\_i=i+1$.

In our BC generation algorithm, we have changed (P3-4), (P3-5) and (P4) into (P3-4$^{'}$), (P3-5$^{'}$) and (P4$^{'}$), respectively, as described below for condition (i), and we have changed (P5) into (P5$^{'}$) for condition (ii).

Changes in our BC generation algorithm

(P3-4$^{'}$) \textls[-20]{After (P3-3), if $u$ in ${\mathrm{BC}}_i$ has at least two restricted links, then execute (P3-4$^{'}$-1). Otherwise, if $u$ in ${\mathrm{BC}}_i$ has one restricted link, then execute (P3-4$^{'}$-2), otherwise execute (P3-4$^{'}$-3).}

(P3-4$^{'}$-1) We temporarily change all the remaining links of $u$ in ${\mathrm{BC}}_i$, which are all normal links, to isolated links.

(P3-4$^{'}$-2) f $u$ has normal links in ${\mathrm{BC}}_i$, then we randomly select one arbitrary link and temporarily change it to a restricted link, and we temporarily change the remaining normal links to isolated links.

(P3-4$^{'}$-3) If $u$ has at least two normal links in ${\mathrm{BC}}_i$, then we randomly select two arbitrary links and temporarily change them to restricted links, and we temporarily change the remaining normal links to isolated links.

(P3-5$^{'}$) After (P3-4$^{'}$), if $u$ in ${\mathrm{BC}}_i$ has at least two restricted links, then the isolation of $u$ is successful, the temporary settings of links of $u$ in ${\mathrm{BC}}_i$ are fixed, and $u$ becomes an isolated node in ${\mathrm{BC}}_i$; otherwise the isolation of $u$ in ${\mathrm{BC}}_i$ fails, the temporary settings are canceled and proceed (P4$^{'}$).

(P4$^{'}$) If $i=n$, then $i=1$, otherwise $i=i+1$. If $i=start\_i$, then the isolation of node $u$ fails and it means that we fail to generate such ${\mathrm{BC}}_1$, ${\mathrm{BC}}_2$, ..., ${\mathrm{BC}}_n$ that satisfy condition (i), otherwise proceed to (P3).

(P5$^{'}$) If there is a node which has not been isolated yet, then proceed to (P6). Otherwise (i.e. it means that all nodes have been isolated so that condition (i) is satisfied) if each normal node has at least two normal links, then because it means that all nodes have been isolated so that condition (ii) is satisfied, otherwise it means that condition (ii) is not satisfied.

Next, we describe the isolated node connecting algorithm in Step 4-3. If an isolated node (say $u$) has more than two restricted links, then we randomly select two (say links $u$-$v_1$ and $u$-$v_2$; that is, $u$ connects to nodes $v_1$ and $v_2$ in the shrunken topology) of them and remove the others.

Without loss of generality, $P(v_1,d)$ and $P(v_2,d)$ in $T^d_1$ and $P(v_1,d)$ and $P(v_2,d)$ in $T^d_2$ have one of the following relations as shown in Fig. 6.

(R1) $P(v_1,d)$ includes $P(v_2,d)$ in $T^d_1$, and $P(v_2,d)$ includes $P(v_1,d)$ in $T^d_1$.

(R2) $P(v_1,d)$ includes $P(v_2,d)$ in $T^d_1$, and $P(v_1,d)$ and $P(v_2,d)$ are node-independent of each other in $T^d_2$.

(R3) $P(v_1,d)$ and $P(v_2,d)$ are node-independent of each other in $T^d_1$, and they are also node-independent of each other in $T^d_2$.

In (R1) to (R3), if we connect $u$ to $v_2$ in $T^d_1$ and connect $u$ to $v_1$ in $T^d_2$, then $T^d_1$ and $T^d_2$ remain NISTs of each other. The proof is obvious.

4.1 Possibility of Obtaining NISTs

For several numbers of nodes $N$ ranging from 20 to 200, we generated five topologies with minimum node degrees of 3, 4, 5, 6, 8 or 10 in the Waxman (Wax) model ^[17] and the Barab\'{a}si-Albert (BA) model ^[18] using the BRITE (Boston university Representative Internet Topology gEnerator) topology generator ^[19], and we applied our NIST generation algorithm to each of the topologies to examine the possibility of obtaining two NISTs from each topology.

We used topologies with minimum degrees of three or more because we focus on IPFRR that can deal with two network component failures. Each node must have three or more links because if a node has two links or fewer and these links fail, recovery is not possible because the node has no remaining links to connect to other nodes after failure. Thus, we did not consider topologies with a minimum node degree of two or less. On the other hand, as described below, we were able to obtain two NISTs for all topologies with minimum node degrees of four or more, which supports the effectiveness of our NIST generation algorithm. Thus, we did not examine the possibility for topologies with a minimum node degree of eleven or more because we could expect that two NISTs could be obtained for most of such topologies. Furthermore, we used the Wax and BA models because these models have been used as sample network topologies in many previous studies relevant to Internet technologies.

Figs. 7(a) and 7(b) show the necessary number of BCs in order to obtain two NISTs for each topology in the Wax model and BA model, respectively. The results show that we can successfully generate NISTs for many topologies with a minimum node degree of three and for all topologies with minimum node degrees of four and five. Although we do not show the results for topologies with minimum node degrees of 6, 8, and 10, we were successfully able to obtain NISTs for all the topologies. In Figs. 7(a) and 7(b), a lack of vertical bars for a minimum node degree of three (for example, the first and second spaces at 140 nodes in the Wax model) means that the generation of two NISTs failed.

When the minimum node degree is five, the necessary numbers of BCs in the BA model are roughly equal to those in the Wax model and range from three to eight. On the other hand, when the minimum node degree is three or four, the necessary numbers of BCs in the BA model are roughly larger than those in the Wax model. The reason for this is as follows. The BA model has the property that much fewer nodes with higher node degrees (we call such nodes hub nodes) and many more nodes with lower node degrees (we call such nodes non-hub nodes) coexist in each topology. In such a topology, it is difficult to isolate hub nodes in the same BCs, and consequently the possibility that we have to use different BCs to isolate hub nodes increases when the minimum node degree is low. On the other hand, the Wax model does not have this property, and its node-degree difference is smaller than that in the BA model. Thus, it is easy for the necessary number of BCs in the Wax model to be smaller than that in the BA model.

4.2 Increased Number of Hops upon Double Network Component Failures

Next, we discuss the number of hops increasing because of double failures. Let $P_{sd}$ be the number of hops from source node $s$ to destination node $d$ in the failure-free state, and let $P^{ij}_{sd}$ be the number of hops from $s$ to $d$ under failure of network components $i$ and $j$ (each of $i$ and $j$ is a link or a node). Let $NP_{ij}$ be the number of s-d pairs such that $P^{ij}_{sd}-P_{sd}>0$, where we do not consider an s-d pair in which $s$ or $d$ is identical to $i$ ($j$) when $i$ ($j$) is a node because we assume in (A2) that a failure node does not send packets and that packets destined for a failure node must be removed.

We define the average number (${AIH}_{ij}$) of increased hops when network components $i$ and $j$ fail as follows:

Let ${AIH}_{LN}$ be the average of ${AIH}_{ij}$ over all combinations of $i$ and $j$ when $i$ is a link (node) and $j$ is a node (link). In the same way, let ${AIH}_{LL}$ (${AIH}_{NN}$) be the average of ${AIH}_{ij}$ over all combinations of $i$ and $j$ when both $i$ and $j$ are links (nodes).

Figs. 8(a) and 8(b) show ${AIH}_{LL}$, ${AIH}_{LN}$, and ${AIH}_{NN}$ in the Wax model when the minimum node degree is four or five, respectively. In our proposed method, ${AIH}_{LL}$, ${AIH}_{LN}$, and ${AIH}_{NN}$ are denoted by ${AIH}_{LL}$-proposed, ${AIH}_{LN}$-proposed, and ${AIH}_{NN}$-proposed, respectively. We also show ${AIH}_{LL}$, ${AIH}_{LN}$, and ${AIH}_{NN}$ in OSPF for comparison with our proposed method, and these are denoted by ${AIH}_{LL}$-OSPF, ${AIH}_{LN}$-OSPF, and ${AIH}_{NN}$-OSPF, respectively.

In our proposed method, the three $AIH${s} range roughly from two to four with changes in $N$. When comparing the three $AIH$s for each value of $N$, the result is ${AIH}_{LL}$-proposed $>$ ${AIH}_{LN}$-proposed $> {AIH}_{NN}$-proposed, which means that a link failure has more impact on $AIH$. This is because a node pair $\mathrm{(}s,d\mathrm{)}$ is removed from the calculation of $AIH_{ij}$ when $s$ or $d$ is identical to $i$ or $j$, as described in the definition of $AIH_{ij}$.

Figs. 8(c) and 8(d) show the three $AIH$s in the BA model, which range roughly from two to three. As with the Wax model, we see that ${AIH}_{LL}$-proposed $>$ ${AIH}_{LN}$-proposed $>$ ${AIH}_{NN}$-proposed.

When we compare the $AIH$s in the BA model and those in the Wax model, the formers are roughly equal to the latters for smaller $N$ and generally smaller for larger $N$. Although the reason for this is unclear at the moment, we infer that it is closely related to the fact that the BA model has hub nodes with many ${s}$-${d}$ paths in the failure-free state passing through them.

As shown in Fig. 8, although the AIHs in OSPF are roughly one hop, we cannot reroute packets quickly using OSPF. On the other hand, although the AIHs in our proposed method are roughly two to four hops and so only slightly more than those in OSPF, we can reroute packets quickly using our proposed method.