In-packet bloom filter based multicast is a family of techniques that have been recently proposed to address scalability issues in IP multicast. The main problem motivating these techniques is that network forwarding elements supporting traditional IP multicast store group specific forwarding state for every multicast tree traversing the element, resulting in poor memory scalability in networks with many active groups. Techniques in this family address this problem by encoding multicast routing information into in-packet bloom filters, which are memory efficient, probabilistic data structures for representing set membership. However, in existing approaches the probabilistic nature of bloom filters results in false-positive packet delivery, thereby introducing forwarding anomalies, unnecessary bandwidth utilization, and violations of security policies. In this work we contribute BloomFlow, a novel approach to bloom filter based multicast in SDN that achieves substantial forwarding state reduction while eliminating false positive packet delivery. The BloomFlow approach compensates for the stochastic uncertainty associated with bloom filters by incorporating the SDN network controller's knowledge of the network topology and traffic workload into the generation of variable length and false-positive-free bloom filters. We further contribute a set of extensions to the OpenFlow protocol that demonstrates how our approach can be integrated into OpenFlow enabled networks with minimal modifications to switch hardware. We implement a working system prototype by extending the Stanford OpenFlow 1.0 Reference Switch and the POX SDN controller. We evaluate our approach through both flow level simulation, and packet level network emulation with Mininet and real media streams. We demonstrate that multicast forwarding using BloomFlow can achieve significant reductions in memory requirements due to network forwarding state (up to a ∼79% reduction in realistic WAN topologies under heavy multicast workloads). We find that this forwarding state reduction can be achieved with minimal bandwidth utilization overhead (averaging under ∼1%), and that our approach successfully meets time constraints required for deployment in a real-time SDN controller.

Additional Metadata
Keywords Bloom filter, Ethernet switch, Flow-based, Multicast, OpenFlow, SDN
Persistent URL dx.doi.org/10.1016/j.comcom.2017.05.018
Journal Computer Communications
Citation
Craig, A. (A.), Nandy, B. (B.), Lambadaris, I, & Koutsakis, P. (P.). (2017). Bloomflow: Openflow extensions for memory efficient, scalable multicast with multi-stage bloom filters. Computer Communications, 110, 83–102. doi:10.1016/j.comcom.2017.05.018