An Efficient Study of Job Scheduling Algorithms
with ACO in Cloud Computing Environment

M.Vijayalakshmi; K.Muthusamy

An Efficient Study of Job Scheduling Algorithms with ACO in Cloud Computing Environment

M.Vijayalakshmi, K.Muthusamy
Department of CSE, Anna University, Regional centre, Coimbatore, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

Cloud Computing is emerging as the next generation platform which would facilitate the user on pay use mode as per requirement in modern distributed computing. It gives a better way of scheduling jobs in restricted conditions. Since the number of cloud users need different kind of virtual machines(VM) as per the requirement and cloud provider provides these services as per the Service Level Agreement(SLA) to ensure QoS. To manage large amount of VM requests, then the cloud providers require an efficient job scheduling algorithm. The objective of the paper is to achieve a practical comparison of various job scheduling algorithms for scheduling virtual machines proposes optimization technique which resolves the issues in the scheduling based algorithm that one of these algorithms is better for scheduling and provisioning with the perspective of cost and security of VMs.

Keywords

Cloud Computing, Job Scheduling, Scheduling Algorithm, Cloud Analyst.

INTRODUCTION

Cloud computing is everywhere for business institutions and research institutions, in last few years. When we open at any IT magazines, websites and TV channels, cloud will definitely catch our eye. Cloud computing is a most recent new computing paradigm where applications, records and IT services are provided over the Internet[1]. Cloud computing is the fastest new model for delivering on demand services over internet and can be described as software for internet centric. Cloud computing has become an interesting and beneficial way of changing the whole computing. Schedulers for cloud computing determine on which processing resource jobs of a workflow should be allotted. Scheduling theory for cloud computing is in advance a lot of awareness with increasing popularity in this cloud epoch. Service provider like to ensure that income are utilized to their fullest and best capacity so that resource power is not left unused. Scheduling is a critical problem in Cloud computing, because a cloud provider has to serve many users in Cloud computing system[2]. So scheduling is the leading issue in establishing Cloud computing systems. The main goal of scheduling is to expand the resource utilization and minimize processing time of the tasks[3].

The cloud computing environment provides a different platform by creating a virtual machine that assists users in Accomplishing their jobs within a reasonable time and cost effectively without sacrificing the quality of the services[4]. The huge growth in virtualization and cloud computing technologies reflect the increasing number of jobs that require the services of the virtual machine. Various types of scheduling algorithms have been applied on various data workloads and measured with different performance metrics to evaluate the performance. Most of the scheduling algorithms are developed to accomplish two aims. The first is to improve the quality of services in executing the jobs and provide the expected output on time. The second is to maintain efficiency and fairness for all jobs. There are numerous literatures which propose scheduling algorithms. Some of these proposed algorithms are particularly for serving jobs in a cloud computing environment and some are tailored to fit the cloud environment.

A. Scheduling in Cloud

An essential requirement in cloud computing environment is scheduling the current jobs to be executed with the given constraints. Cloud Computing is also about how IT is provisioned and used and not only about technological improvements and also the scheduling of data centers. The main target of scheduling is to maximize the resource utilization and minimize processing time of the tasks. The scheduler should order the jobs in a way where balance between improving the quality of services and at the same time maintaining the efficiency and fairness among the jobs[5]. An efficient job scheduling strategy must aim to yield less response time. so that the execution of submitted jobs takes place within a stipulated time and simultaneously there will be an occurrence of intime resource reallocation. As a result of this, jobs takes place and more number of jobs can be submitted to the cloud by the clients which ultimately results in accelerating the business performance of the cloud system[6].

This study aims at analyze and investigate four job scheduling algorithms under cloud environment, namely, Round Robin (RR), Random Resource Selection, Opportunistic Load Balancing and Minimum Completion Time, in terms of their ability to provide quality service for the tasks and guarantee fairness amongst the jobs served. Furthermore, study the behavior of these scheduling algorithms and determine the most appropriate job scheduling algorithm for running jobs under cloud environment as a solution based on Ant Colony Optimization[7].

B. Contributions

In this paper, we make the following contributions:

To inspect the different scheduling algorithms which can be adopted in cloud-based systems and simulate these algorithms using CloudSim.

Appraise these algorithms performance and determine both of their advantage and disadvantage.

Propose an improved scheduling algorithm or policy and verify the proposed algorithm in CloudSim as well as extend CloudSim.

Though, these work using the java program to implement the job scheduling system.

RELATED WORK

A. Concepts of Cloud Computing

