-the issue of task scheduling in a cloud environment is one of the most important issues that must be considered by the cloud platform providers in data centers. The use of the right solution to solve this problem enables cloud platform providers to have the most use of available resources; and also increase the customer satisfaction by providing quality of service parameters. In this paper it has been tried to provide a dynamic scheduling algorithm using machine learning techniques and naïve-Bayes classifier in a cloud environment. The proposed method is one of the dynamic task scheduling methods and load distribution at any moment is conducted according to the latest information from previous and current server status. The distinction of this method with previous studies is the use of data mining techniques (classification) in load distribution. Since this classification method has higher accuracy and speed compared with other methods, therefore this classifier helps us to achieve the optimal solution in less time. Simulation results show that the proposed method has a good improvement in terms of Makespan time and load balancing degree.
INTRODUCTION Cloud environment provides a huge context of servers in the data center, so that when users request resources, provides them in shared mode. To enable the applications to use the resources in accordance with their requirements, an appropriate mechanism to distribute requests to virtual machines is required. That is why the scheduling of the requests is one of the most important issues in cloud environment and in recent years it has attracted much attention of researchers. Task scheduling in cloud computing means optimal allocation of requests to the computing resources in the data center [1]. In scheduling, tasks are allocated to different types of virtual machines with regard to the limitations specified by the user and service provider. One of the major challenges in task scheduling is the equitable distribution requests on the resources according to application requirements. Providing scheduling algorithm with the aim of load balancing can reduce makespan time and increase productivity of machines.
In this paper, a dynamic task scheduling algorithm has been proposed to increase the load balancing in the cloud environment. Using Naïve Bayesian classifier technique, the proposed algorithm has tried to put the requests on the machines in a balanced way; as in addition to the reduction of makespan time, increases the efficiency of resources. The advantage of the proposed algorithm in the above method is to reduce the overload and increase resource utilization. Simulation results show that this method performs well in completion time of the longest task and increasing the level of load balancing. In summary it can be said that our main focus in this article includes the following: 1. Providing an appropriate method for scheduling the requests using data mining techniques to reduce makespan time and increase resource utilization; 2. The use of classification techniques for equitable distribution of requests; 3. Targeted analysis to show the effectiveness of the proposed algorithm, compared to previous algorithms; The remainder of this paper consists of the following sections: Section 2 reviews related work, in section 3 after the introduction of Naïve Bayesian classifier and formulation of the problem, details of the proposed method is described in detail. In Section 4, simulation and evaluation of the proposed method is presented and finally, in Section 5, conclusions and future works are expressed.
II.
Different studies are carried out in conjunction with load
balancing in cloud environment, load balancing algorithms are
generally divided into two categories: static and dynamic: In the
static method, the allocation of tasks to virtual machines is based
on the functionality of virtual machine and initial condition of
each machine; in other words, this process is only based on the
data of the nodes and their features. This information includes
the amount of processing power, internal memory and storage
capabilities and the power of communications between other
virtual machines. An important feature of static algorithms is
that, these algorithms do not consider changes occurred
dynamically on virtual machines at any moment. In addition,
they do not have the ability to adapt to changing workloads on
each virtual machine over time. Some static algorithms are
Round Robin (RR) algorithms or weighted RR or load balancing
algorithm using ant colony algorithm [2] or procedures based on
the amount of the resources of physical machines [3].
Unlike static algorithms, dynamic method of distribution in
addition to the basic functionality of each virtual machine,
assigns tasks to virtual machines based on the current status of
the machine and the workload on it. Such algorithms are
required to review each moment of machines and based on the
results of this review, the requests are transferred from one
machine to another. These methods, however, are of greater
complexity than the static method, but they are more efficient
[4]. A lot of related work has been done on dynamic load
balancing and each has been presented with different objective
such as response time[5,6,7], scalability[6,8], reducing
migration time in requests [
Mittal et al. [
III.
PROPOSED METHOD
Naïve Bayesian is a statistical method for classification. Research shows that although this method compared with other methods such as classification decision tree and selected neural network classifiers have equal efficiency; in contrast has higher accuracy and speed than other methods [17].
Assume that, there is m classes called {Y1, Y2, … ,Ym} and tuple X have been given as input. Using the Classifier it is predicted that X belongs to the class with the highest posterior probability, in other words, X belongs to the class Yi if and only if the Eq. (3-1) is true.
P(Yi|X) ≥ P(Yj|X) j ∈ 1, . . m (3-1) In Eq. (3-11) probability is calculated using Eq. (3-2).
P(Yi|X) = P(X|Yi)×P(Yi) (3-2)
P(X) In the Eq. (3-2), P (X) is constant for all classes and only the values P (X | Yi) × P (Yi) should be highest value. To calculate P (X | Yi) under the assumptions of Naïve Bayes, it is assumed that class conditional is independent and based on previous training is obtained according to Eq. (3-3).
P(X|Yi) = ∏kn=1 P(xk|Yi) (3-3) In Eq. (3-3) if the values of P (X | Yi) × P (Yi) is more than most other classes in Yi class, this class is selected.
Suppose VM = {VM1, VM2… VMm} is a set of virtual machines used to host user requests. Also Task = {T1, T2... Tn} is a set of tasks that are intended to be run on virtual machines. Details of the proposed method for assigning requests are as follows: 1. First for initial allocation of the requests on virtual machines MAX-MIN method is used. As from the request queue the request with the highest runtime is selected and put on the machine where the runtime of this request is less. Then the requests in the queue waiting and the runtime of requests on each machine are updated. And it will continue until the completion of all requests. 2. After the initial allocation of the requests to the method by Max-Min, in this step, the load balancing status of the system is investigated. To do this, the standard deviation of the system load is obtained and thereby the load balancing of the system will be evaluated. To calculate the standard deviation of the load in the system the Eq.(3-4) can be used: σ = √ m1 ∑im=1(PTi − PT)2 (3-4) Where m is the number of machines in the system and PTi is the processing time of virtual machine i and PT is the processing time of the system. If the standard deviation is greater than the desired threshold, the system is unbalanced and requires a request transfer from overloaded machines to under-loaded machines. For this, the machines are divided into three categories: overload, balanced and under load and the request is then removed from the overload set and then in accordance with the following procedure they will transfer to the members of the set of under-load machines. To transfer the requests from the overload class to the under-load class, Naïve Bayesian Classification Method is used. For this purpose, each of the machines of under-load class is considered as a class. Request tk is selected from the overload class, and then Eq. (3-5) is calculated for it.
P(VMi|tk = compatibl)e=
P(tk = cmpatibl|eVMi) × P(VMi)
P(tk=compatible) (3-5) (3-6) (3-7) For all virtual machines P(tk=compatible) is constant and is obtained according to Eq. (3-6). if(Global Capacitoyn allVM > Requested Capacity fToarsk)
P(tk=compatible) = 1 else P(VMi) For each machine is based on the utilization of the machine. Since the utilization of each machine is less, it is better to be selected, to achieve this goal, the probability of the machine with less utilization increases; therefore P(VMi) is obtained according to the Eq. (3-7): P(VMi) = 1 − Ucpu
Where
Ucpu =used CPU Capacity
ALL CPU Capacity The amount of P(tk = cmpatibl|eVMi) is also calculated according to Eq. (3-3) based on the product of the probability of previous requests put on that machine.
As a result, using Naïve Bayesian Classification Method for transfer of requests from overload machine to under-load machines, a machine from under-load machines is selected which its compatibility with the considered request is higher than other machines and it has less utilization. This trend has continued until load balancing in the whole system. Figure (1) shows the pseudo-code of the proposed algorithm.
IV.
RESULT EVALUATION In this section we will discuss the details of the simulation of the algorithm presented in the previous section. Then through the charts the proposed method are evaluated. This fact that, the environment is software as a service and also our tools for simulation is CloudSim software [18], would be useful. This simulator allows us to create a virtualized environment and supports the allocation of resources based on the request. In fact, the core of the simulator for modeling our method is extended. Cloud computing has been simulated to assess this sector of a data center consisting 3 hosts with virtualization capabilities. In fact, it is assumed that the virtual instruments such as Xen have been installed, which can share resources. The properties of each host are according to Table (1). 16 virtual machines with different characteristics are put on this data center. Each virtual machine runs some applications with variable number of instructions between 500 and 4500. As mentioned earlier, we aim to provide comprehensive and appropriate algorithms for request scheduling in the cloud platform, as it has the minimum makespan time and maximum load balancing degree with equitable distribution requests on the virtual machines.
Input :list of tasks output : list of Vm Id for running any task; 1. Allocate Tasks to VMs Base on MAX-MIN Algorithm. 2.Calculate Standard deviation for load of all VMs
If (Standard deviation>threshold)
Group VMs based on load as UVM, BVM and OVM if (OVM≠ ) Select VM by maximum processing Time in OVM
TaskID: Select task by minimum processing time in Selected VM in OVM
Calculate Probablity value Of any VM in UVM based on equation (3-5)
Sort Probablity value any VMs in UVM by ascending order.
Select VM by maximum Probablity value VMID=selected VM id
Allocate selected task to VMID Else
break;
3. Repeat step 2 for load of all VMs
If Makespan is calculated according to the Eq. (4-1); Figure (2)
indicates a comparison between the Makespan in the Round
Robin method and scheduling of paper [
Improved RASA[
Proposed Another criterion which is important is the degree of imbalance defined as the Eq. (4-2) [5].
DI = Tmax−Tmin (4-2)
Tavg
In Eq. (4-2), Tmax and Tmin are the highest and lowest runtimes
between virtual machines and Tavg is the average runtime among
all virtual machines. Figure. (4) Shows the comparison between
the degree of imbalance in the method provided in algorithm of
paper [
Proposed by using SVM
Proposed
Conclusions and future works
In this paper we have provided a task scheduling method with
Naïve Bayesian Classification Method aim at creating load
balancing. This algorithm with classification of virtual machines
and selection of suitable machine for the existing requests
reduces the makespan time and increases the level of load
balancing. In the following, the proposed method is compared
with the basic Round Robin method and the scheduling method
[