Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers

Jiaxin Li; Dongsheng Li; Yuming Ye; Xicheng Lu

doi:10.1109/TST.2015.7040517

Tsinghua Science and Technology 2015, 20(1): 81-89 https://doi.org/10.1109/TST.2015.7040517

Open Access | Issue | Published: 12 February 2015

Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers

Show Author's Information Hide Author's Information Jiaxin Li(

), Dongsheng Li, Yuming Ye, Xicheng Lu

National Key Laboratory of Parallel and Distributed Processing （PDL）, College of Computer, National University of Defense Technology, Changsha 410073, China.

Keywords:

virtual machine allocation, cloud data center, multiple tenants, multiple knapsack problem

Cite this article:

Li J, Li D, Ye Y, et al. Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers. Tsinghua Science and Technology, 2015, 20(1): 81-89. https://doi.org/10.1109/TST.2015.7040517

Download citation

EndNote(RIS)

BibTeX

397

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

Virtual Machine (VM) allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and the network distance between a tenant's VMs may considerably impact the tenant's Quality of Service (QoS). In this study, we define and formulate the multi-tenant VM allocation problem in cloud data centers, considering the VM requirements of different tenants, and introducing the allocation goal of minimizing the sum of the VMs' network diameters of all tenants. Then, we propose a Layered Progressive resource allocation algorithm for multi-tenant cloud data centers based on the Multiple Knapsack Problem (LP-MKP). The LP-MKP algorithm uses a multi-stage layered progressive method for multi-tenant VM allocation and efficiently handles unprocessed tenants at each stage. This reduces resource fragmentation in cloud data centers, decreases the differences in the QoS among tenants, and improves tenants' overall QoS in cloud data centers. We perform experiments to evaluate the LP-MKP algorithm and demonstrate that it can provide significant gains over other allocation algorithms.

Full text

Abstract

Full text

Outline

About this article

Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers

Show Author's information Hide Author's Information Jiaxin Li(

), Dongsheng Li, Yuming Ye, Xicheng Lu

National Key Laboratory of Parallel and Distributed Processing （PDL）, College of Computer, National University of Defense Technology, Changsha 410073, China.

Abstract

Keywords: virtual machine allocation, cloud data center, multiple tenants, multiple knapsack problem

References(22)

[1]

Endo P. T., Palhares A. V. de Almeida, Pereira N. N., Goncalves G. E., Sadok D., Kelner J., Melander B., and Mangs J. E., Resource allocation for distributed cloud: Concepts and research challenges, Network, IEEE, vol. 25, no. 4, pp. 42-46, 2011.

DOI Google Scholar

[2]

Lu X., Wang H., Wang J., Xu J., and Li D., Internet-based virtual computing environment: Beyond the data center as a computer, Future Generation Computer Systems, vol. 29, no. 1, pp. 309-322, 2013.

DOI Google Scholar

[3]

Rathod C. J., A survey on different virtual machine placement algorithms, International Journal of Advance Research in Computer Science and Management Studies, vol. 2, no. 2, pp. 266-271, 2014.

Google Scholar

[4]

Alicherry M. and Lakshman T., Network aware resource allocation in distributed clouds, in INFOCOM, 2012 Proceedings IEEE, 2012, pp. 963-971.

DOI

[5]

Chen W., Cao J., and Wan Y., QoS-aware virtual machine scheduling for video streaming services in multi-cloud, Tsinghua Science and Technology, vol. 18, no. 3, pp. 308-317, 2013.

DOI Google Scholar

[6]

Li M., Lukyanenko A., Tarkoma S., and Yla-Jaaski A., Mptcp incast in data center networks, Communications, China, vol. 11, no. 4, pp. 25-37, 2014.

DOI Google Scholar

[7]

Greenberg A., Hamilton J. R., Jain N., Kandula S., Kim C., Lahiri P., Maltz D. A., Patel P., and Sengupta S., Vl2: A scalable and flexible data center network, ACM SIGCOMM Computer Communication Review, vol. 39, pp. 51-62, 2009.

