Next: MPLS Multicast Fast Reroute Up: A multicast routing tree Previous: Maximization of the resilience   Contents

Subsections

Complexity analysis

In this section, we first present a fast computation method for the metric based on an expression for derived from its definition, and methods to compute metrics and . Second, we give a general expression for the complexity of Algorithms 1, 2 and 3. Then, we give a complexity analysis in both the average case and worst case of a tree embedded in a network for all three algorithms.

Computation of the metrics

Algorithm 1 is articulated around the computation of several metrics. In line 6 of Algorithm 1, metric is computed between two nodes of . It is possible to compute between two nodes with the definition given in Section 3.1. In Claim 3 we derive a new expression for which makes use of the metrics. Computing the metrics for all links of the tree and then computing a value for between two nodes in the tree is faster than computing using the definition. We postpone the discussion on the gain in time complexity incurred by this method until Section 3.3.3.

Claim 3   Let and . Then
 (4)

Proof:
We prove Claim 3 using a partitioning of . Let . We assume that a backup path has been established between nodes and . A partitioning of is with:

Let . By definition of , therefore a partitioning of is as shown in Figure 3.7. According to the definition of :

Thus, using the partitioning of :

 = + + = + +

When injecting the definition of in the last line, the equation becomes:

The computation method for we have presented requires the knowledge of the metrics and , and computations of Least Common Ancestors. Each of the metrics and can be computed for all links of prior to any evaluation of (lines 1 to 3 in Algorithm 1) with the following recursive relations:

for and:

for .

In [33] the authors show that it is possible to determine a Least Common Ancestor for any pair of nodes in a tree in constant time after a linear preprocessing of . This tree preprocessing is performed in line 4 of Algorithm 1.

General case

We now analyze the time complexity of Algorithms 1, 2 and 3 in the general case. Let be the number of vertices of the graph , be the number of nodes of the tree . The number of links in is . Let be the number of leaves of the tree.

Consider Algorithm 1. In lines 1 to 3, the metrics and are computed for every link of . Computing each metric for all links of the tree can be performed in linear time with the recursive formula given in Section 3.3.1. Therefore, the time complexity of lines 1 to 3 is .

In line 4, tree is preprocessed so as to speed up further LCA computations. After the tree preprocessing, it is possible to determine the LCA of any pair of nodes in constant time. A linear tree preprocessing algorithm is proposed in [33], hence a time complexity of for line 4.

Last, line 9 computes a backup path between two vertices in a graph of edges. Classic Dijkstra's shortest path algorithm [24] solves this problem in time .

Overall, the time complexity of Algorithm 1 is:

Since and , an upper bound for the complexity of Algorithm 1 is .

Now consider Algorithm 2. Lines 1 to 7 of Algorithms 1 and 2 are identical. In line 8, metric is determined for nodes, then the set of all these metrics is sorted. Since computing a metric takes time and sorting a set of size takes time , the time complexity of line 8 of Algorithm 2 is . In lines 9 to 13, a shortest path is computed for up to pairs of nodes, thus the time complexity of lines 9 to 13 is . Overall the time complexity of Algorithm 2 is:

Since , an upper bound for the complexity of Algorithm 2 is .

Finally, consider Algorithm 3. The maximum length for a path in a tree of nodes is thus the time complexity of lines 1 to 3 is . In lines 4 to 6, metrics are updated. Updating a single metric has a time complexity of hence a time complexity of for lines 4 to 6. In line 7, the minimum of a set of is determined in time and in line 8 a shortest path is computed in time . Therefore, the complexity of Algorithm 3 is:

Since , an upper bound for the complexity of Algorithm 3 is . Although Algorithms 1 and 3 have the same asymptotic time complexity, Algorithm 3 is faster than Algorithm 1 as Algorithm 3 most of the metric computations do need not to be recomputed and updating for a pair of node is requires fewer operations.

In the next sections, we show that the time complexity of Algorithm 1 in the average case is and give a worst case example where the upper bound is reached. We present similar results for Algorithms 2 and 3.

Average case

The height of a tree is the maximum number of edges on the path between the root of the tree and any leaf. We consider as the average case a tree with height , where the number of children of any node of the tree is bounded by a constant and where the number of leaves is bounded by ( ).