Cloud computing is based on the concept of infrastructure convergence[6] and distributing services[7], in an attempt to Provide unique types of services through provisioning of dynamically scalable and virtualized resources. It is a combination of techniques from parallel computing, distributed computing, as well as platform virtualization technologies.

The primary goal of Cloud Computing is to provide efficient access to remote and geographically distributed resources with the help of Virtualization in Infrastructure as a Service (IaaS). We need various kind of virtual machines (VM) as per the requirement and cloud provider provides these services as per the Service Level Agreement (SLA) to ensure QoS. For managing enormous amount of VM requests, the cloud providers require an efficient resource scheduling algorithm. In this paper, a relative study has been made for different types of VM scheduling and provisioning algorithms and are briefly discussed and analyzed. Then conclude that one of these algorithms is better for scheduling and provisioning with the perspective of cost and security of VMs. Job scheduling in cloud computing has attracted great attention. Most research in job scheduling adopt a model in which a job in cloud computing system is characterized by its workload, dead-line and the corresponding utility obtained by its completion before deadline, which are factors considered in devising an effective scheduling algorithm.

A comparative study was done comparing the various existing algorithms with the proposed algorithm and the results were illustrated in the form of graphs. However, the proposed algorithm does not handle certain cases like the failure of nodes. Also, the uptime and downtime of nodes have not been measured. This scheduling algorithm can be extended to suit other cloud platforms also. Here, the load factor above which the highest priority node changes is kept constant. Further extension to this algorithm can be done by varying the maximum load factor, above which the priority of a node decreases, dynamically by setting it to an optimum value based on the present conditions. May be in future Cloud computing will be the main platform to save the world. This makes people can have everything they need on it.

The study in presented two scheduling algorithms for scheduling tasks in cloud computing, taking into account their computational complexity and the computing capacity of the processing elements. The algorithms are designed for private cloud environment where the resources are limited. The first algorithm is named Longest Cloudlet Fastest Processing Element (LCFPE) which considers the computational complexity of the cloudlets in the process of making scheduling decisions. The second algorithm is named Shortest Cloudlet Fastest Processing Element (SCFP).

This deals with the design of an Ant Colony Optimization (ACO) algorithm that aims to allocate tasks on to available resources in cloud computing environment. ACO is a meta-heuristic approach applied successfully to single objective combinatorial problems. This chapter examines the concepts involved in the design of ACO algorithms to tackle Multi objective Task scheduling problem such as defining multi objective pheromone information, calculation of probability matrix and pheromone update strategies. Individual ants are behaviorally much unsophisticated insects. They have a very limited memory and exhibit individual behavior that appears to have a large random component. Acting as a collective however, ants manage to perform a variety of complicated tasks with great reliability and consistency. Although this is essentially self-organization rather than learning, ants have to cope with a phenomenon that looks very much like overtraining in reinforcement learning techniques.

PROBLEMS IN EXISTING SYSTEM

The scheduler should order the jobs in a way where balance between improving the quality of services and at the same time maintaining the efficiency and fairness among the jobs. Thus, estimate the performance of scheduling algorithms is crucial towards realizing large scale distributed computing. In spite of the various scheduling algorithms proposed for cloud environment, there is no extensive performance study undertaken which provides a unified platform for comparing such algorithms. Comparing these scheduling algorithms in an Infrastructure as a Service (IaaS) of cloud computing from different perspectives is an aspect that needs to be addressed.

For the cloud environment, many adapted scheduling algorithms are proposed to enhance the total system performance such as throughput, make span and the cost. However, the variety of scheduling algorithms increases the complexity of selecting the best one for adoption. Achieving a practical comparison study among four common job scheduling algorithms in cloud computing. The existing system aims at analyze and investigate four job scheduling algorithms under cloud environment.

PROPOSED SYSTEM

A. The Proposed Algorithm

A comparative study was done comparing the various existing algorithms with the proposed algorithm and the results were illustrated in the form of graphs. A user sends a request for resources to a provider. When the provider receives the request, it looks for resources to satisfy the request and assigns the resources to the requesting user, typically as a form of virtual machines (VMs).Then the user uses the assigned resources to run applications and pays for the resources that are used. When the user is done with the resources, they are returned to the provider. Job scheduling strategy is very effective technique to solve the scheduling problem and also better utilization of the resources.

Figure 3 Architecture of a System Scheduling

To improve the VMs capability to offer reliable services in Cloud computing platform, this study proposes cloud computing system with different master and slave system architecture.

SYSTEM IMPLEMENTATION

