More Web Proxy on the site http://driver.im/

research-article

Optimal false-positive-free Bloom filter design for scalable multicast forwarding

Authors:

János Tapolcai,

József Bíró,

Péter Babarczi,

András Gulyás,

Zalán Heszberger,

Dirk TrossenAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 23, Issue 6

Pages 1832 - 1845

https://doi.org/10.1109/TNET.2014.2342155

Published: 01 December 2015 Publication History

Abstract

Large-scale information dissemination in multicast communications has been increasingly attracting attention, be it through uptake in new services or through recent research efforts. In these, the core issues are supporting increased forwarding speed, avoiding state in the forwarding elements, and scaling in terms of the multicast tree size. This paper addresses all these challenges---which are crucial for any scalable multicast scheme to be successful---by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept, we build our Bloom filter by enclosing limited information about the structure of the tree. Analytical investigation is conducted and approximation formulas are provided for optimal-length Bloom filters, in which we got rid of typical Bloom filter illnesses such as false-positive forwarding. These filters can be used in several multicast implementations, which are demonstrated through a prototype. Thorough simulations are conducted to demonstrate the scalability of the proposed Bloom filters compared to its counterparts.

References

[1]

J. Crowcroft, "Cold topics in networking," Comput. Commun. Rev., vol. 38, no. 1, pp. 45--47, Jan. 2008.

Digital Library

[2]

P. Jokela, A. Zahemszky, C. Esteve Rothenberg, S. Arianfar, and P. Nikander, "LIPSIN: Line speed publish/subscribe inter-networking," Comput. Commun. Rev., vol. 39, no. 4, pp. 195--206, 2009.

Digital Library

[3]

S. Ratnasamy, A. Ermolinskiy, and S. Shenker, "Revisiting IP multicast," Comput. Commun. Rev., vol. 36, no. 4, p. 26, 2006.

Digital Library

[4]

M. Särelä et al., "Forwarding anomalies in Bloom filter-based multicast," in Proc. IEEE INFOCOM, Shanghai, China, 2011, pp. 2399--2407.

[5]

V. Jacobson et al., "Networking named content," in Proc. ACM CoNEXT, 2009, pp. 1--12.

Digital Library

[6]

T. Koponen et al., "A data-oriented (and beyond) network architecture," Comput. Commun. Rev., vol. 37, no. 4, pp. 181--192, 2007.

Digital Library

[7]

D. Trossen and G. Parisis, "Designing and realizing an information-centric internet," IEEE Commun. Mag., vol. 50, no. 7, pp. 60--67, Jul. 2012.

[8]

F. Németh, Á. Stipkovits, B. Sonkoly, and A. Gulyás, "Towards Smart-Flow: Case studies on enhanced programmable forwarding in Open-Flow switches," Comput. Commun. Rev., vol. 42, no. 4, pp. 85--86, 2012.

Digital Library

[9]

C. Rothenberg, C. Macapuna, F. Verdi, M. Magalhães, and A. Zahemszky, "Data center networking with in-packet Bloom filters," in Proc. Brazilian Symp. Comput. Netw. (SBRC), Gramado, Brazil, 2010, pp. 553--566.

[10]

S. Deering and D. Cheriton, "Multicast routing in datagram internetworks and extended LANs," Trans. Comput. Syst., vol. 8, no. 2, pp. 85--110, 1990.

Digital Library

[11]

S. Deering, C. Partridge, and D. Waitzman, "Distance vector multicast routing protocol," Internet Request For Comments RFC-1075, 1988.

[12]

B. Fenner, M. Handley, H. Holbrook, and I. Kouvelas, "Protocol independent multicast-sparse mode (PIM-SM): Protocol specification (Revised)," Internet Engineering Task Force, RFC 4601 (Proposed Standard), Aug. 2006, updated by RFCs 5059 and 5796.

[13]

M. Bag-Mohammadi and N. Yazdani, "A fast and efficient explicit multicast routing protocol," IEICE Trans. Commun., vol. E-88B, no. 10, pp. 4000--4007, 2005.

[14]

J. Bion, D. Farinacci, M. Shand, and A. Tweedly, "Explicit Route Multicast (ERM)," Internet Engineering Task Force, Jun. 2000.

[15]

M. Bag-Mohammadi, S. Samadian-Barzoki, and N. Yazdani, "Linkcast: Fast and scalable multicast routing protocol," in Proc. IFIP Netw., 2004, pp. 1282--1287.

[16]

B. Bloom, "Space/time trade-offs in hash coding with allowable errors," Commun. ACM, vol. 13, no. 7, pp. 422--426, 1970.

Digital Library

[17]

J. Tapolcai et al., "Stateless multi-stage dissemination of information: Source routing revisited," in Proc. IEEE GLOBECOM, 2012, pp. 2797--2802.

[18]

W. Yang, D. Trossen, and J. Tapolcai, "Scalable forwarding for information-centric networks," in Proc. IEEE ICC-NGN, Budapest, Hungary, 2013, pp. 3639--3644.

[19]

D. Trossen, M. Sarela, and K. Sollins, "Arguments for an information-centric internetworking architecture," Comput. Commun. Rev., vol. 40, no. 2, pp. 26--33, Apr. 2010.

Digital Library

[20]

