Research On Load Balancing Scheduling Method For Workflow Applications In Geo-distributed Clouds

With the rapid developments of Internet,cloud computing which has emerged as a novel paradigm to change our life is applied on many applications including online search,video stream and social network.Recently,many cloud computing services are deployed on geo-distributed infrastructures.That is to say,the services are provided by geo-distributed data centers,which can improve the performance and reliability of the system.The large scale of geo-distributed clouds and the high complexity of workflow applications will cause the waste of resources and increase energy consumption.How to allocate cloud resources optimally and reduce the energy consumption is a momentous problem.Therefore,the research on load balancing scheduling method for workflow applications in geo-distributed clouds is of great theoretical value and practical significance.According to the mentioned problems,this thesis mainly includes the following three aspects,(1)Most of the job scheduling approaches in geo-distributed clouds did not consider the states of each cloud.In this thesis,we proposed a job scheduling method for workflow based on load balancing in geo-distributed clouds.First,the proposed job scheduling method applies Logistic regression method to analyze the states of each cloud according to workloads,resource utilizations and job complexities.The average job execution time is achieved according to the cloud states.Then,we formulate the job scheduling problem as a queueing problem.In each cloud,there is an M/M/C queue.According to the queueing theory,a nonlinear minimization problem with equality constraints is formulated.Finally,the optimal job arrival rates to each cloud is achieved to reduce the job waiting time and improve the system throughput.(2)In order to improve the efficiency of task scheduling for workflow applications in geo-distributed clouds,a task scheduling method for workflow applications based on shortest path algorithm in geo-distributed clouds is proposed.First,workflow applications are modeled as hypergraphs.According to their internal relationships,these hypergraphs are partitioned into components by k-way partitioning algorithm.Then,the task scheduling problem is formulated as a shortest path problem for these components.Fibonacci heap based Dijkstra algorithm is applied to obtain the shortest path of the component graph whose weights are derived with respect to the energy consumption and execution time.Finally,the tasks will be dispatched to optimal clouds in order to reduce the total energy consumption of geo-distributed clouds.(3)The performance of the proposed algorithm is obtained by comparing it with the existing scheduling algorithms.In the experiments of the job scheduling algorithm for workflow based on load balancing in geo-distributed clouds,the job execution time prediction algorithm based on Logistic regression method is verified first.The mean absolute percentage error(MAPE)of our prediction algorithm is 3.4% when experiment has been executed for 200 times.Then,the proposed job scheduling algorithm compared with SRPT algorithm and SWAG algorithm can reduce the average job waiting time up to 66.7% and 41%.Compared with SRPT algorithm and SWAG algorithm,our proposed job scheduling algorithm can reduce the average job response time up to 45.2% and 31%.Our job scheduling algorithm can improve the system throughput efficiently.In the experiments of the task scheduling algorithm for workflow applications based on the shortest path algorithm in geo-distributed clouds,the optimal number of hypergraph partitions is 64.Compared with MCMKCut algorithm and CAWT algorithm,our proposed task scheduling algorithm can reduce the makespan up to 35% and 22.9% and improve QoS satisfaction rate up to 7.4% and 3.8%.