Load balancing

Load balancing has been shown to have the potential to provide better performance than load sharing if the overhead of load distribution is ignored [#KruegerTDOOD##1#]. It is rather more equitable than load sharing and it addresses situations in which some processors are lightly loaded and some heavily loaded; it does not restrict migration to idle processors. According to Goscinski [#GoscinskiDOSTL##1#] there are a number of questions which must be answered in forming any load balancing policy:

When to migrate processes to balance the system workload?
How to compare workloads of different computers to decide which should be offloaded first whilst others wait?
Which process from a chosen computer should be moved?
Which computer is the best destination for a process to be migrated?
Which computer should be involved in searching for a lightly loaded (or idle) computer? Should it be the source computer for a given process, or should lightly loaded computers perhaps offer their services?
When are the scheduling/load balancing decisions to be made?
Which parameters should be taken into consideration in making the decisions required by the above mentioned questions?
What can happen when data is not available or out of date?
Should the data necessary to make these decisions be gathered and stored centrally or in a distributed manner?
Should computers cooperate in making decisions or not? If so, what mechanisms are needed to update system state in relevant computers?
What is the tradeoff between performance and overhead of making scheduling/load balancing decisions?
How can one avoid overloading a lightly loaded computer?
How can one avoid starvation by constantly migrating the same processes between machines?

There are several different reasonable answers to all of these questions. Consequently there are tens if not hundreds of different approaches presented in the literature. This means that it would be impracticable to cover each in any detail. Fortunately, they can be separated into a relatively small number of different categories, which can be discussed separately. The taxonomy in general use is that due to Casavant and Kuhl [#CasavantATOSI##1#].