P2P流媒体应用层组播路由算法研究
|
摘要
随着多媒体技术和网络技术的日趋成熟,在互联网发展内在需求的驱动下,作为两者交叉领域的流媒体技术的应用和研究也取得了长足的进步。多媒体数据量大,对网络带宽要求很高。传统的流媒体技术试图利用IP组播来传输流媒体数据,以减少带宽的消耗。但是,IP组播对网络层设备有较大的依赖,需要对组播路径上所有的网络层设备进行调整和升级,为大范围部署IP组播带来了阻碍。因此IP组播很长的一段时间以来都没有得到广泛的应用。应用层组播在终端主机上实现组播的功能;只需要安装应用软件,并且不需改变现有的网络架构;因此基于应用层组播的P2P流媒体发展迅速。
综述了P2P技术、应用层组播技术和流媒体技术。详细介绍了适合流媒体直播的应用层组播树构造算法,并分析了其优缺点。由于节点服务能力差异较大,此外节点还可能随时加入或退出系统,而流媒体对数据播放具有较严格的时序要求,因此对P2P流媒体直播技术的研究也面临诸多挑战,包括节点的加入、节点离开或失效的处理等,这些挑战实际上也构成了P2P流媒体直播中的关键问题。给出了一种考虑带宽的主动式的快速重建路由的应用层组播路由算法。它在节点离开或者发生故障之前就为其孩子节点计算备用路由,一旦节点离开,其孩子节点可以迅速找到并平滑地切换新的父节点,并且尽量选择服务能力较强的节点作为备用路由,从而增加树的稳定性。
对算法进行了仿真和性能评价。结果显示,在恢复时间上比响应式方法小很多,跟杨氏方法基本上一样。控制流量开销比杨氏方法低,在某些特殊情况下甚至比响应式方法也低。尽管数据传输延迟比其它方法稍微有些大,但是随着节点度数的增加这种差别越来越小。
With the development of multimedia and network technology, application and research of stream media which is a cross-subject have made considerable progress. Multimedia has large data and demands wide bandwidth. Conventional stream media try to save bandwidth by using IP-multicast to transmit media data .However, IP-multicast depends much on devices in IP layer, and it needs to adjust or upgrade every device in IP layer. So it’s unpractical to use IP-multicast widely. Therefore IP-multicast has not been largely applied for a long time. Application level multicast implements multicast in application layer, thereby it is convenient to use ALM by installing software rather than adjusting the structure of present networks. So that P2P stream media based on ALM has mushroomed.
Theory of P2P networks ALM technology and stream media technique are summarized. Algorithm for construct ALM spanning tree which is applied in stream media living broadcast is introduced. The service ability of each node is difference and they may join or quit randomly while stream media is strict with scheduling when playing. So research on peer-to-peer live stream media confront with many challenge which is the key problem. A bandwidth considered proactive route maintenance method is given. In this method every non-leaf node maintains backup route for its children nodes before it leaves. So children nodes can quickly switch to backup route when their current parent node leaves. In order to improve the stability of the spanning tree it selects the node having the max service capability when computing backup route.
The performance of our bandwidth considered proactive approach is evaluated using simulations. Simulation results indicate that the recovery time of our approach is much less than reactive method and is approximately equal to Yang’s approach. The control overheads are smaller than Yang’s approach and even smaller than reactive method in some special cases. Though the data delivery delay is a little larger than other methods the difference between them becomes smaller as the degrees of nodes increase.
综述了P2P技术、应用层组播技术和流媒体技术。详细介绍了适合流媒体直播的应用层组播树构造算法,并分析了其优缺点。由于节点服务能力差异较大,此外节点还可能随时加入或退出系统,而流媒体对数据播放具有较严格的时序要求,因此对P2P流媒体直播技术的研究也面临诸多挑战,包括节点的加入、节点离开或失效的处理等,这些挑战实际上也构成了P2P流媒体直播中的关键问题。给出了一种考虑带宽的主动式的快速重建路由的应用层组播路由算法。它在节点离开或者发生故障之前就为其孩子节点计算备用路由,一旦节点离开,其孩子节点可以迅速找到并平滑地切换新的父节点,并且尽量选择服务能力较强的节点作为备用路由,从而增加树的稳定性。
对算法进行了仿真和性能评价。结果显示,在恢复时间上比响应式方法小很多,跟杨氏方法基本上一样。控制流量开销比杨氏方法低,在某些特殊情况下甚至比响应式方法也低。尽管数据传输延迟比其它方法稍微有些大,但是随着节点度数的增加这种差别越来越小。
With the development of multimedia and network technology, application and research of stream media which is a cross-subject have made considerable progress. Multimedia has large data and demands wide bandwidth. Conventional stream media try to save bandwidth by using IP-multicast to transmit media data .However, IP-multicast depends much on devices in IP layer, and it needs to adjust or upgrade every device in IP layer. So it’s unpractical to use IP-multicast widely. Therefore IP-multicast has not been largely applied for a long time. Application level multicast implements multicast in application layer, thereby it is convenient to use ALM by installing software rather than adjusting the structure of present networks. So that P2P stream media based on ALM has mushroomed.
Theory of P2P networks ALM technology and stream media technique are summarized. Algorithm for construct ALM spanning tree which is applied in stream media living broadcast is introduced. The service ability of each node is difference and they may join or quit randomly while stream media is strict with scheduling when playing. So research on peer-to-peer live stream media confront with many challenge which is the key problem. A bandwidth considered proactive route maintenance method is given. In this method every non-leaf node maintains backup route for its children nodes before it leaves. So children nodes can quickly switch to backup route when their current parent node leaves. In order to improve the stability of the spanning tree it selects the node having the max service capability when computing backup route.
The performance of our bandwidth considered proactive approach is evaluated using simulations. Simulation results indicate that the recovery time of our approach is much less than reactive method and is approximately equal to Yang’s approach. The control overheads are smaller than Yang’s approach and even smaller than reactive method in some special cases. Though the data delivery delay is a little larger than other methods the difference between them becomes smaller as the degrees of nodes increase.
引文
[1] Diot C., Levine B. N., Lyles B., et al. Deployment Issues for the IP multicast Service and Architecture. IEEE Network Magazine Special Issue on Multicasting, 2000, 14(1):78～88
[2] Deshpande H., Bawa M., Garcia-Molina H. Live Media Streaming over a Peer-to-Peer Network. Technical Report Stanford database group technical report, 2001, 3(2):15～23
[3] Xu D., Hefeeda M., Hambrush S., et al. On Peer-to-Peer Media Streaming. In: Proceedings of IEEE International Conference on Distributed Computing Systems(ICDCS).Vienna, Austria: 2002.363～371
[4] Sripanidkulchai K., Ganjam A., Maggs B., et al. The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points. In: Proceedings of ACM SIGCOMM. Portland, Oregon, USA:ACM Press, 2004.107～120
[5] Zhang Chao, Jin Hai, Deng Da-fu, et al. Anysee: Multicast-based Peer-to-Peer Media Streaming Service System. In: Asia-Pacific Conference on Communications. Pernth, Western Australia: 2005. 274～278
[6] Dan A., Shabuddin P., Sitaram D., et al. Channel Allocation under Batching and VCR Control in Video-on-demand Systems. Journal of Parallel and Distributed Computing, 1994, 30(2):168～179
[7] Dan A., Sitaram D., Shahabuddin P. Dynamic Batching Policies for an On-Demand Video Server. ACM Multimedia Systems, 1996, 4(3):112～121
[8] Gao L., Towsley D. Threshold-based Multicast for Continuous Media Delivery. IEEE Transactions on Multimedia, 2001, 3(4):405～414
[9] Juhn L., Tseng L. Fast Data Broadcasting and Receiving Scheme for Popular Video Services. IEEE Transaction on Broadcasting, 1998, 44(1):127～132
[10] Banerjee S., Bhattacharjee B., Kommareddy C. Scalable application layer multicast. ACM SIGCOMM Computer Communication Review, 2002, 32(4):205～217
[11] Tran D.A., Hua K. A., Do T.T. Zigzag: An Efficient Peer-to-Peer Scheme for Media Streaming. In: Proceedings of IEEE I6 INFOCOM03. San Francisco, CA, USA:IEEE Press, 2003.1283～1292
[12] Yang M., Fei Z. A Proactive Approach to Reconstructing Overlay Multicast Trees. In: Proceedings of IEEE INFOCOM. Hong Kong: IEEE Communications Society, 2004.2743～2753
[13] Guo M., Amman M. Scalable Live Video Streaming to Cooperative Clients Using Time Shifting and Video Patching. In: Proceedings of IEEE INFOCOM. Hong Kong: IEEE Communications Society, 2004. 1501～1511
[14] Guo M., Ammar M., Zegura E. Cooperative Patching: A Client Based P2P Architecture for Supporting Continuous Live Video Streaming. In: Proceedings of IEEE International Conference on Computers, Communication and Networks (IC3N). Chicago: 2004. 481～486
[15] Banerjee S., Lee S., Bhattacharjee B., et al. Resilient Multicast Using Overlays. In: Proceedings of ACM Sigmetrics. San Diego, CA, USA:2003. 102～113
[16]董海韬.对等网络的流媒体系统技术研究. [硕士学位论文].北京:清华大学图书馆,2005.
[17] Sylvia Ratnasamy, Paul Francis, Mark Handley, et al. A Scalable Content-Addressable Network. In: Proceedings of ACM SIGCOMM2001, San Diego, California, USA:2001.161～172
[18] Ion Stoica, Robert Morris, David Karger, et al. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In: Proceeding of ACM SIGCOMM 2001, San Diego, California, USA:2001.149～160
[19] Antony Rowstron, Peter Druschel. Pastry:Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems. In: Proceeding of IFIP/ACM International Conference on Distributed,Heidelberg, Germany: 2001.329～350
[20] Zhao Ben Y., John Kubiatowicz, Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley, 2001.
[21] Harvey N.J., Jones M.B., Saroiu S., et al. SkipNet: A Scalable Overlay Network with Practical Locality Properties. In: Proceedings of Fourth USENIX Symposium on Internet Technologies and Systems. CA, USA:2003.161～172
[22] Saltzer J, Reed D, Clark D. End-to-end Arguments in System Design. ACM Transactions on Computer Systems, 1984, 2(4):195～206
[23] Chu Y H, Rao S G, Seshan S, et al. A Case for End System Multicast. ACMSIGMETRICS Performance Evaluation Review, 2000, 28(1):1～12
[24] Chu Y H, Rao S G, Seshan S, et al. Enabling Conferencing Applications on the Internet Using an Overlay Multicast Architecture. ACM SIGCOMM Computer Communication Review, 2001, 31(4):55～67
[25] Pendarakis D, Shi S. ALMI: An Application Level Multicast Infrastructure. In: Anderson T. The 3rd USENIX Symposium on Internet Technologies and Systems. San Francisco, CA, USA:USENIX Association, 2001.49～60
[26] Padmanabhan V N, Wang H J, Chou P A, et al. Distributing Streaming Media Content Using Cooperative Networking. In: The 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video. Miami, Florida, USA:ACM Press, 2002.177～186
[27] Goyal V K. Multiple description coding: Compression meets the Network. IEEE Singal Processing Mag, 2001, 18(5):74～93
[28] Chawathe Y. Scattercast: An Architecture for Internet Broadcast Distribution as an Infrastructure Service. [Ph. D. Thesis]. USA, University of California, Berkeley, 2000.
[29] Jannotti J, Gifford D K, Johnson K L. Overcast: Reliable Multicasting with an Overlay Network. In: Jones M B, Kaashoek F.USENIX Symposium on Operating System Design and Implementation. San Diego, CA, USA:USENIX Association, 2000.197～212
[30] Zhang Bei-chuan, Jamin S, Zhang Li-xia. Host multicast: A Framework for Delivering Multicast to End Users. In: Kermani P.IEEE INFOCOM 2002. New York, NY, USA:IEEE Press, 2002.1366～1375
[31] Zhuang S Q, Zhao B Y, Joseph A D. Bayeux: Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination. In: Nieh J, Schulzrinne H. The Eleventh International Workshop on Network and Operating System Support for Digital Audio and Video. New York, USA:ACM Press, 2001. 11～20
[32] Ratnasamy S, Handley M, Karp R, et al. Application-level Multicast Using Content-addressable Networks. In: Crowcroft J, Hofmann M. Networked Group Communication, Third International COST264 Workshop, London, UK: Springer, 2001.14～29
[33] Liebeherr J, Nahas M, Si W. Application-layer Multicasting with Delaunay Triangulation Overlays. IEEE Journal on Selected Areas in Communications, 2002, 20(8):1472～1488
[34]杨音颖,吴家皋,陈益新.基于Overlay网络的应用层组播系统的研究与实现.计算机应用, 2004, 24(9):61～64
[35]王艳丽,鲜继清,白洁.基于P2P的流媒体技术.计算机应用, 2005, 25(6):1267～1270
[36]章淼,徐明伟,建平.应用层组播研究综述.电子学报, 2004 S1:26～29
[37]李辉,胡瑞敏,艾浩军等.基于RTP的多媒体流的自适应传输.计算机工程与应用,2004, 40(5):174～176
[38]顾洪军.流媒体应用中的QoS问题分析.计算机应用研究, 2003, 20(11):117～119
[39]马永泉.对等网络存储系统中激励机制的研究. [硕士学位论文].北京:清华大学图书馆2005.
[40]李伟.基于层次结构的应用层组播方案的设计. [硕士学位论文].北京:北京师范大学2004.
[41]李伟,沈长宁.应用层组播协议的研究.计算机工程与应用, 2004, 40(24):156～159
[42]林闯,单志广,任丰原.计算机网络的服务质量(QoS).清华大学出版社, 2004.4. 26～28
[2] Deshpande H., Bawa M., Garcia-Molina H. Live Media Streaming over a Peer-to-Peer Network. Technical Report Stanford database group technical report, 2001, 3(2):15～23
[3] Xu D., Hefeeda M., Hambrush S., et al. On Peer-to-Peer Media Streaming. In: Proceedings of IEEE International Conference on Distributed Computing Systems(ICDCS).Vienna, Austria: 2002.363～371
[4] Sripanidkulchai K., Ganjam A., Maggs B., et al. The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points. In: Proceedings of ACM SIGCOMM. Portland, Oregon, USA:ACM Press, 2004.107～120
[5] Zhang Chao, Jin Hai, Deng Da-fu, et al. Anysee: Multicast-based Peer-to-Peer Media Streaming Service System. In: Asia-Pacific Conference on Communications. Pernth, Western Australia: 2005. 274～278
[6] Dan A., Shabuddin P., Sitaram D., et al. Channel Allocation under Batching and VCR Control in Video-on-demand Systems. Journal of Parallel and Distributed Computing, 1994, 30(2):168～179
[7] Dan A., Sitaram D., Shahabuddin P. Dynamic Batching Policies for an On-Demand Video Server. ACM Multimedia Systems, 1996, 4(3):112～121
[8] Gao L., Towsley D. Threshold-based Multicast for Continuous Media Delivery. IEEE Transactions on Multimedia, 2001, 3(4):405～414
[9] Juhn L., Tseng L. Fast Data Broadcasting and Receiving Scheme for Popular Video Services. IEEE Transaction on Broadcasting, 1998, 44(1):127～132
[10] Banerjee S., Bhattacharjee B., Kommareddy C. Scalable application layer multicast. ACM SIGCOMM Computer Communication Review, 2002, 32(4):205～217
[11] Tran D.A., Hua K. A., Do T.T. Zigzag: An Efficient Peer-to-Peer Scheme for Media Streaming. In: Proceedings of IEEE I6 INFOCOM03. San Francisco, CA, USA:IEEE Press, 2003.1283～1292
[12] Yang M., Fei Z. A Proactive Approach to Reconstructing Overlay Multicast Trees. In: Proceedings of IEEE INFOCOM. Hong Kong: IEEE Communications Society, 2004.2743～2753
[13] Guo M., Amman M. Scalable Live Video Streaming to Cooperative Clients Using Time Shifting and Video Patching. In: Proceedings of IEEE INFOCOM. Hong Kong: IEEE Communications Society, 2004. 1501～1511
[14] Guo M., Ammar M., Zegura E. Cooperative Patching: A Client Based P2P Architecture for Supporting Continuous Live Video Streaming. In: Proceedings of IEEE International Conference on Computers, Communication and Networks (IC3N). Chicago: 2004. 481～486
[15] Banerjee S., Lee S., Bhattacharjee B., et al. Resilient Multicast Using Overlays. In: Proceedings of ACM Sigmetrics. San Diego, CA, USA:2003. 102～113
[16]董海韬.对等网络的流媒体系统技术研究. [硕士学位论文].北京:清华大学图书馆,2005.
[17] Sylvia Ratnasamy, Paul Francis, Mark Handley, et al. A Scalable Content-Addressable Network. In: Proceedings of ACM SIGCOMM2001, San Diego, California, USA:2001.161～172
[18] Ion Stoica, Robert Morris, David Karger, et al. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In: Proceeding of ACM SIGCOMM 2001, San Diego, California, USA:2001.149～160
[19] Antony Rowstron, Peter Druschel. Pastry:Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems. In: Proceeding of IFIP/ACM International Conference on Distributed,Heidelberg, Germany: 2001.329～350
[20] Zhao Ben Y., John Kubiatowicz, Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley, 2001.
[21] Harvey N.J., Jones M.B., Saroiu S., et al. SkipNet: A Scalable Overlay Network with Practical Locality Properties. In: Proceedings of Fourth USENIX Symposium on Internet Technologies and Systems. CA, USA:2003.161～172
[22] Saltzer J, Reed D, Clark D. End-to-end Arguments in System Design. ACM Transactions on Computer Systems, 1984, 2(4):195～206
[23] Chu Y H, Rao S G, Seshan S, et al. A Case for End System Multicast. ACMSIGMETRICS Performance Evaluation Review, 2000, 28(1):1～12
[24] Chu Y H, Rao S G, Seshan S, et al. Enabling Conferencing Applications on the Internet Using an Overlay Multicast Architecture. ACM SIGCOMM Computer Communication Review, 2001, 31(4):55～67
[25] Pendarakis D, Shi S. ALMI: An Application Level Multicast Infrastructure. In: Anderson T. The 3rd USENIX Symposium on Internet Technologies and Systems. San Francisco, CA, USA:USENIX Association, 2001.49～60
[26] Padmanabhan V N, Wang H J, Chou P A, et al. Distributing Streaming Media Content Using Cooperative Networking. In: The 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video. Miami, Florida, USA:ACM Press, 2002.177～186
[27] Goyal V K. Multiple description coding: Compression meets the Network. IEEE Singal Processing Mag, 2001, 18(5):74～93
[28] Chawathe Y. Scattercast: An Architecture for Internet Broadcast Distribution as an Infrastructure Service. [Ph. D. Thesis]. USA, University of California, Berkeley, 2000.
[29] Jannotti J, Gifford D K, Johnson K L. Overcast: Reliable Multicasting with an Overlay Network. In: Jones M B, Kaashoek F.USENIX Symposium on Operating System Design and Implementation. San Diego, CA, USA:USENIX Association, 2000.197～212
[30] Zhang Bei-chuan, Jamin S, Zhang Li-xia. Host multicast: A Framework for Delivering Multicast to End Users. In: Kermani P.IEEE INFOCOM 2002. New York, NY, USA:IEEE Press, 2002.1366～1375
[31] Zhuang S Q, Zhao B Y, Joseph A D. Bayeux: Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination. In: Nieh J, Schulzrinne H. The Eleventh International Workshop on Network and Operating System Support for Digital Audio and Video. New York, USA:ACM Press, 2001. 11～20
[32] Ratnasamy S, Handley M, Karp R, et al. Application-level Multicast Using Content-addressable Networks. In: Crowcroft J, Hofmann M. Networked Group Communication, Third International COST264 Workshop, London, UK: Springer, 2001.14～29
[33] Liebeherr J, Nahas M, Si W. Application-layer Multicasting with Delaunay Triangulation Overlays. IEEE Journal on Selected Areas in Communications, 2002, 20(8):1472～1488
[34]杨音颖,吴家皋,陈益新.基于Overlay网络的应用层组播系统的研究与实现.计算机应用, 2004, 24(9):61～64
[35]王艳丽,鲜继清,白洁.基于P2P的流媒体技术.计算机应用, 2005, 25(6):1267～1270
[36]章淼,徐明伟,建平.应用层组播研究综述.电子学报, 2004 S1:26～29
[37]李辉,胡瑞敏,艾浩军等.基于RTP的多媒体流的自适应传输.计算机工程与应用,2004, 40(5):174～176
[38]顾洪军.流媒体应用中的QoS问题分析.计算机应用研究, 2003, 20(11):117～119
[39]马永泉.对等网络存储系统中激励机制的研究. [硕士学位论文].北京:清华大学图书馆2005.
[40]李伟.基于层次结构的应用层组播方案的设计. [硕士学位论文].北京:北京师范大学2004.
[41]李伟,沈长宁.应用层组播协议的研究.计算机工程与应用, 2004, 40(24):156～159
[42]林闯,单志广,任丰原.计算机网络的服务质量(QoS).清华大学出版社, 2004.4. 26～28