GASd: 基於基因演算法之雲端資源佈署策略

Abstract

在雲端運算環境中，使用者可以透過雲端服務提供者(CSP)所提供的資源，來執行作業系統或應用程式，而不需負擔硬體建置及維護費用。而CSP必須負責管理並分配實體機資源給虛擬機，以執行使用者的應用程式。如果發生分配不當造成負載失衡的情形，將會導致某些實體機上的有限資源幾乎被耗盡，因而在這一些實體機上運行的虛擬機會受限於硬體資源不足而無法有正常的效能，致使CSP可能需要賠償使用者的損失。如果能維持實體機之間的負載平衡，那麼就能避免這種因為少數機器負載過重而衍生的賠償。在本論文中，我們提出了一個資源重分配的架構給CSP來維持實體機之間的負載平衡。這個架構使用探測子來蒐集虛擬機的CPU使用率，並且定時回傳給控制伺服器。控制伺服器根據這些回傳的資料，使用我們所提出的演算法(GASd)來決定新的虛擬機佈署策略。GASd是一種基於基因演算法(GA)的演算法，可以讓CSP快速地得到新的佈署策略。GASd允許CSP偏好某一種資源使用率，讓最後結果傾向平衡該資源使用率，同時，GASd也允許CSP調整虛擬機的遷移比例。在實驗中，我們證明了GASd可以把各實體機的CPU跟記憶體的使用率標準差都降至3\%，而運算的時間大約是0.25秒。同時也可以針對其中一個資源，使得該資源的使用率標準差收斂到最小，而另一種資源的使用率標準差則是一個可接受的結果。我們也討論了GASd的可擴展性，並且模擬了一個有2500台實體機以及10000台虛擬機的環境，結果是GASd可以在2分半鐘內找出一個佈署策略，使得資源使用率的標準差總和是6.25%，從而證實GASd可擴展性。

In cloud computing, users can save hardware cost by using cloud resources provided and managed by cloud service provider (CSP). If an inappropriate distribution strategy is applied and a load unbalancing situation occurs, the virtual machines run on an overloading host can not work well. Thus, keeping load balancing is an issue for a CSP. In this research, we present a resource reallocating framework for a CSP to manage resources and keep physical machines in a load balanced state. The proposed framework uses probes to collect CPU utilization data and send the collection to the control server. Then the control server makes a distribution strategy using the proposed algorithm, GASd. GASd is an algorithm based on Genetic Algorithm(GA). The design of GASd allows a CSP to have preference to a load dimension of CPU or memory, and also to control the migration ratio of virtual machines. We conduct several experiments to evaluate the ability of GASd. In the experiments, we show that GASd can reduce the load deviation among physical machines to about 3% for both load dimensions in about 0.25 seconds. GASd can make a strategy to minimize utilization standard deviation of one load dimension with acceptable standard deviation of another load dimension. We also discuss the scalability of GASd to distribute 10000 virtual machines to 2500 physical machines, and GASd can find an optimal distribution strategy for the running cloud system in 2.5 minutes with distance 6.25%.