Scalable Data Center Multicast using Multi-class Bloom Filter

Monday, 8th August 2011, 1:30 am (SCE Meeting Room)
Speaker: Dr. Li Dan (Tsinghua University )
Title: Scalable Data Center Multicast using Multi-class Bloom Filter

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 take 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.


Dr. Li Dan joined the faculty of Tsinghua University in Mar 2010, where he is now an assistant professor in computer science department. His research interests include Internet architecture and protocol design, P2P networks, data center networks and green networking. He received his M.E. degree and Ph.D from Tsinghua University in 2005 and 2007 respectively, both in computer science. Before that, he spent four undergraduate years in Beijing Normal University and got a B.S. degree in 2003, also in computer science. He joined Microsoft Research Asia in Jan 2008, where he worked as an associate researcher in Wireless and Networking Group until Feb 2010. He has published more than 30 technical papers, including top conferences (e.g., SIGCOMM, INFOCOM) and top journals (e.g., ToN, TMM) in respective fields he worked in. He also serves as a TPC member for many international conferences, including INFOCOM, GLOBECOM, ICCCN, and etc.