Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19936
標題: 一個用於網路感知虛擬機器配置之貪婪事件調度方法
A Greedy Events Scheduling Method for Network-aware Virtual Machine Placement
作者: 蕭宇辰
Hsiao, Yu-Chen
關鍵字: 數據中心;datacenter;虛擬化技術;雲端運算;排程;網路感知;貪婪方法;循序排程;virtualization techniques;cloud computing;scheduling;greedy approach;round bobin scheduler
出版社: 資訊科學與工程學系所
引用: [1] T. P. Jing and Y. Jun, "A Network-aware Virtual Machine Placement and Migration Approach in Cloud Computing," in 2010 Ninth International Conference on Grid and Cloud Computing, pp. 87–92, Nov. 2010. [2] W. Hao, I.-L. Yen and B. Thuraisingham, "Dynamic Service and Data Migration in the Clouds," in Proceedings of the 33rd Annual IEEE International Computer Software and Applications Conference, Seattle, WA, USA, 20–24 July 2009: IEEE Computer Society, Washington, DC, USA, 2009, pp.134–139. [3] J-L. Kim, and R. D. Ellis, " A Framework for Integration Model of Resource-Constrained Scheduling using Genetic Algorithms," in Proceedings of the Winter Simulation Conference, Orlando, Florida, USA, December 2005, pp.2119 – 2126. [4] C. Tang, M. Steinder, M. Spreitzer and G. Pacifici, "A Scalable Application Placement Controller for Enterprise Data Centers," in Proceedings of the 16th international conference on World Wide Web, pp.331 – 340, Banff, Alberta, Canada, May 2007. [5] H. N. Van, F. D. Tran, and J-M, "Menaud. Autonomic Virtual Resource Management for Service Hosting Platforms." in Proceedings of the 2009 ICSE Workshop on software Engineering Challenges of Cloud Computing, CLOUD ''09, Vancouver, Canada, 2009, pp.1-8. [6] R. Buyya, http://www.buyya.com/gridbus/cloudsim/, access at 20/5/2010 [7] K. Li, G. Xu, G. Zhao, Y. Dong and D. Wang, " Cloud Task Scheduling Based on Load Balancing Ant Colony Optimization." Paper presented at the Chinagrid Conference (ChinaGrid), Sixth Annual, 2011. [8] G. Wang and T. E. Ng, "The impact of virtualization on network performance of amazon EC2 data center," in Proceedings of IEEE INFOCOM 2010, Houston, TX, USA, March 2010 [9] R.N. Calheiros, R. Ranjan, C.A.F. De Rose, R.Buyya, "CloudSim: A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services," Grid Computing and Distributed Systems Laboratory in Technical Report, The University of Melbourne, Australia, 2009. [10] G. Belalem, F. Z. Tayeb and W. Zaoui, "Approaches to improve the resources management in the simulator CloudSim," in Proceedings of the First International Conference of Information Computing and Applications, pp.189-196, 2010. [11] W. Bhathiya, R. Buyya and R. Ranjan, "CloudAnalyst: A CloudSimbased Visual Modeller for Analysing Cloud Computing Environments and Applications," in Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications, pp.446-452, 2010. [12] K. Tsakalozos, M. Roussopoulos, V. Floros and A. Delis. "Nefeli: Hint-based execution of workloads in clouds," in Proceeding of the 2010 IEEE 30th International Conference on Distributed Computing Systems, pp. 74-85, Washington, DC, USA, 2010. [13] J. Li, M. Qiu, J. Niu, Y. Chen and Z. Ming, "Adaptive resource allocation for preemptable jobs in cloud systems," in Intelligent Systems Design and Applications (ISDA), 2010 10th International Conference on, pp.31-36. [14] Fangzhe Chang, Jennifer Ren, and Ramesh Viswanathan. "Optimal resource allocation in clouds," in Proceeding of the 2010 IEEE 3rd International Conference on Cloud Computing, CLOUD 10, pp.418-425, Washington, DC, USA, 2010. [15] 林姿華,全世界漫步在雲端-淺談科技新知識『雲端運算』, http://www.nhu.edu.tw/~society/e-j/86/13.htm [16] 劉鵬,雲計算CLOUD COMPUTING(第二版),03/2010。 [17] 許詠慶,(民100)。雲端計算中工作序列的虛擬機器排程方法,國立台灣大學資訊工程研究所碩士論文。 [18] 張雅芳、周宗毅,"漫步雲端 嶄新未來",http://www.cs.nthu.edu.tw/~cherung/teaching/2010cs1356/cloud.pdf
摘要: 
虛擬化技術的進步,加快了雲端運算的發展。在高速交換的連結上,數千萬台的主機形成一個大規模的數據中心,服務給網路上使用者的多樣化需求。例如:搜索、社交網路、線上地圖,以及其他許許多多的服務。巨大互聯網路的普及,需要有效的資源管理以及虛擬機配置,以保持快速的資源需求。虛擬機器的配置問題已成為一個研究重點。然而,現有的放置方法,強調了資源優化配置,卻忽略網路的影響。這會導致應用程序在密集檢索文件或資料時存取時間大增。
在本篇論文中,我們提出一個在虛擬機配置上的一個調度方法。這個方法以貪婪方法將事件調度到虛擬機上。在確定事件的完成時間表上,這個方法考慮到事件最短的計算時間以及最好的資料存取時間。我們去評估,事件在不同虛擬機上的完成時間以及虛擬機是否有足夠的資源。此外,我們考慮到數據訪問的時間,在虛擬機配置時可以有最小的資料存取時間。換句話說,在確定虛擬機配置時,我們的方法可以透過網路感知來降低資料存取的成本。我們的方法會對事件進行虛擬機器上的搜索,以求最好的配置。當下我們要求事件能夠取得最短的計算時間和存取時間,之後對該事件進行配置。我們重複這個過程,直到所有事件都配置到正確的虛擬機器上。
我們提出的方法能夠有效減少事件完成時間。在模擬結果明顯的看出,該方法優於傳統的循序調度。當事件數量提升,平均完成時間可以比循序調度更來的小。例如:在事件數量約在25到30時,循序調度的平均完成時間會大幅增加。然而,我們的方法可以有效的控制平均完成時間的增加,可以比循序調度大幅減少約600秒的時間。

