12 - Load Balancing

Summary

Introduction

In this chapter, we consider the load balancing problem, which in its simplest form is to assign jobs with different sizes sequentially to multiple machines so as to minimize the maximum of the sum of the sizes of jobs assigned to any machine at any point in time.

We present some of the basic techniques developed for solving the load balancing problem under many settings of interest. We start with the simplest setting, where all machines are identical and all jobs are of equal size, and they are permanent, i.e., once they arrive, they do not leave the system. In this setting, round robin is an optimal algorithm; however, it needs to remember past decisions, requiring memory. One challenge is to devise algorithms that are memoryless but still have performance close to that of round robin. In this setting, we present the power-of-d algorithm, where a job on its arrival is assigned to the least loaded machine among d machines, where the d machines are chosen uniformly randomly from the set of all machines.

When job sizes are arbitrary, the load balancing problem is a bit more difficult. For permanent jobs with arbitrary sizes, we consider the case where machine speeds are not identical, and present a near-optimal deterministic online algorithm. Compared to the permanent jobs setting, the temporary jobs setting is more practical but challenging, where jobs arrive into the system and leave at an arbitrary time that is not necessarily known to an algorithm. In the temporary jobs case, we consider two well-studied models: (i) with machine restriction, where each job can be processed by a subset of machines while all the machines have identical speed, and (ii) without machine restriction, where any job can be processed by any machine; however, machine speeds are non-identical.

Finally, we consider the load balancing problem over a network, where each job corresponds to a source–destination pair, and fulfilling a job involves finding a path from the specified source to the destination. Assigning a job to a path means that each edge on that path carries an additional load equal to the size of the job.