Problem modeling

Figure 3.1: Network and multicast group model.

The network considered in this chapter consists of a set of routers which can be either Label Switching Routers (LSRs) or Label Edge Routers (LERs). The modeling process is shown in Figure 3.1 for an example. Routers are connected by point-to-point links. End-hosts are attached to LERs of the MPLS network either directly or via other networks. Links between an LER of the considered network and an end-host or a router of another network are called access links. A multicast group is a set of hosts which communicate together. Data that is sent by a multicast group member to a multicast group is received by all other group members.

In this section, we model the network as a graph $G=(V,E)$. The set $V$ of the vertices of the graph contains the routers (LSRs and LERs) of the network. The set $E$ of the edges of the graph contains the links of the network. Set $E$ does not contain the access links. All links are assumed to be bidirectional.

Further, we assume that a multicast communication has been established over the network. Let $T=(V_T, E_T)$ be the undirected link weighted tree which maps the multicast routing tree of the multicast communication. The multicast routing trees can be organized as a shortest path tree or a core based tree. In the case where the multicast routing tree is a core based tree, we assume that the core is not a LER. We denote by $S$ the source of $T$ if $T$ is a shortest path tree or the core of $T$ if $T$ is a core based tree. The set $V_T$ of the nodes of the tree contains the routers of the multicast routing tree. The set $E_T$ of the links of the tree contains the links of the multicast routing tree. Tree $T$ is embedded in graph $G$ and therefore $V_T \subset V$ and $E_T \subset E$.

In a tree, the children of a node $i$ are the nodes immediately downstream of $i$ with regards to $S$ and the parent of $i$ is the node immediately upstream of $i$ with regards to $S$. Let $child_i \subset V_T$ be the set of the children of node $i \in V_T$ and $parent_i \in V_T$ be the parent of node $i$. Similarly, given a link $l$, let $down_l \subset E_T$ be the set of the links immediately downstream of link $l$ with regards to $S$. Let $sub_T(i)=(V_{sub_T(i)}, E_{sub_T(i)})$ be the subtree of $T$ with regards to $S$ and which root is node $i$. Let $lsub_T(l)=(V_{lsub_T(l)}, E_{lsub_T(l)})$ be the subgraph of $T$ which contains node $i$ upstream of $l$ with regards to $S$, link $l$, and the subtree rooted at the node $j$ downstream of $l$ with regards to $S$. By definition, $lsub_T(l)=(\{i\} \cup V_{sub_T(j)}, \{l\} \cup E_{sub_T(j)})$ is a tree.

We define the weight $w_{T, l}$ of a link $l \in E_T$ as follows. Consider a node $i \in V_T$ and link $up_i \in E_T$ immediately upstream of $i$ with regards to $S$. If $i$ is a LER, $w_{T, up_i}$ is the number of multicast group members that send or receive multicast traffic via an access link attached to node $i$. If $i$ is a LSR, then let $w_{T, up_i} = 0$. LERs of the MPLS network can learn the number of multicast hosts accessible via each access link by a signaling protocol like IGMP v3 [16]. If the information on the number of multicast hosts accessible via each access link is not available in the MPLS network, we set to ``1'' the weight of the link upstream of each LER which sends or receives multicast traffic for the considered multicast group via at least one of its access links. In summary, link weights are assumed to be known at multicast routing tree establishment time. We call a receiver a node immediately downstream of a link $l$ with regards to $S$ such that $w_l \neq 0$. Receivers are LERs which transmit multicast traffic to or from multicast group members over an access link. A leaf of a tree $T$ is a node $i \in V_T$ such that $child_i = \emptyset$. Let $L_T \subset V_T$ be the set of the leaves of $T$. Note that all leaves are receivers, but a receiver is not necessarily a leaf. Indeed, a LER that forwards traffic from the tree over access links can also forward the same traffic to LSRs or other LERs of the tree before this traffic reaches an access link. In practice, such a LER pops labels before sending packets over the access link and swaps labels before sending packets to other routers of the MPLS domain. We introduced this capability as mixed L2/L3 forwarding in Section 1.3.4. In Figure 3.1 for instance, LER 2 performs mixed L2/L3 forwarding. If only one host is attached to LER 2 via the access link of LER 2, then the weight of the link between LER 2 and LSR 2 is ``1'' while LER 2 is not a leaf for tree $T$.

