跳到主要內容

臺灣博碩士論文加值系統

(18.204.48.64) 您好!臺灣時間:2021/08/04 17:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林易達
研究生(外文):I-Ta Lin
論文名稱:結構化點對點網路上具有地域性的負載平衡演算法
論文名稱(外文):Robust Locality-Aware Load Balancing for Structured Peer-to-Peer Networks
指導教授:蕭宏章
指導教授(外文):Hung-Chang Hsiao
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:49
中文關鍵詞:點對點系統負載平衡位置察覺分散式雜湊表
外文關鍵詞:peer-to-peer systemsdistributed hash tableslocation awarenessload balance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:88
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
虛擬伺服器(virtual server)是一個能用來開發並充分利用在分散式雜湊表裡(distributed hash table 或DHT)異質計算節點能力(capabilities of heterogeneous peers)的抽象層 (abstraction layer)。由於不同的虛擬伺服器會對系統帶來不同的工作量,同時相異節點能在系統裡自由地加入與離開,我們因而可藉由隨時分配虛擬伺服器到網路裡的任一節點使平衡系統負載。
在這個研究工作裡,我們提出的是具有虛擬伺服器這樣抽象層的負載平衡DHT 網路(load-balanced DHT network)。我們的負載平衡DHT 網路致力在花費低網路延遲消耗下來搬動虛擬伺服器使系統能到達負載平衡的狀態。我們規劃的研究方法是首先設計能負載平衡DHT 網路,其中參與系統的計算節點根據本身的能力來接受等比例的負載工作量。利用對系統裡節點計算能力以及虛擬伺服器工作量進行採樣(sampling),我們估計節點計算能力與虛擬伺服器工作量的機率分佈(probability distribution)。節點會以這樣估計的計算能力機率分佈為依據,將自己身上的虛擬伺服器與其他的節點進行配對。為了能夠降低因搬動虛擬伺服器所造成的網路延遲消耗,我們會放寬一個節點所能接受工作負載的限制,也就是讓系統負載稍微不平衡,使每一個節點能有彈性的選擇在網路上實際接近的虛擬伺服器。
我們的研究工作的貢獻有:(1)一個DHT 網路除了能盡可能的平衡節點之間的負載,還能在使用近乎常數量的網路消耗下配置虛擬伺服器。(2)有別於過去的研究,我們的設計是在嚴謹效能分析的引導下而產出。(3)我們並將藉由大量的模擬對我們的系統設計做效能評估。
關鍵詞:點對點系統(peer-to-peer systems),分散式雜湊表(distributed hash tables),負載平衡(load balance),位置察覺(location awareness)
Virtual servers provide an abstraction layer to exploit the heterogeneity of peers (or nodes) that participate in a peer-to-peer (P2P) network based on the distributed hash table (DHT). A virtual server can be allocated to an arbitrary peer in the network. Since different virtual servers may introduce different workloads to the network, and participating peers that are heterogeneous may come and go freely, one common technique for balancing loads among peers is to dynamically reallocate virtual servers to hosting peers.
In this thesis, we present a load-balanced DHT network with the abstraction layer of virtual servers. Our load-balanced DHT network aims to balance the loads among peers in a low network cost due to moving virtual servers. Our proposal is first driven by a perfect load-balanced DHT network that each participating peer accepts the loads proportional to its capacity. By sampling the capacities of peers and workloads of virtual servers in the system, our design approximates the probability distributions for the capacities and workloads. Each node is based on the probability distributions to match their local virtual servers and other peers. We then relax the constraints for loads that a node can accept such that each peer can allocate a virtual server to its physically close node. The major contributions of our study include (1) a DHT network that not only balances the loads among peers as much as possible, but takes a constant network cost in expectation to allocate virtual servers. (2) Our design is guided by rigorous performance analysis. (3)We evaluate our proposal in extensive simulations, and the simulation results show that our design significantly outperforms prior proposals.
Keywords: peer-to-peer systems, distributed hash tables, load balance, location awareness
1 Introduction.......1
1.1 Problem Statement.......2
1.2 Our Idea and Contributions.......4
1.3 Roadmap.......6
2 Related Work.......7
2.1 Load Balancing Algorithms for DHTs.......7
2.1.1 Balancing the Key Space.......7
2.1.2 Balancing Non-Uniform Loads of Objects.......8
2.1.3 Load Balance via Replication.......10
2.2 The Balls-and-Bins Paradigm.......11
2.3 Linear Programming Techniques.......12
3 Our Proposal.......15
3.1 Overview.......15
3.2 Sampling.......20
3.2.1 Approximation of Probability Distribution for Capacities of Peers.......20
3.2.2 Approximation of Probability Distribution for Loads of VSs.......24
3.3 Disseminating Estimated Probability Distributions.......25
3.4 Allocating Virtual Servers with a Low Network Cost.......26
3.5 Handling System Dynamics.......29
4 Simulations.......34
4.1 Experimental Setting.......34
4.1.1 The Coordinate-based Hierarchical Matching Algorithm.......36
4.2 Comparing CHMA and Our Proposal.......37
4.2.1 Load Imbalance Factor.......37
4.2.2 The Network Delay Cost of Moving a Virtual Server.......40
4.2.3 Other System Configurations.......41
4.3 Varying the Number of Samples.......42
5 Summary.......43
[1] Y. Chu, S. Rao, and H. Zhang, “A Case for End System Multicast,” in Proceedings of the International Conference on Measurements and Modeling of Computer Systems. ACM Press, 2000, pp. 1–12.
[2] X. Zhang, J. Liu, B. Li, and T.-S. Yum, “CoolStreaming/DONet: A Data-driven Overlay Network for Peer-to-Peer Live Media Streaming,” in Proceedings of IEEE INFOCOM, March 2005, pp. 2102–2111.
[3] X. Liao, H. Jin, Y. Liu, L. M. Ni, and D. Deng, “AnySee: Peer-to-Peer Live Streaming,” in Proceedings of IEEE INFOCOM. IEEE Communication Society, March 2006, pp. 1–10.
[4] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network,” in Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. ACM Press, August 2001, pp. 161–172.
[5] 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 Transactions on Networking, vol. 11, no. 1, pp. 17–21, Feburary 2003.
[6] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems,” Lecture Notes in Computer Science, vol. 2218, pp. 161–172, November 2001.
[7] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, “Tapestry: A Resilient Global-scale Overlay for Service Deployment,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41–53, January 2004.
[8] D. Eastlake and P. Jones, “US Secure Hash Algorithm 1 (SHA1),” RFC 3174, September 2001.
[9] D. Karger and M. Ruhl, “Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems,” in Proceedings of the Symposium on Parallel Algorithms and Architectures. ACM Press, June 2004, pp. 36–43.
[10] G. S. Manku, “Balanced Binary Trees for ID Management and Load Balance in Distributed Hash Tables,” in Proceedings of the Symposium on Principles of Distributed Computing. ACM Press, July 2004, pp. 197–205.
[11] M. Bienkowski, M. Korzeniowski, and F. M. auf der Heide, “Dynamic Load Balancing in Distributed Hash Tables,” in Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2005, pp. 217–225.
[12] K. Kenthapadi and G. S. Manku, “Decentralized Algorithms using Both Local and Random Probes for P2P Load Balancing,” in Proceedings of the Symposium on Parallel Algorithms and Architectures. ACM Press, July 2005, pp. 135–144.
[13] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, “Load Balancing in Structured P2P Systems,” in Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2003, pp. 68–79.
[14] Y. Zhu and Y. Hu, “Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 349–361, April 2005.
[15] H. Shen and C.-Z. Xu, “Locality-Aware and Churn-Resilient Load Balancing Algorithms in Structured P2P Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 6, pp. 849–862, June 2007.
[16] B. Godfrey and I. Stoica, “Heterogeneity and Load Balance in Distributed Hash Tables,” in Proceedings of IEEE INFOCOM. IEEE Communication Society, March 2005, pp. 596–606.
[17] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, “Balanced Allocations,” SIAM Journal on Computing, vol. 29, no. 1, pp. 180–200, February 1999.
[18] V. Stemann, “Parallel Balanced Allocations,” in Proceedings of the Symposium on Parallel Algorithms and Architectures. ACM Press, June 1996, pp. 261–269.
[19] C. Chen and K.-C. Tsai, “The Server Reassignment Problem for Load Balancing in Structured P2P Systems,” IEEE Transactions on Parallel and Distributed Systems, 2007 (in press).
[20] H. Zhang, A. Goel, and R. Govindan, “Improving Lookup Latency in Distributed Hash Table Systems Using Random Sampling,” ACM/IEEE Transactions on Networking, vol. 13, no. 5, pp. 1121–1134, October 2005.
[21] N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, “SkipNet: A Scalable Overlay Network with Practical Locality Properties,” in Proceedings of the USENIX Symposium on Internet Technologies and Systems, March 2003.
[22] M. F. Kaashoek and D. R. Karger, “Koorde: A Simple Degree-Optimal Distributed Hash Table,” Lecture Notes in Computer Science, vol. 2735, pp. 98–107, October 2003.
[23] H. Shen, C.-Z. Xu, and G. Chen, “Cycloid: A Scalable Constant-Degree Lookup-Efficient P2P Overlay Network,” Performance Evaluation, vol. 63, no. 3, pp. 195–216, March 2006.
[24] Y. Chen, R. H. Katz, and J. Kubiatowicz, “Dynamic Replica Placement for Scalable Content Delivery,” in Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, March 2002, pp. 306–318.
[25] S. Iyer, A. Rowstron, and P. Druschel, “Squirrel: A Decentralized, Peer-to-Peer Web Cache,” in Proceedings of the Annual Symposium on Principles of Distributed Computing. ACM Press, July 2002, pp. 213–222.
[26] V. Ramasubramanian and E. G. Sirer, “Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays,” in Proceedings of the Symposium on Networked Systems Design and Implementation. USENIX Press, March 2004.
[27] M. Mitzenmacher, A. Richa, and R. Sitaraman, Handbook of Randomized Computing. Springer Press, July 2001, vol. 1, ch. The Power of Two Random Choices: A Survey of Techniques and Results, pp. 255–312.
[28] P. Berenbrink, F. M. auf der Heide, and K. Schrぴoder, “Allocating Weighted Jobs in Parallel,” in Proceedings of the Symposium on Parallel Algorithms and Architectures. ACM Press, June 1997, pp. 302–310.
[29] S. Fu, C.-Z. Xu, and H. Shen, “Random Choices for Churn Resilient Load Balancing in Peer-to-Peer Networks,” in Proceedings of the International Parallel and Distributed Processing Symposium. IEEE Computer Society, April 2008.
[30] D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization. Athena Scientific, 1997, ch. Integer Programming Methods, pp. 479–531.
[31] D. P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998, ch. Network Problems with Integer Constraints, pp. 467–543.
[32] ——, “Auction Algorithms for Network Flow Problems: A Tutorial Introduction,” Computational Optimization and Applications, vol. 1, no. 1, pp. 7–66, October 1992.
[33] C.-Z. Xu and F. C. Lau, “Iterative Dynamic Load Balancing in Multicomputers,” Journal of Operational Research Society, vol. 45, no. 7, pp. 786–796, July 1994.
[34] V. King and J. Saia, “Choosing a Random Peer,” in Proceedings of the Symposium on Principles of Distributed Computing. ACM Press, July 2004, pp. 125–130.
[35] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge, 2005.
[36] H.-C. Hsiao and C.-T. King, “Scoped Broadcast in Dynamic Peer-to-Peer Networks,” in Proceedings of the International Computer Software and Applications Conference. IEEE Computer Society, July 2005, pp. 533–538.
[37] D. R. Karger and M. Ruhl, “Finding Nearest Neighbors in Growth-Restricted Metrics,” in Proceedings of the Annual Symposium on Theory of Computing. ACM Press, May 2002, pp. 741–750.
[38] J. C. Chu, K. S. Labonte, and B. N. Levine, “Availability and Locality Measurements of Peer-to-Peer File Systems,” in Proceedings of ITCom: Scalability and Traffic Control in IP Networks. SPIE, July 2002, pp. 310–321.
[39] S. Saroiu, P. K. Gummadi, and S. D. Gribble, “Measurement Study of Peer-to-Peer File Sharing Systems,” in Proceedings of Multimedia Computing and Networking. January, 2002.
[40] Gnutella, http://rfc-gnutella.sourceforge.net/.
[41] Napster, http://www.napster.com/.
[42] G. Pandurangan, P. Raghavan, and E. Upfal, “Building Low-Diameter Peer-to-Peer Networks,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 6, pp. 995–1002, August 2003.
[43] PlanetLab, http://www.planet-lab.org/.
[44] 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-Sharing Workload,” in Proceedings of the Symposium on Operating systems principles. ACM Press, October 2003, pp. 314–329.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