Complexity analysis

In this section, we first present a fast computation method for the metric $R_d$ based on an expression for $R_d$ derived from its definition, and methods to compute metrics $tdrop$ and $adrop$. 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 $R_d$ is computed between two nodes of $T$. It is possible to compute $R_d$ between two nodes with the definition given in Section 3.1. In Claim 3 we derive a new expression for $R_d$ which makes use of the $adrop$ metrics. Computing the $adrop$ metrics for all links of the tree and then computing a value for $R_d$ between two nodes in the tree is faster than computing $R_d$ using the definition. We postpone the discussion on the gain in time complexity incurred by this method until Section 3.3.3.

Figure 3.7: Computation of $R_d(A, B)$.

Claim 3   Let $A, B \in V_T$ and $S'=S'_{A, B}$. Then

$$R_d(A, B)=\underbrace{\sum\limits_{i \in V_{PP_{A, B}}}{\sum... ...dren_i \atop j \notin V_{P_{S, S'}}}{adrop_{(i, j)}}}}_{(3)}.$$ (4)

Proof:
We prove Claim 3 using a partitioning of $E_T$. Let $A, B \in V_T$. We assume that a backup path has been established between nodes $A$ and $B$. A partitioning of $E_T$ is $(E_{T}^{1}, E_{T}^{2}, E_{T}^{3})$ with:

$$\left\{ \begin{array}{lcl} E_{T}^{1} &=& E_{sub_T(S')}, \ ... ...nt_l \neq S' \wedge l \notin E_{P_{S, S'}}. \end{array}\right.$$

Let $E=E_T \setminus E_{PP_{A, B}}$. By definition of $S'$, $E_{PP_{A, B}} \subset E_{T}^{1}$ therefore a partitioning of $E$ is $(E_{T}^{1} \setminus E_{PP_{A, B}}, E_{T}^{2}, E_{T}^{3})$ as shown in Figure 3.7. According to the definition of $R_d$:

$$R_d(A, B)=\sum\limits_{k \in E}{f_k tdrop_k}.$$

Thus, using the partitioning of $E$:

$R_d(A, B)$	=	$\sum\limits_{k \in E_{T}^{1} \setminus E_{PP_{A, B}}}{f_k tdrop_k}$
		+ $\sum\limits_{k \in E_{T}^{2}}{f_k tdrop_k}$
		+ $\sum\limits_{k \in E_{T}^{3}}{f_k tdrop_k}$
	=	$\sum\limits_{i \in V_{PP_{A, B}}}{\sum\limits_{j \in children_i \atop j \notin V_{PP_{A, B}}}{\sum\limits_{l \in lsub_T(i, j)}{f_l tdrop_l}}}$
		+ $\sum\limits_{k \in E_{P_{S, S'}}}{f_k tdrop_k}$
		+ $\sum\limits_{i \in V_{P_{S, S'}} \atop i \neq S'}{\sum\limits_{j \in children_i \atop j \notin V_{P_{S, S'}}}{\sum\limits_{l \in lsub_T(i, j)}{f_l tdrop_l}}}$

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

$$R_d(A, B)= \sum\limits_{i \in V_{PP_{A, B}}}{\sum\limits_{j ... ...\in children_i \atop j \notin V_{P_{S, S'}}}{adrop_{(i, j)}}}.$$

$\Box$

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

$$tdrop_l=\left\{ \begin{array}{l@{\quad}l}w_l & \mbox{if the n... ..._l}{tdrop_i}\right)+w_l & \mbox{otherwise.} \end{array} \right.$$

for $tdrop$ and:

$$adrop_l=\left\{\begin{array}{l@{\quad}l} f_l tdrop_l & \mbox... ...op_i}\right)+f_l tdrop_l & \mbox{otherwise.}\end{array}\right.$$

for $adrop$.

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 $T$. 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 $N=\vert V\vert$ be the number of vertices of the graph $G$, $n=\vert V_T\vert$ be the number of nodes of the tree $T$. The number of links in $T$ is $\vert E_T\vert=n-1$. Let $\ell=\vert L_T\vert$ be the number of leaves of the tree.

Consider Algorithm 1. In lines 1 to 3, the metrics $tdrop$ and $adrop$ are computed for every link of $T$. 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 $O(n)$.

In line 4, tree $T$ 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 $O(n)$ for line 4.

Nodes $A$ and $B$ are determined in lines 5 to 8 by computing the metric $R_d$ between a leaf and another node. Thus, $O(\ell n)$ metrics $R_d$ have to be computed and compared. Computing $R_d$ with Definition 3 involves the addition of products between link failure rate weights and $tdrop$ metrics for all links of the tree except on the path between two nodes, hence a complexity of $O(n)$. The complexity of lines 5 to 8 is thus $O(\ell n^2)$ if $R_d$ is computed with its definition. If $R_d$ is computed with the expression from Equation 3.2, then three terms must be added. Term (1) involves to determine the LCA $S'$ of a pair of nodes and the addition of metrics $adrop$ for links downstream of vertices of the protected path between the two nodes for which $R_d$ is computed. Determining a LCA is performed in constant time as already stated and at most all $n$ metrics $adrop$ are added in Term (1), hence a time complexity of $O(n)$ to compute Term (1) of Equation 3.2. Term (2) involves the addition of products between $f$ and $tdrop$ metrics for all links on the path between $S'$ and root $S$. Since a path can be up to $n$ links long, the time complexity for computing Term (2) of Equation 3.2 is $O(n)$. Same as Term (1), Term (3) requires the addition of up to $n$ terms hence a time complexity of $O(n)$. In summary, computing a single metric $R_d$ between two leaves can be done in time $O(n)$ with either the definition or the method previously introduced, and the time complexity of lines 5 to 8 is also $O(\ell n^2)$ in the general case.

Last, line 9 computes a backup path between two vertices in a graph of $N-n$ edges. Classic Dijkstra's shortest path algorithm [24] solves this problem in time $O((N-n)\log(N-n))$.

Overall, the time complexity of Algorithm 1 is:

$$O(n)+O(n)+O(\ell n^2)+O((N-n)\log(N-n))=O(\ell n^2+(N-n)\log(N-n)).$$

Since $\ell=O(N)$ and $n=O(N)$, an upper bound for the complexity of Algorithm 1 is $O(N^3)$.

Now consider Algorithm 2. Lines 1 to 7 of Algorithms 1 and 2 are identical. In line 8, metric $R_d$ is determined for $N_{pairs}=O(n^2)$ nodes, then the set of all these metrics is sorted. Since computing a metric $R_d$ takes time $O(n)$ and sorting a set of size $n^2$ takes time $O(n^2 \log(n^2))=O(n^2 \log(n))$, the time complexity of line 8 of Algorithm 2 is $O(n^2 n+n^2 \log(n))=O(n^3)$. In lines 9 to 13, a shortest path is computed for up to $N_{pairs}$ pairs of nodes, thus the time complexity of lines 9 to 13 is $O(n^2(N-n)\log(N-n))$. Overall the time complexity of Algorithm 2 is:

$$O(n)+O(n)+O(n^3)+O(n^2(N-n)\log(N-n))=O(n^3+n^2(N-n)\log(N-n)).$$

Since $n=O(N)$, an upper bound for the complexity of Algorithm 2 is $O(N^3\log(N))$.

Finally, consider Algorithm 3. The maximum length for a path in a tree of $n$ nodes is $n$ thus the time complexity of lines 1 to 3 is $O(n)$. In lines 4 to 6, $\ell n$ metrics $R_d$ are updated. Updating a single metric $R_d$ has a time complexity of $O(n)$ hence a time complexity of $O(\ell n^2)$ for lines 4 to 6. In line 7, the minimum of a set of $N_{pairs}$ is determined in time $O(n^2)$ and in line 8 a shortest path is computed in time $O((N-n)\log(N-n))$. Therefore, the complexity of Algorithm 3 is:

$$O(n)+O(\ell n^2)+O(n^2)+O((N-n)\log(N-n))=O(\ell n^2+(N-n)\log(N-n)).$$

Since $n=O(N)$, an upper bound for the complexity of Algorithm 3 is $O(N^3)$. 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 $R_d$ 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 $O(N^2\log(N))$ and give a worst case example where the upper bound $O(N^3)$ 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 $S$ of the tree and any leaf. We consider as the average case a tree $T$ with height $\log{n}$, where the number of children of any node of the tree is bounded by a constant $k$ and where the number of leaves is bounded by $n$ ( $\ell=\Theta(n)$).

First, consider Algorithm 1. The computations performed in lines 1 to 4 are the same as in the general case, hence a complexity of $O(n)$. In lines 5 to 8, metric $R_d$ must be computed between each of the $\ell$ leaves and all other nodes. Therefore $O(\ell n)=O(n^2)$ metrics $R_d$ must be computed. Suppose we use the definition to compute $R_d$. Computing $R_d$ involves the addition of products between $f$ and $tdrop$ metrics for all $n$ links of the tree except those on the protected path between $A$ and another leaf. Therefore, $n-2\log(n)$ products have to be added hence a time complexity of $O(n-2\log(n))=O(n)$ to compute each of the $n-1$ metrics $R_d$, and a complexity of $O(n^3)$ 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 $R_d$ between two nodes $Y$ and $Z$ of $T$. First, part (1) of Equation 3.2 requires the addition of at most $k$ terms for each vertex on the protected path $PP_{Y, Z}$ for which $R_d$ is computed. A protected path consists of at most $2\log(n)$ vertices, thus complexity of Term (1) is $O(2k\log(n))=O(\log(n))$. Second, the number of links on the path from $S'_{A, B}$ to $S$ is at most $\log(n)$. Determining an LCA $S'$ is done in constant time as previously stated therefore part (2) of Equation 3.2 has a complexity of $O(\log(n))$. Third, Term (3) involves the addition of at most $k$ metrics for each link of the path between $S$ and $S'$, hence a time complexity of $O(k \log(n))=O(\log(n))$ for Term (3) of Equation 3.2. Overall, the time complexity of the computation of all metrics $R_d$ performed by lines 5 to 8 of Algorithm 1 is $O(n^2) (O(\log(n))+O(\log(n))+O(\log(n)))=O(n^2 \log(n))$, instead of $O(n^3)$ if the definition of $R_d$ was used.

The last step of Algorithm 1 computes a shortest path between two nodes in a graph with $(N-n)$ edges. The classic Dijkstra's shortest path Algorithm [24] solves the problem in time $O((N-n)\log(N-n))$.

All in all, the complexity of Algorithm 1 is:

$$O(n)+O(n)+O(n^2 \log(n))+O((N-n)\log(N-n))=O(n^2 \log(n)+(N-n)\log(N-n)).$$

Note that if we used the definition of $R_d$ to compute all metrics $R_d$ in lines 5 to 8 then the complexity of Algorithm 1 would be $O(n^3+(N-n)\log(N-n))$, which justifies a posteriori why we introduced an alternate method to compute $R_d$ in Section 3.3.1.

Now consider Algorithm 2. We have shown above that the time complexity of lines 1 to 7 is $O(n^2\log(n))$. Computing and sorting the set of all $R_d$ metrics in line 8 takes time $O(n^2\log(n))$. Computing all possible backup paths takes time $O(n^2(N-n)\log(N-n))$, hence the time complexity of Algorithm 2 in the general case:

$$O(n^2\log(n) + n^2 \log(n) + n^2(N-n)\log(N-n)) = O(n^2\log(n)+n^2(N-n)\log(N-n)).$$

Last, consider Algorithm 3. The length of the path between $D$ and $S$ is $\log(n)$ thus computing metrics $tdrop'$ in lines 1 to 3 is done in time $O(\log(n))$. The size of the set $E_{P_{D, S}} \setminus E_{PP_{i, j}}$ is $\log(n)$ therefore updating a metric $R_d$ takes time $O(\log(n))$. Updating all the metrics $R_d$ takes time $O(n^2\log(n))$ (lines 4 to 6). In line 7, determining a minimum of $N_{pairs}$ values takes time $O(n^2)$. In line 8, a shortest path is computed in time $O((N-n)\log(N-n))$. The time complexity of Algorithm 3 in the average case is:

$$O(\log(n)) + O(n^2 \log(n)) + O(n^2) + O((N-n)\log(N-n)) = O(n^2 \log(n) + (N-n)\log(N-n)).$$

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

Figure 3.8: Worst case for Algorithm 1. With this topology, the complexity of Algorithm 1 reaches the higher bound $O(N^3)$.

Consider Algorithm 1. The general expression for its time complexity is $O(\ell n^2+(N-n)\log(N-n))$. The upper bound $O(N^3)$ can be reached only when $\ell=\Theta(N)$ and $n=\Theta(N)$. Consider the graph $G^w=(E^w, V^w)$ and the tree $T^w=(E_T^w, V_T^w)$ depicted in Figure 3.8. Suppose that all links from the tree have the same relative failure probability and the same weight $w=1$. Tree $T^w$ has $n=\frac{N+1}{2}=\Theta(N)$ links and $\ell=\frac{N-1}{2}=\Theta(N)$ leaves.

Lines 1 to 4 take time $O(n)=O(N)$ to complete. Then, $\ell n=\frac{N^2-1}{4}=O(N^2)$ metrics $R_d$ must be computed to determine $A$ and $B$. Computing each metric $R_d$ takes time $O(N)$. Indeed, in this case the protected path between a leaf $Y \in L_T$ and any node $Z \in V_T$ is reduced to $PP_{A, Z}=(Y, S, Z)$. Term (1) of Equation 3.2 is the sum of the metrics $adrop$ for all links of the tree except the two links of the protected path, hence a complexity $O(N-2)=O(N)$ for Term (1). Since $S=S'$, Terms (2) and (3) of Equation 3.2 are equal to zero. In this case, using the alternate method to compute each metric $R_d$ is as complex as using the definition of $R_d$. Complexity of lines 5 to 8 is $O(N^2 N)=O(N^3)$. Determining the shortest path in this graph is performed in time $O(N\log(N))$.

In summary, in this case the complexity of Algorithm 1 is $O(N^3)$. We have shown that $N^3$ was an upper bound for the complexity of Algorithm 1, and presented a case where this bound was attained.

Figure 3.9: Worst case for Algorithm 2. With this topology, the complexity of Algorithm 2 reaches the higher bound $O(N^3\log(N))$.

We now show that the upper bound $O(N^3\log(N))$ can be attained for Algorithm 2. The general expression of the time complexity is $O(n^3+n^2(N-n)\log(N-n))$. 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 $n=\Theta(N)$, the time complexity of Algorithm 2 in this particular case is $O(N^3\log(N))$.

Figure 3.10: Worst case for Algorithm 3. With this topology, the complexity of Algorithm 3 reaches the higher bound $O(N^3)$.

Last, we show that the upper bound $O(N^3)$ can be attained for Algorithm 3. Consider Figure 3.10 where node $C$ leaves the group. The path between $S$ and $C$ is such that $\vert E_{P_{S,C}}\vert=\Theta(n)$ and $D$ is located in the middle of this path. After $C$ leaves the group we have $\ell=\Theta(N)$ and $n=\Theta(N)$. Then, $\ell n = \Theta(N^2)$ metrics $R_d$ must be recomputed. The path between $D$ and $S$ has $\Theta(N)$ links thus for any two nodes $i$ and $j$ such that $i, j \notin E_{P_{D, S}}$ the size of the set $E_{P_{D, S}} \setminus E_{PP_{i, j}}$ is $\Theta(N)$. There are $\Theta(N^2)$ such pairs of nodes. According to Equation 3.1, updating one metric $R_d$ takes time $O(n)=O(N)$. Therefore, updating all metrics $R_d$ takes time $O(N^3)$. In this case, the time complexity of Algorithm 3 is $O(N^3)$.