Survey on Scheduling Techniques in Cloud Computing

Survey on Scheduling Techniques in Cloud Computing

Liji Jacob

Computer Science Department Karunya University Coimbatore-India

V. Jeyakrishnan

Assistant Professor, Computer Science Department

Karunya University Coimbatore-India

Abstract- Cloud computing refers to the infrastructure as a cloud through which the users are able to access the applications on demand from anywhere in the world. The resources in cloud computing are dynamic in nature therefore there is a need for effective scheduling. The scheduling techniques should be selected in such a way that the various user demands are satisfied and minimization of the makespan and cost. In this paper gives an overview of how the various scheduling techniques are used in the cloud environment and what all parameters are met.

Keywords- cloud computing, makespan, Scheduling, , virtual resources ,virtualization

1. INTRODUCTION

The existing technologies like grid computing and utility computing leads to the development of cloud computing. It is a parallel and distributed computing of some interconnected and virtualized computers that can be allocated dynamically. Cloud computing has become prominent based on three major trends: virtualization, service orientation and standardization of computing through the internet. The cloud computing refers to a stack of summary, highly scalable and administrated IT infrastructures that is able to provide the customer applications and is billed based on use.Based on the preference and requirements of the user the computing resources are allocated dynamically. By using the virtualization technology the cloud computing resources are packed into virtual resources [9].The jobs cannot be scheduled manually since the user is dealing with a thousand of virtualized resources. Because of the emergence of commercialization and virtualization technology in the cloud architecture the job scheduling complexity of cloud computing is left to the virtual machine layer through resource utilization. Hence in the allocation of the resources to each job efficiently scheduling plays an important role.

In the distributed environment the scheduling techniques are selected in such a way that it should satisfy the QoS parameters and to minimize the total completion time of the tasks and also to minimize the cost of execution. It should

also maximize the throughput and a high performance should be obtained.

The objective of the paper is to focus of various scheduling techniques. The rest of the paper is organized as follows. Section 2 presents various existing scheduling algorithms and section 3 concludes the paper.

