進階搜尋


下載電子全文  
系統識別號 U0026-3105201012362300
論文名稱(中文) 結構疊蓋式系統上利用不完整資訊的負載平衡演算法
論文名稱(英文) Load Balance with Imperfect Information in Structured Peer-to-Peer Systems
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 98
學期 2
出版年 99
研究生(中文) 陳思達
研究生(英文) Ssu-Ta Chen
學號 p7697104
學位類別 碩士
語文別 英文
論文頁數 49頁
口試委員 口試委員-陳宗禧
口試委員-張燕光
口試委員-謝孫源
口試委員-李強
指導教授-蕭宏章
中文關鍵字 結構疊蓋式網路(structured peer-to-peer network)  負載平衡(load balance)  不同性質(heterogeneity) 
英文關鍵字 structured peer-to-peer network  load balance  heterogeneity 
學科別分類
中文摘要 隨著虛擬服務器(virtual server)的概念,加入到不同性質(heterogeneity)的結構疊蓋
式網路(structured peer-to-peer network)的節點(peer)可以擁有一些虛擬服務器,然後這些
節點可以靠著搬移這些虛擬服務器來分配這些負載,而每個節點的負載又會根據他的
能力來做分配。現存且設計在不同性質的結構疊蓋式網路中的分散式負載平衡演算法
可能需要建立一個輔助的網路來獲得全部的資訊,又或者是需要疊蓋式網路中階級式
(hierarchical)的特質。這裏我們呈現一種新的負載平衡(load balance)演算法且不需要輔
助的網路以及疊蓋式網路的幾何性,也就是這個演算法對於每個加入到系統的節點來
說,只需要根據其中的部分資訊來去估計系統中節點能力的機率分布以及虛擬服務器
負載的機率分布。那我們有了這些資訊後,進而能夠同時去計算每個節點所預計該負
擔的負載和應該重新配置的負載。接下來我們透過大量的模擬來去對我們的方法做一
個評估。這些模擬結果顯示出
(1) 我們的設計對於集中式的方法是可以做比較的,而且根據負載不平衡因素(load
imbalance factor)、虛擬服務器的搬移成本、以及訊息的量,我們的方法勝過一些
階級式的方法;
(2) 在一些現存的解決方法中,因為一些節點需要去執行負載平衡的演算法,因此造
成另外的不平衡,然而我們的方法在這方面所造成的額外負載,每個節點幾乎都
是一樣;
(3) 我們的方法在動態的環境下也適用,也就是節點可以自由的加入及離開這個系統,
並且隨著時間的過去,節點的能力以及虛擬服務器的負載也可以變動。
英文摘要 With the notion of virtual servers, peers participating in a heterogeneous, struc-
tured peer-to-peer (P2P) network may host di®erent numbers of virtual servers, and
by migrating virtual servers, the peers can balance their loads proportional to their
capacities. The existing and decentralized load balance algorithms designed for the
heterogeneous, structured P2P networks either explicitly construct auxiliary networks
to manipulate global information or implicitly demand the P2P substrates organized
in a hierarchical fashion. Without relying on any auxiliary networks and independent
of the geometry of the P2P substrates, we present in this thesis a novel load balanc-
ing algorithm that is unique in that each participating peer is based on the partial
knowledge of the system to estimate the probability distributions of the capacities of
peers and the loads of virtual servers, resulting in imperfect knowledge of the system
state. Having the imperfect system state, the peers compute their expected loads and
reallocate their loads in parallel. Together with the rigorous performance analysis for
our estimation of the system state, we assess our proposal through extensive simula-
tions. The simulation results reveal the following: (1) our design is comparable with
the centralized solution and outperforms the hierarchical approach in terms of the load
imbalance factor, the movement cost of virtual servers, and/or the protocol message
overheads; (2) while the existing solutions introduce hotspots to the system due to
the manipulation of their load balancing algorithms and thus generate another load
imbalance issue, each peer in our proposal experiences the nearly identical workload in
performing our load balancing algorithm; and (3) our proposal adapts well to dynamic
environments in which peers may come and go freely, and/or the capacities of partici-
pating peers and the loads of virtual servers vary over time.
論文目次 1 Introduction 1
1.1 Roadmap . . . . . . . . . . . . . . . . . . . . . . 5
2 Related Work 6
3 Our Proposal 9
3.1 Algorithm Sketch. . . . . . . . . . . . . . . . . . 9
3.2 Sampling Based on Random Walk. . . . . . . . . . . 14
3.3 Approximating Pr(X) and Pr(Y). . . . . . . . . . . 18
3.3.1 Computing fPr(X). . . . . . . . . . . . . . . 18
3.3.2 Computing fPr(Y). . . . . . . . . . . . . . . 23
3.4 Computing FX-(x) and FY+(y) . . . . . . . . . . . 24
3.5 Estimating |N| and |V| . . . . . . . . . . . . . . 24
4 Simulations 26
4.1 Experimental Setting . . . . . . . . . . . . . . . 26
4.2 Comparative Study. . . . . . . . . . . . . . . . . 28
4.2.1 The Load Imbalance Factor . . . . . . . . . . 28
4.2.2 The Movement Cost . . . . . . . . . . . . . . 30
4.2.3 The Protocol Message Overhead . . . . . . . . 31
4.3 The Effects of System Parameters . . . . . . . . . 33
4.3.1 The Effect of Varying φ and φ . . . . . . . 34
4.4 The Effect of Varying ε . . . . . . . . . . . . . 35
4.4.1 The Effect of Varying Random Walk Steps . . . 36
4.4.2 The Effect of Different Algorithmic Rounds . 37
4.5 System Dynamics. . . . . . . . . . . . . . . . . . 39
5 Summary and Future Work 43
參考文獻 [1] M. Bienkowski, M. Korzeniowski, and F. Meyer auf der Heide. Dynamic Load
Balancing in Distributed Hash Tables. In Proc. 4th Int'l Workshop Peer-to-Peer
Systems (IPTPS'04), pages 217{225, Feb. 2005.
[2] T. L. Casavant and J. G. Kuhl. A Taxonomy of Scheduling in General-Purpose
Distributed Computing Systems. IEEE Trans. Software Eng., 14(2):141{154, Feb.
1988.
[3] C. Chen and K.-C. Tsai. The Server Reassignment Problem for Load Balancing
in Structured P2P Systems. IEEE Trans. Parallel Distrib. Syst., 12(2):234{246,
Feb. 2008.
[4] H. Cherno®. A Measure of Asymptotic E±ciency for Tests of a Hypothesis Based
on the Sum of Observations. Ann. Math. Statist., 23(4):493{507, 1952.
[5] F. Dabek, M. F. Kaashoek, David Karger, R. Morris, and I. Stoica. Wide-Area
Cooperative Storage with CFS. In Proc. 18th ACM Symp. Operating Systems
Principles (SOSP'01), pages 202{215, Oct. 2001.
[6] P. Diaconis and D. Stroock. Geometric Bounds for Eigenvalues of Markov Chains.
Ann. Appl. Probab., 1(1):36{61, Feb. 1991.
[7] D. Eastlake and P. Jones. US Secure Hash Algorithm 1 (SHA1). RFC 3174, Sept.
2001.
[8] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the
Theory of NP-Completeness. W.H. Freeman and Co., 1979.
[9] B. Godfrey and I. Stoica. Heterogeneity and Load Balance in Distributed Hash
Tables. In Proc. IEEE INFOCOM'05, pages 596{606, Mar. 2005.
[10] G. H. Gonnet. Expected Length of the Longest Probe Sequence in Hash Code
Searching. J. ACM, 28(2):289{304, Apr. 1981.
[11] K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan.
Measurement, Modeling, and Analysis of a Peer-to-Peer File-SharingWorkload. In
Proc. 19th ACM Symp. Operating Systems Principles (SOSP'03), pages 314{329,
Oct. 2003.
[12] W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their
Applications. Biometrika, 57(1):97{109, Apr. 1970.
[13] N. L. Johnson and S. Kotz. Urn Models and Their Application: An Approach to
Modern Discrete Probability Theory, chapter Occupancy and Related Problems,
pages 107{175. John Wiley & Sons Inc, 1977.
[14] D. Karger and M. Ruhl. Simple E±cient Load Balancing Algorithms for Peer-to-
Peer Systems. In Proc. 16th ACM Symp. Parallel Algorithms and Architectures
(SPAA'04), pages 36{43, June 2004.
[15] K. Kenthapadi and G. S. Manku. Decentralized Algorithms using Both Local
and Random Probes for P2P Load Balancing. In Proc. 17th ACM Symp. Parallel
Algorithms and Architectures (SPAA'05), pages 135{144, July 2005.
[16] F. C. H. Lin and R. M. Keller. The Gradient Model Load Balancing Method.
IEEE Trans. Software Eng., 13(1):32{38, Jan. 1987.
[17] H.-C. Lin and C. S. Raghavendra. A Dynamic Load-Balancing Policy with a
Central Job Dispatcher (LBC). IEEE Trans. Software Eng., 18(2):148{158, Feb.
1992.
[18] P. K. K. Loh, W. J. Hsu, and N. Sriskanthan W. Cai. How Network Topology
A®ects Dynamic Load Balancing. IEEE Parallel Distrib. Technology, 4(3):25{35,
Sept. 1996.
[19] Q. Lv, S. Ratnasamy, and S. Shenker. Can Heterogeneity Make Gnutella Scalable?
In Proc. 1st Int'l Workshop Peer-to-Peer Systems (IPTPS'02), pages 94{103, Mar.
2002.
[20] G. S. Manku. Balanced Binary Trees for ID Management and Load Balance
in Distributed Hash Tables. In Proc. 23rd ACM Symp. Principles Distributed
Computing (PODC'04), pages 197{205, July 2004.
[21] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller.
Equations of State Calculations by Fast Computing Machines. J. Chemical
Physics, 21(6):1087{1092, June 1953.
[22] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Al-
gorithms and Probabilistic Analysis, chapter Coupling of Markov Chains, pages
271{294. Cambridge University, 2005.
[23] L. M. Ni and K. Hwang. Optimal Load Balancing in a Multiple Processor System
with Many Job Classes. IEEE Trans. Software Eng., 11(5):491{496, May 1985.
[24] L. M. Ni, C.-W. Xu, and T. B. Gendreau. A Distributed Drafting Algorithm for
Load Balancing. IEEE Trans. Software Eng., 11(10):1153{1161, Oct. 1985.
[25] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica. Load Balancing
in Structured P2P Systems. In Proc. 2nd Int'l Workshop Peer-to-Peer Systems
(IPTPS'02), pages 68{79, Feb. 2003.
[26] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A Scalable
Content-Addressable Network. In Proc. ACM SIGCOMM'01, pages 161{172, Aug.
2001.
[27] S. M. Ross. Introduction to Probability Models, chapter Markov Chains, pages
185{280. Academic Press, 9th edition, 2007.
[28] A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and
Routing for Large-Scale Peer-to-Peer Systems. LNCS 2218, pages 161{172, Nov.
2001.
[29] S. Saroiu, P. K. Gummadi, and S. D. Gribble. Measurement Study of Peer-
to-Peer File Sharing Systems. In Proc. Multimedia Computing and Networking
(MMCN'02). Jan., 2002.
[30] H. Shen. Handbook of Research on Scalable Computing Technologies, chapter Load
Balancing in Peer-to-Peer Systems. IGI Global, July 2009.
[31] H. Shen and C.-Z. Xu. Locality-Aware and Churn-Resilient Load Balancing
Algorithms in Structured P2P Networks. IEEE Trans. Parallel Distrib. Syst.,
18(6):849{862, June 2007.
[32] H. Shen, C.-Z. Xu, and G. Chen. Cycloid: A Scalable Constant-Degree Lookup-
E±cient P2P Overlay Network. Performance Evaluation, 63(3):195{216, Mar.
2006.
[33] A. Sinclair. Improved Bounds for Mixing Rates of Markov Chains and Multicom-
modity Flow. Combin. Probab. Comput., 1(4):351{370, Dec. 1992.
[34] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek,
and H. Balakrishnan. Chord: a Scalable Peer-to-Peer Lookup Protocol for Internet
Applications. IEEE/ACM Trans. Netw., 11(1):17{21, Feb. 2003.
[35] S. Surana, B. Godfrey, K. Lakshminarayanan, R. Karp, and I. Stoica. Load Balanc-
ing in Dynamic Structured P2P Systems. Performance Evaluation, 63(6):217{240,
Mar. 2006.
[36] Q. H. Vu, B. C. Ooi, M. Rinard, and K.-L. Tan. Histogram-Based Global Load
Balancing in Structured Peer-to-Peer Systems. IEEE Trans. Knowl. Data Eng.,
21(4):595{608, Apr. 2009.
[37] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatow-
icz. Tapestry: A Resilient Global-Scale Overlay for Service Deployment. IEEE J.
Selected Areas in Comm., 22(1):41{53, Jan. 2004.
[38] Y. Zhu. Handbook of Peer-to-Peer Networking, chapter Load Balancing in Struc-
tured P2P Networks. Springer, July 2009.
[39] Y. Zhu and Y. Hu. E±cient, Proximity-Aware Load Balancing for DHT-Based
P2P Systems. IEEE Trans. Parallel Distrib. Syst., 16(4):349{361, Apr. 2005.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2015-07-15起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2015-07-15起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw