Forwarding anomalies in Bloom filter-based multicast
Mikko Särelä, Christian Esteve Rothenberg, Tuomas Aura, András Zahemszky, Pekka Nikander, Jörg Ott · 2011
Several recently proposed multicast protocols use in-packet Bloom filters to encode multicast trees. These mechanisms are in principle highly scalable because no per-flow state is required in the routers and because routing decisions can be made efficiently by simply checking for the presence of outbound links in the filter. Yet, the viability of previous approaches is limited by the possibility of forwarding anomalies caused by false positives inherent in Bloom filters. This paper explores such anomalies, namely (1) packets storms, (2) forwarding loops and (3) flow duplication. We propose stateless solutions that increase the robustness and the scalability of Bloom filter-based multicast protocols. In particular, we show that the parameters of the filter need to be varied to guarantee the stability of the packet forwarding, and we present a bit permutation technique that effectively prevents both accidental and maliciously created anomalies. We evaluate our solutions in the context of BloomCast, a source-specific inter-domain multicast protocol, using analytical methods and simulations.