Figure 3.2: Link failure rate weight. We consider that the failure of link $CD$ when $f_{CD}$=1 and when two multicast hosts are attached to $D$ is equivalent to the failure of link $CD$ when $f_{CD}$=2 and when one multicast host is attached to $D$.

We assume that the only possible failure for a link is a link cut. When a link $l$ fails, it is removed from $E$. The failure rate $F_l$ for a link $l \in E$ is the average number of failures per unit of time for link $l$. The Mean Time Between Failures (MTBF) of a link is the time that passes before the link fails. If the Mean Time Between Failures $MTBF_l$ of a link $l$ is known, then $F_l=\frac{1}{MTBF_l}$. We assume that the failure rate is known for each link of the network and that link failure rates are low enough to consider that at most one link fails at any given time. We associate a positive link failure rate weight $f_l$ to each link $l \in E$ which is proportional to the link failure rate, relatively to the failure rates of the other links of the network. For instance, if the network is constituted by two different kinds of links, and if links of the first kind fail twice as often as links of the second kind, then $f=2$ for the links of the first kind and $f=1$ for the links of the second kind. In the case where failure rate information is not available, we assume that the failure rate is the same for every link in the network, i.e.:

$$\forall l \in E, f_l = 1.$$

If $l \in E_T$ fails, then tree $T$ is split in two trees $T_1$ and $T_2$. Let $T_1$ be the tree which contains $S$ and let $T_2$ be the other tree. All multicast hosts attached to a LER of $T_2$ are dropped from the multicast communication, and all LERs of $T_2$ are dropped from tree $T$. If LER $i$ is dropped from $T$ then $w_{T, up_i}$ multicast hosts are dropped from the multicast communication. In this thesis, we make the following design choice. We consider that dropping twice a given number of hosts if a link with a given failure rate fails (Figure 3.2(a)) is equivalent to dropping the given number of hosts if a link with twice the failure rate fails (Figure 3.2(b)).

A path $P_{N_1, N_p}$ between two vertices $N_1$ and $N_p$ of graph $G$ is a sequence of vertices $(N_1, N_2, \dots, N_p)$ such that $\forall i \in [1..p-1], (N_i, N_{i+1}) \in E$ and $\forall i\neq j, V_i \neq V_j$. We denote by $V_{P_{N_1, N_p}}=\left\{N_i \vert i \in [1..p]\right\}$ the set of the nodes of $P_{N_1, N_p}$ and by $E_{P_{N_1, N_p}}=\left\{(N_i, N_{i+1}) \vert i \in [1..p-1]\right\}$ the set of the links of $P_{N_1, N_p}$. In a tree $T=(V_T, E_T)$, there exists a unique path between any two nodes $A, B \in V_T$. Therefore, there exists a unique path $P_{S, A}$ between root $S$ and node $A$ on the one hand, and $P_{S, B}$ between $S$ and $B$ on the other hand. Let node $S'_{A, B}$ be the node $N_q \in V_T$ such that $P_{S, A}=(S, N_1, N_2, \dots, N_q, N_r, \dots, A)$, $P_{S, B}=(S, N_1, N_2, \dots, N_q, N_s, \dots, B)$ and $N_r \neq N_s$. Node $S'_{A, B}$ is called the Least Common Ancestor (LCA) of $A$ and $B$.

Definition 1   The Protected Path $PP_{i,j}$ is the unique path $(N_1, \dots, N_p)$ between nodes $i, j \in V_T$ such that:

$$N_1 = i, N_p = j \mbox{ and } (\forall i \in [1..p-1], N_i \in V_T \wedge (N_i, N_{i+1}) \in E_T).$$