1. EXISTING SCHEDULING TECHNIQUES

   1. A Priority based Job Scheduling algorithm:Ghanbari et al.[2]proposed a new priority based job scheduling algorithm in cloud computing. A lot of jobs can be given to the system and some of those jobs cannot stay for a long time since it needs to be fulfilled faster. Therefore there is a need for the priority to be given for each of the jobs. In the priority based job scheduling algorithm the jobs are selected based on the priority being given to them by the system. The basis of this algorithm is the Theory of Analytical Process where a multi-criteria decision making model(MCDM) and a multi-attribute decision making model (MADM) is present. A comparison matrix technique is used to pair the tasks whenever the cloud computing service providers receive the tasks from users. The main demerits of this algorithm are complexity, consistency and finish time. The complexity is due to the computation of the priority vectors of the comparison matrix. The consistency is caused by the decision made by the decision makers. Mainly there are three levels of priority being used in this algorithm: first is an objective level that consists of the scheduling techniques, the second level is an attribute level that consists of various resources and the third level is the alternative level that consists of the jobs given by the users. A reasonable complexity can be obtained by the use of this algorithm.

   2. Job Scheduling algorithm based on Berger Model: Baomin et al.[9] have implemented the job scheduling process based on dual fairness constraint.The commercialization and virtualization characteristics of the cloud computing are addressed for the job scheduling based on the Berger model. In the Berger model a theory of distributive justice is expressed in which two

      fairness constraints task justice and system justice are considered. Likewise in cloud computing also there are two fairness constraints that can be considered. For the first constraint the tasks are classified based on the QoS parameters like the completion time and bandwidth.

      The working mechanism of the algorithm is as follows:

      1. The general expectation of the tasks are established based on the QoS classification.

      2. The better resources of the virtual machines to run the task is selected based on the parameterized task characteristics.

      3. A fairness justice function is evaluated based on the resource allocation value.

         In the second constraint in order to obtain a fair execution the actual allocation resources for tasks are close to the expected resources of the tasks. In the system justice we are assuming n number of tasks T=1,2,.. and also a justice function set as J=1,2, . The justice evaluation function of the system is

         =

         =

         :J= 1 | 1 |. When the value of J is minimum the whole set of users achieve maximum fairness.

         CloudSim is used to test and verify the correctness and validity of the algorithm.an effective implementation of the user tasks with better fairness is obtained.

   3. Dynamic Trusted Scheduling: Wang et al.[8] extended the traditional DIS algorithm which considers the worthiness of resource nodes.The user tasks are met as trust and the task scheduling is made based on the directed acyclic graph. In this algorithm the tasks are executed on trust nodes. The main advantages of this algorithm are the failure task execution is reduced and also the data executive environment security is improved. There are mainly four tiers in the cloud DLS based framework: first is the resource and infrastructure tier next is a middleware for cloud computing next is a trustworthy scheduler and at last a client tier.

      The basic steps in the task scheduling based system framework are:

      1. The tasks are submitted to the task

         queue.

      2. From the task queue the task scheduler fetches the tasks and communicates with the scheduler advisor which then communicates with the trust model.

      3. The trust model analyses the local transactions and communicates with the trust middleware. A trust resource information of tasks are obtained and then transferred to the task scheduler which executes the tasks on most trustworthy resource mode in the cloud.

         A benchmark is developed for the testing of the trusted dynamic level scheduling. Here the execution time and reliability are considered for scheduling.

   4. Cost efficient task scheduling for executing large programs: Su et al.[5] presented two heuristic strategies for the cost efficient tasks scheduling. In the first strategy the tasks are dynamically mapped to the most efficient virtual machines. In the second strategy the monetary cost of non-critical tasks are reduced. A heuristic called Pareto Optimal Scheduling Heuristic(POSH) are used to dispatch the tasks. Inorder to map the highest priority tasks to the most efficient virtual machines therunning time and the monetary cost are considered.

      There are mainly three phases in this heuristic :

      1. The weighting phase in which the nodes and the edges in the workflow are assigned weight.

      2. The prioritizing phase that prioritizes tasks based on the order of execution.

      3. The mapping phase that assigns the tasks to resources based on Pareto dominance.

         A slack time scheduling heuristic can be used after POSH to produce a scheduling time.The main merits of this algorithm is the minimization of makespan and the monetary cost.

   5. Deadline constrained workflow scheduling algorithms: Abrishami et al.[1] proposed two workflow scheduling algorithms called one-phase algorithm and two phase algorithm. In the distributed system the workflow constitutes a common model for the description of the wide range of scientific applications[1]. In this scheduling system model an application model, an IaaS cloud model and a performance criterion for scheduling are present. The one phase algorithm used here is the IaaS cloud partial path algorithm. In this algorithm the actual start time of the dummy nodes are marked. At first the assigned nodes are received by the algorithm and the algorithm then schedules the unassigned parents. The Partial Critical Path of the input node is found by AssignParents. Then the paths are received as inputs and the whole path with the cheapest service is selected. IC-PCPD2 is the two phase algorithm

      being used here. In this algorithm deadline distribution and planning are the two phases. In the first phase the overall deadline of the workflow id distributed over individual tasks and in the next phase based on the assigned sub deadline each of the tasks is assigned to each of the instance of the computation service. The algorithms are evaluated by comparing their performance on scheduling five synthetic workflows. The time complexity is reduced here. The performance can be increased in the feature.

   6. Scheduling strategies for optimal service deployment: Lucas-Simarro et al.[4] emphasized a model architecture for multicloud environment. In this architecture there is a central database that gives the support to the other three components: cloud manager, scheduler and a VM manager. The administrator and the user of the cloud broker acts as the actors in the architecture. The detailed information about the service deployed by the broker are contained in service description file. Based on the needs of the user the cloud broker helps them to include algorithms in the scheduler module. A multi-cloud scenario in which user and provide conditions change with time . Cost optimization policy and performance optimization policy are included in the real environment. The two usecases that can be used for evaluation of the algorithm are an HPC cluster and a webserver.T his can be used for measuring the performance. The main advantage is that in this algorithm the most appropriate type of instance is selected.

      Figure 2.1 cloud brokering architecture

   7. Improved differential evolution algorithm (idea): Tsai et al.[6] based on the proposed cost and time models of cloud computing that optimizes task scheduling and resource allocation using an improved differential evolution algorithm. The IDEA is a combination of Taguchi method and differential evolution algorithm. Therefore IDEA is enhanced and balance in exploration and exploitation. In this the cost model includes the processing and the receiving of the cost and the time model includes receiving, processing and waiting time.Both the cost and time model are used for cloud computing. For scheduling the main ideas are:1)a subtask-resource-based technique to encode a schedule 2)a mask mutation operator to generate a mutated individual 3)for considering diverse individuals the subtasks are changed in mutation and resources are recombined in crossover 4)a systematic reasoning capability of Taguchi method with orthogonal mask is used for selecting subtasks 5)It combines the DEA with improved operators and the Taguchi method. As the input a set of independent resources and a set of resources are given. The assumptions we are taking are that the processing time of each subtask is resource dependent, pre-emption is not allowed and the resources cannot perform more than one subtask at a time. The objective of this paper is to minimize the total cost and makespan.

   8. Rescheduling of reliable job completion: Choon et al.[3] haveaddressed the problem of scheduling bag-of- tasks(BoT) applications in federated distributed systems of grids and clouds. It proposes a rescheduling technique called rescheduling using clouds for reliable completion. The main focus is to investigate the effectiveness of rescheduling using cloud resources. The reliability of job completion is being increased. The two models that are being used are application and system models and scheduling model. In the system model the federated system consists of multiple grid sites and a single cloud site. The main assumptions being taken in the system model is that all the resources in the system are interconnected and for a particular user request a set of cloud resources is dedicated to that user/request once a service level agreement is made between the user and the provider of those cloud resources. An application consists of number of independent tasks without intertasks communications or dependencies. The scheduling problem here is that the scheduling of a set of independent tasks. In order to evaluate the performance three existing heuristics are used.

   Table 2.1 Comparison Table of Various Scheduling Techniques.

   Scheduling techniques	Scheduling parameters	Merits	Environment
   A Priority based Job Scheduling algorithm[2]	Performance Throughput		Cloud environment
   Job Scheduling algorithm based on Berger Model[9]	Completion time Bandwidth		Cloud environment
   Dynamic Trusted Scheduling[8]	Execution time Reliability	1.It can execute tasks in a secure way	Cloud environment
   Cost efficient task scheduling for executing large programs[5]	Cost Makespan		Cloud environment
   Deadline constrained workflow scheduling algorithms[1]	Time complexity Performance		Cloud environment
   Scheduling strategies for optimal service deployment[4]	Performance Cost		Cloud environment
   Improved differential evolution algorithm[6]	Total cost Makespan		Cloud environment
   Rescheduling of reliable job completion[3]	Reliability	1.Reliability of job completion is increased.	Cloud environment and Grid environment

   1. It is used to obtain high performance computing.

   2. It is used to achieve best system throughput.

   1. It is used to execute the user tasks effectively.

   2. It is used to manifest better fairness.

   1. It can reduce costs.

   2. It minimizes the makespan.

   1. It has a polynomial time complexity.

   2. High performance is achieved.

   1. Total performance is improved.

   2. The most appropriate type of instance is being selected.

   1. It is used to minimize total cost.

   2. It reduces the makespan

