Maximization of the resilience of a tree with a single backup path

In this section, we present an algorithm that aims at determining the backup path which maximizes the resilience of a tree. Finding the backup path itself is performed by a shortest path algorithm. We introduce an incremental version of this algorithm that takes into account modifications of a tree which models a multicast group where hosts can leave and join dynamically.

Main algorithm

We suppose here that no backup path has been previously computed for tree $T$. Our algorithm (see Algorithm 1) proceeds as follows. We first compute the $tdrop$ and $adrop$ metrics for each link of the tree, and preprocess the tree so as to speed up further Least Common Ancestor (LCA) computations required to compute metrics $R_d$. Then, we compute in turn $R_d$ for all pairs of nodes constituted by a leaf of the tree and another node of the tree. We denote by $(A, B)$ the pair of nodes of the tree which minimizes the set of the metrics $R_d$ previously computed. A shortest path algorithm computes the backup path between $A$ and $B$. If the shortest path algorithm fails to find a backup path, then no backup path achieves optimal path protection in tree $T$.

Claim 2   If Algorithm 1 returns a backup path then this backup path maximizes the resilience of $T$.

Proof:

Suppose that metrics $adrop$ and $tdrop$ are known for each link of the tree (lines 1 to 3). We first prove by contradiction that at least one end node of a backup path which minimizes $R_d$ is a leaf of $T$. Suppose the end nodes $i$ and $j$ of a backup path that minimizes $R_d$ are known and that, by contradiction, $i$ is not a leaf of $T$.

Let $k \in child_i$ (see Figure 3.5). Then:

$$R_d(i, j) = K + adrop_{ik}$$

and:

$$R_d(k, j) = K + \sum\limits_{h \in child_k}{adrop_{kh}}$$

where $K$ is the part of metric $R_d$ that is common to $R_d(i,j)$ and $R_d(k, j)$. More specifically, $K$ takes into account all link failures except for link (i, k) and for all links downstream of node $k$ with regards to root $S$. Since:

$$adrop_{ik}=f_{ik} tdrop_{ik}+\sum\limits_{h\in child_k}{adrop_{kh}}$$

then:

$$R_d(k, j)<R_d(i, j)$$

therefore the pair of nodes $(i, j)$ does not minimize $R_d$, which contradicts the hypothesis. Therefore, at least one of the end nodes $A$ and $B$ of the backup path $BP_{A, B}$ which maximizes the resilience of $T$ is a leaf. We call $A$ the end node that is a leaf. The other end node $B$ has no such restriction and may or may not be a leaf. By construction of nodes $A$ and $B$ in lines 5 to 8, a backup path between $A$ and $B$ minimizes $R_d$ and thus maximizes the resilience of the tree. The backup path is computed in line 9 using a shortest path algorithm between $A$ and $B$ over the graph $G'=((V \setminus V_T) \cup \{A, B\}, E \setminus E_T)$ so that the backup path and the tree are node and edge disjoint. $\Box$

Figure 3.5: Proof of the algorithm. It can be shown that $R_d(j, k)<R_d(j, i)$. Using a recursion, we show that at least one of the end nodes of the backup path must be a leaf.

Definition 5   A near-optimal backup path $BP_{A, B}$ is a backup path such that:

$$R_d(A, B)=\min\limits_{{i,j \in V_T} \atop {BP_{i, j} exists}}R_d(i, j).$$

If no optimal backup path is found, then it is possible to extend Algorithm 1 to find a near-optimal backup path. The extended algorithm (see Algorithm 2) proceeds as follows. As in Algorithm 1, metrics $tdrop$ and $adrop$ are computed for all links of the tree and $T$ is preprocessed to speed up LCA computations in lines 1 to 4.

For any pair of nodes $n_k \in V_T \times V_T$, the value of the metric $R_d$ does not depend on the order of the nodes of the pair, and is zero if both nodes of the pair are the same. Therefore, in a graph which contains $\vert V_T\vert$ nodes, there is a total number of $N_{pairs}=\frac{\vert V_T\vert(\vert V_T\vert-1)}{2}$ possible pairs of end nodes for a backup path.

In lines 5 to 7 of Algorithm 2, metrics $R_d$ are computed for all $N_{pairs}$ pairs of nodes in the tree as defined above and the set of these metrics is ordered from the lowest to the highest in line 8. In lines 9 to 13, considering in turn each pair of nodes from the ordered set previously defined and starting from the pair of nodes which minimizes the set of metrics $R_d$, a shortest path algorithm computes the backup path between the two nodes of the pair until a backup path is found. As with optimal backup paths, a near-optimal backup path is not guaranteed to exist. More precisely, since Algorithm 2 considers in turn all possible pairs of nodes of the tree and tries to find a backup path between these two nodes until a backup path is found, if no near-optimal backup path exists for tree then no backup path at all exists for the tree. For instance, in the case where $V=V_T$ and $E=E_T$, no optimal nor near-optimal backup path can be found for $T$.

Incremental version

Multicast group members can join or leave a multicast group at all time, making multicast groups and trees dynamic. When the topology of a tree is modified, it is possible to avoid rerunning all of Algorithm 1 to compute a new backup path. We assume here that a backup path has been established between two end nodes $A$ and $B$ for a tree $T$ with Algorithm 1. We propose Algorithm 3 to handle topological modifications in a multicast routing tree $T$.

Figure 3.6: Tree topology modification after a node leaves or joins a multicast group. Links and nodes are removed or added downstream of node $D$ with regards to $S$ when node $C$ leaves or joins the group.

