Scalable data center multicast using multi-class Bloom Filter
Authors:
- 1 October 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10921648,p. 266-275
Abstract
Multicast benefits data center group communications in saving network bandwidth and increasing application throughput. However, it is challenging to scale Multicast to support tens of thousands of concurrent group communications due to limited forwarding table memory space in the switches, particularly the low-end ones commonly used in modern data centers. Bloom Filter is an efficient tool to compress the Multicast forwarding table, but significant traffic leakage may occur when group membership testing is false positive. To reduce the Multicast traffic leakage, in this paper we bring forward a novel multi-class Bloom Filter (MBF), which extends the standard Bloom Filter by embracing element uncertainty. Specifically, MBF sets the number of hash functions in a per-element level, based on the probability for each Multicast group to be inserted into the Bloom Filter. We design a simple yet effective algorithm to calculate the number of hash functions for each Multicast group. We have prototyped a software based MBF forwarding engine on the Linux platform. Simulation and prototype evaluation results demonstrate that MBF can significantly reduce Multicast traffic leakage compared to the standard Bloom Filter, while causing little system overhead.Keywords
This publication has 24 references indexed in Scilit:
- Exploring efficient and scalable multicast routing in future data center networks2011
- BUFFALO2009
- LIPSIN2009
- Dr. Multicast2008
- Incremental Bloom Filters2008
- Theory and Network Applications of Dynamic Bloom Filters2006
- i-DBF: an Improved Bloom Filter Representation Method on Dynamic Set2006
- Spectral bloom filters2003
- On the aggregatability of multicast forwarding state2002
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000