The four job scheduling policies in Cloud computing were carefully selected for evaluation, namely, Random, Round Robin (RR), Minimum Completion Time and Opportunistic Load Balancing. These algorithms are considered the most common and frequently used algorithms for job scheduling in Cloud computing. To practically compare these algorithms and explain the details of each job scheduling algorithm.

A. Random Resource Selection Algorithm

The idea of random algorithm is to randomly assign the selected jobs to the available Virtual Machines (VM). The algorithm does not take into considerations the position of the VM and it will either be under heavy load or low load. Then, this may result in the selection of a VM under heavy load and the job requires a long waiting time before service is obtained. The complexity of this algorithm is quite low as it does not need any overhead or preprocessing.

Two input sets, cloudlets (i.e., jobs) and available VMs.

Index = random() * (NoVM - 1) (1)

Where, Index is to the selected VM, random() that returns a random value between 0 and 1 and NoVM is the total number of available VMs.

The proposed system is designed such a way it works in Virtual machine enables the abstraction of an Operating System and Application running on it from the hardware. The interior hardware infrastructure services interrelated to the Clouds is modelled in the simulator by a Datacenter element for handling service requests. These requests are application elements sandboxed within VMs, which need to be allocated a share of processing power on Datacenter’s host components. Data Center object handles the data center management activities such as VM creation and destruction and does the routing of user requests received from User Bases via the Internet to the VMs. Cloud computing is composed with the virtual machines. When the user catches the large distributed data in cloud computing, the operation will affect the performance of virtual machines. In order to improve the virtual machine’s processing in cloud computing infrastructure, this study proposes system for improving the performance of virtual machines in cloud computing infrastructure.

B. Round Robin Algorithm

Though the algorithm is very simple, there is an additional load on the scheduler to decide the size of quantum and it has longer average waiting time and low throughput. The Round Robin algorithm mainly focuses on distributing the load equally to all the resource. Using this algorithm, the scheduler allocates one VM to a node in a cyclic manner. The round robin scheduling in the cloud is very similar to process scheduling. Then the scheduler starts with a task and moves on to the next task, after a VM is assigned to that task. Restated until all the nodes have been allocated at least one VM and then the scheduler returns to the first task again. Hence, in this case, the scheduler does not wait for the exhaustion of the resources of a node before moving on to the next task. As an example, if there are three job and three VMs are to be scheduled, each task would be allotted one VM, provided all the nodes have enough available resources to run the VMs.

Index-> (index+1) mod NoVM (2)

C. Minimum Completion Time Algorithm

The Minimum Completion Time job scheduling algorithm attempts to allocate the selected job to the available VM that can offer the minimum completion time taking into account its current load. The main criterion to determine the VM in the minimum completion time scheduling algorithm is the processor speed and the current load on each VM. In this algorithm first scans the available VMs in order to determine the most appropriate machine to perform the job. Subsequently, it dispatches the job to the most suitable VM and starts execution.

Index-> Min{v.getready()+cl.length/v.speed|vVML} (3)

D. Opportunistic Load Balancing Algorithm

In this algorithm attempts to dispatch the selected job to the available VMs which has the lowest load compared to the other VMs. The idea is to scale the current loads for each VM before sending the job. Then, the VM that has the minimum load is selected to run the job. Assigns a task to the machine that becomes available next, without considering that the execution time of the task on that machine. when multiple machines become available at the same time, then one is arbitrarily selected.

Index -> Min{v.getready()|v VML} (4)

METHODOLOGY AND DIAGRAM

The planning of the project mainly consists of the following 2 phases:

A. Phase1: Analyzing different job scheduling algorithms and improving some scheduling algorithms.

In the initial phase, to study the different job scheduling algorithms such as Round Robin, Random Resource Selection, Minimum Completion time and Opportunistic Load Balancing algorithms. Afterwards, to evaluate these algorithms performance and conclude their advantages, disadvantages as well as applicability. For simulating all these different algorithms will adopt CloudSim framework. CloudSim is a new generation and extensible simulation platform which enables Cloud Analyst is capable of generating graphical output of the simulation results in the form of tables and charts, which is desirable to effectively summarize the large amount of statistics that is collected from various job scheduling Algorithms during the simulation. Such an effective presentation helps in identifying the important patterns of the output parameters and helps in comparisons between related parameters from the given algorithms. Statistical metrics are produced as output of the simulation. Average, minimum and maximum request processing time by each data center, response time variation pattern during the day as the load changes and details of costs of the operation[9].

B. Phase 2: Analyzing a solution of Load balancing in scheduling algorithms and improving an Ant Colony Optimization algorithm

