# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 5 Simulation Analysis
### Results  
Figure 8 summarises the results we obtained of the four metrics considering the 46k CAIDA map and leaf nodes ranging from 400 to 4000. Figure 8 compares the stretch of GCMR against ST, PIM-SSM, BIER (best) and BIER (worse). Note that the stretch refers to the _distance_ between the MDT created by the protocol and the minimum tree. The minimum tree is obtained with ST and for this reason is one for any leaf node set in this figure. The stretch of GCMR is in between ST and PIM-SSM; with the increase in the size of the MDT from 400 to 4000, GCMR is between 0.1 and 0.05 better than PIM-SSM and between 0.1 and 0.05 worse than ST. In contrast, BIER requires the construction of multiple MDTs to reach all leaf nodes as they need to belong to different subsets (i.e., BIER sub-domains). For instance, BIER (best) requires 2 MDTs for 400 leaf nodes and this number increases up to 16 MDTs to allocate 4000 leaf nodes. The consequence is that the stretch of BIER (best) is higher than the other schemes, reaching almost 1.45 with 4000 leaf nodes. Even worse, the stretch of BIER (worse) is out of scale in the figure when the leaf node set size is below 1600, then it decreases and reaches 1.8 with 4000 leaf nodes. Figure 8 presents the results in terms of memory space (in bits). It is worth mentioning that for the ST, PIM-SSM and BIER cases we do not consider all routing table entries but only those of the nodes part of the MDT and required by the multicast protocols to route packets through the MDT. We can observe that GCMR outperforms the other schemes. For a leaf set of 400 nodes, the memory space ratio between GCMR and the other schemes is almost 2 orders of magnitude. This difference decreases as the size of the leaf node set increases, reaching one order of magnitude with 4000 leaf nodes. Simulation performed on the CAIDA map comprising 46k nodes shows that the communication cost of the GCMR scheme is relatively higher compared to BIER and PIM-SSM (see Figure 8); ST requires a global flooding after each event and thus its communication cost is several times higher than the other schemes. BIER achieves the best performance in this metric as it does not require the construction of the MDT. Nonetheless, this performance comes with a cost: BIER requires addition of a specific BIER header to each packet and, in order to not have very large header, one packet can be transmitted to 256 leaf nodes at maximum. This means that the transmission cost of BIER (see Figure 8d) is higher than the other schemes. In particular, we can observe that, with the best possible configuration of the BIER sub-domains, BIER (best) can obtain similar performance with 400 leaf nodes. However, with increasing leaf node set size, its transmission cost quickly starts to grow and at 4000 leaf nodes BIER (best) is 40% worse than, for instance, GCMR. The other three schemes achieve comparable results, with ST being the best as its packets traverse the minimal tree. In Table 1, we compare the stretch and the memory space ratio considering 2000 leaf nodes and the 16k, 26k, 36k and 46k CAIDA maps. We can observe that the stretch of all schemes increases with increased network size compared to the optimal stretch of ST. As expected, BIER (best) is the scheme experiencing the higher increase while GCMR is very close to the optimal stretch and its deviation only slightly increases with the network size. For the memory space ratio, we used GCMR as the reference as it is the scheme requiring less information in its local routing table. This ratio gives a reasonable indication about the improvements provided by GCMR in terms of the memory space needed to store the routing information and routing table entries compared to the other schemes. We can see that the gain of GCMR increases against the other schemes as the size of the network increases from 16k to 46k nodes: for instance from 146.81 to 270.38 (PIM-SSM) and from 9.54 to 25.7 (BIER).