First, consider Algorithm 1. The computations performed in lines 1 to 4 are the same as in the general case, hence a complexity of . In lines 5 to 8, metric must be computed between each of the leaves and all other nodes. Therefore metrics must be computed. Suppose we use the definition to compute . Computing involves the addition of products between and metrics for all links of the tree except those on the protected path between and another leaf. Therefore, products have to be added hence a time complexity of to compute each of the metrics , and a complexity of for lines 5 to 8 of Algorithm 1. This is the same result as in the general case.

Now suppose that we use the method presented in Section 3.3.1 to compute between two nodes and of . First, part (1) of Equation 3.2 requires the addition of at most terms for each vertex on the protected path for which is computed. A protected path consists of at most vertices, thus complexity of Term (1) is . Second, the number of links on the path from to is at most . Determining an LCA is done in constant time as previously stated therefore part (2) of Equation 3.2 has a complexity of . Third, Term (3) involves the addition of at most metrics for each link of the path between and , hence a time complexity of for Term (3) of Equation 3.2. Overall, the time complexity of the computation of all metrics performed by lines 5 to 8 of Algorithm 1 is , instead of if the definition of was used.

The last step of Algorithm 1 computes a shortest path between two nodes in a graph with edges. The classic Dijkstra's shortest path Algorithm [24] solves the problem in time .

All in all, the complexity of Algorithm 1 is:

Note that if we used the definition of to compute all metrics in lines 5 to 8 then the complexity of Algorithm 1 would be , which justifies a posteriori why we introduced an alternate method to compute in Section 3.3.1.

Now consider Algorithm 2. We have shown above that the time complexity of lines 1 to 7 is . Computing and sorting the set of all metrics in line 8 takes time . Computing all possible backup paths takes time , hence the time complexity of Algorithm 2 in the general case:

Last, consider Algorithm 3. The length of the path between and is thus computing metrics in lines 1 to 3 is done in time . The size of the set is therefore updating a metric takes time . Updating all the metrics takes time (lines 4 to 6). In line 7, determining a minimum of values takes time . In line 8, a shortest path is computed in time . The time complexity of Algorithm 3 in the average case is:

All three Algorithms 1, 2 and 3 are faster in the average case than in the general case. In the next section, we determine the worst case for each algorithm.

Worst case

Consider Algorithm 1. The general expression for its time complexity is . The upper bound can be reached only when and . Consider the graph and the tree depicted in Figure 3.8. Suppose that all links from the tree have the same relative failure probability and the same weight . Tree has links and leaves.

Lines 1 to 4 take time to complete. Then, metrics must be computed to determine and . Computing each metric takes time . Indeed, in this case the protected path between a leaf and any node is reduced to . Term (1) of Equation 3.2 is the sum of the metrics for all links of the tree except the two links of the protected path, hence a complexity for Term (1). Since , Terms (2) and (3) of Equation 3.2 are equal to zero. In this case, using the alternate method to compute each metric is as complex as using the definition of . Complexity of lines 5 to 8 is . Determining the shortest path in this graph is performed in time .

In summary, in this case the complexity of Algorithm 1 is . We have shown that was an upper bound for the complexity of Algorithm 1, and presented a case where this bound was attained.

We now show that the upper bound can be attained for Algorithm 2. The general expression of the time complexity is . Consider the network and the tree depicted in Figure 3.9. The tree is disconnected from the other nodes of the network and therefore Algorithm 2 computes a backup path between all possible pairs of nodes of the tree before failing to find a backup path. Since , the time complexity of Algorithm 2 in this particular case is .

Last, we show that the upper bound can be attained for Algorithm 3. Consider Figure 3.10 where node leaves the group. The path between and is such that and is located in the middle of this path. After leaves the group we have and . Then, metrics must be recomputed. The path between and has links thus for any two nodes and such that the size of the set is . There are such pairs of nodes. According to Equation 3.1, updating one metric takes time . Therefore, updating all metrics takes time . In this case, the time complexity of Algorithm 3 is .

Next: MPLS Multicast Fast Reroute Up: A multicast routing tree Previous: Maximization of the resilience   Contents
Yvan Pointurier 2002-08-11