|Table of Contents|

Virtual machine scheduling algorithm based on K-means clustering in cloud computing


Research Field:
Publishing date:


Virtual machine scheduling algorithm based on K-means clustering in cloud computing
Huang WeiWen ZhipingCheng Chu
School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China
cloud computing K-means clustering virtual machine scheduling greedy algorithm
To improve the resource utilization of cloud computing data centers and optimize virtual machines dynamically,a virtual machine scheduling algorithm is proposed based on K-means clustering.The correlation of virtual machine resource allocation is used as the standard of clustering,and a virtual machine is placed on the physical node complementary to it on resource,so that its resource is used fully and it is effective and stable.An online scheduling algorithm is designed to handle the requirements of new virtual machines.A greedy algorithm is proposed,and the upper bound of the competitive ratio between it and the optimal offline algorithm is given.The correctness of this algorithm is verified based on the experimental results of real data sets.


[1] 陈康,郑纬民.云计算:系统实例与研究现状[J].软件学报,2009,20(5):1337-1348.
Chen Kang,Zheng Weimin.Cloud computing:System instances and current research[J].Journal of Software,2009,20(5):1337-1348.
Song Jie,Li Tiantian,Yan Zhenxing,et al.Energy-efficiency model and measuring approach for cloud computing[J].Journal of Software,2012,23(2):200-214.
[3]Barham P,Dragovic B,Fraser K et al.Xen and the art of virtualization[A].Proceedings of the 19th ACM Symposium on Operating Systems Principles[C].New York,USA:ACM,2003:164-177.
[4]Nurmi D,Wolski R,Grzegorczyk C et al.The Eucalyptus open-source cloud-computing system[A].Cluster Computing and the Grid[C].Shanghai:IEEE,2009:124-131.
[5]Zhu Q,Zhu J,Agrawal G.Power-aware consolidation of scientific workflows in virtualized environments[A].Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing,Networking,Storage and Analysis[C].Washington DC,USA:IEEE,2010:1-12.
[6]Meng X,Isci C,Kephart J,et al.Efficient resource provisioning in compute clouds via VM multiplexing[A].Proceedings of the 7th International Conference on Autonomic Computing[C].NewYork,USA:ACM,2010:11-20.
[7]Bobroff N,Kochut A,Beaty K.Dynamic placement of virtual machines for managing SLA violations[A].10th IFIP/IEEE International Symposium on Intergrated Network Management[C].Munich,Germany:IEEE,2007:119-128.
[8]Minghong L,Wierman A,Andrew L L H et al.Dynamic right-sizing for power-proportional data centers[A].INFOCOM[C].Shanghai:IEEE,2011:1098-1106.
[9]Bin packing problem[EB/OL].http://en.wikipedia.org/wiki/Bin_packing_problem,2013-12-16.
[10]Epstein L,Stee R.Optimal online bounded space multidimensional packing[A].SODA[C].Philadelphia,USA:ACM,2004:214-223.
[11]Sonnek J,Chandra A.Virtual putty:Reshaping the physical footprint of virtual machines[A].Proceedings of the 2009 Conference on Hot Topics in Cloud Computing[C].San Diego,USA:ACM,2009.
[12]Seiden S S.On the online bin packing problem[J].Journal of the ACM,2002,49(5):640-671.
[13]Wood T,Shenoy P,Venkataramani A,et al.Black-box and gray-box strategies for virtual machine migration[A].Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation[C].Berkeley,USA:USENIX Association,2007:229-242.
[14]Jayasinghe D,Pu C,Eilam T,et al.Improving perfor-mance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement[A].Services Computing[C].Washington DC,USA:IEEE,2011:72-79.
[15]Khanna G,Beaty K,Kar G,et al.Application perfor-mance management in virtualized server environments[A].Network Operations and Mangement Symposium[C].Vancouver,Canada:IEEE,2006:373-381.
[16]Meng X,Pappas V,Zhang L.Improving the scalability of data center networks with traffic-aware virtual machine placement[A].INFOCOM[C].San Diego,USA:IEEE,2010:1-9.
[17]Hermenier F,Lorca X,Menaud J M,et al.Entropy:a consolidation manager for clusters[A].Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment[C].New York,USA:IEEE,2009:41-50.


Last Update: 2013-12-31