Article Preview
Top1. Introduction
Cloud Computing is emerging as a promising distributed computing paradigm. It delivers a wide range of services like Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). The cloud resources and services are dynamically provisioned like utilities. The elastic nature of the cloud facilitates users to have as much or little of service depending on their need at any given time. The IaaS model supports on demand provisioning of virtualized resources as a service. In this model, service consumers specify hardware and software configuration of Virtual Machines (VM) to be created and they execute their jobs on each VM (Smith & Nair, 2005). As the nature of the submitted jobs is parallelizable, a VM may require multiple cores for efficient execution. The key challenge is the implementation of efficient VM provisioner which leases suitable hosts for launching VMs that fulfill the customer requirements at the same time minimizing power consumption to facilitate the providers.
Moreover the state of the resource pool gets frequently changed due to the sporadic nature of the resource requirements. Hot migration capabilities of virtualization contribute to resource dynamics where VMs are moved rapidly between physical machines for load balancing and server consolidation (Smith & Nair, 2005). Some servers are shut down periodically for preventive maintenance after migrating the running VMs onto suitable servers, making a few servers unavailable for specific duration (Beltran, 2005; Dikaiakos, Pallis, Katsaros, Mehra, & Vakali, 2009; French, 2009) or the resource dynamics could be due to the failure of hosts. When there is unexpected peak load, few servers are powered on to mitigate the need for resources. Apart from the said dynamics involved due to servers’ availability, there are a few more dynamic attributes such as increase or decrease in the number of Processing Elements (PEs) available, size of memory, storage capacity and bandwidth of the servers during VM creation, VM deletion or VM migration. The Dynamic Voltage and Frequency Scaling (DVFS) technique inherent in recent microprocessor technology also introduces variable processing speed based on the load (Hamidi & Vafaei, 2009; Wang, von Laszewskiy, Dayalz, & Wang, 2010; Russell & Yoon, 2009). All of the above mentioned resource dynamics necessitates the need for a Meta-Scheduler which monitors the environment, detects the state change in the resources and finds the optimal or near optimal schedule for placing the VM instances onto available physical servers.
As the main feature of cloud computing is on-demand access to resources, the datacenters are over provisioned to handle the unexpected workload surges. The major issue here is in managing extremely large and dynamic datacenters for power conservation, while fulfilling the incoming VM requests. In the datacenter of a public cloud, generally hundreds and thousands of servers run at any instance of time, hosting many virtual machines and at the same time the cloud system keeps receiving the batches of VM requests. In this scenario, when there is a need to find few target hosts say 
hosts out of 
powered on hosts, which can fulfill a batch of incoming VM requests, then there is ‘
’ possible permutations of allocating the jobs to hosts making the problem combinatorial (Coffman, 1976).