# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 5 Simulation Analysis  
### Reference Multicast Schemes  
The main objective of these simulation tests is to evaluate the performance of GCMR in the context of inter-domain routing and compare it with the following multicast routing schemes. The Steiner Tree (ST) algorithm offers the lower bound in terms of stretch, based on the concept of multicast routing stretch described in Section 3.1. We use an ST-Integer Linear Programming (ILP) formulation adapted from Sage's Graph Library ([[http://www.sagemath.org/](http://www.sagemath.org/)]([http://www.sagemath.org/](http://www.sagemath.org/)) accessed on 15 September 2021) for bi-directional graphs to obtain a near-optimal solution for the ST problem. The formulation is provided in Appendix A. Although the ST scheme uses a centralised approach to create the minimum tree, we assume that the nodes still require exchange of messages during the MDT construction process, just as they would in a distributed environment. Thus, at each stage of the construction of the MDT, the communication cost of ST is calculated by counting the minimum number of messages generated by the nodes to keep the global knowledge of the MDT status. In this way, any node can create and maintain an entry in its MRIB routing table to reach the MDT's nearest node. It means that there is no need for URIB entries as the the MRIB is constructed from the global knowledge of the MDT status. On the contrary, the TIB table is needed at each node of the tree to forward data packets towards the destination nodes of the multicast group. We assume that ST is also the reference for the transmission cost: packets are sent through the minimum tree with their IP headers without the need for any extra overhead. The currently deployed PIM-SSM routing [18] constructs the MDT using data exchanged via a unicast routing protocol that includes the multicast source \(s\) as well as information about the routing path used to reach that source. If we assume that there are is routing policy changing the default behaviour, the resulting routing path is the shortest path from each leaf node to the source \(s\). As a consequence, the MDT constructed in this way is a Shortest Path Tree (SPT). Each node keeps the following entries in its local routing table (i) an entry in the URIB per neighbour node to exchange routing messages, (ii) an entry in the MRIB per selected path to the multicast source \(s\) (obtained from the unicast routing table), and (iii) a multicast forwarding entry in the TIB for source \(s\) and group \(G\). As in the case of ST, packets do not require any additional overhead besides the standard IP headers. Nonetheless, the stretch of the SPT computed by PIM-SSM should be higher than ST. Hence, we also expect higher transmission cost as packets will traverse additional edges with respect to the ST reference case. The BIER proposal distributes the multicast packet using the unicast routing scheme. As in the PIM case, without routing policy, the routing paths are the shortest path from the source \(s\) to each receiver, meaning that the resulting MDT is an SPT per BIER sub-domain. Each node keeps the following entries in its local routing table: (i) an entry in the URIB per neighbour node to exchange routing messages, (ii) a 16-bit unique number called a BIER Forwarding Router identifier (BFR-id) to identify each router in a BIER sub-domain, and (iii) the Bit Index Routing Table (BIRT) containing an entry per each destination and the route to reach it [4]. Each entry of this BIRT consists of the BFR-id decomposed in the bit-string of 256 bits and its subset of 8 bits, the IP address of the destination and the IP address of the next hop. In addition, BIER adds a header in front of the IP packets containing at least 256 bits for the bit-string and 8 bits for the subset (we assume that the BIER header is 362 bits long as indicated in [36]). Finally, packets belonging to different subsets need to be transmitted separately, meaning that the transmission cost of BIER would probably be higher than the others.