Abstract
Cloud computing is the utility computing that provides virtualized resources, applications, and services using distributed network and Internet. Cloud computing service offers the ability to scale up and scale down your computing requirements and most importantly to reduce the cost of deployment. Many organizations are migrating to cloud computing services to lower the risk and for better business continuity.In case of on-demand access user requests infrastructure services for immediate access and for a very short interval of time, they have to pay certain charge depending upon that duration.In cloud computing, infrastructure requests are served by the allocation of virtual machines to those requests; these virtual machines should be placed on the underlying hardware infrastructure called datacenter. In this paper we have proposed a model for the efficient allocation of virtual machines on the cloud infrastructure to reduce the allocation time and to optimize the resource utilization. The proposed model is simulated and its performance is compared with two other existing models.
INTRODUCTION
Cloud computing is the utility computing that provides unlimited virtualized resource to build a customized infrastructureor platform to run applications or full phase services as a pay-as-you-use basis. Cloud computing has changed the paradigm of system deployment. The details of complex system implementation are abstracted from the end user and with the help of virtualization techniques resources are virtualized that gives an illusion of infinitely scalable and universally available resources [3] [4] . In cloud computingservices are offered with the help of Internet to the end users as Something-as-a-Service. Three universally accepted service models are Software as a Service (SaaS), Platform as a Service (PaaS) and Infrastructure as a Service (IaaS) [5] . Software as a Service provides a complete environment with pre-installed applications along with user interface. Client can access these applications using any device capable of operating a web browser. Platform as a Service provides a framework for the developers to create and deploy their own application on a hosted infrastructure. The customer does not have to bother about the underlyinghardware; they only have to configure the operating environment in the interface provided to them and they can use any programing language supported by the cloud service provider to build their application in that environment.In Infrastructure as a Service computing model client can borrow the fundamental hardware resources for building their own framework. They can customize their entire framework with the help of virtual machines, virtual storage, virtual network etc. The client does not have to manage the actual physical resources, as they are provided with virtual resources which can be managed programmatically.
Fig 1: Cloud Computing Service Models
In Infrastructure as a Service model the infrastructure requests are served by allocating virtual machines to those requests [4] [10] . So on service providers side one of the primary concern is to allocate the virtual machine images into the actual physical resource i.e. the underlying hardware infrastructure. This allocation should be efficient so that resource utilization will be optimized and more requests can be served in lesser time. The virtual machine placement strategy in cloud computing can be classified into three categories [6] ; reservation, on-demand access and spot markets. In case of reservation type a user has to pay a certain fee for a particular period for each instance of a virtual machine. In case of on-demand access user requests virtual machine for immediate access for a very short interval of time, and pay the charge depending upon that duration. While in case of spot markets the users need to specify the amount they are willing to pay for the requested virtual machines, as in spot markets there is frequent fluctuation in provider's price. The users are allocated with virtual machines only when the provider's price is same or less than the user's fee. This allocation part is done by the hypervisor [2] of the service provider. The hypervisor contains the list of all the physical resources available in the datacenters and information about their states. So the hypervisor has to design properly and a In this paper we have designed an efficient algorithm that follows a best fit strategy for allocation of virtual machine requests to the physical host. Because of the best fit strategy the resource utilization is optimized to some extent. We have also followed a tree based approach to represent the resource list, instead of maintaining a resource queue for quick allocation of virtual machine to the host machines.
Fig 1: Cloud Computing Service Models
The rest of this paper is organized as follows. In section 2 we discuss prior works which address issues related to this topic. Section 3 describes the proposed framework followed by proposed algorithm in sub section 3.1. Section 4 presents the performance evaluation of the proposed algorithm. Finally Section 5 concludes the paper by summarization of the work.
RELATED WORK
OpenNebula is an open source toolkit used for deploying cloud service over the underlying hardware devices, the deployment can be either private, public or hybrid [7] [14] . It manages all the storage and computing requirements of the deployed infrastructure. It uses the kernel based virtual machine-KVM and can fit into any existing datacenter by integrating it with storage and networking solution. The virtual machine scheduler used in OpenNebula is known as match making scheduler, which uses a predefined rank [9] [12] for prioritizing the available resources. Based on the priority, this scheduler places the virtual machine on the host having the highest priority [11] . This algorithm takes requirements and predefined rank as its input and produces the resource number in which to place the virtual machine as output. When a virtual machine request arrives at the scheduler, first it sweeps away the resources which are not befitting into the requirement. The rank scheduling algorithm is delineated below. Zang Y. et al. [13] proposed a scheme for integration of ondemand infrastructure resource by considering resource consumption and allocation. They introduced two adoptive control loops for managing infrastructure requests for PaaS application: resource allocation loop and resource consumption optimization loop. To improve the resource utilization they used optimization loop which includes a management function and to provide appropriate amount of resource they used allocation loop. They have combined these two loops for providing resource on-demand by running it repeatedly. A framework called SmartRod is implemented to verify the correctness of the scheme.
RELATED WORK
Kim H. et al. [10] designed a system based on Grid middleware to improve performance and resource utilization of cloud system. As the resource requests are dynamic and not monotonous hence static configuration is not capable to serve these requests. But by using virtualization reliability can't be guaranteed, hence they proposed three methods to solve this limitation of virtualization. Xen and Globus toolkit is used to simulate the framework. They performtwo kinds of experiments: middleware overhead analysis and Grid middleware utilization. Figure 2 elucidates the model for allocation of virtual machines to physical host machines present in the datacenters. Client/user can place their list of requirements for any service in the interface provided with the help of a web browser, that may require computational and storage infrastructure. That request is communicated to the cloud service provider through internet. The service provider will serve the requests by placing individual requests to suitable virtual machines that can perform the requisite operations. The virtual machine specification is now forwarded to the hypervisor of the service provider. Hypervisor uses the virtualization tools to create virtual machines of the specified specification. The virtual machine manager keeps track of the created virtual machines. But the problem is to map the virtual machine requests to the host machines. To resolve this problem virtual machine manager sends the virtual machine specifications to the virtual machine scheduler (VM Scheduler). But in this model instead of sending that request directly, a binary search tree of the requested virtual machines is created and that is sent to the VM Scheduler. This is done to improve the resource utilization, which is explained in the next sub section in the algorithm. Now VM scheduler will take the maximum requirement node from that virtual machine tree and will search for a host that will best fit the requirement. For implementing the best-fit strategy all the physical resources are also logically organized in a binary search tree, sincesearching a host using this data structure will take in average O (log N) time where N is the number of physical hosts. This will reduce the time for allocation. After getting the proper host the scheduler will return the host number to the virtual machine manager for placement of virtual machine on that host.
PROPOSED MODEL