DOI Google Scholar

[8]

Al-Fares M., Loukissas A., and Vahdat A., A scalable, commodity data center network architecture, ACM SIGCOMM Computer Communication Review, vol. 38, pp. 63-74, 2008.

DOI Google Scholar

[9]

Martello S. and Toth P., Heuristic algorithms for the multiple knapsack problem, Computing, vol. 27, no. 2, pp. 93-112, 1981.

DOI Google Scholar

[10]

Nakada H., Hirofuchi T., Ogawa H., and Itoh S., Toward virtual machine packing optimization based on genetic algorithm, in Distributed Computing, Artificial Intelligence, Bioinformatics, Soft Computing, and Ambient Assisted Living. Springer, 2009, pp. 651-654.

DOI

[11]

Vega W. F. De La and Lueker G. S., Bin packing can be solved within 1+ε in linear time, Combinatorica, vol. 1, no. 4, pp. 349-355, 1981.

DOI Google Scholar

[12]

Gao Y., Guan H., Qi Z., Hou Y., and Liu L., A multi-objective ant colony system algorithm for virtual machine placement in cloud computing, Journal of Computer and System Sciences, vol. 79, no. 8, pp. 1230-1242, 2013.

DOI Google Scholar

[13]

Song F., Huang D., Zhou H., Zhang H., and You I., An optimization-based scheme for efficient virtual machine placement, International Journal of Parallel Programming, vol. 42, no. 5, pp. 853-872, 2014.

DOI Google Scholar

[14]

Gupta R., Bose S. K., Sundarrajan S., Chebiyam M., and Chakrabarti A., A two stage heuristic algorithm for solving the server consolidation problem with item-item and bin-item incompatibility constraints, in Services Computing, 2008, SCC'08, IEEE International Conference on, vol. 2, 2008, pp. 39-46.

DOI

[15]

Zhu Y., Liang Y., Zhang Q., Wang X., Palacharla P., and Sekiya M., Reliable resource allocation for optically interconnected distributed clouds, in Communications (ICC), 2014 IEEE International Conference on, 2014, pp. 3301-3306.

DOI

[16]

Song Y., Sun Y., and Shi W., A two-tiered on-demand resource allocation mechanism for vm-based data centers, Services Computing, IEEE Transactions on, vol. 6, no. 1, pp. 116-129, 2013.

DOI Google Scholar

[17]

Hao F., Kodialam M., Lakshman T., and Mukherjee S., Online allocation of virtual machines in a distributed cloud, in INFOCOM, 2014 Proceedings IEEE, 2014, pp. 10-18.

DOI

[18]

Ahmed W. and Wu Y., Estimation of cloud node acquisition, Tsinghua Science and Technology, vol. 19, no. 1, pp. 1-12, 2014.

DOI Google Scholar

[19]

Beloglazov A., Abawajy J., and Buyya R., Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing, Future Generation Computer Systems, vol. 28, no. 5, pp. 755-768, 2012.

DOI Google Scholar

[20]

Meng X., Pappas V., and Zhang L., Improving the scalability of data center networks with traffic-aware virtual machine placement, in INFOCOM, 2010 Proceedings IEEE, 2010, pp. 1-9.

DOI

[21]

OpenStack, http://www.openstack.org/, 2014.

[22]

CloudStack, http://cloudstack.apache.org/, 2014.

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 05 November 2014

Revised: 01 December 2014

Accepted: 08 December 2014

Published: 12 February 2015

Issue date: February 2015

Copyright

Acknowledgements

This work was supported in part by the National Key Basic Research and Development (973) Program of China (No. 2011CB302600), the National Natural Science Foundation of China (No. 61222205), the Program for New Century Excellent Talents in University, and the Fok Ying-Tong Education Foundation (No. 141066).