2. CONCLUSION

The scheduling of tasks in the cloud computing is one of the greatest issue. In this paper we survey various existing scheduling techniques in cloud environment. A large number of parameters can be included in the future for satisfying the needs of the user. The various existing scheduling techniques are also being compared here.

REFERENCES

1. Abrishami. Saeid, Naghibzadeha. Mahmoud, Dick H.J. Epemab., Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds,Future Generation Computer Systems29 ,p.158169,2013.

2. Ghanbari.Shamsollah.,Mohamed.Othman., A Priority based Job Scheduling Algorithm in Cloud Computing, Procedia Engineering 50,p.778-785,2012.

3. Lee.Choon.Young.,Zomaya.Y.Albert, Rescheduling for reliable job completion with the support of clouds

   ,Future Generation Computer Systems 26,p.1192- 1199,2010.

4. Lucas- Simarro.Luis.Jose.,MoreVozmediano.Rafael.,Montero.Ru ben.S.,Llorente.Ignacio.M.,Scheduling strategies for optimal service deployment across multiple clouds,

   Future Generation Computer Systems 29, p.1431 1441,2013.

5. Su.Sen.,Li.Jian.,Huang.Qingjia.,Huang.Xiao., Shuang . Kai.,Wang.Jie,Cost-efficient task scheduling for executing large programs in the cloud ,Parallel Computing 39 p.177188,2013.

6. Tsai.Jinn-Tsong.,Fang.Jia-Cen.,Chou.Jyh-Horng., Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm,Computers& Operational Research 40,p.3045-3055,2013.

7. V.Vignesh., KS. Sendhil.Kumar, Jaisankar N., Resource management and scheduling in Cloud environment, International Journal of Scientific and Research Publications, Volume 3, Issue 6, ISSN 2250-3153,2013.

8. Wang. Wei., Zeng. Guosun ., Tang. Daizhong ., Yao. Jing,Cloud-DLS: Dynamic trusted scheduling for Cloud computing, Expert Systems with Applications 39 p.23212329,2012.

9. Xu.Baomin.,Zhao.Chunyan.,Hu.Enzhao.,Hu.Bin., Job scheduling algorithm based on Berger model in cloud environment ,Advances in Engineering Software 42, p.419-425,2011.