由於雲端應用的蓬勃發展以及倍速成長的網路流量,各網路龍頭不斷在世界各地擴建資料中心。隨著資料中心的擴建與內部伺服器的增加,資料中心的耗電量增加成為決策者相當重視的議題,現代資料中心應用虛擬化技術,將工作以虛擬機器執行,虛擬機器會被分配給伺服器,以取得運算資源,因此,若是能夠有效管理虛擬機器在伺服器群中的配置,將可以降低能源消耗、節省成本,此為所謂的虛擬機器配置問題。 虛擬機器配置問題是屬於NP-hard問題,當問題規模很大時,例如虛擬機器數量或是伺服器數量很龐大時,使用整數規劃法會耗費大量的時間,不符合實務上的效益,而啟發式演算法為另一種解決方法,可以在合理的時間內求得不錯的結果。本研究所應用的方法為變動鄰域搜尋法 (Variable Neighborhood Search;VNS),乃是一套近年來被廣為應用的啟發式演算法,過去研究顯示,VNS在求解組合最佳化問題時有很好的表現。 本研究針對虛擬機器配置問題提出兩種不同的數學模式,目標為伺服器總能源消耗最小化,並針對兩種模式分別提出VNS架構來求解。藉由隨機產生的測試例題,將VNS的求解結果與最佳化軟體Gurobi的實驗結果作比較,並使用能源消耗與求解時間作為績效衡量指標,實驗結果顯示出VNS在多數例題中能夠在較短時間內,搜尋出等同於Gurobi的最佳解或是勝於Gurobi的上限值。
During the last few years, the development of cloud computing and the Internet usage has rapid growth. Many Internet companies build data centers which are located all over the world in order to meet the Internet demand. However, along the increasing of data centers and servers, the huge electricity consumption has become an important issue for managers. Modern data centers adopt the technique of virtualization, in which each service runs as a virtual machine that has its own resource demand. Multiple services can be hosted and operated on a single physical server simultaneously. Therefore, the allocation of virtual machine on server clusters should be arranged so that the energy consumption of data centers can be minimized. That is so called virtual machine allocation problem (VMAP). Virtual machine allocation problem falls in the category of NP-Hard problem. When the number of virtual machines or servers increases, the computational time of the exact methods such as mathematical programming grow exponentially. Therefore, using meta-heuristic algorithms which are able to find satisfying results within reasonable time is an appropriate option. Variable Neighborhood Search (VNS), one of the widely used meta-heuristic algorithms, has shown its performance in solving combinatorial optimization, hence is chosen as the method in this study. This research proposes two different mathematical models for the virtual machine allocation problem which considers the energy consumption of server components respectively. In the first model, the modified model proposed in this study reduces the complexity and the CPU time of the model from the literature. In addition, this research proposes Variable Neighborhood Search structure to solve both models proposed in this study. The proposed algorithms are run using test suites and compared with the results obtained by a mathematical programming solver — Gurobi, and the performance measures are total energy consumption and CPU time. The result shows that VNS can find optima or improve the upper bound of Gurobi’s result in most of the test instances within a comparably short time. This research has successfully illustrated the promising of VNS on VMAP.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。