الفهرس 
CHAPTER1: INTRODUCTIONOnly 14 pages are availabe for public view
 |  | from | 187 |  |  |
| | | from | 187 | | |
Abstract
Presently, cloud computing has become a very popular platform in the computing world. It provides users with high efficient resources on demand. Nevertheless, due to the strong turnout to use the cloud in everything in the Information Technology (IT) field, cloud platforms have become very crowded with heavy loads. Therefore, providers need to use new techniques to manage resources allocation to users. One of the most important techniques, in managing cloud resources, is scheduling technique. Scheduling in cloud computing is one of the most issues that face the cloud computing environment.
In this thesis, we propose new scheduling algorithms for manage the virtual resources of cloud computing. We can divide the algorithms into four classes: heuristic scheduling algorithms for independent tasks, met-heuristic scheduling algorithms for independent tasks, heuristic scheduling algorithms for workflow applications, and meta-heuristic scheduling algorithms for workflow applications.
In the first class, we develop some scheduling algorithms for scheduling some independent tasks on the available virtual resources. These algorithms are: Traveling Salesman Approach for Cloudlet Scheduling (TSACS), Online Potential Finish Time (OPFT), Highest Priority First Serve (HPFS) and Highest Priority First Execute (HPFE).
The main idea of TSACS is to convert the cloudlet-scheduling problem into an instance of the Traveling Salesman Problem (TSP) and then apply one of the TSP solution strategies to solve the problem. The proposed approach consists of three phases: clustering phase, converting phase, and assignment phase. In the clustering phase, the proposed approach converts the large size cloudlet-scheduling problem into a small size cluster-scheduling problem to minimize computation time complexity of the proposed approach. In the converting phase, the approach forms the cluster-scheduling problem as an instance of the TSP. In the assignment phase, the approach schedules the clusters into
| P a g e ix
the available virtual machines by using the nearest neighbor algorithm. The proposed approach is evaluated by using the CloudSim and the results are compared with that obtained by the most recent algorithms. The results show that the proposed approach enhances the overall system performance in terms of schedule length, balancing degree, and time complexity. In addition, the proposed TSACS overcomes the oscillation problem of the existing cloudlet-scheduling algorithms.
The next proposed algorithm is OPFT. It is developed to enhance the cloud datacenter broker, which is responsible for the scheduling process, and achieve the QoS. The main idea of the new approach is inspired from the idea of passing vehicles through the highways. Whenever the width of the road increases, the number of passing vehicles increases. We apply this idea to assign different users’ tasks into the available VMs. The number of tasks that are allocated to a VM is in proportion to the processing power of this VM. Whenever the VM capacity increases, the number of tasks that are assigned into this VM increases.
Providers want to trade-off between the customer needs and their profits. This requires applying new techniques which achieves provider profits without the SLA violation. For this purpose, we present new resource allocation technique called Highest Priority First Served (HPFS) algorithm to allocate the available resources into multi-users with multi-tasks. The new algorithm considers the constraints of SLA and achieves the provider profits. However the HPFS ignores the security issue. For this reason, we develop new algorithm called HPFE algorithm which is considered the security issue.
In the second class, we propose two hybrid meta-heuristic algorithms: Ant Colony Optimization with Simulated Annealing (ACOSA) and Simulated Annealing with Ant Colony (SAAC) algorithms to schedule the independent tasks into the available resources. In addition, we develop new meta-heuristic optimization techniques: Water Density Change Optimization WDCO and Water Pressure Change Optimization for scheduling the independent tasks in cloud computing.
| P a g e x
The proposed approach ACOSA combines both the Ant Colony Optimization (ACO) and Simulated Annealing (SA) algorithm to improve the quality of solutions. In addition, the algorithm uses greedy strategy as initial stage to get near optimal solution and then improve the solution by SA. However, it has high time complexity. To avoid this issue, we propose the SAAC algorithm.
The main proposed behind developing the SAAC is to balance workload on the available VMs and minimize makespan (i.e., the completion time at the maximum loaded VM). In the first phase, the SAAC approach applies the Simulated Annealing (SA) to find a near optimal scheduling of the cloudlets. While, in the second phase, the SAAC approach improves the cloudlets distribution by applying the Ant Colony Optimization (ACO) considering the solution obtained by the SA as the initial solution. The SAAC approach overcomes the computational time complexity of the ACO algorithm and low solutions quality of the SA.
Although the ACOSA and the SAAC algorithms give good solutions, they use large memory to schedule some tasks. Thus we develop new optimization techniques (WDCO and WPCO) to overcome this issue. The new techniques are inspired from the phenomenon of water density changing when increasing the pressure or temperature due to the changing in the physical characteristics of the water.
In the third class, we propose a new heuristic algorithm: Intelligent Planner (IP) for solving the workflow scheduling problem. The IP algorithm tries to distribute the overall load according the power of each virtual resource to achieve the maximum load balance with low makespan.
Finally, we develop new meta-heuristic algorithms CR-AC algorithm and SAC algorithm to solve the workflow scheduling problem. The CR-AC algorithm uses the CRO algorithm and the ACO algorithm to solve the problem and achieve low makespan and low cost, whereas, the SAC algorithm uses the same idea of the SAAC algorithm to solve the workflow scheduling problem.
| P a g e xi
The proposed algorithms are implemented in the CloudSim toolkit and evaluated by using real applications and Amazon EC2 pricing model. Moreover, the results are compared with the existed algorithms: FCFS, RR, MIN-MIN, MAX-MIN, MCT, HEFT, SA, GA, PSO, ACO, CRO, and CEGA. The experimental results indicate that the new algorithms achieve better results than the others, in terms of total cost, time complexity, throughput, utilization, load balance, memory usage and schedule length