CDN与P2P混合网络中Peer节点负载均衡研究
|
摘要
CDN与P2P混合网络,具有较好的可扩展性、自适应性与健壮性,从而能够为分布在异构网络环境中的大规模用户提供服务质量保证,并尽可能节省服务器成本开销。在CDN与P2P混合网络中Peer节点负载均衡是使其有效运行的重要因素之一。本文研究CDN与P2P混合网络中Peer节点负载均衡算法,主要解决访问请求不均匀造成的负载不均衡问题。
解决访问请求不均匀造成的负载不均衡主要算法有:基于复制技术的算法、基于流言传播的算法、基于意识路由的算法、基于虚拟节点的算法。基于复制技术的算法将副本存放在将来访问请求到来的位置,已有的基于复制技术的算法在副本存放位置上作了假设,即现在访问请求到来的位置也将是未来访问请求到来的位置。
本地域外Peer节点负载均衡算法——改进CDN-PR算法,在CDN-PR副本算法思想上进行了改进,未改进的算法假设副本存放的位置是将来访问请求到来的位置,这个假设有些时候是正确的,但也存在与假设相反的情况,缺少理论的支撑,因此引入了马尔科夫预测模型,预测将来资源访问请求到来的位置,其次是因为CDN-PR副本算法适合于CDN网络中Peer节点负载均衡;马尔科夫预测模型根据访问请求现在到来的区域及其变化趋势,预测访问请求在将来某一特定时刻可能到来的区域,为副本位置决策提供了依据。
本地域内Peer节点负载均衡算法——改进多次尝试请求RR(Request Retries)算法。在多次尝试请求算法思想上,通过马尔科夫预测模型预测节点的可用能力,在节点心跳报文中夹带节点的可用能力。由节点可用能力与路由距离综合选择服务节点,性能好的节点会负担多一点的任务,性能弱的节点会负担少一点的任务。
在Peersim仿真平台下,对本地域内Peer节点负载均衡算法——改进的多次尝试请求算法进行了仿真实验及性能分析,对本地域外Peer节点负载均衡算法——改进的CDN-PR算法进行仿真实验及性能分析。仿真实验验证了改进的两个Peer节点负载均衡算法略优于未改进前的算法。
The hybrid CDN and P2P network make a better network scalability, adaptability and robustness. The hybrid network provided service quality assurance for the distribution of large-scale heterogeneous network environment users and save server overhead as much as possible. Peer node load balancing is one of the key factors impact on the hybrid CDN and P2P network. The Peer node load balancing, mainly solve the query load imbalance problems.
The existing load balancing algorithms caused by Peer node unbalanced requests, they are algorithm based on replication technology、algorithm based on rumor propagation、algorithm based on the awareness of the routing、algorithm based on the virtual node. Studied the replica placement; Replication algorithms based on the assumption—the future requests will come from the position of the elapsed requests, it lacks theoretical support.
Load balancing of outside local area Peer node algorithm– Improve the CDN-PR replica algorithm. Improve the CDN-PR algorithm is because it makes an assumption that the future requests will come from the position of the elapsed requests, this assumption is correct sometimes, however, it is incorrect sometimes. To support the theory, import the Markov model predicting the position of the future requests, and secondly because the CDN-PR replica algorithm is proper for the CDN Peer node load balancing; Markov forecast the future requests based on the right now state of regional trends, predict future requests in a particular area may happen, provided the basis for the replica position decision making.
Load balancing of local area Peer node algorithm - Improve the request retries algorithm. The improved request retries algorithm compute the node capacity by the Markov Model. It bring the node capacity in the heart beat package. Use the node capacity and TTL select nodes. Node with good performance will service more requests, node with bad performance will service less requests.
Under the Peersim simulation platform, make the simulation and performance analysis on the load balancing of outside local area Peer node algorithm - Improved the CDN-PR replica algorithm. Make the simulation and performance analysis on the load balancing of local area Peer node algorithm - Improved request retries algorithm. The simulation reveal that both of the improved algorithm performance much better than the algorithm which is not improved.
解决访问请求不均匀造成的负载不均衡主要算法有:基于复制技术的算法、基于流言传播的算法、基于意识路由的算法、基于虚拟节点的算法。基于复制技术的算法将副本存放在将来访问请求到来的位置,已有的基于复制技术的算法在副本存放位置上作了假设,即现在访问请求到来的位置也将是未来访问请求到来的位置。
本地域外Peer节点负载均衡算法——改进CDN-PR算法,在CDN-PR副本算法思想上进行了改进,未改进的算法假设副本存放的位置是将来访问请求到来的位置,这个假设有些时候是正确的,但也存在与假设相反的情况,缺少理论的支撑,因此引入了马尔科夫预测模型,预测将来资源访问请求到来的位置,其次是因为CDN-PR副本算法适合于CDN网络中Peer节点负载均衡;马尔科夫预测模型根据访问请求现在到来的区域及其变化趋势,预测访问请求在将来某一特定时刻可能到来的区域,为副本位置决策提供了依据。
本地域内Peer节点负载均衡算法——改进多次尝试请求RR(Request Retries)算法。在多次尝试请求算法思想上,通过马尔科夫预测模型预测节点的可用能力,在节点心跳报文中夹带节点的可用能力。由节点可用能力与路由距离综合选择服务节点,性能好的节点会负担多一点的任务,性能弱的节点会负担少一点的任务。
在Peersim仿真平台下,对本地域内Peer节点负载均衡算法——改进的多次尝试请求算法进行了仿真实验及性能分析,对本地域外Peer节点负载均衡算法——改进的CDN-PR算法进行仿真实验及性能分析。仿真实验验证了改进的两个Peer节点负载均衡算法略优于未改进前的算法。
The hybrid CDN and P2P network make a better network scalability, adaptability and robustness. The hybrid network provided service quality assurance for the distribution of large-scale heterogeneous network environment users and save server overhead as much as possible. Peer node load balancing is one of the key factors impact on the hybrid CDN and P2P network. The Peer node load balancing, mainly solve the query load imbalance problems.
The existing load balancing algorithms caused by Peer node unbalanced requests, they are algorithm based on replication technology、algorithm based on rumor propagation、algorithm based on the awareness of the routing、algorithm based on the virtual node. Studied the replica placement; Replication algorithms based on the assumption—the future requests will come from the position of the elapsed requests, it lacks theoretical support.
Load balancing of outside local area Peer node algorithm– Improve the CDN-PR replica algorithm. Improve the CDN-PR algorithm is because it makes an assumption that the future requests will come from the position of the elapsed requests, this assumption is correct sometimes, however, it is incorrect sometimes. To support the theory, import the Markov model predicting the position of the future requests, and secondly because the CDN-PR replica algorithm is proper for the CDN Peer node load balancing; Markov forecast the future requests based on the right now state of regional trends, predict future requests in a particular area may happen, provided the basis for the replica position decision making.
Load balancing of local area Peer node algorithm - Improve the request retries algorithm. The improved request retries algorithm compute the node capacity by the Markov Model. It bring the node capacity in the heart beat package. Use the node capacity and TTL select nodes. Node with good performance will service more requests, node with bad performance will service less requests.
Under the Peersim simulation platform, make the simulation and performance analysis on the load balancing of outside local area Peer node algorithm - Improved the CDN-PR replica algorithm. Make the simulation and performance analysis on the load balancing of local area Peer node algorithm - Improved request retries algorithm. The simulation reveal that both of the improved algorithm performance much better than the algorithm which is not improved.
引文
[1]任立勇,王焘,段翰聪,周旭,基于P2P和CDN的流媒体直播系统的设计与实现,计算机科学,第36卷,第7期,2009年7月
[2]詹晓涛,CDN与P2P相结合的流媒体系统设计,电视技术,2009第33卷,第6期
[3]余晓俊,吕智慧,吴杰,张世永,PRTP辅助的CDN-P2P混合模式的流媒体点播平台设计与实现,第2 6卷第7期,2009年7月,计算机应用与软件
[4]张建东,王劲林,一种用于VoIP的负载平衡对等网络架构,计算机工程与应用,2007 , 43 (12)
[5]汤琪亮,基于Chord的P2P网络的负载平衡的研究,复旦大学2006硕士学位论文
[6]卢良进,万健,徐向华,推拉结合的-----P2P直播系统研究与实现,计算机工程,第34卷,第8期,2008年4月
[7]段翰聪,P2P流媒体-----分发技术研究, 2007,电子科技大学博士学位论文
[8]熊伟,谢冬青,焦炳旺,刘洁,一种结构化P2P协议中的负载均衡方法,软件学报,Vol.20,No.3,March 2009
[9]常可沛,基于P2P和CDN技术的分层流媒体系统及其关键问题研究,厦门大学硕士学位论文,2008
[10] El Dick, M.,Pacitti, E.,Kemme, B.,A Highly Robust P2P-CDN Under Large-Scale and Dynamic Participation, Advances in P2P Systems, 2009. AP2PS '09. First International Conference on Issue Date: 11-16 Oct. 2009 On page(s): 180 - 185
[11] Gang Peng , CDN:Content Distribution Network, Department of Computer Science,State University of New York at Stony Brook,Stony Brook, February 1, 2008
[12] Mema Roussopoulos and Mary Baker,Practical load balancing for content requests in peer-to-peer networks ,Computer Science, Distributed Computing Volume 18, Number 6, 421-434
[13] Zhe Xiang,Qian Zhang,Wenwu Zhu,Zhensheng Zhang,Ya-Qin Zhang,Peer-to-peer based multimedia distribution service,Multimedia, IEEE Transactions on ,Issue Date: April 2004 volume: 6 Issue:2 On page(s): 343 - 355
[14] Tim Wauters,Jan Coppens,Bart Dhoedt,Piet Demeester,Dept.Load balancing through efficientdistributed content placement ,2005, of Information Technology(INTEC) Ghent University-IMEC
[15] David R. Karger and Matthias Ruhl,Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems ,Computer Science ,Theory of Computing Systems Volume 39, Number 6, 787-804
[16] M. Mitzenmacher,On the Analysis of Randomized Load Balancing Schemes ,Computer Science,1999, Theory of Computing Systems Volume 32, Number 3, 361-386,
[17] Dahlin, M.,Interpreting stale load information, IEEE Computer Society , Parallel and Distributed Systems, IEEE Transactions on Issue Date: Oct 2000 Volume: 11 Issue:10 On page(s): 1033 - 1047
[18] Kai Shen,Tao Yang,Lingkun Chu,Cluster load balancing for fine-grain network services, Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM Issue Date: 2002 ,On page(s): 51 - 58
[19] Ledlie, J.,Seltzer, M.,Distributed, secure load balancing with skew, heterogeneity and churn, INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE Issue Date: 13-17 March 2005 On page(s): 1419 - 1430 vol. 2
[20] Towards High Performance Peer-to-Peer Content and Resource Sharing Systems, Peter Triantafillou,Chrysanni Xiruhaki,Manolis Koubarakis,Nikolaos Ntarmos,Proceedings of the 2003 CIDR Conference
[21] Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in: Proceedings of the 16th Annual ACM International Conference on Supercomputing, 2002.
[22] Bustos-Jimenez, J.,Caromel, D.,di Costanzo, A.,Leyton, M.,Piquer, J.M.,Balancing active objects on a peer to peer infrastructure, Chilean Computer Science Society, 2005. SCCC 2005. 25th International Conference of the Issue Date: 7-11 Nov. 2005 On page(s): 7 pp.
[23] Tyler Steele , Vivek Vishnumurthy , Paul Francis ,A parameter-free load balancing mechanism for P2P networks,IPTPS'08 Proceedings of the 7th international conference on Peer-to-peer systems USENIX Association Berkeley, CA, USA ?2008
[24] Zhiyong Xu, Bhuyan, L. ,Effective Load Balancing in P2P Systems, Cluster Computing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposium on Issue Date: 16-19 May 2006 On page(s): 81 - 88
[25] Qin Lv ,Pei Cao,Edith Cohen,Kai Li,Scott Shenker,Search and replication in unstructuredpeer-to-peer networks , ICS '02 Proceedings of the 16th international conference on Supercomputing, ACM New York, NY, USA ?2002, Pages 84-95
[26] Zhiyong Xu, Bhuyan, L.,Effective Load Balancing in P2P Systems,Cluster Computing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposium on 16-19 May 2006 On Pages: 81-88
[27] Alqaralleh, B.A.; Wang, C.; Zhou, B.B.; Zomaya, A.Y.; ,Effects of Replica Placement Algorithms on Performance of structured Overlay Networks ,in Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International Pages 1-8
[28] Anwitaman Datta, Roman Schmidt, Karl Aberer, Query-load balancing in structured overlays, ccgrid, Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid '07), 2007, Pages 453-460
[29] Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp and Ion Stoica, Load Balancing in Structured P2P Systems ,Lecture Notes in Computer Science, 2003, Volume 2735/2003, Pages 68-79
[30] MIRCHANDANEY R,T OWSLEY D,STANKOVI C J .Analysis of the effects of delays on load sharing[ J ] . IEEE Transactions on Computers,1989,38 (11) :1513—1525.
[31] Qin Lv,Pei Cao,Edith Cohen,Kai Li,Scott Shenker,Search and replication in unstructured peer-to-peer networks,ICS '02 Proceedings of the 16th international conference on Supercomputing ,ACM New York, NY, USA ?2002 ,Pages 84 - 95
[32] PeerSim website,http://peersim.sourcefarge.net/
[33] Alex Fabrikant, Elias Koutsoupias_, and Christos H. Papadimitriou,Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet ,Lecture Notes in Computer Science, 2002, Volume 2380/2002,781
[2]詹晓涛,CDN与P2P相结合的流媒体系统设计,电视技术,2009第33卷,第6期
[3]余晓俊,吕智慧,吴杰,张世永,PRTP辅助的CDN-P2P混合模式的流媒体点播平台设计与实现,第2 6卷第7期,2009年7月,计算机应用与软件
[4]张建东,王劲林,一种用于VoIP的负载平衡对等网络架构,计算机工程与应用,2007 , 43 (12)
[5]汤琪亮,基于Chord的P2P网络的负载平衡的研究,复旦大学2006硕士学位论文
[6]卢良进,万健,徐向华,推拉结合的-----P2P直播系统研究与实现,计算机工程,第34卷,第8期,2008年4月
[7]段翰聪,P2P流媒体-----分发技术研究, 2007,电子科技大学博士学位论文
[8]熊伟,谢冬青,焦炳旺,刘洁,一种结构化P2P协议中的负载均衡方法,软件学报,Vol.20,No.3,March 2009
[9]常可沛,基于P2P和CDN技术的分层流媒体系统及其关键问题研究,厦门大学硕士学位论文,2008
[10] El Dick, M.,Pacitti, E.,Kemme, B.,A Highly Robust P2P-CDN Under Large-Scale and Dynamic Participation, Advances in P2P Systems, 2009. AP2PS '09. First International Conference on Issue Date: 11-16 Oct. 2009 On page(s): 180 - 185
[11] Gang Peng , CDN:Content Distribution Network, Department of Computer Science,State University of New York at Stony Brook,Stony Brook, February 1, 2008
[12] Mema Roussopoulos and Mary Baker,Practical load balancing for content requests in peer-to-peer networks ,Computer Science, Distributed Computing Volume 18, Number 6, 421-434
[13] Zhe Xiang,Qian Zhang,Wenwu Zhu,Zhensheng Zhang,Ya-Qin Zhang,Peer-to-peer based multimedia distribution service,Multimedia, IEEE Transactions on ,Issue Date: April 2004 volume: 6 Issue:2 On page(s): 343 - 355
[14] Tim Wauters,Jan Coppens,Bart Dhoedt,Piet Demeester,Dept.Load balancing through efficientdistributed content placement ,2005, of Information Technology(INTEC) Ghent University-IMEC
[15] David R. Karger and Matthias Ruhl,Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems ,Computer Science ,Theory of Computing Systems Volume 39, Number 6, 787-804
[16] M. Mitzenmacher,On the Analysis of Randomized Load Balancing Schemes ,Computer Science,1999, Theory of Computing Systems Volume 32, Number 3, 361-386,
[17] Dahlin, M.,Interpreting stale load information, IEEE Computer Society , Parallel and Distributed Systems, IEEE Transactions on Issue Date: Oct 2000 Volume: 11 Issue:10 On page(s): 1033 - 1047
[18] Kai Shen,Tao Yang,Lingkun Chu,Cluster load balancing for fine-grain network services, Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM Issue Date: 2002 ,On page(s): 51 - 58
[19] Ledlie, J.,Seltzer, M.,Distributed, secure load balancing with skew, heterogeneity and churn, INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE Issue Date: 13-17 March 2005 On page(s): 1419 - 1430 vol. 2
[20] Towards High Performance Peer-to-Peer Content and Resource Sharing Systems, Peter Triantafillou,Chrysanni Xiruhaki,Manolis Koubarakis,Nikolaos Ntarmos,Proceedings of the 2003 CIDR Conference
[21] Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in: Proceedings of the 16th Annual ACM International Conference on Supercomputing, 2002.
[22] Bustos-Jimenez, J.,Caromel, D.,di Costanzo, A.,Leyton, M.,Piquer, J.M.,Balancing active objects on a peer to peer infrastructure, Chilean Computer Science Society, 2005. SCCC 2005. 25th International Conference of the Issue Date: 7-11 Nov. 2005 On page(s): 7 pp.
[23] Tyler Steele , Vivek Vishnumurthy , Paul Francis ,A parameter-free load balancing mechanism for P2P networks,IPTPS'08 Proceedings of the 7th international conference on Peer-to-peer systems USENIX Association Berkeley, CA, USA ?2008
[24] Zhiyong Xu, Bhuyan, L. ,Effective Load Balancing in P2P Systems, Cluster Computing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposium on Issue Date: 16-19 May 2006 On page(s): 81 - 88
[25] Qin Lv ,Pei Cao,Edith Cohen,Kai Li,Scott Shenker,Search and replication in unstructuredpeer-to-peer networks , ICS '02 Proceedings of the 16th international conference on Supercomputing, ACM New York, NY, USA ?2002, Pages 84-95
[26] Zhiyong Xu, Bhuyan, L.,Effective Load Balancing in P2P Systems,Cluster Computing and the Grid, 2006. CCGRID 06. Sixth IEEE International Symposium on 16-19 May 2006 On Pages: 81-88
[27] Alqaralleh, B.A.; Wang, C.; Zhou, B.B.; Zomaya, A.Y.; ,Effects of Replica Placement Algorithms on Performance of structured Overlay Networks ,in Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International Pages 1-8
[28] Anwitaman Datta, Roman Schmidt, Karl Aberer, Query-load balancing in structured overlays, ccgrid, Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid '07), 2007, Pages 453-460
[29] Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp and Ion Stoica, Load Balancing in Structured P2P Systems ,Lecture Notes in Computer Science, 2003, Volume 2735/2003, Pages 68-79
[30] MIRCHANDANEY R,T OWSLEY D,STANKOVI C J .Analysis of the effects of delays on load sharing[ J ] . IEEE Transactions on Computers,1989,38 (11) :1513—1525.
[31] Qin Lv,Pei Cao,Edith Cohen,Kai Li,Scott Shenker,Search and replication in unstructured peer-to-peer networks,ICS '02 Proceedings of the 16th international conference on Supercomputing ,ACM New York, NY, USA ?2002 ,Pages 84 - 95
[32] PeerSim website,http://peersim.sourcefarge.net/
[33] Alex Fabrikant, Elias Koutsoupias_, and Christos H. Papadimitriou,Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet ,Lecture Notes in Computer Science, 2002, Volume 2380/2002,781