虛擬化是雲端計算的主要技術之一，利用軟體對硬體資源進行虛擬化，讓計算資源的使用更具有高度彈性。雲端計算系統透過網路整合、管理叢集內所有伺服器的計算資源，讓使用者可以依照自己的需求建立不同數量、不同效能的虛擬機器。如何有效地分配系統資源，並且將各種不同效能的虛擬機器配置到適當的實體機器上執行，是虛擬機器配置的主要問題。然而，當多個虛擬機器同時在一個實體機器上執行時，虛擬機器可能會互相減損執行效能，我們稱此現象為「虛擬機器之間的效能干擾」。另一方面，使用者執行在虛擬機器上的應用程式，可能也有不同的服務品質要求。為了滿足應用程式的服務品質要求，系統雖然可以配給虛擬機器足夠的計算資源，但是在效能干擾的情況下，最終還是可能無法滿足應用程式的服務品質要求。在本論文中，我們研究雲端計算系統的虛擬機器配置問題，目的除了要有效地分配系統資源，也盡可能地滿足應用程式的服務品質、降低虛擬機器之間的效能干擾。我們首先將此問題公式化，並且用整數線性規劃(Integer Linear Programming)求得最佳解。然而，整數線性規劃求解的過程可能花費許多計算時間，因此我們提出一個啟發式演算法(Heuristic algorithm)，在多項式時間之內解決此問題。最後，我們進行模擬實驗，與其他的虛擬機器配置演算法作比較，展示啟發式演算法的效能。

Cloud computing provides scalable computing and storage resources. These scalable resources can be dynamically organized as many virtual machines (VMs) to run user applications based on a pay-per-use basis. In practice, the required resources of a VM are sliced from a physical machine (PM) in the cloud computing system. A PM may hold one or more VMs. When a cloud provider would like to create a number of VMs, the main concerned issue is the VM placement problem, such that how to place these VMs at appropriate PMs to provision their required resources. However, if two or more VMs are placed at the same PM, there exists certain degree of interference between the VMs due to sharing some common resources. This phenomenon is called as the VM interference. This paper investigates the interference-aware VM placement (IAVMP) problem. In addition to fully exploiting the resources of PMs, the IAVMP problem considers the quality of service (QoS) requirements of user applications and the VM interference reduction. We first formulate the IAVMP problem by an Integer Linear Programming (ILP) model to solve it optimally. Due to the computation complexity of the ILP model, we also propose a polynomial-time heuristic algorithm to efficiently solve the IAVMP problem. Finally, simulation experiments are performed to demonstrate the effectiveness of the proposed heuristic algorithm by comparing with other VM placement algorithms.

LIST OF FIGURES . . . V
LIST OF TABLES . . . VI
CHAPTER 1 Introduction . . . 1
CHAPTER 2 Preliminaries . . . 6
2.1 Virtualization Techniques . . . 6
2.2 Xen . . . 7
2.3 Xen Cloud Platform . . . 7
2.4 System Model . . . 8
2.5 Related Work . . . 9
CHAPTER 3 Interference-Aware VM Placement . . . 12
3.1 ILP Model . . . 12
3.2 The QoS-violation Assessment . . . 18
3.3 Heuristic Algorithm . . . 21
3.3.1 Contention Phase . . . 25
3.3.2 Placement Phase . . . 27
3.3.3 Reformation Phase . . . 28
CHAPTER 4 Performance Evaluation . . . 32
4.1 Simulation Environment . . . 33
4.2 Simulation Results . . . 34
CHAPTER 5 Conclusions . . . 39
References . . . 40

