An Inhomogeneous Hidden Markov Model for Efficient Virtual Machine Placement in Cloud Computing Environments

• Date: 01 July 2017
• Author: Kyrre Begnum,Hugo Lewi Hammer,Anis Yazidi
• Published date: 01 July 2017
• DOI: http://doi.org/10.1002/for.2441

Journal of Forecasting,J. Forecast. 36, 407–420 (2017)

Published online 19 September 2016 in Wiley Online Library (wileyonlinelibrary.com)DOI: 10.1002/for.2441

An Inhomogeneous Hidden Markov Model for Efficient Virtual

Machine Placement in Cloud Computing Environments

HUGO LEWI HAMMER,ANIS YAZIDI AND KYRRE BEGNUM

Department of Computer Science, Oslo and Akershus University College of Applied Sciences,

Oslo, Norway

ABSTRACT

In a cloud environment virtual machines are created with different purposes, such as providing users with computers

or handling web traffic. A virtual machine is created in such a way that a user will not notice any difference from

working on a physical computer. A challenging problem in cloud computing is how to distribute the virtual machines

on a set of physical servers. An optimal solution will provide each virtual machine with enough resources and at the

same time not using more physical services (energy/electricity) than necessary to achieve this.

In this paper we investigate how forecasting of future resource requirements (CPU consumption) for each virtual

machine can be used to improve the virtual machine placement on the physical servers. We demonstrate that a time-

dependent hidden Markov model with an autoregressive observation process replicates the properties of the CPU

consumption data in a realistic way and forecasts future CPU consumption efficiently. Copyright © 2016 John Wiley

& Sons, Ltd.

KEY WORDS cloud computing; CPU consumption; inhomogeneous hidden Markov model; stochastic

bin packing

INTRODUCTION

The use of cloud computing is increasing at tremendous speed as a result of the use of virtual machines having

exploded in recent years. More companies are centralizing their resources to data centres to ensure uninterrupted

power, better security, greater opportunities and availability. The number of data centres increased by 56% world-

wide from 2005 to 2010 (Koomey, 2008), and more hardware is being installed to handle the rapidly increasing

demand. Cloud computing now consumes more electricity every day than India (Greenpeace, 2010), and Google

alone consumes the same amount of energy as Norway’s capital city (Statistisk sentralbyrå, 2014; New York Times,

2011).

The need to make cloud environments more energy efficient is a major driver for data centres and cloud providers.

The idea is simple in principle: always align the number of running physical servers with current demand. This cannot

be solved just by knowing the virtual machine creation time, which is where the state-of-the art currently is in cloud

solutions such as OpenStack (2015). Virtual machines are created and removed by the cloud’s tenants, leaving ‘gaps’

of vacant capacity on physical servers. It is not guaranteed that new virtual machines will properly fill these gaps,

leaving an overhead of waste on many servers. Furthermore, since not all virtual machines are active all the time

(in fact, the opposite is much more likely), one can textitmigrate them and textitpack them into a smaller number

of physical machines in order to power the remaining servers down, thus saving energy. Conversely, in the case of

increased demand for capacity and computational power, more physical servers can be booted and virtual machines

redistributed, so that their requirements are met.

Even though most cloud technologies and virtual environments support the technical building blocks of dynamic

power savings, the remaining part consists of the algorithms by which the process can be automated. It is a major

challenge that most cloud environments have virtual machines that behave on the basis of the local context of their

users and user demands, making it difficult to reuse workload profiles. For example, a cloud deployment at a college

or university would be used to run computational jobs and student labs, but not to run commercial services. Its usage

profiles would not match that of a commercial cloud vendor whose virtual machines follow other usage patterns to a

greater extent. The problem therefore fits well with the domain of machine learning and statistical forecasting, where

local behaviour has to be learned so that accurate predictions can be made as the basis for action.

A lot of effort has been devoted to designing optimal solutions for virtual server consolidation (see, for example,

Ferdaus and Murshed, 2014, for a positive review). The majority of the works consider the problem as a deterministic

resource allocation problem and typically as a bin-packing problem (Johnson, 1974). In reality, resource demands

Correspondence to: Hugo Lewi Hammer, Department of Computer Science, Oslo and Akershus UniversityCollege of Applied Sciences, Oslo,

Norway. E-mail: hugo.hammer@hioa.no

Copyright © 2016 John Wiley & Sons, Ltd