P. Elias, "Universal codeword sets and representations of the integers," IEEE Trans. Inf. Theory, vol. IT-21, no. 2, pp. 194--203, Mar. 1975.

Digital Library

[21]

P. Bose et al., "On the false-positive rate of Bloom filters," Inf. Process. Lett., vol. 108, no. 4, pp. 210--213, 2008.

Digital Library

[22]

A. Kirsch and M. Mitzenmacher, "Less hashing, same performance: Building a better Bloom filter," in Proc. ESA, 2005, vol. 14, pp. 456--467.

Digital Library

[23]

"Intel 64 and IA-32 Architectures Optimization Reference Manual" 2014 {Online}. Available: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

[24]

T.-C. Chiueh and P. Pradhan, "High-performance IP routing table lookup using CPU caching," in Proc. 18th. Annu. IEEE INFOCOM, 1999, vol. 3, pp. 1421--1428.

[25]

SNDlib, "Survivable fixed telecommunication network design library," 2006 {Online}. Available: http://sndlib.zib.de

[26]

S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, "The Internet Topology Zoo," 2013 {Online}. Available: http://www.topology-zoo.org

Cited By

Huang JChen ZWang YLi HLi ZWang QLi SHe ZJiang W(2024)Achieving High Efficiency for Datacenter Multicast using Skewed Bloom FilterProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673126(1227-1236)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673126
Wu RJia W(2023)CSVRFIET Communications10.1049/cmu2.1270118:1(40-54)Online publication date: 17-Dec-2023
https://dl.acm.org/doi/10.1049/cmu2.12701
Jia WChen YJin ZGeng W(2023)Scalable multicast control-plane for optical packet forwarding enginesOptical Switching and Networking10.1016/j.osn.2022.10071347:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.osn.2022.100713
Show More Cited By

Recommendations

Scalable datacenter multicast using in-packet bitmaps

Scalability is a key issue in datacenter multicast as it needs to support a large number of groups in commodity switches with limited fast memory. Previous in-packet Bloom filter-based datacenter multicast schemes have been proposed to address the ...
On reducing false positives of a bloom filter in trie-based algorithms
ANCS '14: Proceedings of the tenth ACM/IEEE symposium on Architectures for networking and communications systems

Many IP address lookup approaches employ Bloom filters to obtain a high-speed search performance. Especially, the search performance of trie-based algorithms can be significantly improved by adding Bloom filters, because Bloom filters can determine ...
Application and Research on Weighted Bloom Filter and Bloom Filter in Web Cache
WMWA '09: Proceedings of the 2009 Second Pacific-Asia Conference on Web Mining and Web-based Application

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters and their generalizations, weighted Bloom filters and compressed Bloom filters have been suggested as a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 23, Issue 6

December 2015

306 pages

ISSN:1063-6692

Editor:
R. Srikant
Univ. Illinois at Urbana-Champaign, Urbana, IL

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2015

Published in TON Volume 23, Issue 6

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang JChen ZWang YLi HLi ZWang QLi SHe ZJiang W(2024)Achieving High Efficiency for Datacenter Multicast using Skewed Bloom FilterProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673126(1227-1236)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673126
Wu RJia W(2023)CSVRFIET Communications10.1049/cmu2.1270118:1(40-54)Online publication date: 17-Dec-2023
https://dl.acm.org/doi/10.1049/cmu2.12701
Jia WChen YJin ZGeng W(2023)Scalable multicast control-plane for optical packet forwarding enginesOptical Switching and Networking10.1016/j.osn.2022.10071347:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.osn.2022.100713
Wu RJia W(2022)A Caching Mechanism for SVRF-based Multicast Packet Forwarding EnginesProceedings of the 10th International Conference on Communications and Broadband Networking10.1145/3538806.3538819(7-13)Online publication date: 25-Feb-2022
https://dl.acm.org/doi/10.1145/3538806.3538819
Jin ZJia W(2022)DH-SVRF: A Reconfigurable Unicast/Multicast Forwarding for High-Performance Packet Forwarding EnginesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.310889933:5(1262-1275)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1109/TPDS.2021.3108899
Borgia EBruno RPassarella A(2022)Reliable data delivery in ICN-IoT environmentsFuture Generation Computer Systems10.1016/j.future.2022.04.004134:C(271-286)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.future.2022.04.004
Heszberger Z(2022)Hyperbolic trees for efficient routing computationThe Journal of Supercomputing10.1007/s11227-022-04485-578:13(15250-15268)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04485-5
Jin ZWu XJia WShi X(2021)Fractional-N SVRF Forwarding Algorithm for Low Port-Density Packet Forwarding Engines2021 IEEE 18th Annual Consumer Communications & Networking Conference (CCNC)10.1109/CCNC49032.2021.9369540(1-5)Online publication date: 9-Jan-2021
https://dl.acm.org/doi/10.1109/CCNC49032.2021.9369540
Gao WNguyen JWu YHatcher WYu W(2020)Routing in Large-scale Dynamic NetworksACM Transactions on Internet Technology10.1145/340719220:4(1-24)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1145/3407192
Concas FXu PHoque MLu JTarkoma S(2020)Multiple Set Matching with Bloom Matrix and Bloom VectorACM Transactions on Knowledge Discovery from Data10.1145/337240914:2(1-21)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3372409
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents