Computer Science ›› 2016, Vol. 43 ›› Issue (6): 77-81.doi: 10.11896/j.issn.1002-137X.2016.06.016

Previous Articles     Next Articles

High Stability Low Delay Spanning Tree Algorithm for Application Layer Multicast

CUI Jian-qun, CHEN Ai-ling, XIA Zhen-chang and WU Li-bing   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Since application layer multicast(ALM) relies on terminal hosts to forward multicast data,any intermediate node fails or quits would result in the system stability problem.Meanwhile,ALM has strict requirement for multicast tree delay.To improve stability and data transmission efficiency,this paper introduced a Spanning tree problem model SDMD based on stability probability,degree-constrained,and minimum diameter for ALM,according to the influencing factor of ALM stability and delay.The SDMD problem was proved to be NP-hard and an approximation algorithm TG-Swas proposed to solve it.The simulation result demonstrates the advantages of TG-S algorithm in average receiving delay,multicast tree delay and accumulative interrupt times.

Key words: Application layer multicast,Stability,Minimum delay,NP-hard,Time gaining

[1] Deering S E.Multicast routing in a datagram internetwork[R].Stanford Univ CA Dept of Computer Science,1991
[2] Cao Ji-jun,Su Jin-shu.Delay-Bounded and High Stability Spanning Tree Algorithm for Application Layer Multicast[J].Journal of Software,2010,21(12):3151-3164(in Chinese) 曹继军,苏金树.应用层组播的时延受限高稳定性生成树算法[J].软件学报,2010,1(12):3151-3164
[3] Deering S.Host extensions for IP multicasting.IETF RFC1112,1989.http://www.ietf.org/rfc/rfc1112.txt
[4] Hosseini M,Ahmed D T,Shirmohammadi S,et al.A Survey of Application-Layer Multicast Protocols[J].Communication Surveys & Tutorials IEEE,2007,9(3):58-74
[5] Yeo C K,Lee B S,Er M H.A survey of application level multicast techniques[J].Computer Communications,2004,27(15):1547-1568
[6] Alpes P A I R,Project-Team P,Eric P,et al.Application-level Multicast Transmission Techniques over the Internet[J].IEEE Transactions on Device & Materials Reliability,2004,2(2):462-469
[7] El-Sayed A,Roca V,Mathy L.A survey of proposals for an alternative group communication service[J].Welding International,2003,17(1):46-51
[8] Francis P.Yoid:Extending the Multicast Internet Architecture[EB/OL].http://www.isi.edu/div7/yoid/docs/ycHtml/htmlRoot.html
[9] Chu Y,Rao S G,Zhang H.A Case for End System Multicast.2000[J].The Proceedings of Acm Sigmetrics,2000,28(1):1-12
[10] Zhang B,Jamin S,Zhang L.Host multicast:A framework for delivering multicast to end users[C]∥Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2002).IEEE,2002:1366-1375
[11] Banerjee S,Bhattacharjee B,Kommareddy C.Scalable Applica-tion Layer Multicast[J].ACM Sigcomm Computer Communication Review,2002,32(4):205-217
[12] Sripanidkulchai K,Ganjam A,Maggs B,et al.The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points[J].Proceedings of Acm Sigcomm,2004,34(4):107-120
[13] Su Jin-shu,Cao Ji-jun,Zhang Bo-feng.A Survey of the research on ALM stability enhancement[J].Chinese Journal of Compu-ter,2009,32(3):576-590(in Chinese) 苏金树,曹继军,张博锋.应用层组播稳定性提高技术综述[J].计算机学报,2009,32(3):576-590
[14] Roca V,El-Sayed A.A Host-Based Multicast (HBM) Solution for Group Communications[M]∥Networking-ICN 2001.Springer,2001:610-619
[15] Luo Jian-guang,Zhao Li,Yang Shi-qiang.An algorithm of constructing ALM tree based on user behavior analysis [J].Journal of Computer Research and Development,2006,43(9):1557-1563(in Chinese) 罗建光,赵黎,杨士强.基于用户行为分析的应用层组播树生成算法[J].计算机研究与发发展,2006,3(9):1557-1563
[16] Veloso E,Almeida V,Meira W,et al.A hierarchical charac-terization of a live streaming media workload[C]∥Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement 2002.Marseille,France,2002:117-130
[17] Cao Jia,Lu Shi-wen.A Multimum Delay Spanning Tree Algorithm for the Application-Layer Multicast[J].Journal of Software,2005,6(10):1766-1773(in Chinese) 曹佳,鲁士文.应用层组播的最小延时生成树算法[J].软件学报,2005,6(10):1766-1773
[18] Cui Jian-qun,Xiong Nai-xue,Park J H,et al.A novel and efficient source-path discovery and maintenance method for application layer multicast[J].Computers and Electrical Engineering,2013,9(1):67-75
[19] Zhang X C,Yang M H,Zhu X J,et al.A loss recovery approach for reliable application layer multicast[J].Journal of Systems and Software,2012,85(5):1198-1204

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!