分散式雜湊表已經成為許多大型分散式系統的關鍵性元件之一。雲端計算的應用上，分散式雜湊表可以提供一個Key-value型態的儲存空間。而在分散式雜湊表加入虛擬伺服器的概念，讓每個節點可以擁有不同的虛擬伺服器，且節點之間可以藉由搬動虛擬伺服器來達到負載平衡。

在本文中，我們將提出一個基於虛擬伺服器的負載平衡演算法。每個節點依據一個機率分布，各自搬動自身所擁有的虛擬伺服器來達到負載平衡。最後，我們將此演算法應用到雲端系統上，實作出可以雲端系統上的負載平衡。

Distributed hash tables (DHTs) are key building blocks in the design and implementation of successful large-scaled distributed applications. In popular cloud infrastructures (e.g., Amazon Dynamo), DHTs serve as large-scaled key-value stores. With the notion of virtual servers in state-of-the-art DHTs, participating nodes may host different numbers of virtual servers, and they are enabled to balance their loads in the reallocation of virtual servers.

The thesis presents a fully distributed load balancing algorithm for DHTs based on virtual servers. Nodes in a DHT estimate and represent the system state as probability distributions. Based on the probability distributions, each node independently reallocates its locally hosted virtual servers without synchronization. For proof of concept, we implement the load balancing algorithm in an emerging cloud computing platform, Hadoop.

[1] 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 Application," IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 17-21, February 2003.

[2] A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer System," Lecture Notes in Computer Science, vol. 2118, pp. 161-172, November 2001.

[3] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, and S. Sivasubramanian, "Dynamo: Amazon's Highly Available Key-value Store," ACM Symposium on Operating Systems Principles, pp. 205-220, Octor 2007.

[4] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, "Load Balancing in Structured P2P Systems," in Proc, International Workshop on Peer-To-Peer Systems, pp. 68-79, February 2003.

[5] Y. Zhu and Y. Hu, "Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems," IEEE Transactions on Parallel Distributed Systems, vol. 16, no. 4, pp. 349-361, April 2005.

[6] S. Surana, B. Godfrey, K. Lakshminarayanan, R. Karp, and I. Stoica, "Load Balancing in Dynamic Structured P2P Systems," Performance Evaluation, vol. 63, no. 6, pp. 217-240, March 2006.

[7] H. Shen and C.-Z. Xu, "Locality-Aware and Churn-Resilient Load Balancing Algorithms in Structured P2P Networks," IEEE Transactions on Parallel Distributed Systems, vol. 18, no. 6, pp. 849-862, June 2007.

[8] C. Chen and K.-C. Tsai, "The Server Reassignment Problem for Load Balancing in Structured P2P Systems," IEEE Transactions on Parallel Distributed Systems, vol. 21, no. 2, pp. 234-246, February 2008.
[9] Amazon EC2, http://aws.amazon.com/ec2/.

[10] T. L. Casavant and J. G. Kuhl, "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems," IEEE Transactions on Software Engineering, vol. 14, no. 2, pp. 141-154, February 1988.

[11] L. M. Ni and K. Hwang, "Optimal Load Balancing in a Multiple Processor System with Many Job Classes," IEEE Transactions on Software Engineering, vol. 11, no. 5, pp. 491-496, May 1985.

[12] L. M. Ni, C.-W. Xu, and T. B. Gendreau, "A Distributed Drafting Algorithm for Load Balancing," IEEE Transactions on Software Engineering, vol. 11, no. 10, pp. 1153-1161, Octor 1985.

[13] F. C. H. Lin and R. M. Keller, "The Gradient Model Load Balancing Method," IEEE Transactions on Software Engineering, vol. 13, no. 1, pp. 32-38, January 1987.

[14] Y. Zhu, Handbook of Research on Scalable Computing Technologies: Springer, 2009.

[15] H. Shen, Handbook of Research on Scalable Computing Technologies: IGI Global, 2009.

[16] H.-C. Hsiao, H. Liao, S.-S. Chen, and K.-C. Huang, "Load Balance with Imperfect Information in Structured Peer-to-Peer Systems," IEEE Transactions on Parallel Distributed Systems, vol. 22, no. 4, pp. 634-649, 2010.

[17] 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.

[18] P. Fonseca, R. Rodrigues, A. Gupta, and B. Liskov, "Full-Information Lookups for Peer-to-Peer Overlays," IEEE Parallel and Distributed Systems, vol. 20, no. 9, pp. 1339-1351, Setember 2009.

[19] VirtualBox, http://www.virtualbox.org/.

[20] Apache Hadoop,, http://hadoop.apache.org.