异质结构化对等网络动态副本访问负载均衡策略研究
|
摘要
对等网络技术打破了传统的“客户/服务器”模式,使网络中所有的结点都处于平等地位,任何两个网络结点之间都能够共享文件、传递消息。对等网络的目的是让一切网络成员享有“自由、平等、互联”的功能,这使得对等网络技术受到越来越多的青睐并取得巨大发展。结构化对等网络假设所有文件访问频率是相同的。然而,在实际应用中,用户对于不同文档的关注程度并不一样。此外,在某些突发情况下,极大部分请求会涌向极少数的结点,形成“访问热点”。倘若出现访问热点的结点没有足够的能力来处理这些超负荷的请求,就很容易造成结点崩溃,导致请求者由于屡次请求没有得到响应而放弃使用对等网络。系统的异质性也会影响到负载的均衡,各结点的性能不同,处理请求的能力也不同。如何充分利用系统的异质性,及时地均衡访问负载,消除访问热点,是一项提高网络效率的关键技术。
国内外有很多学者都对消除热点达到访问负载均衡问题进行了研究,也取得了很大的成效。常用的动态负载均衡热点消除技术有复制技术、虚拟结点技术,其中复制技术最为常用。本文针对国内外在对等网络中采用的各种复制技术进行研究分析,提出一种基于异质结构化对等网络的动态副本策略(DRS)。该策略充分利用每一个结点的处理能力,通过动态副本的设置,提高了网络的负载均衡程度。同时,该算法还采用了动态调整副本策略,结点根据自身的利用率和热点数据访问频率动态决定副本的数量,并发散地分布在网络中。本算法还为副本设定了生命周期,并定期地检查副本的使用情况,从而大大减少了维护开销。
本文通过仿真实验,在p2psim仿真器上对DRS方法进行模拟。实验结果表明,上述方法能够较好地均衡负载,请求报文的丢弃也相对减少,同时,网络的利用率上也得以平衡。
The peer-to-peer network (P2P) broke the traditional client/server mode. In P2P network, all nodes are in the equal state, which make each node can share files and transmit information freely. Due to its character of freedom, equal and inter-connect, people pay more attention to it. Structured P2P networks suppose all the files sharing the equal accessing frequency, but in real situation, all the people's demands to these files are different. In some emergency condition, the web will be flooded by people's request which makes it become the "hotspot". If the web isn't able to deal with these too hot accesses, it may be crashed. People will lose the confidence to P2P and turn to other choice because of the frequently packets-dropping. The heterogeneity of system also causes the imbalance of node's load. The node's character determines its ability to handle the access. In one word, how to make full use of the heterogeneity of system, deal with the imbalance of load, and eliminate the hotspot is one of the most important problems in the P2P network.
Plenty of scholars home and abroad did a lot research on this problem, and some made good results. The popular methods are replication strategy and virtual node strategy. People prefer replication strategy. This paper first compares common load-balancing methods, then, according to the shortage, it put forward a dynamic replication strategy (DRS) based on the heterogeneous structured P2P networks. DRS could resolve the load-imbalance problem, it also take full advantage of the heterogeneity. Besides, DRS decides the number of replicas according to the node's utility and the frequency of the accessing. DRS also proposes the periodically replication managing strategy which aimed to reducing the cost of maintaining the coherence of all the replicas.
In order to analyze the performance of DRS, this paper utilizes p2psim to simulate the strategy on Chord. The results show that it could balance the load to a great extent, and the number of dropping packets is also reduced. The utility of node is balanced as well.
国内外有很多学者都对消除热点达到访问负载均衡问题进行了研究,也取得了很大的成效。常用的动态负载均衡热点消除技术有复制技术、虚拟结点技术,其中复制技术最为常用。本文针对国内外在对等网络中采用的各种复制技术进行研究分析,提出一种基于异质结构化对等网络的动态副本策略(DRS)。该策略充分利用每一个结点的处理能力,通过动态副本的设置,提高了网络的负载均衡程度。同时,该算法还采用了动态调整副本策略,结点根据自身的利用率和热点数据访问频率动态决定副本的数量,并发散地分布在网络中。本算法还为副本设定了生命周期,并定期地检查副本的使用情况,从而大大减少了维护开销。
本文通过仿真实验,在p2psim仿真器上对DRS方法进行模拟。实验结果表明,上述方法能够较好地均衡负载,请求报文的丢弃也相对减少,同时,网络的利用率上也得以平衡。
The peer-to-peer network (P2P) broke the traditional client/server mode. In P2P network, all nodes are in the equal state, which make each node can share files and transmit information freely. Due to its character of freedom, equal and inter-connect, people pay more attention to it. Structured P2P networks suppose all the files sharing the equal accessing frequency, but in real situation, all the people's demands to these files are different. In some emergency condition, the web will be flooded by people's request which makes it become the "hotspot". If the web isn't able to deal with these too hot accesses, it may be crashed. People will lose the confidence to P2P and turn to other choice because of the frequently packets-dropping. The heterogeneity of system also causes the imbalance of node's load. The node's character determines its ability to handle the access. In one word, how to make full use of the heterogeneity of system, deal with the imbalance of load, and eliminate the hotspot is one of the most important problems in the P2P network.
Plenty of scholars home and abroad did a lot research on this problem, and some made good results. The popular methods are replication strategy and virtual node strategy. People prefer replication strategy. This paper first compares common load-balancing methods, then, according to the shortage, it put forward a dynamic replication strategy (DRS) based on the heterogeneous structured P2P networks. DRS could resolve the load-imbalance problem, it also take full advantage of the heterogeneity. Besides, DRS decides the number of replicas according to the node's utility and the frequency of the accessing. DRS also proposes the periodically replication managing strategy which aimed to reducing the cost of maintaining the coherence of all the replicas.
In order to analyze the performance of DRS, this paper utilizes p2psim to simulate the strategy on Chord. The results show that it could balance the load to a great extent, and the number of dropping packets is also reduced. The utility of node is balanced as well.
引文
[1]陈贵海,李振华等.对等网络:结构、 应用与设计.清华大学出版社.2007
[2]刑小良等.P2P技术及其应用.人民邮电出版社.2008
[3]暴励等.P2P技术的应用与研究.电脑开发与应用,2009年22卷
[4]詹晓强,胡德敏.基于P2P系统的动态负载均衡算法.计算机工程与设计,2009年30期
[5]肖斐,邓亚平等.一种结构化P2P负载均衡策略的研究.微计算机信息,2009年第25卷
[6]黄李健,王建新等.P2P搜索技术研究.中国新通信,2008年12期
[7]李莉,韩慧健.无结构P2P网络资源搜索方法研究.网络与通信,2007年第1期
[8]STOICAI,MORRIS R,KARGER D,et al.Chord:a scalable peer-to-peer lookup service for Internet applications.Proceedings of ACM SIGCOMM.San Diego,2001
[9]D.R.Karger,M.F.Kaashoek.Koorde:A simple degree-optimal distributed hash table.In Proc.2nd IPTPS,Berkeley,CA,Feb.2003,Feb.10 2003.
[10]http://www.lwlm.com
[11]http://pdos.csail.mit.edu/p2psim/howto.html
[12]http://blog.csdn.net/kikikind/archive/2008/08/03/2760576.aspx
[13]Erich Gammma等著,李英军等译.设计模式--可复用面向对象软件的基础.机械工业出版社.2000
[14]邵一峰.结构化对等网络中负载平衡技术研究.上海交通大学硕士学位论文.2007
[15]陈晨.结构化对等网络中访问热点引起的负载均衡技术研究.北京交通大学硕士学位论文.2008
[16]Rowstron A I T,Druschel P.Pastry.Scalable,distributedobject location and routing for large-scale peer-to-peer systems.Proceedings of IFIP/ACM International Conferenceon Distributed Systems Platforms(Middleware),New York:ACM Press,2001
[17]朱娴淑.结构化对等网中基于复制的访问热点消除方法研究.湖南大学硕士论文.2007
[18]Lv Q,CaD P,Cohen E,et al.Search and Replication in Unstructured Peer-to-Peer Networks.In proceedings of 16th ACM International Conference on Supercomputing.New York:ACM Press,2002
[19]Bassam A.Alqaralleh,Chen Wang,Bing Bing Zhou,Albert Y.Zomaya.Effects of Replica Placement Algorithms on Performance of structured Overlay Networks.In proceedings of IPDPS,2007
[20]A.Rowstron,P.Druschel.Storage management and caching in PAST,a large-scale,persistent peer-to-peer storage utility.In Proceedings of the 18th ACM Symposium on Operating Systems Principles,Chateau Lake Louise,Banff,Canada,October 2001
[21]F.Dabek,M.F.Kaashoek,D.Karger,R.Morris,I.Stoica.Wide-area cooperative storage with CFS.In Proceedings of the 18th ACM Symposium on Operating Systems Principles,Chateau Lake Louise,Banff,Canada,October 2001
[22]Gopalakrishnan V,Silaghi B,Bhattacharjee B,et al.Adaptive replication in peer-to-peer systems.In:Proc of 24th ICDCS.Japan:IEEE Press,2004
[23]Xu Z,Bhuyan L.Effective Load Balancing in P2P Systems.In:Proc of the Sixth IEEE International Symposium on Cluster Computing and the Grid.Washington,DC,USA:IEEE Computer Society,2006
[24]Yamamoto H,maruta D,Oie Y.Replication Methods for Load Balancing on Distributed Storages in P2P Networks.In:Proc of the 2005 Symposium on Applications and the Internet.Japan:IEEE Press,2005
[25]Predrag Knezevic.Andreas Wombacher.Thomas Risse.DHT-based Self-adapting Replication Protocol for Achieving High Data Availability.In International Conference on Singal-image Technology and Internetbased Systems(SITIS),2006
[26]Bassam A.Alqaralleh,Chen Wang,Bing Bing Zhou,Albert Y.Zomaya.Effects of Replica Placement Algorithms on Performance of structured Overlay Networks.IEEE International Parallel and Distributed Processing Symposium,2007
[27]Ananth Rao,Karthik Lakshminarayanan,Sonesh Surana,Richard Karp,Ion Stocia.Load Balancing in Structured P2P Systems.in:Proceedings of the IPTPS,February,2003
[28]朱承,刘忠,张维明等.结构化P2P网络中基于流言传播的负载均衡.通信学报,2004,第25卷第4期
[29]罗慧君,徐洁,赖坤锋.结构化P2P自适应混合负载均衡策略.微计算机信息,2009年3月
[30]Anwitaman Datta,Roman Schmidt,Karl Aberer.Query-load balancing in structured overlays.Seventh IEEE International Symposium on Cluster Computing and the Grid(CCGrid),2007
[31]V.Gopalakrishnan,B.Silaghi,B.Bhattacharjee,P.Keleher.Adaptive replication in peer-to-peer systems Distributed Computing Systems.In Proceedings 24th International Conference,2004
[32]Qin Lv,Pei Cao,Edith Cohen,Kai Li,Scott Shenker.Search and Replication in Unstructured P2P Networks.In:Proceedings of the 16th ACM International Conference on Supercomputing(ICS 02),New York,USA,2002
[2]刑小良等.P2P技术及其应用.人民邮电出版社.2008
[3]暴励等.P2P技术的应用与研究.电脑开发与应用,2009年22卷
[4]詹晓强,胡德敏.基于P2P系统的动态负载均衡算法.计算机工程与设计,2009年30期
[5]肖斐,邓亚平等.一种结构化P2P负载均衡策略的研究.微计算机信息,2009年第25卷
[6]黄李健,王建新等.P2P搜索技术研究.中国新通信,2008年12期
[7]李莉,韩慧健.无结构P2P网络资源搜索方法研究.网络与通信,2007年第1期
[8]STOICAI,MORRIS R,KARGER D,et al.Chord:a scalable peer-to-peer lookup service for Internet applications.Proceedings of ACM SIGCOMM.San Diego,2001
[9]D.R.Karger,M.F.Kaashoek.Koorde:A simple degree-optimal distributed hash table.In Proc.2nd IPTPS,Berkeley,CA,Feb.2003,Feb.10 2003.
[10]http://www.lwlm.com
[11]http://pdos.csail.mit.edu/p2psim/howto.html
[12]http://blog.csdn.net/kikikind/archive/2008/08/03/2760576.aspx
[13]Erich Gammma等著,李英军等译.设计模式--可复用面向对象软件的基础.机械工业出版社.2000
[14]邵一峰.结构化对等网络中负载平衡技术研究.上海交通大学硕士学位论文.2007
[15]陈晨.结构化对等网络中访问热点引起的负载均衡技术研究.北京交通大学硕士学位论文.2008
[16]Rowstron A I T,Druschel P.Pastry.Scalable,distributedobject location and routing for large-scale peer-to-peer systems.Proceedings of IFIP/ACM International Conferenceon Distributed Systems Platforms(Middleware),New York:ACM Press,2001
[17]朱娴淑.结构化对等网中基于复制的访问热点消除方法研究.湖南大学硕士论文.2007
[18]Lv Q,CaD P,Cohen E,et al.Search and Replication in Unstructured Peer-to-Peer Networks.In proceedings of 16th ACM International Conference on Supercomputing.New York:ACM Press,2002
[19]Bassam A.Alqaralleh,Chen Wang,Bing Bing Zhou,Albert Y.Zomaya.Effects of Replica Placement Algorithms on Performance of structured Overlay Networks.In proceedings of IPDPS,2007
[20]A.Rowstron,P.Druschel.Storage management and caching in PAST,a large-scale,persistent peer-to-peer storage utility.In Proceedings of the 18th ACM Symposium on Operating Systems Principles,Chateau Lake Louise,Banff,Canada,October 2001
[21]F.Dabek,M.F.Kaashoek,D.Karger,R.Morris,I.Stoica.Wide-area cooperative storage with CFS.In Proceedings of the 18th ACM Symposium on Operating Systems Principles,Chateau Lake Louise,Banff,Canada,October 2001
[22]Gopalakrishnan V,Silaghi B,Bhattacharjee B,et al.Adaptive replication in peer-to-peer systems.In:Proc of 24th ICDCS.Japan:IEEE Press,2004
[23]Xu Z,Bhuyan L.Effective Load Balancing in P2P Systems.In:Proc of the Sixth IEEE International Symposium on Cluster Computing and the Grid.Washington,DC,USA:IEEE Computer Society,2006
[24]Yamamoto H,maruta D,Oie Y.Replication Methods for Load Balancing on Distributed Storages in P2P Networks.In:Proc of the 2005 Symposium on Applications and the Internet.Japan:IEEE Press,2005
[25]Predrag Knezevic.Andreas Wombacher.Thomas Risse.DHT-based Self-adapting Replication Protocol for Achieving High Data Availability.In International Conference on Singal-image Technology and Internetbased Systems(SITIS),2006
[26]Bassam A.Alqaralleh,Chen Wang,Bing Bing Zhou,Albert Y.Zomaya.Effects of Replica Placement Algorithms on Performance of structured Overlay Networks.IEEE International Parallel and Distributed Processing Symposium,2007
[27]Ananth Rao,Karthik Lakshminarayanan,Sonesh Surana,Richard Karp,Ion Stocia.Load Balancing in Structured P2P Systems.in:Proceedings of the IPTPS,February,2003
[28]朱承,刘忠,张维明等.结构化P2P网络中基于流言传播的负载均衡.通信学报,2004,第25卷第4期
[29]罗慧君,徐洁,赖坤锋.结构化P2P自适应混合负载均衡策略.微计算机信息,2009年3月
[30]Anwitaman Datta,Roman Schmidt,Karl Aberer.Query-load balancing in structured overlays.Seventh IEEE International Symposium on Cluster Computing and the Grid(CCGrid),2007
[31]V.Gopalakrishnan,B.Silaghi,B.Bhattacharjee,P.Keleher.Adaptive replication in peer-to-peer systems Distributed Computing Systems.In Proceedings 24th International Conference,2004
[32]Qin Lv,Pei Cao,Edith Cohen,Kai Li,Scott Shenker.Search and Replication in Unstructured P2P Networks.In:Proceedings of the 16th ACM International Conference on Supercomputing(ICS 02),New York,USA,2002