簡易檢索 / 詳目顯示

研究生: 梁守銘
Shou-ming Liang
論文名稱: 結構化疊加網路負載平衡方法之研究
Effective Migration-based Load Balancing for Distributed Hash Tables
指導教授: 陳秋華
Chyou-Hwa Chen
口試委員: 馮輝文
none
金台齡
none
學位類別: 碩士
Master
系所名稱: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
論文出版年: 2007
畢業學年度: 95
語文別: 中文
論文頁數: 31
中文關鍵詞: 負載平衡
外文關鍵詞: Load Balancing
相關次數: 點閱:187下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

介紹一種以Chord 為基礎的P2P protocol中,如何能以更有效的負載平衡使得
搜尋的資料能快速有效率找到所在的位置。
我們考慮以DHT ID-space [11 ] 的邏輯環狀網路為模型,在環狀網路的節點負責保有一些物件而每個節點分別管理環狀網路的某些部分,稱為區間 (zone) 而每個節點所負責的區間是不會重疊的。
以虛擬伺服器 (Virtual server) 為基本架構的負載平衡演算法包括M2M , k-choice.這2個演算法會根據目前區間負載的情形來達到負載平衡。


We consider the logical ring as the model for DHT ID-space[11]. Peers or nodes are placed on the ring and are responsible for objects fallen in the non-overlapping parts of the ring, called zones. Many distributed join algorithms to partition the ID-space between the nodes have been studied[11].
Virtual server-based Load balancing schemes include M2M, K-choices.
M2M and K-choices actively migrate the VS among nodes from time to time so that nodes are responsible for different zones according to current load situation on the ring to achieve load balance.

摘要I ABSTRACTII 誌謝III TABLE OF CONTENTSIV LIST OF FIGURESVI LIST OF TABLESVII 1INTRODUCTION1 1.1MOTIVATION1 2RELATED WORKS2 2.1CHORD PROTOCOL2 2.1.1Node Joins2 2.1.2Node lookups4 2.1.3Virtual Server6 3PROTOCOLS FOR EFFECTIVE MIGRATION-BASED LOAD BALANCING IN P2P SYSTEMS8 3.1ORIGINAL M2M ALGORITHM8 3.2K-CHOICE ALGORITHM10 3.3EFFECTIVE MIGRATION M2M ALGORITHM (M2M-D)11 4SIMULATION RESULTS12 4.1SIMULATION ENVIRONMENT12 4.2SIMULATION RESULTS13 4.2.1System performance comparison between our scheme and Original M2M Success Ratio Higher Channel Entrance Factor13 4.2.2System overhead comparison: Number of VS14 4.2.3System overhead comparison: Average Route Length15 4.2.4System overhead comparison: Stabilization Overhead16 4.2.5Robustness of our scheme to shifting workloads: success ratio17 4.2.6Robustness of our scheme to shifting workloads: stabilization overhead18 4.2.7Robustness of our scheme to shifting workloads: Average number of VS moved19 4.2.8Performance impact of Churn20 4.2.9The basic effect of our algorithm, and the necessity of emergency action21 4.2.10Effectiveness of the algorithms to support node and workload heterogeneity: node capacity heterogeneity22 4.2.11Performance for load balancing storage objects26 4.2.12The number of virtual servers necessary at various system utilizations28 4.2.13Performance for load balancing storage objects :the effect of nonuniform object arrival patterns, showing that our algorithm is robust29 5DISCUSSIONS AND CONCLUSIONS30 5.1CONCLUSION30 5.2FUTURE WORKS30 REFERENCES31

1.V. Stemann, Parallel balanced allocations,” in Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996.
2.M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen. Parallel randomized load balancing. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 238--247, 1995
3.P. Berenbrink, F. Meyer auf der Heide, and K. Schroder, Allocating weighted jobs in parallel,” ACM Trans. Comput. Syst., 32(3), pp. 1703-1739, 1999.
4.On the Effectiveness of Migration-based Load Balancing Strategies in DHT Systems, Di Wu, Ye Tian and Kam-Wing Ng, IEEE ICCCN 06
5."Practical Load Balancing for Content Requests in Peer-to-Peer Networks", Mema Roussopoulos and Mary Baker, Distributed Computing, Vol. 18, No. 6, June 2006
6.Minimizing Churn in Distributed Systems", P. Brighten Goedfrey, Scott Shenker, and Ion Stoica, to appear in Proceedings of ACM SIGCOMM'06, Pisa, Italy, September, 2006
7.D. Leonard, Z. Yao, V. Rai, and D. Loguinov, "On Lifetime-Based Node Failure and Stochastic Resilience of Decentralized Peer-to-Peer Networks," To Appear in IEEE/ACM Transactions on Networking, vol. 15, no. 5, October 2007
8.Distributed, Secure Load Balancing with Skew, heterogeneity, and Churn Jonathan Ledlie and Margo Seltzer,In Proceedings of IEEE INFOCOM 2005, March 2005
9.A performance vs. cost framework for evaluating DHT design tradeoffs under churn, Jinyang Li, Jeremy Stribling, Robert Morris, M. Frans Kaashoek and Thomer M. Gil, INFOCOM 05
10.1 Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications ,Ion Stoicay , Robert Morrisz, David Liben-Nowellz, David R. Kargerz, M. Frans Kaashoekz, Frank Dabekz,Hari Balakrishnan
11.Load Balancing in Structured P2P Systems , Ananth Rao Karthik Lakshminarayanan Sonesh Surana Richard Karp Ion Stoica
12.Load Balancing in Dynamic Structured P2P Systems , Brighten Godfrey Karthik Lakshminarayanan Sonesh Surana Richard Karp Ion Stoica
13.X. Wang and D. Loguinov, "Load-Balancing Performance of Consistent Hashing: Asymptotic Analysis of Random Node Join," IEEE/ACM Transactions on Networking, vol. 15, no. 5, October 2007

QR CODE