Advances in virtualization techniques have accelerated the development of cloud computing technology. Connected by high-speed switches, tens of thousands of servers form a datacenter on a warehouse scale to service Internet users with diverse requests: search, social networking, online maps, and many others. The tremendous popularity of such Internet services necessitates efficient resource management and virtual machine placement to keep up with the rapid resource demands. The placement problem of virtual machines has become a focal point of research. However, the existing placement methods emphasize resource optimization, neglecting the effect of networks. This could lead to a dramatic increase in access time for applications to retrieve files or data.
In this thesis, we propose a scheduling method for virtual machine placement. The proposed method uses a greedy approach to scheduling tasks on virtual machines. While determining the task schedule, the proposed method considers the minimization of computing time and data access time as well. Virtual machines are checked to make sure that they provide adequate resources, and task completion times over different virtual machines are evaluated. In addition, our method takes data access time into account. The proposed method intends to choose virtual machines in order that data relevant to the applications can be rapidly accessed with minimal network latency. In other words, while determining the placement, our method is aware of the cost of data access through networks. The proposed method conducts a search for the task with the best placement that, for the time being, requires the minimum time of computing and data access combined. And the task is scheduled with the placement. This process repeats until all the tasks are scheduled and their placements are determined.
Our proposed method can effectively minimize the completion time of tasks. The simulation results indicate that our method outperforms the conventional round robin(RR) scheduler. The average task completion time becomes smaller by the proposed method than by the RR scheduler, particularly when the number of tasks increases. For example, as the number of tasks approaches 25-30, the average completion time by the RR scheduler shoots up drastically. However, our method can effectively control the increase in the average completion time. And it maintains lower task completion times than the RR scheduler, by a wide margin of 600 seconds.
URI: http://hdl.handle.net/11455/19936
其他識別: U0005-1307201213231200
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.