透過您的圖書館登入
IP:54.243.2.41
  • 學位論文

變動鄰域搜尋法於虛擬機器配置問題之探討

Variable Neighborhood Search for Energy-aware Optimization of Virtual Machine Allocation Problem

指導教授 : 梁韵嘉

摘要


由於雲端應用的蓬勃發展以及倍速成長的網路流量,各網路龍頭不斷在世界各地擴建資料中心。隨著資料中心的擴建與內部伺服器的增加,資料中心的耗電量增加成為決策者相當重視的議題,現代資料中心應用虛擬化技術,將工作以虛擬機器執行,虛擬機器會被分配給伺服器,以取得運算資源,因此,若是能夠有效管理虛擬機器在伺服器群中的配置,將可以降低能源消耗、節省成本,此為所謂的虛擬機器配置問題。 虛擬機器配置問題是屬於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.

參考文獻


[35] 田佳芸, "變動鄰域搜尋法於雙目標平行機台排程問題之研究," 碩士論文, 元智大學, 民國96年.
[37] 郭男極, "變動鄰域搜尋法於多目標專案投資組合問題之研究," 碩士論文, 元智大學, 民國97年.
[36] 高淑娟, "應用變動鄰域搜尋法於資源分配問題之研究," 碩士論文, 元智大學, 民國97年.
[33] 胡志凱, "雲端運算中動態調整虛擬機器運算資源機制," 碩士論文, 大同大學, 民國99年.
[40] 許嘉文, "變動鄰域搜尋法於考慮備用策略於複置配置問題之應用," 碩士論文, 元智大學, 民國100年.

被引用紀錄


彭鵬(2012)。低收入戶之脫貧行為-以政策、經濟與失業角度分析〔碩士論文,淡江大學〕。華藝線上圖書館。https://doi.org/10.6846%2fTKU.2012.00651
李怡慶(2014)。醫院關係品質之前置及調節變項之研究〔博士論文,國立中正大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0033-2110201613564880

延伸閱讀