When a node $C$ leaves (or joins) a multicast group, a certain number of nodes and links are removed from (or added to) the multicast routing tree. Consider the path $P_{C, S}$ in tree $T$. Let $D$ be the first node on $P_{C, S}$ that is either a LER or has more than one child in $T$. Therefore, when $C$ leaves (or joins) the multicast group, all links and nodes except $D$ of the path $P_{C, D}$ are removed from (or added to) the tree as shown in Figure 3.6. We denote by $T'$ the modified tree and $tdrop'$ the modified metrics $tdrop$ of $T'$. If $tdrop_l$ is the value of metric $tdrop$ for link $l$ in $T$, then $tdrop'_l$ is the value of metric $tdrop$ for link $l$ in $T'$. According to the definition of $tdrop$, if a topology modification occurs downstream of $D$ with regards to $S$, then the values of the metrics $tdrop$ for links upstream of $D$ with regards to $S$ only are changed.

Algorithm 3 proceeds as follows. First, metrics $tdrop$ are recomputed for links on the path between nodes $D$ and $S$ in lines 1 to 3. Then, in lines 4 to 6, the metrics $R_d$ are updated for all pairs of nodes of tree $T'$. Let $R_d'(i, j)$ be the new value of the metric $R_d$ taken between nodes $i$ and $j$ in tree $T'$. It is possible to compute $R_d'(i, j)$ in $T'$ using the value of $R_d(i,j)$ in $T$ and therefore avoid doing all computations again. For instance, if Definition 3 is used to compute the metrics $R_d$ and $R_d'$, then, when $C$ leaves the group:

$R_d(i,j)$	=	$\sum\limits_{k \in E_T \setminus E_{PP_{i, j}}}{f_k tdrop_k}$
	=	$\sum\limits_{k \in E_{P_{C, D}} \setminus E_{PP_{i, j}}}{f_k tdrop_k}$
		+ $\sum\limits_{k \in E_{P_{D, S}} \setminus E_{PP_{i, j}}}{f_k tdrop_k}$
		+ $\sum\limits_{k \in E_T \setminus (E_{PP_{i, j}} \cup E_{P_{C, D}} \cup E_{P_{D, S}})}{f_k tdrop_k}$.

Since all nodes of $P_{C, D}$ are removed from the tree when $C$ leaves the group, neither $i$ nor $j$ can be between $C$ and $D$. Therefore:

$$\sum\limits_{k \in E_{P_{C, D}} \setminus E_{PP_{i, j}}}{f_k tdrop_k}=\sum\limits_{k \in E_{P_{C, D}}}{f_k tdrop_k}.$$

If we call $l$ the first link on the path from $D$ to $C$, then the expression above can be further simplified:

$$\sum\limits_{k \in E_{P_{C, D}}}{f_k tdrop_k}=adrop_l$$

and thus:

$R_d(i,j)$	=	$adrop_l$
		+ $\sum\limits_{k \in E_{P_{D, S}} \setminus E_{PP_{i, j}}}{f_k tdrop_k}$
		+ $\sum\limits_{k \in E_T \setminus (E_{PP_{i, j}} \cup E_{P_{C, D}} \cup E_{P_{D, S}})}{f_k tdrop_k}$.

Furthermore:

$R_d'(i, j)$	=	$\sum\limits_{k \in E_{T'} \setminus E_{PP_{i, j}}}{f_k tdrop'_k}$
	=	$\sum\limits_{k \in E_{P_{C, D}} \setminus E_{PP_{i, j}}}{f_k tdrop'_k}$
		+ $\sum\limits_{k \in E_{P_{D, S}} \setminus E_{PP_{i, j}}}{f_k tdrop'_k}$
		+ $\sum\limits_{k \in E_{T'} \setminus (E_{PP_{i, j}} \cup E_{P_{C, D}} \cup E_{P_{D, S}})}{f_k tdrop'_k}$
	=	$0$
		+ $\sum\limits_{k \in E_{P_{D, S}} \setminus E_{PP_{i, j}}}{f_k tdrop'_k}$
		+ $\sum\limits_{k \in E_{T'} \setminus (E_{PP_{i, j}} \cup E_{P_{D, S}})}{f_k tdrop_k}.$

Consequently:

$$R_d'(i, j) = R_d(i, j) - adrop_l + \sum\limits_{k \in (E_{P_{D, S}} \setminus E_{PP_{i, j}})}{f_k(tdrop'_k-tdrop_k)}.$$ (3)

Similar expressions are available in the case where $C$ joins a group. Therefore, instead of completely recomputing all metrics $R_d'$, it is possible to compute the new metrics $R_d'$ by substracting from the old metrics $R_d$ a value of the metric $adrop$ and adding products $f_k(tdrop'_k-tdrop_k)$ for links $k$ of a path of a tree. When all metrics $R_d$ are updated, a backup path is computed in lines 7 to 8 using a shortest path algorithm between the two nodes of the pair which maximizes the set of all metrics $R_d$ as in Algorithm 1.

Algorithm 3 is able to handle the modification of a multicast routing tree incurred by any leaving or joining node. In the case where a node is leaving the multicast group, and where this node is not an end node of the backup path computed for the tree topology prior to the modification, a trivial alternative to Algorithm 3 is available to handle the modification. This alternative merely consists in leaving the formerly computed backup path unchanged. Obviously, the unchanged backup path is not guaranteed to be optimal anymore, but no further computation is required to update the backup path. Therefore, to reduce the amount of computations required to update a backup path on a tree topology change, it is possible to set a threshold on the number of modifications of the multicast routing tree and not update the backup path until this threshold is reached. Then, Algorithm 3 can be used to recompute the backup path.