DHT网络中一种基于虚拟服务器拆分的负载平衡算法

doi:10.3969/j.issn.1000-436X.2013.12.007

摘要/Abstract

摘要：

分析比较了目前DHT网络中基于虚拟服务器（virtual server）的负载平衡算法，根据节点间间距的分布概率，建立了基于虚拟服务器的DHT网络负载分布数学模型，详细分析和计算了DHT网络中单虚拟服务器问题（SVSP）发生的概率，提出了一种基于虚拟服务器拆分的负载平衡算法（VSSLBA），仿真实验验证了理论推导的正确性与算法方案的有效性。

关键词: DHT网络, 虚拟服务器, 负载平衡, SVSP, 虚拟服务器拆分算法

Abstract:

The method using virtual servers for balancing the load in DHT-Based P2P systems was studied.The load distribution in DHT-based overlay network using virtual servers were modeled,the occurrence probability of single vir-tual server problem (SVSP) was analyzed and computed in details,and a novel VS-split load balancing algorithm (VSSLBA) was proposed to deal with the SVSP by splitting virtual server into small ones.Simulations verify the cor-rectness of probability analysis and the performance of VSSLBA.

Key words: DHT-based network, virtual server, load balance, single virtual server problem, VS-split load balancing al-gorithm

杨磊,李仁发,柳石,陈志兴,李肯立. DHT网络中一种基于虚拟服务器拆分的负载平衡算法[J]. 通信学报, 2013, 34(12): 60-70.

Lei YANG,Ren-fa LI,Shi LIU,Zhi-xing CHEN,Ken-li LI. VS-split load balancing algorithm in DHT-based P2P systems[J]. Journal on Communications, 2013, 34(12): 60-70.

图/表 15

图1

表1

表2

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 22

