Stateless overlay multicast with in-packet bloom filters

doi:10.1016/S1005-8885(17)60232-2

JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM ›› 2017, Vol. 24 ›› Issue (5): 44-52.doi: 10.1016/S1005-8885(17)60232-2

• Networks • Previous Articles Next Articles

Stateless overlay multicast with in-packet bloom filters

Tian Shengwen, Wang Jingyu, Yang Hongyong, Cui Guanghai

1. School of Information and Electrical Engineering, Ludong University, Yantai 264000, China
2. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2017-04-24 Revised:2017-09-29 Online:2017-10-30 Published:2017-12-18
Contact: Tian Shengwen, E-mail: sw_tian@yeah.net E-mail:sw_tian@yeah.net
About author:Tian Shengwen, E-mail: sw_tian@yeah.net
Supported by:
This work was supported by the National Natural Science Foundation of China (62673200), Foundation of Ludong University in China (LB2016019, LB2016017), Natural Science Foundation of Shandong Province (ZR2017MF062).

Abstract

Abstract: Due to the difficulty of deploying Internet protocol (IP) multicast on the Internet on a large scale, overlay multicast has been considered as a promising alternative to develop the multicast communication in recent years. However, the existing overlay multicast solutions suffer from high costs to maintain the state information of nodes in the multicast forwarding tree. A stateless overlay multicast scheme is proposed, in which the multicast routing information is encoded by a bloom filter (BF) and encapsulated into the packet header without any need for maintaining the multicast forwarding tree. Our scheme leverages the node heterogeneity and proximity information in the physical topology and hierarchically constructs the transit-stub overlay topology by assigning geometric coordinates to all overlay nodes. More importantly, the scheme uses BF technology to identify the nodes and links of the multicast forwarding tree, which improves the forwarding efficiency and decreases the false-positive forwarding loop. The analytical and simulation results show that the proposal can achieve high forwarding efficiency and good scalability.

Key words: overlay multicast, BF, Internet node coordinate, network awareness

CLC Number:

TP393

Tian Shengwen, Wang Jingyu, Yang Hongyong, Cui Guanghai. Stateless overlay multicast with in-packet bloom filters[J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(5): 44-52.

References

References

1. Hosseini M, Ahmed D T, Shirmohammadi S, et al. A survey of application-layer multicast protocols. IEEE Communications Surveys and Tutorials, 2007, 9(3): 58-74

2. Kurian J, Sarac K. A survey on the design, applications, and enhancements of application-layer overlay networks. ACM Computing Surveys, 2010, 43(1): Article 5

3. Banerjee S, Kommareddy C, Kar K, et al. OMNI: An efficient overlay multicast infrastructure for real-time applications. Computer Networks, 2006, 50(6): 826-841

4. Lao L, Cui J H, Gerla M, et al. A scalable overlay multicast architecture for large-scale applications. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(4): 449-459

5. Castro M, Druschel P, Kermarrec A M, et al. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1489-1499

6. Tapolcai J, Gulyás A, Heszbergery Z, et al. Stateless multi-stage dissemination of information: Source routing revisited. Proceedings of the 2012 IEEE Global Communications Conference (GLOBECOM’12), Dec 3-7, 2012, Anaheim, CA, USA. Piscataway, NJ, USA: IEEE, 2012: 2797-2802

7. Yao C C. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 2006, 11(4): 721-736

8. Rowstron A. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms (Middleware’01), Nov 12-16, 2001, Heidelberg, Germany. LNCS 2218. Berlin, Germany: Springer-Verlag, 2001: 329-350

9. Zhang W Z, Zheng Q H, Li H F, et al. An overlay multicast protocol for live streaming and delay-guaranteed interactive media. Journal of Network and Computer Applications, 2012, 35(1): 20-28

10. Mokhtarian K, Jacobsen H A. Minimum-delay overlay multicast. Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM’13), Apr 14-19, 2013, Turin, Italy. Piscataway, NJ, USA: IEEE, 2013: 1771-1779

11. Mokhtarian K, Jacobsen H A. Minimum-delay multicast algorithms for mesh overlays. IEEE/ACM Transactions on Networking, 2015, 23(3): 973-986

12. Kim K, Mehrotra S, Venkatasubramanian N. Efficient and reliable application layer multicast for flash dissemination. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(10): 2571-2582

13. Li Z Y, Zhu Z Y, Xie G G, et al. Fast and proximity-aware multi-source overlay multicast under heterogeneous environment. Computer Communications, 2009, 32(2): 257-267

14. Stoica I, Morris R, Karger D, et al. Chord: A scalable peer-to-peer lookup service for internet applications. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM’01), Aug 27-31, 2001, San Diego, CA, USA. New York, NY, USA: ACM, 2001: 149-160

15. Tarkoma S, Rothenberg C E, Lagerspetz E. Theory and practice of Bloom filters for distributed systems. IEEE Communications Surveys and Tutorials, 2012, 14(1): 131-155

