# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 3 The Greedy Compact Multicast Routing (GCMR) Scheme
### Basic Functionality  
The GCMR scheme seeks to reduce the size of each node's routing table (and hence memory space) at the expense of (i) multicast routing paths with relatively modest deviations compared to the optimal stretch generated by the reference ST algorithm, and (ii) greater communication costs compared to PIM and BIER. GCMR achieves the minimisation of the memory space because only direct neighbourhood information is needed to be stored locally at each node and thus it scales linearly with the node degree. This information is used during the MDT construction to provide the next hop along the least cost branching path. Thus, GCMR does not need: (i) non-local topology/path information like PIM; (ii) the construction of complex structures such as sparse covers like in compact routing methods [28]; (iii) tree structures like in ST; or (iv) additional labels or headers containing information for computing the routing paths like in BIER. The difficulty is keeping the best possible compromise between the stretch and the memory space while limiting the communication cost, i.e., the amount of messages exchanged during the construction of the MDT. In GCMR, any node \(u\in V,u\
otin T_{s,M}\) can become a leaf node of a given multicast source \(s\) by creating a least cost branch path to its MDT \(T_{s,M}\), i.e., GCMR is leaf-initiated. The information needed to join a MDT is acquired when needed by means of a two-stage search process. Figure 1 illustrates this process schematically. Node \(u\) starts with a local search sending a type-R message within its vicinity ball \(B(u)\) for any node \(v\
eq u,v\in T_{s,M}\) (see Figure 1a). The vicinity ball covers the joining node's neighbourhood. The reasoning is that in large networks with a diameter \(\delta(G)\) that is logarithmically proportional to the number of nodes \(n\), i.e., \(\delta(G)\sim\log(n)\), the likelihood of finding the node \(v\) within a few hops distance from the joining node \(u\) is high. Furthermore, this probability rises as the MDT grows in size. If the local search over the vicinity ball \(B(u)\) fails, the search is resumed across the remaining undiscovered topology without requiring global knowledge of the MDT (see Figure 1b). In order to avoid costly global search in terms of the amount of messages, a variable path budget \(\pi\) is utilised to limit the distance they can travel. As to not repeat the unsuccessful search inside the \(B(u)\), the global search starts at the edge nodes of the \(B(u)\); such edge nodes are identified during the local search and requested by the joining node \(u\) to start the global flooding outside \(B(u)\) only. In any of these two phases, if a node belonging to the MDT is found, it returns an answer (type-A message) to the joining node. If an intermediate node receives more than one answer during a given time frame, it only forwards one answer to the joining node. The decision about which answer depends on the costs/metrics defined and transported in the answer. In a context without QoS, the cost is unique and can represent the number of hops; the least cost branching path is therefore the minimum hop distance between the joining node and the node belonging to the MDT. In a context with QoS, we can define metrics that accumulate additively along the path (e.g., number of hops, delay, path length, etc.) or metrics that exclude given paths (e.g., not enough bandwidth, too low reliability, etc. ), and thus the decision at each intermediate node can be based on the requested QoS level. For sake of simplicity, in this paper we evaluate the GCMR performance in a scenario without QoS. As a consequence of this process, the routing table of each node \(v\in T_{s,M}\) includes the following entries (i) one entry in the MRIB table that indicates the upstream neighbour node to which the join message is sent for each multicast source \(s\) and (ii) one entry in the TIB table to enable routing of incoming multicast traffic (originated by that source \(s\)) from its incoming port to a set of outgoing ports.