Definition 2   A Backup Path $BP_{i,j}$ is a path $(N_1, \dots, N_p)$ between two nodes $i \in V_T$ and $j \in V_T$ such that:

$$N_1 = i, N_p = j \mbox{ and } (\forall i \in [2..p-1], N_i \i... ... } (\forall i \in [1..p-1] (N_i, N_{i+1}) \in E \setminus E_T).$$

While a protected path is unique, a backup path may not be unique for a given pair of nodes. Backup paths protect trees from link failures by providing path redundancy. A backup path and tree $T$ are link disjoint so that the failure of a link in the tree does not prevent the backup path to reroute traffic. Similarly, a backup path and tree $T$ are vertex disjoint so as to avoid any interference between non-rerouted traffic and rerouted traffic at any node of a backup path.

We now show that, given two nodes $i$ and $j$ of tree $T$, if a link of the protected path $PP_{i,j}$ fails then it is possible to reroute traffic through a backup path $BP_{i,j}$ without dropping any member of the multicast group. More formally, it is possible to transform a tree where a link has failed into a new tree $T'$ with the same total link weight by appending the backup path to the original tree.

Claim 1   Given a tree $T=(V_T, E_T)$, two nodes $i, j \in V_T$, the protected path $PP_{i,j}$, a backup path $BP_{i,j}$, and a link $b \in E_{PP_{i, j}}$, there exists a tree $T'=(V_{T'}, E_{T'})$ such that

1. $V_{T'}=V_T \cup V_{BP_{i, j}}$
2. $E_{T'}=\{E_T \cup E_{BP_{i, j}} \} \setminus \{b\}$
3. $\sum\limits_{l \in E_{T'}}{w_{T', l}}=\sum\limits_{l \in E_{T}}{w_{T, l}}$

Proof:

Let $T_1=(V_{T_1}, E_{T_1})$ and $T_2=(V_{T_2}, E_{T_2})$ be the two smaller trees that result from the removal of link $b$ in tree $T$. Trees $T$ and $T_1$ are rooted at node $S$. Assume without loss of generality that $j \in V_{T_1}$ and $i \in V_{T_2}$. Let $i$ be the root of tree $T_2$. Trees $T_1$ and $T_2$ are link and node disjoint therefore the graph $T'=(V_T \cup V_{BP_{i, j}}, \{E_T \cup E_{BP_{i, j}} \} \setminus \{b\})$ which results from merging $T_1$ and $T_2$ via backup path $BP_{i,j}$ is a tree, hence (1) and (2). Let $S$ be the root of $T'$. The sum $\sum\limits_{l \in E_{T}}{w_{T, l}}$ is the total number of multicast hosts attached to all LERs of $T$. Similarly, the sum $\sum\limits_{l \in E_{T'}}{w_{T', l}}$ is the total number of multicast hosts attached to all LERs of $T'$. Since $V_{T'}=V_T \cup V_{BP_{i, j}}=V_T \cup (V_{BP_{i, j}} \setminus \{i, j\})$ and no multicast host is attached to a vertex of $V_{BP_{i, j}} \setminus \{i, j\}$, the numbers of multicast hosts attached to any LER of $T$ and $T'$ are the same, hence (3). $\Box$

Figure 3.3: Protection of a tree from a link failure on the protected path with a backup path. When link $b$ fails, multicast traffic that was using tree $T$ is rerouted to use tree $T'$ so that no multicast group member is dropped.

On a link failure in tree $T$ rooted at $S$, $T$ is split into two trees $T_1$ and $T_2$ as described above and all receivers in $T_2$ are disconnected from $S$. If a backup path $BP_{i,j}$ is inserted in $T$ (see Figure 3.3(a)), then when any link $b$ from the protected path $PP_{i,j}$ fails a new tree $T'$ replaces $T$ to carry multicast traffic and no receiver is dropped (see Figure 3.3(b)), thus improving the resilience of the tree as defined in the previous section.

Figure 3.4: Weight $w$ and metrics $tdrop$ and $adrop$ for all links of a sample tree. In this example, we assume that all seven links of the tree have the same failure rate ( $\forall l\in E, f_l=1$) and that each receiver is attached to one multicast group member.

Let $tdrop_l$ be the number of hosts attached to receivers that are dropped from tree $T$ when link $l \in E_T$ fails and no backup path is set up. Since $E_{lsub_T(l)}$ is the set that contains at the same time link $l$ and all links in the subtree of $T$ rooted at the node immediately downstream of $l$ with regards to $S$, then, by definition of $tdrop_l$:

$$tdrop_l = \sum\limits_{k \in E_{lsub_T(l)}}{w_k}.$$

Similarly, we denote by $adrop_l$ the number of hosts attached to receivers that are dropped from the tree $T$ on the single failure of link $l$ or any link downstream of $l$ when no backup path is set up weighted by the link failure rates. By definition:

$$adrop_l = \sum\limits_{k \in E_{lsub_T(l)}}{f_k tdrop_k}.$$

In Figure 3.4, we give the values of $w$, $tdrop$ and $adrop$ for all links on an example. In the following, we use metric $tdrop$ to formally define the resilience of a tree, and metric $adrop$ to speed up resilience computations.

We now introduce a formal definition for the resilience of a tree. We have seen how a link failure partitions a tree $T$ into two trees $T_1$ and $T_2$. If a backup path $BP_{i,j}$ is set up in $T$, then according to Claim 1 it is possible to build a new tree $T'$ such that no receiver is dropped from the communication if any link from the protected path $PP_{i,j}$ fails. Therefore the weighted number of receivers dropped from a multicast communication using a tree protected by a backup path $BP_{i,j}$ on a single link failure is:

$$R_d(i, j) = R_d(j, i) = \sum\limits_{k \in E_T \atop k \notin E_{PP_{i, j}}}{f_k tdrop_k}.$$

Moreover, assuming that no backup path is set up in $T$, the number of hosts dropped from a multicast communication on an single link failure is:

$$R_t = \sum\limits_{k \in E_T}{{f_k tdrop_k}}.$$

Quantity $R_t$ is a constant that depends on the tree topology only whereas $R_d$ also depends on the end nodes $i$ and $j$ of the backup path $BP_{i,j}$. Quantity $R_t$ measures the impact of a link failure on a tree that is not protected by any backup path, while $R_d$ measures the impact of a link failure on a tree where a backup path is set. The difference between these two quantities is the number of hosts not dropped from the communication after traffic is rerouted over the backup path.

Definition 3   The resilience of a tree $T=(V_T, E_T)$ protected by a backup path between nodes $i,j \in V_T$ is defined as:

$$R(i, j)=R_t-R_d(i, j).$$

In Chapter 2, we have defined the resilience of a network as the ``ability of a network to keep services running despite a failure''. Therefore, according to the definition from Chapter 2, a tree protected by a backup path is resilient when a link failure in the tree with the backup path set up leads to a low number of group members being dropped from the communication. The metric $R(i,j)$ measures how well a backup path protects a multicast routing tree and thus matches the definition of the resilience given in Chapter 2. The higher this metric, the more resilient the tree protected by the backup path. A resilience is a number between $0$ and $R_t$. A resilience of $R_t$ means that on any link failure in the tree, no multicast group member is dropped from the multicast communication. On the other hand, a resilience of 0 implies that the backup path does not prevent any group member from being dropped on any single link failure.

Definition 4   A backup path $BP_{A, B}$ achieves optimal path protection in a tree $T$ when:

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

According to Definition 3, $R(i,j)=R_t-R_d(i,j)$ where $R_t$ is a constant. Therefore maximizing the resilience $R(i,j)$ boils down to minimizing the quantity $R_d(i,j)$. A backup path which maximizes the resilience of a tree also achieves optimal path protection for the tree. In the next section, we propose an algorithm which aims at finding a backup path that maximizes the resilience of a tree by minimizing quantity $R_d$.