16. Rothenberg C E, Macapuna C A B, Magalhães M F, et al. In-packet Bloom filters: Design and networking applications. Computer Networks, 2011, 55(6): 1364-1378

17. Jokela P, Zahemszky A, Esteve Rothenberg C, et al. LIPSIN: Line speed publish/subscribe inter-networking. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 195-206

18. Tsilopoulos C, Xylomenos G. Scaling Bloom filter-based multicast via filter switching. Proceedings of the 2013 IEEE Symposium on Computers and Communications (ISCC’13), Jul 7-10, 2013, Split, Croatia. Piscataway, NJ, USA: IEEE, 2013: 548-553

19. Särelä M, Rothenberg C E, Aura T, et al. Forwarding anomalies in Bloom filter-based multicast. Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’11), Apr 10-15, 2011, Shanghai, China. Piscataway, NJ, USA: IEEE, 2011: 2399-2407

20. Tian X H, Cheng Y. Loop mitigation in Bloom filter based multicast: A destination-oriented approach. Proceedings of the 31st Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’12), Mar 25-30, 2012, Orlando, FL, USA. Piscataway, NJ, USA: IEEE, 2012: 2131-2139

21. Costa M, Castro M, Rowstron A, et al. PIC: Practical Internet coordinates for distance estimation. Proceedings of the 24th International Conference on Distributed Computing Systems, Mar 23-26, 2004, Tokyo, Japan. Piscataway, NJ, USA: IEEE, 2004: 178-187

22. Nelder J A, Mead R. A simplex method for function minimization. Computer Journal, 1965, 7(4): 308-313

23. Ruhrup S, Schindelhauer C, Volbert K, et al. Performance of distributed algorithms for topology control in wireless networks. Proceedings of the 2003 IEEE International Symposium on Parallel and Distributed Processing, Apr 22-26, 2003, Nice, France. Piscataway, NJ, USA: IEEE, 2003: 8p

24. Rocketfuel ISP topology data. Redwood City, CA, USA: Rocket Fuel Inc

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd

[1]	Zhang Luying, Liu Xiaokai, Li Zhao, Xu Fangmin, Zhao Chenglin. Prediction based dynamic resource allocation method for edge computing first networking [J]. The Journal of China Universities of Posts and Telecommunications, 2023, 30(3): 78-87.
[2]	Chen Hui, Jiang Xiaoling, Wu Tianting, Mou Xingyu. Crowd sensing data delivery based on tangle DAG network [J]. The Journal of China Universities of Posts and Telecommunications, 2023, 30(3): 88-98.
[3]	Zhu Ruijie, Li Gong, Wang Peisen, Zhang Wenchao. Reinforced virtual optical network embedding algorithm in EONs for edge computing [J]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(6): 18-29.
[4]	Zhao Guosheng, Liu Dongmei, Wang Jian. Cloud security situation prediction method based on grey wolf optimization and BP neural network [J]. The Journal of China Universities of Posts and Telecommunications, 2020, 27(6): 30-41.
[5]	Liu Kun, Wang Hui , Shen Zihao. Prediction of network attack profit path based on NAPG model [J]. The Journal of China Universities of Posts and Telecommunications, 2020, 27(5): 91-102.
[6]	Li Bo, Sun Xuehong, Li Chunshu, Xue Kaiping, Zhang Xiaoguang. Downlink energy efficiency modeling and optimization with backhaul awareness and interference price in ultra cellular HetNet [J]. The Journal of China Universities of Posts and Telecommunications, 2019, 26(2): 67-81.
[7]	Zhang Junsong, Jiang Yongcong, Gan Yong, Zhang Qikun. Bilinear pair based authentication protocol for wireless medical sensor network [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2018, 25(2): 28-38.
[8]	Yang Jingmin1, Zhang Wenjie1, Zou Fumin2. Survey of outdoor and indoor architecture design in TVWS networks [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(6): 24-38.
[9]	Wu Zhijun,Cui Zihan, Wang Caiyun, Lei Jin. Access control scheme with attribute revocation for SWIM [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(6): 49-54.
[10]	Yao Yukun, Liu Jiangbing, Xu Dongliang, Ren Zhi, Hu Qing. Centralized congestion control routing protocol based on multi-metrics for low power and lossy networks [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(5): 35-43.
[11]	Tan Xiaoying, Huang Dan, Guo Yuchun, Chen Changjia. Dynamic resource allocation in cloud download service [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(5): 53-59.
[12]	. Power savings in software defined data center networks via modified hybrid genetic algorithm [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(4): 76-86.
[13]	. Quality of experience evaluation of HTTP video streaming based on user interactive behaviors [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(3): 24-32.
[14]	. Research of the multi-way connectivity probability for platoon-based Vehicle-to-Infrastructure communication network [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2016, 23(1): 1-7.
[15]	. Trusted GPSR protocol without reputation faking in VANET [J]. Acta Metallurgica Sinica(English letters), 2015, 22(5): 22-31.

Stateless overlay multicast with in-packet bloom filters

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments