Load balancing of non-pre-emptive independent tasks on virtual machines
VMs代写 Load balancing and task scheduling in cloud computing environment are considered as an NP-hard optimization problem.
Load balancing and task scheduling in cloud computing environment are considered as an NP-hard optimization problem. Load balancing of non-pre-emptive tasks on VMs (Virtual Machines) is an important aspect of cloud computing. There are certain times when some of the VMs are overloaded with tasks whereas other VMs have no enough load or are under-utilized, and to solve this problem load balancing is applied to achieve optimal use of various VMs.
This paper will focus on the Honey Bee behavior algorithms to solve load balancing problems in VMs. HBB-LB – honey bee behavior load balancing, focuses on achieving a well-balanced load for various virtual machines and hence would be able to maximize the throughput. The algorithm proposed also solves the purpose of balancing the priorities of the tasks and hence in that way the waiting time of each task is minimized. The algorithm is also being compared with previous existing algorithms and hence has proven to be effective against other existing algorithms. The approach to illustrate how significantly execution time and waiting time of tasks is reduced.
This paper is divided into various parts which will showcase various parts of the parts. VMs代写
The first part is the introduction part which will describe the background of the topic and the justification of the research and also will include the main research question and also the organization of the study. The next part is the literature review which will demonstrate various studies and would also analyze the potential of the idea and some insights would also be provided on how it can be implemented and also how can it be evaluated.
The next part of the report consists of Methodology which will contribute to the outline of the proposed research work and also will justify the method undertaken. The next part of the report will consist of Design specification which will help in identifying the techniques of the architecture which will help in implementation. In the next part, there is an evaluation which will showcase the main findings of the study.
Table of Content 3
Literature Review 5
Design Specification 11
Cloud computing is the delivery of computing services such as storage, software, database and more to the clients or users over the internet which is in this case “the cloud”. It is made up of interlinked computer networks using complex algorithms. The concepts of parallelism and distributed systems are incorporated in cloud computing for user experience and interaction with shared hardware, software, and information. There is a functionality of pay per use functionality which would help the end user to not buy the whole software or hardware and can use the functionality of it as long as he liked on rent.
This way the end user does not need to buy the whole package for the software he is using and also need to pay the rent for the duration he is using the software. This has changed the conventional software licensing policies and hence the money expender is being avoided on the packages the user does not require. Like the processors in desktops and personal computers, cloud computing has virtual machines which execute tasks quickly and simultaneously (Rittinghouse and Ransome, 2009).
The VM operations have challenges of balancing task scheduling reducing of different users’ requests in a limited resource center (Huaizhou Shi et al., 2014). VMs代写
The scheduler should be coded according to the optimal use of resources. as multiple tasks are being given to one VM and the environment should make sure the all the VMs are well balanced and hence one VM should not be overloaded with tasks and hence the other one should not be under loaded. In this case, the work of the task scheduler is load balancing across all the machine resources available. The algorithm for load balancing can be used for the purpose of attempting to improve the response time for the tasks provided by the users and hence making maximum use of the resources.
The load balancing algorithms are used to reduce the execution time of tasks. The executions of applications for various load balancing methods are discussed in grids that are heterogeneous and homogeneous. The two load balancing methods are static and dynamic. The static algorithm works if the variation between the loads is low and hence dynamic algorithms are more advantageous than static algorithms as they can deal with high variations in load. This paper approaches to load balancing by modeling using honey bee behavior. The algorithms discussed in this paper are derived from the analysis of the behavior of honey bees.
The overload tasks removed from VMs are considered as various honey bees (L.D. and Venkata Krishna, 2013). VMs代写
When the task is being provided to the underloaded VM the task updates the number on various priority lists and load of VM to other waiting lists. When a high priority task is submitted the VM assigned is the one with the least priority of task so that it can be updated quickly. Loading up of a task to a VM is similar to Honey Bee foraging food source and when a VM is overloaded then the task is being scheduled to an underloaded VM which is similar when the honey is depleted from one food source then the bee finds another source. The updating of the removed task to the remaining task of the VM is similar to bee dancing and informing another member of the Hive (Arunarani and Manjula, 2016).
Load Balancing is known for reassigning of tasks from overloaded VM to the underloaded VMs and thus optimizing the use of resources and maximizing the throughput (Shaw and Singh, 2014). The algorithms for load balancing are classified into static and dynamic load balancing. Static load balancing refers to that the load will be balanced at the time of compilation and the requirement for resources are provided.
The advantage of the static algorithm is the simplicity of handling overhead and implementation and not requiring nodes monitoring. These algorithms work properly if there are low variations in loads of VMs. Hence static algorithms are generally unsuitable for environments with a high variation of loads like grid and cloud computing. In such environments, the dynamic load balancing algorithms are used load balancing (Patni and Aswal, 2015). These algorithms are used to make changes to loads of various VMs at the runtime. They are able to make decisions by studying the current load at runtime.
A group of scholars Pacini, Mateos and García Garino (2014) VMs代写
Have worked on the throughput of the tasks and also the response time in balancing the cloud by using an ant colony based algorithm in the cloud computing environment. The aim of investigating private clouds was because they are the host in performing numerous experiments which have been received by a lot of users. Peng et al. (2017) had worked on the load offsetting in the cloud computing environment. Because of a large number of users, the clouds are mostly dependent on various large sophisticated data centers which are able to handle a large number of users.
According to Kumar and Raj, (2015) they considered the static load balancing algorithms as that on a tree which is fixed. Hu et al proposed a data migration algorithm which was being operated in diffused dynamic load balancing which was proved through rigorous calculations of the Lagrange multiplier of the Euclidian form of transferred weight. The theory could have worked effectively if the environment was homogenous, but this theory does not include the factors for a heterogeneous environment.
Genaud, Giersch, and Vivien, (2004) were able to make an improvement on MPI scatter primitive so that it is able to support the master-slave load balancing. The support is achieved by the use of linear programming algorithms to analyze and make optimal use of load distribution and computing. The application was used in static load balancing algorithms.
The overload tasks removed from VMs are considered as various honey bees (L.D. and Venkata Krishna, 2013). VMs代写
When the task is being provided to the underloaded VM the task updates the number on various priority lists and load of VM to other waiting lists. When a high priority task is submitted the VM assigned is the one with the least priority of task so that it can be updated quickly. Loading up of a task to a VM is similar to Honey Bee foraging food source and when a VM is overloaded then the task is being scheduled to an underloaded VM which is similar when the honey is depleted from one food source then the bee finds another source.
The updating of the removed task to the remaining task of the VM is similar to bee dancing and informing another member of the Hive (Arunarani and Manjula, 2016).
Below are the policies based on which load balancing algorithms can be categorized.
- Triggering – It determines the right and suitable time to start the operation of load balancing.
- Information- It is a basic data warehouse which specifies which information has to be taken and also specifies when it has to be taken and from where.
- Type of Resource- It is used to classify a resource as a receiver or a server of tasks based on the availability of resources.
- Location Server- It utilizes the result from resource type policy to find to locate a partner suitable for a server.
- Selection – It is used to define the task that is needed to be migrated from the overloaded VMs to the underloaded VMs.
Other categories of load balancing are application level vs. system level load balancing or centralized vs. distributed load balancing.
In grid computing, dynamic load balancing method is used to address the problem encountered (Zheng, Tham, and Veeravalli, 2008). There are two basic objectives for load balancing. (Kumar and Mishra, 2015).
These objectives are- VMs代写
- Reducing the mean submission time of tasks which are being submitted to the grid.
- Reducing the communication time which is between the transfers of tasks. The strategy mentioned above is able to deal with all three layers of an algorithm which are an intrasite, intracluster and intra grid.
A load balancing routing policy for grid computing environment utilizes the routing concepts from the local machine in order to define a neighborhood and it then searches for the most appropriate systems to in order to divide the workload of the system(Zheng, Tham, and Veeravalli, 2008). This algorithm was being designated in order to distribute loads of the task of the parallel applications equally over the environment for grid computing (CHENG, 2010). Route algorithms are being indicated towards the environment where there are a heterogeneous system and a lot of tasks running in the parallel applications.
When there is a large system the main objective of minimizing the total time taken to execute tasks is not the only objective as there are other factors such as the communication costs as a result of the load redistribution. In order to solve this purpose, Shi and He (2010) had proposed the hierarchal load balancing model as a new approach which is used for balancing load in a Grid. There exist a bottleneck in this model. The mathematical model in cloud computing use honey bee algorithms is used to optimize web services in which the web servers are scattered (L.D. and Venkata Krishna, 2013).
Service provision in cloud computing is similar to that of water and electricity (Tian, Meng, and Zhan, 2010). The customers do not continuous incur the cost of bandwidth and server resources when they are off, they only incur cost only they turn the service on. The cloud computing is used together with the internet and thus the resources such as software and data are shared and provided to customers on their request (Lauw, Hui and Lai, 2004). Consequently, the cost of renting space from the third party is reduced.
The VMs allow access of multiple users simultaneously or a single user directing multiple requests. In this situation, the task scheduler is activated to ensure that the VMs are running in parallel and loads are balanced (Sanders, 1999). In such a case, the user receives a prompt response from the server saving time and cost of service. Under the literature survey section, various ways on load balancing are discussed. Under this method, VMs perform their task by having task priorities which are like an extension of Honeybee Behaviour Based Load Balancing (Yao and He, 2013).
In this case, when the VM has the minimum number of queuing priorities, it executes the task with the highest priority first (Mizouni, 2015). VMs代写
This method prefers to consider the expected runtime of for the request when choosing efficient VM rather than its cost. When choosing which optimal VM to acquire, Pareto dominance method is used where the cost of execution and runtime for executing a task are compared with other VMs (Dumedah, Berg and Wineberg, 2012). Eventually, the VM with a minimum value of the minimization function is selected and assigned the task. To compute the minimization function, both the runtime and cost are used. Therefore, this method aims at reducing the execution time as well as the cost of using the VM.
In the concept of cloud computing, the physical infrastructures and servers are reduced to data centers and hosts respectively (Ouanouki, Morales and April, 2014). Thus, the data center has N hosts which have n VMs. The submissions for execution are made to the VM use the task processing element in the algorithms. Based on priorities, some tasks wait in their corresponding VM. The VMs are grouped into three categories OVM, UVM, and BVM which is based on their calculated capacity and load. To balance the load, the under loads VM in UVM set are used. The loaded task is set in the VM in such a way that it is executed without much waiting in the queue.
The problem statement of the report is- VMs代写
i. Load balancing techniques are –
- For static algorithms to work effectively the load variation in the nodes have to be low. Because the cloud environments load varies at varying times, these algorithms are not suitable (Sankara Narayanan and Ramakrishnan, 2016).
- The dynamic load balancing algorithms come with additional costs of collection and maintenance of load data. This technique ignores the task priorities and queues in the VMs.
ii. According to Sankara Narayanan and Ramakrishnan regardless of how a VM is loaded with tasks, in a cloud computing environment, all the tasks have to be removed.
This became a problem because when a VM overloaded with the task, the task had to be cleared off the task list.
The Existing systems are as follows: VMs代写
i. For static algorithms to work effectively the load variation in the nodes have to be low. Because the cloud computing environments load varies at varying times, these algorithms are not suitable (Rimal, Choi, and Lumb, 2009).
ii. The scheduling of the tasks is not done on a priority basis.
iii. More time is required to allocate the task to individual users.
iv. Dynamic load balancing is preferred over static algorithms. However, it comes with additional costs for the collection and maintenance of load data.
v. The static algorithm is written in a standard ram model in order to track and control data dependencies. This was an extension of a previously covered model based on functional programs. On the other hand, the automatic dynamic algorithm needs a strict focus on stress stability based on traces so as to be analyzed. Consider a trace AT (I) for algorithm A on input I and a distance metric (;) is well explained prior to defining a trace. To capture the trace in this process, there are operations that have to be executed by the algorithm.
vi. The cloud services provided to the customers by the cloud servers are on the basis of paper used. VMs代写
The different service the model provides makes it attractive to be adopted in institutional organizations as well. The current cloud computing system is facing a number of concerns which include load balancing, security, energy, government regulations etcetera. Getting away with is these is issues is necessary considering the exponential rate at which web traffic is increasing each day making load balancing an area of focus in researches. However, this paper will focus on the second type of load balancing. The downsides of the system include:
- In cloud computing is scheduling of tasks for optimization is hard
- Load balancing on non-pre-emptive independent tasks on VM
- Some VMs are overloaded while others are under loaded with tasks. This needs a balancing of VMs for optimal machine use
Below are systems proposed mitigations for solving problems related to the system downsides: VMs代写
- Application of Honeybee Behaviour for load balancing. The object is to have well balanced virtual machines for optimum utilization.
- Balancing of task priorities needs using the proposed algorithm is necessary to reduce tasks waiting time in the queue.
- Use algorithm inspired by honey bee behavior task scheduling and load balancing of the non-pre-emptive independent task in the cloud computing environment.
- Explore advantages and disadvantages of various theoretical concepts and literature on load balancing algorithms.
- Get a correlation between the HBB-LB proposed algorithms and the behavior of a honey bee when foraging by use of flow diagram for comparison.
- Carry out analysis and empirical research using numerical facts to explain how the load balancing process adapted from honey bee behavior has an impact on the cloud computing environment.
Advantages of the system proposed include: VMs代写
- Priority-based task allocation
- Task scheduling simplify the allocation
- Better utilization of VMs saving on time
- Increase efficiency in management
The process methodology is as follow:
- Getting a VM capacity
- Getting all VMs capacity
- Getting a VM load
- Find out about VM group
- Look out for the overloaded VM
- Get the task transfer from study and analysis of various VM groups
Processor: Intel Core i5 6200U
RAM: 8 GB
Hard Disk: 1 Tbytes
Operating System: Windows 10
IDE: NetBeans 8.2
The system proposed modules include:
- Cloud configuration
- Scheduling and Load Balancing
- VM grouping
- Load Prediction
the first module initializations are VM, data center, cloudlet, and cloud broker. Next is initializations of VM bandwidth, Ram size, and VM size. And lastly, the system initializations include file size, output size, cloudlet length and are followed by the creation of a cloud environment for further actions.
Scheduling and load balancing- VMs代写
according to Wang (2010), the services requested by clients have diverse applications and are routed randomly to the data centers than to the cloud servers. The cloud management policies route requests from the user randomly to various servers based on a number of servers and closeness to the database.
First in First out (FIFO) and Weighted Round Robin (WRR) policies are the two principles used in a non-preemptive system. However, they may have varied degrees of the load from one VM to the other. This causes load differences in VMs working in parallel. This problem creates differences in loads run time and time wastage.
The system has to make a load balancing decision, that is, if there are workload and deviation, the system makes a decision on which step to take. In this, there are likely situations, which is finding out the balancing state of the system and finding out the saturation level of the system. In this case, the current number of tasks in a VM set is in overload if they exceed the capacity of the VM group.
VM Grouping- VMs代写
virtual machines will be grouped based on their loads. The grouping of virtual machines is done based on their workloads. They are grouped into overloaded VMs, under loaded VMs and balanced VMs. Each VM set has jobs to do. When a task is removed from the overloaded VM set, the decision has to be made on where to place it considering the load and the number of tasks in the underloaded VM. This is referred to as honey bee, and thus low loaded VMs is the destination of the honey bee
Various bee updates include the load on a VM, the load on all VMs, tasks in each VM, and the number of VMs in each VM group and task priorities.
In load balancing, VMs with which are balanced are not involved in task switching, but rather they are included in the balanced of VM set and excluded during the switching process. When the set has all VMs and is balanced successfully, we say the tasks are balanced.
Load Prediction- VMs代写
the VM scheduler has the role of triggering load balancing aspect to make a decision on load balancing. In this case, the Maxim algorithm is applied in order to do load balancing.
There is a challenge of having to divide the scarce resources to the group of users who are usually assigned equal privileges to the resources, but on the contrary, some need fewer resources than others.
The maxi-min fair share of allocation is defined as follows:
- Resource allocation increase demand.
- All the sources get resources equal to their demand
- Equal sharing of resources to those sources with unsatisfied demand
The algorithm is implemented as follows:
- Getting the capacity loads of all the VMs. The system check is whether the balance exists or not.
- The load balancing decision is in form of If L> Max capacity the balancing is not possible and balancing aspect is triggered.
- The VMs grouping that exists is LVM, BVM, and OVM.
- The supply during load balancing in UVM is Supply of LVMj = Max Capacity – Load/Capacity.
The demand for OVM is
The demand for OVM j is = Load/Capacity – Maximum Capacity
The OVMs are then put in descending order
The LVMs are put in ascending order
Task priorities are then set
The virtual machine needs to check the load to ascertain whether it can be accommodated and if the machine is empty, whether the task is pre-emptive or not.
Other steps that take place once the load balancing is over include; the update of the number of tasks assigned to VMs and the updates of the number of priority tasks assigned to the VMs. The load is then updated on VMs.
After all, the updates of OVM, LVM, and BVM are done. During sorting the OVM and LVM are put in descending and ascending order respectively.
The LVM, OVM, and BVM are defined as:
LVM (Low Loaded VM) – store the VMs of the load loaded.
OVM (Overloaded VM) – this set stores all the overloaded VMs
BVM (Balanced VMs) – after separating the LVM and OVM the rest of the balanced VMs are stores in this.
There are certain capabilities that a cloud computing system needs to have. The system need be able to withstand hurdles like load balancing ion networks, network flow, scalability, and the Federation of the clouds, trust management and more. The research on cloud computing generally focuses on different priority issues. There are unprecedented services offered by the clouds. Therefore, they are being equipped to be able to handle the service demand variations through dynamic provision through the cloud.
To experiment with these new techniques in real cloud computing has not been possible tests are susceptible to affecting the quality of services like cost, security, and speed. Chand et al explored the issue of fast access security in the cloud provided by Ubuntu. The available cloud simulators have never been disputed in the performance of experiments. One of these many simulators is cloudism. The simulator offers a generalized framework environment, allowing the user to model, simulate, and experiment with the cloud computing infrastructure and its application services. The cloudism framework is used to analyze the algorithms.
There are various performance parameters in obtaining the results from the proposed procedure.
They include task execution time, the time is taken in the queue, the time taken to get a response, the time taken for service, and more. The procedure is performed based on the system accuracy to offloading the processes.
Figure 1: below is a pictorial representation of the proposed model FIFO. In the graph, burst time decreases for every task in the process which maximizes the overall system performance. The execution time for all tasks is maximized in comparison with burst time it also improves the overall performance of cloud and utilizes resources more effectively.
Figure 2: the graphical representation below is service time and start time of the tasks processed in the cloud environment. This presentation was taken after completion of all tasks. According to the presentation, the service time decreases with the use of honey bee algorithms for the tasks directed on the virtual machines. Better service time is achieved by the use and implementation of honey bee algorithm in the cloud environment system.
Figure 4: the proposed algorithm is represented in the figure below.
In today’s time of technological advancements and internet use, balancing of the loads in the system had become the biggest issues to the computer scientists and the computing industry. This is because there are a number of different techniques and algorithms are being used to solve this problem. In this particular survey, a number of different balancing methods used in the various environments have been done. In this context it came out to be that different parameter as well as soft computing techniques can be used to improve the system further.
Arunarani, A. and Manjula, D. (2016). BABC task scheduler: hybridization of BAT and artificial bee colony for deadline constrained task scheduling. International Journal of Business Intelligence and Data Mining, 11(4), p.379.
CHENG, H. (2010). Task scheduling model based on resource prediction for grid computing. Journal of Computer Applications, 30(9), pp.2530-2534.
Dumedah, G., Berg, A., and Wineberg, M. (2012). Evaluating Autoselection Methods Used for Choosing Solutions from Pareto-Optimal Set: Does Nondominance Persist from Calibration to Validation Phase?. Journal of Hydrologic Engineering, 17(1), pp.150-159.
Genaud, S., Giersch, A. and Vivien, F. (2004). Load-balancing scatters operations for grid computing. Parallel Computing, 30(8), pp.923-946.
Huaizhou Shi, Prasad, R., Onur, E. and Niemegeers, I. (2014). Fairness in Wireless Networks: Issues, Measures, and Challenges. IEEE Communications Surveys and Tutorials, 16(1), pp.5-24.
Kumar, A. and Raj, A. (2015). A New Static Load Balancing Algorithm in Cloud Computing. International Journal of Computer Applications, 132(2), pp.13-18.
Kumar, N. and Mishra, N. (2015). Load Balancing Techniques: Need, Objectives and Major Challenges in Cloud Computing- A Systematic Review. International Journal of Computer Applications, 131(18), pp.11-19.
L.D., D. and Venkata Krishna, P. (2013). Honey bee behavior inspired load balancing of tasks in cloud computing environments. Applied Soft Computing, 13(5), pp.2292-2303.
Lauw, H., Hui, S. and Lai, E. (2004). Shared-storage auction ensures data availability. IEEE Internet Computing, 8(5), pp.22-28.
Mizouni, R. (2015). Project Schedule Simulation: Incorporating Human Factors’ Uncertainty and Features’ Priority in Task Modeling. Journal of Software, 10(8), pp.939-960.
Ouanouki, R., Morales, A. and April, A. (2014). Rationalizing the Cloud Computing Concept: An Analogy with the Car. Journal of Cloud Computing, pp.1-8.
Pacini, E., Mateos, C. and García Garino, C. (2014). Distributed job scheduling based on Swarm Intelligence: A survey. Computers and Electrical Engineering, 40(1), pp.252-269.
Peng, J., Tang, M., Li, M. and Zha, Z. (2017). A Load Balancing Method For Massive Data Processing Under Cloud Computing Environment. Intelligent Automation & Soft Computing, 23(4), pp.547-553.
Patni, J. and Aswal, M. (2015). Distributed load balancing model for grid computing environment. 2015 1st International Conference on Next Generation Computing Technologies (NGCT).
Rimal, B., Choi, E. and Lumb, I. (2009). A Taxonomy and Survey of Cloud Computing Systems. 2009 Fifth International Joint Conference on INC, IMS and IDC, pp.44-51.
Rittinghouse, J. and Ransome, J. (2009). Cloud Computing. 1st ed. Boca Raton: CRC Press.
Sanders, P. (1999). Analysis of nearest neighbor load balancing algorithms for random loads. Parallel Computing, 25(8), pp.1013-1033.
Shaw, S. and Singh, A. (2014). A survey on scheduling and load balancing techniques in a cloud computing environment. 2014 International Conference on Computer and Communication Technology (ICCCT).
Sankara Narayanan, S. and Ramakrishnan, M. (2016). A Comprehensive Study on Load Balancing Algorithms in Cloud Computing Environments. Research Journal of Applied Sciences, Engineering, and Technology, 13(10), pp.794-799.
Tiang, G., Meng, D. and Zhan, J. (2010). Reliable Resource Provision Policy for Cloud Computing. Chinese Journal of Computers, 33(10), pp.1859-1872.
Yao, J. and He, J. (2013). Load balancing strategy of cloud computing based on adaptive artificial bee colony algorithm. Journal of Computer Applications, 32(9), pp.2448-2450.
Zheng, Q., Tham, C. and Veeravalli, B. (2008). Dynamic Load Balancing and Pricing in Grid Computing with Communication Delay. Journal of Grid Computing, 6(3), pp.239-253.