Next: Maximization of the resilience Up: A multicast routing tree Previous: A multicast routing tree   Contents

# Problem modeling

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 . The set of the vertices of the graph contains the routers (LSRs and LERs) of the network. The set of the edges of the graph contains the links of the network. Set 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 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 the source of if is a shortest path tree or the core of if is a core based tree. The set of the nodes of the tree contains the routers of the multicast routing tree. The set of the links of the tree contains the links of the multicast routing tree. Tree is embedded in graph and therefore and .

In a tree, the children of a node are the nodes immediately downstream of with regards to and the parent of is the node immediately upstream of with regards to . Let be the set of the children of node and be the parent of node . Similarly, given a link , let be the set of the links immediately downstream of link with regards to . Let be the subtree of with regards to and which root is node . Let be the subgraph of which contains node upstream of with regards to , link , and the subtree rooted at the node downstream of with regards to . By definition, is a tree.

We define the weight of a link as follows. Consider a node and link immediately upstream of with regards to . If is a LER, is the number of multicast group members that send or receive multicast traffic via an access link attached to node . If is a LSR, then let . 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 with regards to such that . Receivers are LERs which transmit multicast traffic to or from multicast group members over an access link. A leaf of a tree is a node such that . Let be the set of the leaves of . 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 .

If fails, then tree is split in two trees and . Let be the tree which contains and let be the other tree. All multicast hosts attached to a LER of are dropped from the multicast communication, and all LERs of are dropped from tree . If LER is dropped from then 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 between two vertices and of graph is a sequence of vertices such that and . We denote by the set of the nodes of and by the set of the links of . In a tree , there exists a unique path between any two nodes . Therefore, there exists a unique path between root and node on the one hand, and between and on the other hand. Let node be the node such that , and . Node is called the Least Common Ancestor (LCA) of and .

Definition 1   The Protected Path is the unique path between nodes such that:

Definition 2   A Backup Path is a path between two nodes and such that:

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 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 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 and of tree , if a link of the protected path fails then it is possible to reroute traffic through a backup path 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 with the same total link weight by appending the backup path to the original tree.

Claim 1   Given a tree , two nodes , the protected path , a backup path , and a link , there exists a tree such that

Proof:

Let and be the two smaller trees that result from the removal of link in tree . Trees and are rooted at node . Assume without loss of generality that and . Let be the root of tree . Trees and are link and node disjoint therefore the graph which results from merging and via backup path is a tree, hence (1) and (2). Let be the root of . The sum is the total number of multicast hosts attached to all LERs of . Similarly, the sum is the total number of multicast hosts attached to all LERs of . Since and no multicast host is attached to a vertex of , the numbers of multicast hosts attached to any LER of and are the same, hence (3).

On a link failure in tree rooted at , is split into two trees and as described above and all receivers in are disconnected from . If a backup path is inserted in (see Figure 3.3(a)), then when any link from the protected path fails a new tree replaces 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.

Let be the number of hosts attached to receivers that are dropped from tree when link fails and no backup path is set up. Since is the set that contains at the same time link and all links in the subtree of rooted at the node immediately downstream of with regards to , then, by definition of :

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

In Figure 3.4, we give the values of , and for all links on an example. In the following, we use metric to formally define the resilience of a tree, and metric 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 into two trees and . If a backup path is set up in , then according to Claim 1 it is possible to build a new tree such that no receiver is dropped from the communication if any link from the protected path fails. Therefore the weighted number of receivers dropped from a multicast communication using a tree protected by a backup path on a single link failure is:

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

Quantity is a constant that depends on the tree topology only whereas also depends on the end nodes and of the backup path . Quantity measures the impact of a link failure on a tree that is not protected by any backup path, while 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 protected by a backup path between nodes is defined as:

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 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 and . A resilience of 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 achieves optimal path protection in a tree when:

According to Definition 3, where is a constant. Therefore maximizing the resilience boils down to minimizing the quantity . 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 .

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