[1]Amazon EC2. [Online]. Available: http://aws.amazon.com/ec2/
[2]GoGrid. [Online]. Available: http://www.gogrid.com/
[3]Amazon EC2 Instance Types. [Online]. Available: http://aws.amazon.com/ec2/instance-types/
[4]Xen. [Online]. Available: http://xen.org/
[5]VMware. [Online]. Available: http://www.vmware.com/
[6]S. Ibrahim, B. He, and H. Jin, “Towards Pay-As-You-Consume Cloud Computing,” in Proceedings IEEE International Conference Services Computing, 2011, pp. 370–377.
[7]B. Zhang, X. Wang, R. Lai, L. Yang, Y. Luo, and X. Li, “A Survey on I/O Virtualization and Optimization,” in Proceedings 5th Annals ChinaGrid Conference, 2010, pp. 117–123.
[8]X. Pu, L. Liu, Y. Mei, S. Sivathanu, Y. Koh, C. Pu, and Y. Cao, “Who is Your Neighbor: Net I/O Performance Interference in Virtualized Clouds,” IEEE Transactions on Services Computing, vol. 99, 2012.
[9]M. G. Kallitsis, R. D. Callaway, M. Devetsikiotis, and G. Michailidis, “Presence-aware Optimum Resource Allocation for Virtual Collaboration Web 3.0 Environments,” in IEEE Workshop GLOBECOM ’2009, Dec. 2009, pp. 1–5.
[10]P. Campegiani and F. L. Presti, “A General Model for Virtual Machines Resources Allocation in Multi-tier Distributed Systems,” in Proceedings 5th International Conference Autonomic and Autonomous Systems, 2009, pp. 162–167.
[11]H. N. Van, F. D. Tran, and J.-M. Menaud, “Autonomic Virtual Resource Management for Service Hosting Platforms,” in Proceedings Workshop Software Engineering Challenges of Cloud Computing, Vancouver, Canada, May 2009, pp. 1–8.
[12]M. Cardosa, A. Singh, H. Pucha, and A. Chandra, “Exploiting Spatio-Temporal Tradeoffs for Energy Efficient MapReduce in the Cloud,” Department of Computer Science and Engineering, University of Minnesota, Technical Report TR-10-008, Apr. 2010.
[13]J. Xu and J. A. B. Fortes, “Multi-Objective Virtual Machine Placement in Virtualized Data Center Environments,” in Proceedings IEEE/ACM International Conference Green Computing & Communication & International Conference Cyber, Physical and Social Computing, Washington, DC, USA, 2010, pp. 179–188.
[14]S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimal Virtual Machine Placement across Multiple Cloud Providers,” in IEEE Asia-Pacific Services Computing Conference (APSCC’09), Dec. 2009, pp. 103–110.
[15]S. Chaisiri, B.-S. Lee, and D. Niyato, “Optimization of Resource Provisioning Cost in Cloud Computing,” IEEE Transactions on Services Computing, vol. 99, 2011.
[16]S. Dasgupta, C. H. Papadimitriou, and U. V. Vaziran, Algorithms. McGraw-Hill, May 2006.
[17](2012) Xen Cloud Platform. [Online]. Available: http://xen.org/products/cloudxen.html/
[18]P. R. Barham, B. Dragovic, K. A. Fraser, S. M. Hand, T. L. Harris, A. C. Ho, E. Kotsovinos, A. V. Madhavapeddy, R. Neugebauer, I. A. Pratt, and A. K.Warfield, “Xen 2002,” University of Cambridge, Cambridge, Technical Report, Jan. 2003.
[19]P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, “Xen and the Art of Virtualization,” in Proceedings 19th ACM Symposium Operating Systems Principles (SOSP ’03), Dec. 2003, pp. 164–177.
[20]D. Boutcher and A. Chandra, “Does Virtualization Make Disk Scheduling Passe?” ACM SIGOPS Operating Systems, vol. 44, pp. 20–24, Jan. 2010.
[21]M. Kesavan, A. Gavrilovska, and K. Schwan, “On Disk I/O Scheduling in Virtual Machines,” in Proceedings 2nd Workshop on I/O Virtualization, Pittsburgh, PA, USA, May 2010, pp. 1–6.
[22]Y. Mei, L. Liu, X. Pu, and S. Sivathanu, “Performance Measurements and Analysis of Network I/O Applications in Virtualized Cloud,” in Proceedings IEEE 2010 International Conference on Cloud Computing (Cloud ’10), Florida, USA, Jul. 2010, pp. 59–66.
[23](2010) MATLAB – The Language of Technical Computing. [Online]. Available: http://www.mathworks.com/
[24]K. L. Calvert, M. B. Doar, and E. W. Zegura, “Modeling Internet Topology,” IEEE Communication Society, vol. 35, pp. 160–163, Jun. 1997.