[1]	STOICA I , MORRIS R , KARGER D , et al. Chord:a scalable peer-to-peer lookup service for internet applications[A]. Proc of the ACM SIGCOMM '01 Conference on Applications,Technologies,Ar-chitectures,and Protocols for COMPUTER Communications[C]. San Diego, 2001.149-160.
[2]	DABEK F , KAASHOEK M F , KARGER D , et al. Wide-area coopera-tive storage with CFS[A]. Proc of the 18th ACM Symp on Operating System Principles(SOSP)[C]. Banff, 2001.202-215.
[3]	ROWSTRON A , DRUSCHEL P . Pastry:scalable,distributed object location and routing for large-scale peer-to-peer systems[A]. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware)[C]. Heidelberg, 2001.329-350.
[4]	DRUSCHEL P , ROWSTRON A . PAST:a large-scale,persistent peer-to-peer storage utility[A]. Proc of the Eighth Workshop o Hot Topics in Operating Systems[C]. Schoss Elmau, 2001.75-80.
[5]	ZHAO B Y , KUBIATOWICZ J D , JOSEPH A D . Tapestry:an Infrastruc-ture for Faulttolerance Wide-Area Location and Routing[R]. U C Berkeley Technical Report UCB//CSD-01-1141,Berkeley, 2001.329-350.
[6]	ANANTH R , LAKSHMINARAYANAN K , SURANA S , et al. Load balancing in structured P2Psystems[A]. Proc IPTPS[C]. 2003.68-79.
[7]	GODFREY B , LAKSHMINARAYANAN K , SURANA S , et al. Load balancing in dynamic structured P2P systems[A]. Proceedings of IEEE INFOCOM[C]. 2003.2253-2262.
[8]	GODFREY P , STOICA I . Heterogeneity and load balance in distri-buted hash tables[A]. Proceedings of IEEE INFOCOM[C]. 2005.596-606.
[9]	ZHU Y W , HU Y M . Efficient,proximity-aware load balancing for DHT-based P2P systems[J]. IEEE Transactions on Parallel and Distri-buted Systems, 2005,16(4):349-361.
[10]	WANG X H , PENG Y X , LI D S . An efficient load balancin method for constant degree P2P systems[A]. Computer Design and Applica-tions (ICCDA),2010 International Conference on[C]. Qinhuangdao,China, 2013.25-27.
[11]	HSIAO H C , LIAO H . Load balance with imperfect information in structured peer-to-peer Systems[J]. IEEE Trans Parallel Disturb Sys-tem, 2011,22(4):634-649.
[12]	GUPTA A , AGRAWAL D , A ABBADI E . Approximate range selec-tion queries in peer-to-peer systems[A]. Proceedings of the First Biennial Conference on Innovative Data Systems Research[C]. Asi-lomar, 2003.
[13]	CAI M , FRANK M , CHEN J , et al. MAAN:a multi-attribute ad-dressable network for grid information services[J]. Journal of Grid Computing, 2004,2(1):3-14.
[14]	MAYMOUNKOV P , MAZIERES D . Kademlia:a peer-to-peer infor-mation system based on the XOR metric[A]. Proceedings f the 1st International Workshop on Peer-to-Peer Systems(IPTPS'02)[C]. 2002.53-65.
[15]	KRISHNAMURTHY S , LANSARY S E , ERIK A , et al. An analytical study of a structured overlay in the presence of dynamicmembership[J]. IEEE/ACM Transactions on Networking(TON), 2008,16(4):814-825.
[16]	聂晓文，卢显良，周旭等. DHT 算法基本统计特性及应用[J]. 四川大学学报(工程科学版)， 2009,41(5):170-175. NIE X W , LU X L , ZHOU X , et al. Elementary statistical properties in DHT and their application[J]. Journal of Sichuan Universi-ty(Engineering Science Edition), 2009,41(5):170-175.
[17]	聂晓文，卢显良，孟江涛等. 一类 DHT 算法中负载的概率分布[J]. 计算机应用研究， 2009,26(10):3763-3766. NIE X W , LU X L , MENG J T , et al. Probabilistic distribution of load in one class of DHT[J]. Application Research of Computers, 2009,26(10):3763-3766.
[18]	肖波，聂晓文，侯孟书 . DHT 网络规模估计算法的定量分析与设计[J]. 电子科技大学学报， 2011,40(2):261-266. XIAO B , NIE X W , HOU M S . Quantitative analysis and design of an estimation algorithm on DHT network size[J]. Journal of University of Electronic Science and Technology of China, 2011,40(2):261-266.
[19]	聂晓文 . DHT覆盖网若干基础性问题研究[D]. 西安：电子科技大学， 2009.37-45. NIE X W . Research on Several Fundamental Problems of DHTOver-lay[D]. Xi'an:University of Electronic Science and Technology of China, 2009.37-45.
[20]	BUSTAMANTE F E , QIAO Y . Friendships that last:peer lifespan and its role in P2P protocols,in Web content caching and distribution[A]. Proceedings of the 8th International Workshop[C]. 2004.233-246.
[21]	STUTZBACH D , REJAIE R . Understanding chum in peer-to-peer networks[A]. Proceedings of the 6th ACM sJGCoMM Conference On Internet Measurement Rio de Janeriro[C]. Brazil, 2006.89-202.
[22]	Group of Prof Zitterbart Oversim[EB/OL]. , 2012.

k的值	x/E(x)的值	p的值
2	1/5	0.629 1
2	2/5	0.363 5
2	3/5	0.199 6
2	4/5	0.106 0
3	1/5	0.470 8
3	2/5	0.175 5
3	3/5	0.055 9
3	4/5	0.016 0
5	1/5	0.243 3
5	2/5	0.030 1
5	3/5	0.002 2
5	4/5	0.000 1
6	1/5	0.168 0
6	2/5	0.010 8
6	3/5	0.000 3
6	4/5	5.107 9×10^{- 6}

k的值	能力分布范围（x/E(x)）	P(0)的值
2	1/5~4/5	2.900 5×10^{- 97}
2	3/5~4/5	4.583 0×10^{- 37}
2	4/5	4.664 0×10^{- 25}
3	1/5~4/5	9.504 9×10^{- 50}
3	3/5~4/5	1.007 6×10^{- 8}
3	4/5	3.144 5×10^{- 4}
5	1/5~4/5	1.206 0×10^{- 17}
5	3/5~4/5	0.562 4
5	4/5	0.951 2
6	1/5~4/5	2.566 6×10^{- 11}
6	3/5~4/5	0.926 6
6	4/5	0.997 5