Publicação

Efficient lower bounding procedures with application in the allocation of virtual machines to data centers

Detalhes bibliográficos
Resumo:	Cloud computing is becoming an alternative model for delivering computing resources and services to end-users and companies. The configuration of the clouds raises many issues that come from the need to manage efficiently the available resources in the data centers and from the agreements on the quality of the service that must be delivered to the clients. One of the key issues in the operation of the clouds consists in determining how the workload should be distributed among the physical machines such that the utilization of the computing resources in the cloud computing data centers is maximized. In this paper, we address this latter problem. We describe in particular a set of new and fast procedures for computing lower bounds on the number of physical machines that are required by a cloud provider to execute efficiently a set of user applications (virtual machines). To compute the bounds, we formulate this virtual machine allocation problem as a bin-packing problem and we address some of its variants. All our lower bounding procedures are polynomial-time algorithms that rely on the use of maximal dual-feasible functions. These functions are parameter dependent. We describe the best set of parameters when the 1-dimensional variant of the problem is considered, and we discuss the complexity of the lower bounding procedures that are proposed. We report also on extensive computational experiments conducted on benchmark instances of the literature. The results of these experiments show the strength of the lower bounds described in this paper.
Autores principais:	Rietz, Jurgen Endre
Outros Autores:	Macedo, Rita; Alves, Cláudio; Carvalho, José Valério de
Assunto:	Combinatorial optimization Lower bounds Maximal dual-feasible functions Polynomial complexity Virtual machine allocation problem Cloud computing.
Ano:	2011
País:	Portugal
Tipo de documento:	artigo
Tipo de acesso:	acesso restrito
Instituição associada:	Universidade do Minho
Idioma:	inglês
Origem:	RepositóriUM - Universidade do Minho

Descrição
Resumo:	Cloud computing is becoming an alternative model for delivering computing resources and services to end-users and companies. The configuration of the clouds raises many issues that come from the need to manage efficiently the available resources in the data centers and from the agreements on the quality of the service that must be delivered to the clients. One of the key issues in the operation of the clouds consists in determining how the workload should be distributed among the physical machines such that the utilization of the computing resources in the cloud computing data centers is maximized. In this paper, we address this latter problem. We describe in particular a set of new and fast procedures for computing lower bounds on the number of physical machines that are required by a cloud provider to execute efficiently a set of user applications (virtual machines). To compute the bounds, we formulate this virtual machine allocation problem as a bin-packing problem and we address some of its variants. All our lower bounding procedures are polynomial-time algorithms that rely on the use of maximal dual-feasible functions. These functions are parameter dependent. We describe the best set of parameters when the 1-dimensional variant of the problem is considered, and we discuss the complexity of the lower bounding procedures that are proposed. We report also on extensive computational experiments conducted on benchmark instances of the literature. The results of these experiments show the strength of the lower bounds described in this paper.

Atividades financiadas

Não foram encontrados projetos financiados.