In this phase, for investigating the proposed work for cloud computing the process of the work scheduling and resource allocation problems based on ant colony algorithm[3]. It involves the development of proposing a method based on Ant Colony optimization to resolve the problem of load balancing in cloud environment.

Improves both its performance and scalability.

This method reduces the amount of metadata that must be stored at the centralized index effectively.

Scheduling method is increased by algorithm.

Better scheduling performance.

RESULTS DISCUSSION AND COMPARISON

A. Comparative Study

Many jobs can be run and that will lead to an increase of cost. The Round Robin algorithm produced less cost compared to the minimum completion time and the opportunistic load balancing algorithms. The Random algorithm is the superior in all cases in terms of the total cost compared with the other algorithms. Nevertheless, the Random algorithm has the same cost with the Round Rubin algorithm when the number of jobs is up to 500, 600 and 700.

B. Performance Evaluation

Various performance metrics were taken into consideration in order to measure and evaluate the selected job scheduling algorithms. These metrics include the make span, amount of throughput and total cost. These performance metrics are the most important and frequently used metrics in the previous works for evaluating the scheduling algorithms in cloud computing environment.

System is performed with Random and Round Robin algorithm for efficient and fairness.

It is also performed with Minimum Completion Time and Opportunistic Load Balancing Algorithm with faster.

Sometimes both produces the same result.

ACO algorithm is also used for better efficiency with faster.

CONCLUSION AND FUTURE WORK

In this Study based on the results, it can be also concluded that there is not a single scheduling algorithm that provides superior performance with respect to various types of quality services. This is because job scheduling algorithms needs to be selected based on its capability to ensure good aspect of services with reasonable cost and maintain fairness by fairly distribute the available resources among all the jobs and respond to the constraints of the users. Existing scheduling algorithm gives high throughput and cost effective but they do not consider reliability and availability. It involves the development of proposing a method based on Ant Colony optimization to resolve the problem of load balancing in cloud environment. In future work will propose a new algorithm for resource scheduling and comparative with existing algorithms. The efficiency of the user request first may be optimized the processor and execute the request.

ACKNOWLEDGEMENT

It’s my immense pleasure to thank my Guide and Mentor for his earnest efforts and incessant support throughout my project accomplishment.

References

Isam Azawi Mohialdeen, “A Comparative Study of Scheduling Algorithms in Cloud Computing Environment” 2013 Science Publications.
Jinhua Hu, Jianhua Gu, Guofei Sun Tianhai Zhao “A Scheduling Strategy on Load Balancing of Virtual Machine Resources in Cloud Computing Environment” 2010 IEEE.
Kun Li, Gaochao Xu, Guangyu Zhao, Yushuang Dong, Dan Wang “ Cloud Task scheduling based on Load Balancing Ant Colony Optimization” 2011 IEEE.
Yang, B., X. Xu, F. Tan and D.H. Park “An utility based job scheduling algorithm for cloud computing considering reliability factor” Proceedings of the 2011 International Conference on Cloud and Service Computing, IEEE Xplore Press.
Vijindra and Sudhir Shenai. A, “Survey of Scheduling Issues in Cloud Computing”, 2012, Elsevier Ltd.,
Sindhu, S. and S. Mukherjee “Efficient task scheduling algorithms for cloud computing environment” 2011. Commun. Comput. Inform. Sci.,
Sandeep Tayal, “Tasks Scheduling Optimization for the cloud computing systems”, (IJAEST) International Journal Of Advanced Engineering Sciences And Technologies, Volume-5, No.2, p 11 – 15, 2011.
L.M.Vaquero, L.Rodero Merino, J.Caceres, and M.Lindner, “A break in the clouds: towards a cloud definition,” ACMSIG COMM Computer Communication Review, vol.39, no.1, pp.50– 55,2008.
hathiya, Wickremasinghe. “Cloud Analyst: A Cloud Sim-based Visual Modeller for Analysing Cloud Computing Environments and Applications”.
R.Buyya, C.Yeo, S.Venugopal, J.Broberg, and I.Brandic, “Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility,” Future Generation computer systems,vol.25,no.6,pp.599–616,2009.
Dr Ajay jangra , Tushar Saini “Scheduling Optimization in Cloud Computing” 2013 Science Publications.
Linan Zhu,Quinshui Li, and Lingna He “Study on Cloud Computing Resource Scheduling Strategy Based on the Ant Colony Optimization Algorithm” 2012 Science Publications.
C T Lin, " “Comparative Based Analysis of Scheduling Algorithms for Resource Management in Cloud Computing Environment” ", Vol. 1, Issue-1, July 2013.