期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

A P2P Load Balancing-Supported ID Management Algorithm

A P2P Load Balancing-Supported ID Management Algorithm
原文传递
导出
摘要 Load balancing is a critical issue in peer-to-peer networks. DHT （distributed hash tables） do not evenly partition the hash-function range, and some nodes get a larger portion of it. The loads of some nodes are as much as O（log n） times the average. In this paper, a low-cost, decentralized algorithm for ID allocation with complete knowledge in DHT-based system is proposed. It can adjust system load on nodes’ departure. It is proved that the ratio of longest arc to shortest arc is no more than 4 with high probability when network scale increases non-strictly. When network scale decreases from one stable state to another, algorithm can repair the unevenness of nodes distribution. The performance is analyzed in simulation. Simulating results show that updating messages only occupy a little of network bandwidth. Load balancing is a critical issue in peer-to-peer networks. DHT （distributed hash tables） do not evenly partition the hash-function range, and some nodes get a larger portion of it. The loads of some nodes are as much as O（log n） times the average. In this paper, a low-cost, decentralized algorithm for ID allocation with complete knowledge in DHT-based system is proposed. It can adjust system load on nodes’ departure. It is proved that the ratio of longest arc to shortest arc is no more than 4 with high probability when network scale increases non-strictly. When network scale decreases from one stable state to another, algorithm can repair the unevenness of nodes distribution. The performance is analyzed in simulation. Simulating results show that updating messages only occupy a little of network bandwidth.
作者 WANG Bin SHEN Qingguo
机构地区 Institute of Communications Engineering
出处 《Wuhan University Journal of Natural Sciences》 CAS 2011年第4期293-300,共8页 武汉大学学报（自然科学英文版）
关键词 P2P load balance ID allocation DHT （distributed hash tables） P2P load balance ID allocation DHT （distributed hash tables）
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献13

  • 1Karger D, Lehman E, Leighton T, et al. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web [C]//Proc 29th Annual ACM Symposium on Theory of Computing, New York: ACM Press, 1997.
  • 2Naor M, Wieder U. Novel architectures for P2P applications: The continuous-discrete approach [J]//ACM Transactions on Algorithms, 2007, 3(3): 50-59.
  • 3VMerie K, Jared S. Choosing a random peer [C][/Proc 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), New York: ACM Press, 2004: 125- 130.
  • 4聂晓文,卢显良,李梁,徐海湄,蒲汛.DHT负载均衡的必要性[J].计算机科学,2009,36(9):92-95. 被引量：1
  • 5Wang Xiaoming, Dmitri L. Load-balancing performance of consistent hashing: asymptotic analysis of random node join [J].IEEE/ACM Transactions on Networking, 2007, 15(4): 892-905.
  • 6Adler M, Halperin E, Karp R M, et al. A stochastic process on the hypercube with applications to peer-to-peer networks [C]//Proc 35nd ACM Symposium on Theory of Computing (STOC'03), New York: ACM Press, 2003: 575-584.
  • 7Ittai A, Baruch A, Yossi A, et al. A generic scheme for building overlay networks in adversarial scenarios [C]//ProcInternational Parallel and Distributed Processing Symposium (IPDPS'03), Washington D C: IEEE Computer Society, 2003.
  • 8Karger D, Ruhl M. Simple efficient load balancing algorithms for peer-to-peer systems [C]/IProc 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'04), New York: ACM Press, 2004.
  • 9Kenthapadi K. Decentralized algorithms using both local and random probes for P2P load balancing [C]//Proc 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'05), New York: ACM Press, 2005: 135-144.
  • 10Gurmeet S M. Balanced binary trees for ID management and load balance in distributed hash tables [C]llProc 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), New York: ACM Press, 2004: 197-205.

二级参考文献14

  • 1Zhao B Y,Kubiatowicz J D,Joseph A D.Tapestry:An Infrastructure for Fault-tolerant Wide-area Location[D].University of California at Berkeley,2001.
  • 2Stoica l,et al.Chord:a scalable peer-to-peer lookup protocol for Internet applications[J].Networking,IEEE/ACM Transactions,2003,11 (1):17-32.
  • 3Rowstron A I T,Druschel P.Pastry:Scalable,Decentralized Object Location,and Routing for Large-Scale Peer-to-Peer Systems[C]//Proceedings of the IFIP/ACM International Conference on Distributed Systcms Platforms Heidelberg.Springer-Verlag,2001.
  • 4Krishnamurthy S,et al.A Statistical Theory of Chord under Churn[C]//Proceedings of The 4th Annual International Workshop on Peer-To-Peer Systems (IPTPS 05).Ithaca,NY,USA,2005.
  • 5Mo Z,Yafei D,Xiaoming L.A measurement study of the structured overlay network in P2P file-sharing systems[M].Hindawi Publishing Corp,2007.
  • 6Silvia Bianchi S S,Felber P,Kropf P.Adaptive Load Balancing for DHT Lookups[C]//Proceedings of the 15th International Conference on Computer Communications and Networks (ICCCN'06).Arlington,VA,October 2006.
  • 7Datta A,Schmidt R,Aberer K.Query-load balancing in structured overlays[C]//Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGRID'07).Riode Janeiro,Brazil,2007.
  • 8Baeza-Yates R,Ribeiro-Neto B.Modern Information Retrieval[M].Addison Wesley,1999.
  • 9Saroiu S G,Krishna,Steven G.A Measurement Study of Peerto-Peer File Sharing Systems[C]//Proceedings of Multimedia Computing and Networking 2002 (MMCN'02).2002.
  • 10Rhea S,et al.Handling Churn in a DHT[D].EECS Department,University of California,Berkeley,2003.
Wuhan University Journal of Natural Sciences
2011年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部