Stateless overlay multicast with in-packet bloom filters

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

中国邮电高校学报(英文版) ›› 2017, Vol. 24 ›› Issue (5): 44-52.doi: 10.1016/S1005-8885(17)60232-2

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

收稿日期:2017-04-24 修回日期:2017-09-29 出版日期:2017-10-30 发布日期:2017-12-18
通讯作者: Tian Shengwen, E-mail: sw_tian@yeah.net E-mail:sw_tian@yeah.net
作者简介:Tian Shengwen, E-mail: sw_tian@yeah.net
基金资助:
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).

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

摘要： 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.

关键词: overlay multicast, BF, Internet node coordinate, network awareness

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

中图分类号:

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

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

[1]	刘琨, 王辉, 申自浩. Prediction of network attack profit path based on NAPG model[J]. 中国邮电高校学报(英文版), 2020, 27(5): 91-102.
[2]	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]. 中国邮电高校学报(英文版), 2019, 26(2): 67-81.
[3]	Zhang Junsong, Jiang Yongcong, Gan Yong, Zhang Qikun. Bilinear pair based authentication protocol for wireless medical sensor network[J]. 中国邮电高校学报(英文版), 2018, 25(2): 28-38.
[4]	Yang Jingmin1, Zhang Wenjie1, Zou Fumin2. Survey of outdoor and indoor architecture design in TVWS networks[J]. 中国邮电高校学报(英文版), 2017, 24(6): 24-38.
[5]	Wu Zhijun,Cui Zihan, Wang Caiyun, Lei Jin. Access control scheme with attribute revocation for SWIM[J]. 中国邮电高校学报(英文版), 2017, 24(6): 49-54.
[6]	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]. 中国邮电高校学报(英文版), 2017, 24(5): 35-43.
[7]	Tan Xiaoying, Huang Dan, Guo Yuchun, Chen Changjia. Dynamic resource allocation in cloud download service[J]. 中国邮电高校学报(英文版), 2017, 24(5): 53-59.
[8]	谢坤黄小红马懋德张沛. Power savings in software defined data center networks via modified hybrid genetic algorithm[J]. 中国邮电高校学报(英文版), 2017, 24(4): 76-86.
[9]	李文璟喻鹏王瑞一丰雷董欧洲邱雪松. Quality of experience evaluation of HTTP video streaming based on user interactive behaviors[J]. 中国邮电高校学报(英文版), 2017, 24(3): 24-32.
[10]	邵彩幸张建华. Research of the multi-way connectivity probability for platoon-based Vehicle-to-Infrastructure communication network[J]. 中国邮电高校学报(英文版), 2016, 23(1): 1-7.
[11]	肖雅郑世慧孙斌. Trusted GPSR protocol without reputation faking in VANET[J]. Acta Metallurgica Sinica(English letters), 2015, 22(5): 22-31.
[12]	Zhang Yi, Guo Yuchun, Chen Yishuai. Optimized bandwidth allocation for maximizing user’s QoE in hybrid cloud P2P content distribution [J]. Acta Metallurgica Sinica(English letters), 2015, 22(3): 84-91.
[13]	石文孝吴丹许银龙王继红. Routing metric of interference-aware link quality: an improved ETX in wireless mesh networks[J]. Acta Metallurgica Sinica(English letters), 2014, 21(5): 61-67.
[14]	肖丁石川. Autonomic discovery of subgoals in hierarchical reinforcement learning[J]. Acta Metallurgica Sinica(English letters), 2014, 21(5): 94-104.
[15]	丁郁刘亚志王文东龚向阳. Road traffic and geography topology based opportunistic routing for VANETs[J]. Acta Metallurgica Sinica(English letters), 2014, 21(4): 32-39.

Stateless overlay multicast with in-packet bloom filters

Stateless overlay multicast with in-packet bloom filters

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价