# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## 2 Related Work and Our Contribution
### Brief Overview of Multicast Routing in the Internet
An example is the hybrid SDN model proposed in [26] where multicast traffic is managed thanks to a set of OpenFlow flow rules instantiated in network nodes under control of the centralised SDN controller. Nonetheless, any centralised approach suffers of scalability limitations and, in multicast, we have to deal with two dimensions. On the one hand, the number of multicast groups to be managed can be very high: more than 200 millions groups can be created in IPv4, even more if we consider IPv6. On the other hand, hosts can constantly join and leave any multicast group at any time, creating many updates to be sent and managed by the SDN controller to keep all MDTs optimally connected. Another line of research proposes the use of routing schemes based on the _compact_ concept. Compact routing aims at finding the best trade-off between the memory space required to store the routing table entries at each node; the size of the packets headers and the length of the routing paths it produces. Such routing schemes have been extensively studied following the seminal paper in [27]. In the context of multicast routing, prior work is, as far as our knowledge goes, mainly concentrated around the routing schemes proposed in [28]. This scheme enables the construction of multicast routing paths from any source to any set of leaf nodes. Although the author develops an extensive theoretic performance justification and analysis, they do not report any numerical analysis. The upper bounds indicated do not necessarily translate actual performance that can be obtained on graphs underlying large-scale networks such as the internet, which, in addition, shows properties associated to scale-free graphs (small diameter, high-clustering, and power-law degree distribution) [29; 30]. Recent work [4] proposes the Bit Index Explicit Replication (BIER) multicast architecture which does not require any explicit tree-building protocol, nor does it require intermediate nodes to maintain any per-flow state. BIER consists of encapsulating packets in BIER headers that contain a string of bits (called bit-string) in which each bit represents exactly one node in the domain; to forward the packet to a given set of destination nodes, the bits corresponding to those nodes are set in the BIER header. This solution completely relies therefore on the unicast routing to forward multicast packets to the destination nodes. Since its first appearance, BIER attracted much attention for its simplicity, and works have been presented to enhance its basic functionality, for instance, with reliable multicast transmission [31], packet caching for fast retransmission [32], and fast reroute in case of failure [33]. Nevertheless, in BIER, all the required information to route the packets to the leaf nodes is encoded in the BIER header, which implies at least three issues. The first one is that the size of this additional header scales linearly to the number of nodes in the network. Currently, the limitation of the bit-string is set to 256 bits (equivalent to the two IPv6 addresses), meaning no more than 256 routers can be identified as a destination in the BIER header. In an internet with 100k ASes, this is to be a significant constraint. There is the possibility to overcome this limitation by creating (up to 256) subsets, meaning that packets belong to different subsets (also known as BIER sub-domains) need to be sent separately, partially losing therefore the benefits of multicast routing as a bandwidth saving technique. Another problem is that each bit in the bit-string requires the execution of a routing process; the results are then ANDed to merge the common next hops and create the new BIER headers. Finally, the resulting MDT constructed in this way is a combination of shortest paths, i.e., a Shortest Path Tree (SPT) per BIER sub-domain. As we will see in the results, SPT does not provide the optimally performing tree.