# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 3 The Greedy Compact Multicast Routing (GCMR) Scheme  
### Preliminaries  
Consider a network topology modelled by an undirected weighted graph \(G=(V,E,\omega)\), where the set \(V,|V|=n\) represents the finite set of vertices or nodes (all multicast capable), the set \(E,|E|=e\) represents the finite set of edges or links, and \(\omega\) is a non-negative function \(\omega:E\rightarrow\mathbb{R}+\) which associates a non-negative weight or cost \(\omega(u,v)\) to each edge \((u,v)\in E\). For \(u,v\in V\), the path \(p(u,v)\) from vertex \(u\) to \(v\) is defined as the vertex sequence \([x_{0}(=u),x_{1},\ldots,x_{i-1},x_{i},\ldots,x_{p}(=v)]\) such that the vertices \(x_{i}\) are all distinct and vertex \(x_{i-1}\) is adjacent to \(x_{i},\forall(x_{i-1},x_{i})_{i=1,\ldots,p}\in E\). The following definitions apply: (i) the cost \(c(u,v)\) of a path \(p(u,v)\) as the sum of the weights of the edges on the path from \(u\) to \(v\), (ii) the length \(l(u,v)\) of a path \(p(u,v)\) as the number of edges the path traverses from \(u\) to \(v\), (iii) the distance \(d(u,v)\) between two vertices \(u,v\) of the graph \(G\) as the cost of the minimum cost path \(p(u,v)\) from \(u\) to \(v\), and (iv) the diameter \(\delta(G)\) of the graph \(G\) is defined as the largest distance between any two vertices \(u,v\in V\), i.e., \(\delta(G)=\max_{u,v\in V}\{d(u,v)\}\). Let \(S,S\subset V\), be the finite set of multicast source nodes and \(s\in S\) denote a multicast source node. Let \(D,D\subseteq V\,S\), denote the finite set of all possible leaf nodes that can join a multicast source \(s\) and let \(d\in D\) denote a leaf node. The MDT \(T_{s,M}=(V_{T},E_{T})\) is defined as an acyclic connected sub-graph \(H\) of \(G\), i.e., the tree rooted at the multicast source node \(s\) with leaf node set \(M,M\subseteq D\). The tree \(T_{s,M}\) is also referred to as the multicast routing path and its information is usually stored in the TIB table. The set \(M\) corresponds to the current set of nodes at a given construction step of the MDT. The size of the tree \(T_{s,M}\) is defined as the size of the connected graph of \(G\), i.e., \(|T_{s,M}|=h\leq n\). With the objectives of this work in mind, we define the following performance metrics:  
* The stretch of a routing scheme is defined as the maximum ratio between the cost of the path \(p(u,v)\) traversed by a packet and the cost of the shortest path considering all node pairs \(u,v\in V\). For the multicast case, the definition of the stretch changes to the total cost of the edges of the MDT to reach a given group of leaf nodes is divided by the cost of the minimum tree, which is the one produced by solving the corresponding Steiner Tree (ST) problem for the same leaf group [28]. * The memory space (in bits) takes into account the information required to be stored at each node to properly treat the multicast packets. The storage required by the algorithm is directly related to routing system scalability because the less memory a router needs to store its entries, the more scalable the routing system would be. The following routing information bases are defined [16]:
* The Tree Information Base (TIB) essentially stores the state of all multicast distribution trees necessary to forward multicast packets at a router;
The Unicast Routing Information Base (URIIB) is the unicast control message routing and it is used to determine the next shortest hop and/or the path (e.g., like BGP) towards a node of the network; * The Multicast Routing Information Base (MRIB) is the multicast control message routing and it is used to determine the next-hop neighbour to which any Join/Leave message is sent (towards the tree root or source). * The communication cost (in number of messages) is defined as the number of messages exchanged to build the MDT (it is also usually known as the message cost). This metric is directly related to the overhead of the protocol, i.e., the higher the communication cost the longer the time needed to construct and maintain the tree.