The problem is formulated in such a way that there exists a setof n virtual machines denoted as VM={, , … , } and a set of k tasksdenoted as T={, , , … , }. The load and capacity ofeach virtual machine and also the physical machine need to be calculated inorder to perform load balancing. Equation (1) 16 denotes capacity () of a single VM which iscalculated by adding its processing capacity and communication bandwidthability. As load balancing is done at intra-host level, the bandwidth componentis considered to be negligible and hence, the equation (1) is refined to equation(2). Capacity of a PM (C) which is given in equation (3) 16 is calculated bysumming up the capacity of all VMs in that particular PM.
(1) (2) (3)Load on a single VM is estimated using equation (4) consideringthe number of tasks on the service queue N(T) and sum of length of all thetasks running in whereas the load on a PM is calculated asgiven in equation (5). Processing time of a VM and a PM are given in equations (6)and (7) 15 respectively. (4) (5) (6) (7)Based on the values of the above parameters the scout bee checkswhether the host is in a balanced state or not. This is done by calculating thestandard deviation of the load using equation (8) (8)Each task associated with a priority is submitted to any VM inthe PM. Whenever a task is submitted, it is essential to find whether a VM isin a balanced state or not by comparing the calculated standard deviation valuewith a threshold set Ts 0-1. If iswithin the limit of Ts, then the system is said to be in a balanced state.Otherwise, the load balancing algorithm should be triggered to balance the loadamong the VMs.
The threshold value is set by experimenting with all the valuesfrom 0 to 1 and as per the simulation results, the value 0.2 leads to abalanced state. Hence, it is found that if , then the system is said to be in an unbalanced state.
I. Preemptive Scheduling with Honey Bee ForagingFigure 1 depicts the working process of the proposed PSHBFalgorithm. According to the proposed algorithm, load balancing is done byremoving tasks from overloaded VMs and scheduling them to the underloaded VMs.Here task scheduling is done on a preemptive manner by considering the priorityof tasks during preemption. Three classes of priority namely high, medium, andlow are considered. While removing a task from an overloaded VM, both priorityand remaining completion time of that task are taken into consideration inorder to reduce the makespan and the response time of the task. Following twopossibilities are identified during preemption:1.
Considering high priority tasks for preemption2. Exempting high priority tasks for preemptionThe reason for identifying the second possibility is that ifa high priority task under execution is preempted, it will have a greaterimpact on user satisfaction and response time of that task which ultimatelywill result in failure to achieve QoS on the providers’ side. As a result theprovider may be under the risk of SLA violation. Tasks are preempted based onthe load on the VMs. Hence, the VMs are grouped under three classes such asoverloaded VM group (OVM), balanced VM group (BVM), and underloaded VM group(UVM). This grouping is done based on the upper and lower limits (0.7 and 0.
3 respectively)on the load as given in equation (9) and will be useful in finding VMs that areoverloaded () and those that are underutilized (). After grouping, load on VMs in the OVM group and those inthe UVM group should be balanced by removing tasks from VMs of OVM group andscheduling them to suitable VMs of the UVM group.Figure 1. Flowchart for the proposed system Tasks removed from an overloaded VM are considered as scout bees,tasks waiting in the queue as onlooker bees and those executing in the VM asemployed bees.
VMs in the UVM group are considered as the food sources.