Fig 2: Proposed framework for VM placement
Now the virtual machine manager has all information about the virtual machine and its location; it will now send a service activation message to the client/user. After that client/user can access the service for the duration specified.
The VM Scheduler Algorithm
Let Host List = {H 1 3 ,…VM n }. The time interval is used to avoid the problem of starvation and is very small (let's say two seconds) to avoid the delay. Here we have to do a mapping VM Queue → Host List, the mapping should be done in such a way that it will optimize the use of resources and should be faster. Figure 3 elucidate the flow chart of the proposed algorithm where best fit is decided based on the following formula.
The VM Scheduler Algorithm
Here RVMS is required virtual machine specification, and AHS is the available host specification. When a virtual machine request arrives at the scheduler, it calcutes this value at each host arranged in the binary search tree starting from the root node traversing towards the leaf node, until it finds a best fit. If it finds this value to 1 for a perticular host then that is the perfect fit and that host nood is assigned as the best fit node for that virtual machine. If the value calculated is greater than 1 then that host is not a candidate host for that virtual machine and the search will continues to its right child host node.
Fig 3: Flow chart for VM Scheduling algorithm
If the value is less than 1 i.e. a fraction between 0 to 1 then the search bigins in the direction of left host node and the value at each left and right child node is calculated. If the value is found less than the value that has been calculate at its parent host node then it will stop searching further and declare it's parent node as the best fit node. For example let there are five host nodesH 1 to H 5 present at the datacenter having memory specification (in MB) 1024, 360, 525, 575, 680 respectively. These host machines are organized in the host tree as shown in the figurebelow.
Fig 4: Host representation
Suppose a virtual machine request having memory specifacation 480 MB arrives at the scheduler. Now scheduler will calculate the value at the root node i.e H 5 . The value is found to be 0.71. Now the searchwill continue in left direction i.e. H 3 . The value at H 3 is 0.91. Next host node is H 2 and the value iscalculated to 1.33 which is greater than 1, hence rejected. So the best fit host is its parent host node having the calculated value 0.91. Hence host H 3 is the best host to run this virtual machine request. The purpose of arranging the virtual machine requests in binary search tree is: suppose two virtual machine (VM) requests arrive at a time having memory requirment 510 MB and 400 MB. If the allocation of 510 MB VM is processed first then it will get allocated at the H 3 host, and 400 MB request is allocated at H 4 host. The remaining memory at H 3 is 15 MBand at H 4 175 MB. But if the 400 MB request is processed first then first it will get allocated to host H 3 , the remaining memory is 125 MB and 510 MB request is allocated to host H 4 , the remaining memory at H 4 is 65 MB. So in the first case we are left with a big fragment of memory i.e. 175 MB, which can be used to allocate some new requests. In the second case we got two fragments of memory but that may not get utilized (let's say when a VM request for 150 MB memory arrives). Hence this technique improves the resource utilization. Also to insert a new request in that time interval will take in average O(log n)time. The VM scheduling algorithm takes VM Tree i.e BST VM as input and returns allocated host machine as the output. Thedetailed algorithm is delineated below. 
PERFORMANCE EVALUATION
The proposed model is simulated using CloudSim toolkit [18] ; an environment for simulating the cloud computing applications. The proposed VM Scheduling algorithm is compared with OpenNebula Ranking algorithm and Eucalyptus Greedy algorithm, by simulating them using the same toolkit. For simulating this environment we have simulated one datacenter inside which seven host machines of different specifications are running. We also have simulated seven virtual machine requests of different specifications which will be placed on the host machines. The specification of the host machines and virtual machine requests are depicted in table 1 and table 2 respectively. In this experiment we are only varying the memory requirement (In MB) of virtual machine requests i.e. we are considering memory intensive applications. All the three algorithms are executed independently with the same host and virtual machine instances shown in the above two tables. Fig  5 shows the mapping between host machine and virtual machine request. Fig 6 depicts the available memory at each host after all the virtual machines have been scheduled to proper hosts, which shows the resource utilization of threealgorithms. Finally Fig 7 shows the plotted graph between the scheduling algorithms and time consumed by each of them to perform the complete operation. Above graph shows that the highest available memory at a single host is at host H3 using the proposed algorithm, so host H3 can serve a high memory request if any arrives at that time. The proposed algorithm has two big peaks in the graph at H3 and H6, whereas the other algorithms have multiple small peaks which show that the resource utilization of proposed algorithm is better than that of the other two. 
CONCLUSION
In cloud computing infrastructure requests are served by allocating virtual machines on the underlying physical infrastructure. As in on-demand access user requests resources for a short time interval and for immediate use, hence these requests have to be served quickly by allocating them virtual machines. These virtual machines have to beplaced on proper host machines on the actual infrastructure, so that more number of resource requests can be served in lesser time. Hence a proficient resource allocation algorithm should run at the hypervisor that can do this job in lesser time and optimize the use of resources. In this paper our experimental results shows that the proposed framework can improve the resource utilization to serve more number of resource requests at a time without compromising the allocation time.

{'paper_id': '62233755', 'title': 'Efficient Virtual Machine Placement for On-Demand Access to Infrastructure Resources in Cloud Computing', 's2_url': 'https://api.semanticscholar.org/CorpusID:62233755', 'source': 'S2ORC'}