# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 3 The Greedy Compact Multicast Routing (GCMR) Scheme
### Examples  
In Figure 2, we report an illustrative example of the local search process. In Figure 2a, we can observe a joining node \(J\) with its vicinity ball \(B(J)\). In this example, this vicinity ball contains all nodes with at most two hops distant from \(J\) (remember that we are not considering QoS in this work, therefore the only cost used is the number of hops). In Figure 2b, node \(J\) sends a searching request (type-R message) which floods up to find node(s) belonging to a given MDT. If at least one node is found (Figure 2c), it sends an answer back (type-A message) to the joining node; the accumulated path cost is transported in this answer in such a way that, in case of multiple answers, only the least cost branch path reaches the joining node. It is worth mentioning that, during the flooding of type-R messages, nodes store temporarily the port from which the message has arrived: in this way, they can use this information to forward the type-A messages back to the joining node  
Figure 1: Two-stage search process: (**a**) Local search: joining node searching the MDT in its neighbourhood; (**b**) Global search: edge nodes searching outside the joining node’s neighbourhood. without creating entries in the routing tables. In the example, we can see that the answer from node 7 transports an infinite cost, i.e., the MDT has not been found along this path inside \(B(J)\). The other two answers transport cost 1 and cost 2 from node 2 and node 5, respectively. Therefore, the joining node sends the join message towards node 2 which is the least cost branch path to the MDT as we can observe in Figure 2d. Note that, in the case that two or more paths have the same cost, the preference goes to the path that is received first (i.e., the oldest one). Figure 3 presents an illustrative example of the global search process. As in the previous example, node \(J\) wants to join a given MDT but this time the local search fails as there are no nodes belonging to that MDT in the vicinity ball \(B(J)\) (see Figure 3a). It means all type-R messages sent are answered with type-A messages with infinite cost. For simplicity, we do not depict all messages in the figure but only show the paths followed by the request and answer messages up to the edge nodes of the vicinity ball. Therefore, node \(J\) needs now to discover the MDT outside \(B(J)\) with the global search. The global search starts at the edge nodes of the \(B(J)\); such edge nodes are identified during the local search and requested by the joining node \(J\) to start the global flooding outside \(B(J)\) only (see Figure 3b). When a node is found (Figure 3c), it sends an answer back (type-A message) to the joining node transporting the accumulated path cost. In the example, we can observe that three answers arrive to node \(J\), which selects the least cost branching path. As in the local search case, if two or more paths have the same cost, the preference goes to the oldest path. In Figure 3d, we can see that node \(J\) selects the path to node 2 and it is now connected to the MDT. Figure 2: Creation of a branching path between a joining node and the MDT using local search: (**a**) initial situation with joining \(J\) and the MDT; (**b**) joining node searching messages within its vicinity ball; (**c**) nodes’ answers to the joining node; (**d**) node joins the MDT through the least cost branching path. In Figure 4, we show an illustrative example of an adaptation of the MDT after a link failure event. We assume that the link \(l\) fails (Figure 4a) and both upstream node 2 and downstream node 4 (\(D_{1}\)) can detect it, for instance using keepalive messages. In GCMR, the upstream node 2 is in charge of re-connecting the disconnected leaves (Figure 4b). In this example, leaf nodes \(D_{1}\), \(D_{2}\), and \(D_{3}\) are disconnected from the MDT. Node 2 uses type-A messages to the downstream nodes: remember that a type-A message collects the cost of the paths, so then downstream nodes can compare the costs and join the least cost branching paths.