Next: Complexity analysis Up: A multicast routing tree Previous: Problem modeling   Contents

Subsections

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 . Our algorithm (see Algorithm 1) proceeds as follows. We first compute the and 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 . Then, we compute in turn for all pairs of nodes constituted by a leaf of the tree and another node of the tree. We denote by the pair of nodes of the tree which minimizes the set of the metrics previously computed. A shortest path algorithm computes the backup path between and . If the shortest path algorithm fails to find a backup path, then no backup path achieves optimal path protection in tree .

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

Proof:

Suppose that metrics and 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 is a leaf of . Suppose the end nodes and of a backup path that minimizes are known and that, by contradiction, is not a leaf of .

Let (see Figure 3.5). Then:

and:

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

then:

therefore the pair of nodes does not minimize , which contradicts the hypothesis. Therefore, at least one of the end nodes and of the backup path which maximizes the resilience of is a leaf. We call the end node that is a leaf. The other end node has no such restriction and may or may not be a leaf. By construction of nodes and in lines 5 to 8, a backup path between and minimizes and thus maximizes the resilience of the tree. The backup path is computed in line 9 using a shortest path algorithm between and over the graph so that the backup path and the tree are node and edge disjoint.

Definition 5   A near-optimal backup path is a backup path such that:

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 and are computed for all links of the tree and is preprocessed to speed up LCA computations in lines 1 to 4.

For any pair of nodes , the value of the metric 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 nodes, there is a total number of possible pairs of end nodes for a backup path.

In lines 5 to 7 of Algorithm 2, metrics are computed for all 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 , 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 and , no optimal nor near-optimal backup path can be found for .

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 and for a tree with Algorithm 1. We propose Algorithm 3 to handle topological modifications in a multicast routing tree .

When a node 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 in tree . Let be the first node on that is either a LER or has more than one child in . Therefore, when leaves (or joins) the multicast group, all links and nodes except of the path are removed from (or added to) the tree as shown in Figure 3.6. We denote by the modified tree and the modified metrics of . If is the value of metric for link in , then is the value of metric for link in . According to the definition of , if a topology modification occurs downstream of with regards to , then the values of the metrics for links upstream of with regards to only are changed.

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

 = = + + .

Since all nodes of are removed from the tree when leaves the group, neither nor can be between and . Therefore:

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

and thus:

 = + + .

Furthermore:

 = = + + = + +

Consequently:

 (3)

Similar expressions are available in the case where joins a group. Therefore, instead of completely recomputing all metrics , it is possible to compute the new metrics by substracting from the old metrics a value of the metric and adding products for links of a path of a tree. When all metrics 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 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.

Next: Complexity analysis Up: A multicast routing tree Previous: Problem modeling   Contents
Yvan Pointurier 2002-08-11