How Useful Is Old Information?.
AbstractWe consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multiprocessor system where incoming tasks with exponentially distributed service requirements arrive as a Poisson process, the tasks must choose a processor for service, and a task knows when making this choice the processor queue lengths from $T$ seconds ago. What is a good strategy for choosing a processor in order for tasks to minimize their expected time in the system? Such models can also be used to describe settings where there is a transfer delay between the time a task enters a system and the time it reaches a processor for service. Our models are based on considering the behavior of limiting systems where the number of processors goes to infinity. The limiting systems can be shown to accurately describe the behavior of sufficiently large systems and simulations demonstrate that they are reasonably accurate even for systems with a small number of processors. Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield important rules of thumb for system design. The most significant result is that only small amounts of queue length information can be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters. In contrast, using global information can actually degrade performance unless used carefully; for example, unlike most settings where the load information is current, having tasks go to the apparently least loaded server can significantly hurt performance.
Introduction
Distributed computing systems, such as networks of workstations or mirrored sites
on the World Wide Web, face the problem of using their resources effectively. If some
hosts lie idle while others are heavily loaded, system performance can fall significantly.
To prevent this, load balancing is used to distribute the workload, improving performance
measures such as the expected time a task spends in the system. Although
determining an effective load balancing strategy depends strongly on the details of the
underlying system, general models from both queueing theory and computer science
often provide valuable insight and general rules of thumb.
In this paper, we develop analytical models for the realistic setting where old load
information is available. For example, suppose we have a system of n servers, and
incoming tasks must choose a server and wait for service. If the incoming tasks know
the current number of tasks already queued at each server, it is often best for the task
to go to the server with the shortest queue [22]. In many actual systems, however,
it is unrealistic to assume that tasks will have access to up to date load information;
global load information may be updated only periodically, or the time delay for a
task to move to a server may be long enough that the load information is out of date
by the time the task arrives. In this case, it is not clear what the best load balancing
strategy is.
Our models yield surprising results. Unlike similar systems in which up to date
information is available, the strategy of going to the shortest queue can lead to extremely
bad behavior when load information is out of date; however, the strategy
of going to the shortest of two randomly chosen queues performs well under a large
range of system parameters. This result suggests that systems which attempt to exploit
global information to balance load too aggressively may suffer in performance,
either by misusing it or by adding significant complexity.
1.1 Related Previous Work
The problem of how to use old or inexact information is often neglected in theoretical
work, even though balancing workload from distributed clients based on incomplete or
possibly out of date server load information may be an increasingly common system
requirement. A recent work by Awerbuch, Azar, Fiat, and Leighton [2] covers a
similar theme, although their models are substantially different from ours.
The idea of each task choosing from a small number of processors in order to
balance the load has been studied before, both in theoretical and practical contexts. In
many models, using just two choices per task can lead to an exponential improvement
over one choice in the maximum load on a processor. In the static setting, this
improvement appears to have first been noted by Karp, Luby, and Meyer auf der
Heide [10]. A more complete analysis was given by Azar, Broder, Karlin, and Upfal
[3]. In the dynamic setting, this work was extended to a queueing theoretic model in
[15, 16]; similar results were independently reported in [26].
Other similar previous work includes that of Towsley and Mirchandaney [21] and
that of Mirchandaney, Towsley, and Stankovic [12, 13]. These authors examine how
some simple load sharing policies are affected by communication delay, extending
a similar study of load balancing policies by Eager, Lazowska, and Zahorjan [5, 6].
Their analyses are based on Markov chains associated with the load sharing policies
they propose and simulations.
Our work is most related to the queueing models of the above work, although it
expands on this work in several directions. We apply a fluid-limit approach, in which
we develop a deterministic model corresponding to the limiting system as n ! 1.
We often call this system the limiting system. This approach has successfully been
applied previously to study load balancing problems in [1, 15, 16, 17, 19, 26] (see also
[1] for more references, or [18, 25] for the use of this approach in different settings),
and it can be seen as a generalization of the previous Markov chain analysis. Using
this technique, we examine several new models of load balancing in the presence of old
information. In conjunction with simulations, our models demonstrate several basic
but powerful rules of thumb for load balancing systems, most notably the effectiveness
of using just two choices.
The remainder of this paper is organized as follows: in Section 2, we describe
a general queueing model for the problems we consider. In Sections 3, 4, and 5,
we consider different models of old information. For each such model, we present
a corresponding limiting system, and using the limiting systems and simulations we
determine important behavioral properties of these models. In Section 6, we briefly
consider the question of cheating tasks, a concept that ties our models to natural but
challenging game theoretic questions. We conclude with a section on open problems
and further directions for research.
2 The Bulletin Board Model
Our work will focus on the following natural dynamic model: tasks arrive as a Poisson
stream of rate -n, where - ! 1, at a collection of n servers. Each task chooses one of
the servers for service and joins that server's queue; we shall specify the policy used
to make this choice subsequently. Tasks are served according to the First In First
Out protocol, and the service time for a task is exponentially distributed
with mean 1. We are interested in the expected time a task spends in the system in
equilibrium, which is a natural measure of system performance, and more generally
in the distribution of the time a customer spends in the queue. Note that the average
arrival rate per queue is - ! 1, and that the average service rate is assuming
the tasks choose servers according to a reasonable strategy, we expect the system to
be stable, in the sense that the expected number of tasks per queue remains finite in
equilibrium. In particular, if each task chooses a server independently and uniformly
at random, then each server acts as an M/M/1 queue (Poisson arrivals, exponentially
distributed service times) and is hence clearly stable. We will examine the behavior
of this system under a variety of methods that tasks may use to choose their server.
We will allow the tasks choice of server to be determined by load information from
the servers. It will be convenient if we picture the load information as being located at
a bulletin board. We strongly emphasize that the bulletin board is a purely theoretical
construct used to help us describe various possible load balancing strategies and need
not exist in reality. The load information contained in the bulletin board need not
correspond exactly to the actual current loads; the information may be erroneous or
approximate. Here, we focus on the problem of what to do when the bulletin board
contains old information (where what we mean by old information will be specified
in future sections).
We shall focus on distributed systems, by which we mean that the tasks cannot
directly communicate in order to coordinate where they go for service. The decisions
made by the tasks are thus based only on whatever load information they obtain
and their entry time. Although our modeling technique can be used for a large class
of strategies, in this paper we shall concentrate on the following natural, intuitive
strategies:
ffl Choose a server independently and uniformly at random.
ffl Choose d servers independently and uniformly at random, check their load information
from the bulletin board, and go to the one with the smallest load. 1
ffl Check all load information from the bulletin board, and go to the server with
the smallest load.
The strategy of choosing a random server has several advantages: it is easy to
implement, it has low overhead, it works naturally in a distributed setting, and it is
known that the expected lengths of the queues remain finite over time. However, the
strategy of choosing a small number of servers and queueing at the least loaded has
been shown to perform significantly better in the case where the load information
is up to date [5, 15, 16, 26]. It has also proved effective in other similar models
[3, 10, 16]. Moreover, the strategy also appears to be practical and have a low
1 In this and other strategies, we assume that ties are broken randomly. Also, the d choices are
made without replacement in our simulations; in the limiting system setting, the difference between
choosing with and without replacement is negligible.
overhead in distributed settings, where global information may not be available, but
polling a small number of processors may be possible. Going to the server with the
smallest load appears natural in more centralized systems where global information
is maintained. Indeed, going to the shortest queue has been shown to be optimal in a
variety of situations in a series of papers, starting for example with [22, 24]. Hence it
makes an excellent point of comparison in this setting. Other simple schemes that we
do not examine here but can easily be studied with this model include threshold based
schemes [5, 17], where a second choice is made only if the first appears unsatisfactory.
We develop analytical results for the limiting case as n ! 1, for which the
system can be accurately modeled by an limiting system. The limiting system consists
of a set of differential equations, which we shall describe below, that describe in
some sense the expected behavior of the system. This corresponds to the exact
behavior of the system as n ! 1. More information on this approach can be found
in [7, 11, 15, 16, 17, 19, 25, 26]; we emphasize that here we will not detour into a
theoretical justification for this limiting approach, and instead refer the reader to
these sources for more information. (We note, however, that this approach works
only because the systems for finite n have an appropriate form as a Markov chain;
indeed, we initially require exponential service times and Poisson arrivals to ensure
this form.) Previous experience suggests that using the limiting system to estimate
performance metrics such as the expected time in the system proves accurate, even
for relatively small values of n [5, 15, 16, 17]. We shall verify this for the models we
consider by comparing our analytical results with simulations.
3 Periodic Updates
The previous section has described possible ways that the bulletin board can be used.
We now turn our attention to how a bulletin a board can be updated. Perhaps the
most obvious model is one where the information is updated at periodic intervals.
In a client-server model, this could correspond to an occasional broadcast of load
information from all the servers to all the clients. Because such a broadcast is likely
to be expensive (for example, in terms of communication resources), it may only be
practical to do such a broadcast at infrequent intervals. Alternatively, in a system
without such centralization, servers may occasionally store load information in a
readable location, in which case tasks may be able to obtain old load information
from a small set of servers quickly with low overhead.
We therefore suggest the periodic update model, in which the bulletin board is
updated with accurate information every T seconds. Without loss of generality, we
shall take the update times to be 0; :. The time between updates shall be
called a phase, and phase i will be the phase that ends at time iT . The time that the
last phase began will be denoted by T t , where t is the current time.
The limiting system we consider will utilize a two-dimensional family of variables
to represent the state space. We let P i;j (t) be the fraction of queues at time t that
have true load j but have load i posted on the bulletin board. We let q i (t) be the rate
of arrivals at a queue of size i at time t; note that, for time-independent strategies,
the rates q i (t) depend only on the load information at the bulletin boards and the
strategy used by the tasks, and hence is the same as q i (T t ). In this case, the rates q i
change whenever the bulletin board is updated.
We first consider the behavior of the system during a phase, or at all times t 6= kT
for integers k - 0. Consider a server showing i customers on the bulletin board, but
having j customers: we say such a server is in state (i; j). Let 1. What is the
rate at which a server leaves state (i; j)? A server leaves this state when customer
departs, which happens at rate or a customer arrives, which happens at rate
Similarly, we may ask the rate at which customers enter such a state. This can
happen if a customer arrives at a server with load i posted on the bulletin board but
having customers, or a customer departs from a server with load i posted on
the bulletin board but having customers. This description naturally leads us to
model the behavior of the system by the following set of differential equations:
dP i;0 (t)
dt
dP i;j (t)
dt
These equations simply measure the rate at which servers enter and leave each state.
(Note that the case is a special case.) While the queueing process is random,
however, these differential equations are deterministic, yielding a fixed trajectory
once the initial conditions are given. In fact, these equations describe the limiting
behavior of the process as n !1, as can be proven with standard (albeit complex)
methods [7, 11, 16, 17, 19, 25, 26]. Here we take these equations as the appropriate
limiting system and focus on using the differential equations to study load balancing
strategies.
For integers k - 0, at there is a state jump as the bulletin board is
updated. At such t, necessarily P i;j as the load of all servers is
correctly portrayed by the bulletin board. If we let P i;j so that
the just before an update, then
3.1
We consider what the proper form of the rates q i are for the strategies we examine.
It will be convenient to define the load variables b i (t) be the fraction of servers with
load i posted on the bulletin board; that is, b i
In the case where a task chooses d servers randomly, and goes to the one with the
smallest load on the bulletin board, we have the arrival rate
The numerator is just the probability that the shortest posted queue length of the d
choices on the bulletin board is size i. To get the arrival rate per queue, we scale by
-, the arrival rate per queue, and b i (t), the total fraction of queues showing i on the
board. In the case where d = 1, the above expression reduces to q i
servers have the same arrival rate, as one would expect.
To model when tasks choose the shortest queue on the bulletin board, we develop
an interesting approximation. We assume that there always exists servers posting
load 0 on the bulletin board, and we use a model where tasks go to a random server
with posted load 0. As long as we start with some servers showing 0 on the bulletin
board in the limiting system (for instance, if we start with an empty system), then we
will always have servers showing load 0, and hence this strategy is valid. In the case
where the number of queues is finite, of course, at some time all servers will show load
at least one on the billboard; however, for a large enough number of servers the time
between such events is large, and hence this model will be a good approximation. So
for the shortest queue policy, we set the rate
and all other rates q i (t) are 0.
3.2 The Fixed Cycle
In a standard deterministic dynamical system, a natural hope is that the system
converges to a fixed point, which is a state at which the system remains forever once
it gets there; that is, a fixed point would correspond to a point
dP i;j
dt
0. The above system clearly cannot reach a fixed point, since the updating of
the bulletin board at time causes a jump in the state; specifically, all P i;j with
become It is, however, possible to find a fixed cycle for the system. We find
a point P such that if
for all k - k 0 . In other words, we find a state such that if the limiting system begins
a phase in that state, then it ends the phase in the same state, and hence repeats
the same cycle for every subsequent phase. (Note that it also may be possible for the
process to cycle only after multiple phases, instead of just a single phase. We have
not seen this happen in practice, and we conjecture that it is not possible for this
system.)
To find a fixed cycle, we note that this is equivalent to finding a vector ~- i )
such that if - i is the fraction of queues with load i at the beginning of the phase, the
same distribution occurs at the end of a phase. Given an initial ~-, the arrival rate
at a queue with i tasks from time 0 to T can be determined. By our assumptions of
Poisson arrivals and exponential service times, during each phase each server acts as
an independent M/M/1 queue that runs for T seconds, with some initial number of
tasks awaiting service. We use this fact to find the - i .
Formulae for the distribution of the number of tasks at time T for an M/M/1
queue with arrival rate - and i tasks initially have long been known (for example,
see [4, pp. 60-64]); the probability of finishing with j tasks after T seconds, which we
denote by m i;j , is
where here B z (x) is the modified Bessel function of the first kind. If ~- gives the
distribution at the beginning and end of a phase, then the - i must satisfy
can be used to determine the - i .
It seems unlikely that we can use the above characterization to determine a simple
closed form for the state at the beginning of the phase of for the fixed cycle in
terms of T . In practice we find the fixed cycle easily by running a truncated version
of the system of differential equations (bounding the maximum values of i and
above until reaching a point where the change in the state between two consecutive
updates is sufficiently small. This procedure works under the assumption that the
trajectory always converges to the fixed cycle rapidly. (We discuss this more in the
next section.) Alternatively, from a starting state we can apply the above formulae
for m i;j to successively find the states at the beginning of each phase, until we find
two consecutive states in which the difference is sufficiently small. Simulating the
differential equations has the advantage of allowing us to see the behavior of the
system over time, as well as to compute system measurements such as the expected
time a task spends in the system.
3.3 Convergence Issues
Given that we have found a fixed cycle for the relevant limiting system, important
questions remain regarding convergence. One question stems from the approximation
of a finite system with the corresponding limiting system: how good is this approxi-
mation? The second question is whether the trajectory of the limiting system always
converges to its fixed cycle, and if so, how quickly?
For the first question, we note that the standard methods referred to previously
(based on work by Kurtz, [7, 11, 19]) provide only very weak bounds on the convergence
rate between limiting and finite systems. By focusing on a specific problem,
proving tighter bounds may be possible (see, for example, the discussion in [25]).
In practice, however, as we shall see in Section 3.4, the limiting system approach
proves extremely accurate even for small systems, and hence it is a useful technique
for gauging system behavior.
For the second question, we have found in our experiments that the system does
always converge to its fixed cycle, although we have no proof of this. The situation
is generally easier when the trajectory converges to a fixed point, instead of a fixed
cycle, as we shall see. (See also [16].) Proving this convergence hence remains an
interesting open theoretical question.
3.4 Simulations
We present some simulation results, with two main purposes in mind: first, we wish
to show that the limiting system approach does in fact yield a good approximation for
the finite case; second, we wish to gain insight into the problem load balancing using
old information. We choose to emphasize the second goal. As such, we plot data
from simulations of the actual queueing process (except in the case where one server
is chosen at random; in this case we apply standard formulae from queueing theory).
We shall note the deviation of the values obtained from the limiting system and these
simulations where appropriate. For most of our simulations, we focus on the expected
time in the system, as this appears the most interesting system measure. Because
our limiting approach provides a full description of the system state, however, it can
be used to predict other quantities of interest as well.
This methodology may raise the question of why the limiting system models are
useful at all. There are several reasons: first, simulating the differential equations is
often much faster than simulating the corresponding queueing system (we shall say
more on this later). Second, the limiting systems provide a theoretical framework
for examining these problems that can lead to formal theorems. Third, the limiting
system provides good insight into and accurate approximations of how the system be-
haves, independent of the number of servers. This information should prove extremely
Update every T seconds
Update interval T
Average
Choices
3 Choices
Shortest
l=0.5, -= 1.0

Figure

1: Strategy comparison at queues.
useful in practice.
In

Figures

1 and 2, the results for various strategies are given for arrival rates
servers. Simulations were performed for 50,000
time steps, with the first 5,000 steps ignored to allow the dependence on the initial
state to not affect the results. In all cases, the average time a task spends in the
system for the simulations with are higher than the expected time in the
corresponding limiting system. When 0:5, the deviation between the two results
are smaller than 1% for all strategies. When for the strategy of choosing
from two or three servers, the simulations are within 1-2% of the results obtained
from the limiting system. In the case of choosing the shortest queue, the simulations
are within 8-17% of the limiting system, again with the average time from simulations
being larger. We expect that this larger discrepancy is due to the inaccuracy of our
model for the shortest queue system, as described in Section 3.1; however, this is
suitably accurate to gauge system behavior. These results demonstrate the accuracy
of the limiting system approach.
Several surprising behaviors manifest in the figures. First, although choosing the
shortest queue is best when information is current very small values
of T the strategy performs worse than randomly selecting a queue, especially under
high loads (that is, large -). Although choosing the shortest queue is known to be
suboptimal in certain systems with current information [23], its failure in the presence
Update every T seconds
Update interval T
Average
Choices
3 Choices
Shortest

Figure

2: Strategy comparison at queues.
Update every T seconds
Update interval T
Average
Choices
3 Choices
Shortest

Figure

3: Strategy comparison at queues.
of old information is dramatic. Also, choosing from just two servers is the best of our
proposed strategies over a wide range of T , although for sufficiently large T making
a single random choice performs better.
We suggest some helpful intuition for these behaviors. If the update interval T is
sufficiently small, so that only a few new tasks arrive every T seconds, then choosing a
shortest queue performs very well, as tasks tend to wait at servers with short queues.
As T grows larger, however, a problem arises; all the tasks that arrive over those
seconds will go only to the small set of servers that appear lightly loaded on the
board, overloading them while other servers empty. The system demonstrates what
we call herd behavior: herds of tasks all move together to the same locations. As a
real-life example of this phenomenon, consider what happens at a supermarket when
it is announced that "Aisle 7 is now open." Very often Aisle 7 quickly becomes the
longest queue. This herd behavior has been noticed in real systems that use old
information in load balancing; for example, in a discussion of the TranSend system,
et. al. note that initially they found "rapid oscillations in queue lengths" because
their system updated load information periodically [9][Section 4.5].
Interestingly, as the update interval T ! 1, the utility of the bulletin board
becomes negligible (and, in fact, it can actually be misleading!), and the best strategy
approaches choosing a server at random. Although this intuition is helpful, it remains
surprising that making just two choices performs substantially better than even three
choices over a large interval of values of T that seem likely to arise in practice.
The same behavior is also apparent even with a much smaller number of servers.
In

Figure

3 we examine simulations of the same strategies with only eight servers,
which is a realistic number for a current multi-processor machine. In this case the
approximations given by the limiting system are less accurate, although for T ? 1
they are still within 20% of the simulations. Other simulations of small systems
demonstrate similar behavior, and as the number of servers n grows the limiting
system grows more accurate. Hence, even for small systems, the limiting system
approach provides reasonable estimates of system behavior and demonstrates the
trends as the update interval T grows.
Finally, we note again that in all of our simulations of the differential equations,
the limiting system rapidly reaches the fixed cycle suggested in Section 3.2.
On Simulating the Limiting System
Although the limiting system approach provides a useful technique for studying load
balancing models, it becomes difficult to use in the periodic update model (and other
models for old information) at high arrival rates or for large values of T , because
the number of variables to track grows large. For example, suppose we simulate the
differential equations, truncating the system at sufficiently large values of i and j that
we denote by I and J . Then we must keep track of IJ variables P i;j . At high arrival
rates (say, high values of T , we will need to make I and J both
extremely large to obtain accurate calculations, and hence simulating the differential
equations over a period of time becomes very slow, comparable to or worse than the
time required to simulated the underlying queueing system.
In practice, however, we expect such high arrival rates and extremely large values
of T are unlikely to be of interest. In the normal case, then, we expect I and J to
be relatively small, in which case simulating the differential equations is generally
quicker than simulating the underlying queueing model.
3.6 More Complex Centralized Strategies
One would expect that a more sophisticated strategy for dealing with the old load
information might yield better performance. For instance, if the system uses the load
information on the bulletin board to develop an estimate for the current load, this
estimate may be more accurate than the information on the board itself. In this
subsection, we briefly consider more complex strategies that attempt to estimate the
current queue length and gauge their performance. These strategies require significant
centralization, in that all incoming tasks must have access to the complete bulletin
board. However, we believe these strategies are practical for systems of reasonable
size (hundreds of processors), and hence are worth examining.
Our model is still that the bulletin board is updated every T seconds. Our first
proposed strategy requires that the arrival rate to the system and the entire composition
of the bulletin board be known to the incoming tasks; also, tasks need to know
the time since the last update. The idea of the strategy is to use our knowledge of the
arrival rate to calculate the expected number of tasks at the servers, and then choose
a server with the smallest expected load uniformly at random. We describe a strategy
that approximates this one closely, and has the advantage that the underlying
calculations are quite simple.
In this proposed strategy, which we call the time-based strategy we split each
phase of T seconds into smaller subintervals; in a subinterval
choose a server randomly from all servers with load at most k. The division of the
phase is inductively determined by the loads at the beginning of the phase, which is
information available on the bulletin board. At time 0, tasks choose from all servers
with load 0 posted on the board (if any exist). Hence t Customers begin also
choosing from servers with load 1 when the expected number of arrivals to servers of
load 0 has been 1, so that
Similarly, customers beginning choosing from servers with load at most k when the
expected number of arrivals to servers of load 1, or at
Intuitively, this strategy attempts to equalize the load at the servers in the natural
way.
A limiting system, given by a series of differential equations, can be used to
model this system. The equations are entirely similar to (1) and (2), except that the
expression for q i (t) changes depending on the subinterval t k . (We leave the remaining
work of the derivation to the reader.)
In our second proposed strategy, which we call the record-insert strategy we allow
the tasks to update the global bulletin board when they choose a server. That is,
every time a new task enters the system load for the server on the bulletin board
is incremented, but deletions are not recorded until the board is updated (every T
seconds). Tasks choose a queue uniformly at random from those with the smallest
load on the board. 2 This strategy may be feasible when the tasks use a centralized
system for placement, but there is a large dealy for servers to update load information.
This strategy is essentially the one used to solve the problem of herding behavior in
the TranSend system mentioned previously [8, 9].
Again, a limiting system given by a family of differential equations can be model
this system. We still use P i;j to represent the fraction of queues with load i on the
bulletin and j at the queue; however, the load at the board is now incremented on
arrival. The resulting are again similar to (1) and (2) with this difference:
dP i;0 (t)
dt
dP 0;j (t)
dt
dP i;j (t)
dt
Also, the expression for q i (t) becomes more complicated. Now q i (t) is zero unless
i is the smallest load apparent in the system. Because the smallest load changes
over time, the system will have discontinuous behavior. Simulations demonstrate
that these strategies can perform substantially better than choosing two when n is
reasonably large and T grows large. For example, see Figure 4, which is demonstrative
of several basic principles. As one might expect, record-insert does better than time-
based, demonstrating the power of the tasks being able to update an actual centralized
We note that performance improves slightly if the tasks break ties in some fixed order, such as
by machine index; in this case, for sufficiently long updates T , the strategy becomes a round-robin
scheme. However, this model cannot be easily described by a limiting system.
Update every T seconds261 0
Update interval T
Average
Time
Choices
Time-Based
Record-Insert

Figure

4: Centralized strategies can perform better.
bulletin board directly. However, choosing the shortest of two random servers still
performs reasonably well in comparison, demonstrating that in distributed settings
where global information may be difficult to maintain or the arrival rate is not known
in advance it remains a strong choice.
Continuous Update
The periodic update system is just one possible model for old information; we now
consider another natural model for distributed environments. In a continuous up-date
system, the bulletin board is updated continuously, but the board remains T
seconds behind the true state at all times. Hence every incoming task may use load
information from T seconds ago in making their destination decision. This model
corresponds to a situation where there is a transfer delay between the time incoming
jobs determine which processor to join and the time they join.
We will begin by modeling a similar scenario. Suppose that each task, upon entry,
sees a billboard with information with some time X ago, where X is an exponentially
distributed random variable with mean T , and these random variables are independent
for each task. We examine this model, and later consider what changes are
necessary to replace the random variable X by a constant T .
Modeling this system appears difficult, because it seems that we have to keep
track of the past. Instead, we shall think of the system as working as follows: tasks
first enter a waiting room, where they obtain current load information about queue
lengths, and immediately decide upon their destination according to the appropriate
strategy. They then wait for a time X that is exponentially distributed with mean
T and independent among tasks. Note that tasks have no information about other
tasks in the waiting room, including how many there are and their destinations. After
their wait period is finished, they proceed to their chosen destination; their time in
the waiting room is not counted as time in the system. We claim that this system
is equivalent to a system where tasks arrive at the servers and choose a server based
on information from a time X ago as described. The key to this observation is to
note that if the arrival process to the waiting room is Poisson, then the exit process
from the waiting room is also Poisson, as is easily shown by standard arguments.
Interestingly, another interpretation of the waiting room is as a communication delay,
corresponding to the time it takes a task from a client to move to a server. This model
is thus related to similar models in [12].
The state of the system will again be represented by a collection of numbers for
a set of ordered pairs. In this case, P i;j will be the fraction of servers with j current
tasks and i tasks sitting in the waiting room; similarly, we shall say that a server is in
state (i; j) if it has j tasks enqueued and i tasks in the waiting room. In this model
we let q j (t) be the arrival rate of tasks into the waiting room that choose servers with
current load j as their destination. The expression for q j will depend on the strategy
for choosing a queue, and can easily be determined, as in Section 3.1.
To formulate the differential equations, consider first a server with in state (i; j),
where 1. The queue can leave this state in one of three ways: a task can
complete service, which occurs at rate new task can enter the waiting room,
which occurs at rate q j (t); or a message can move from the waiting room to the server,
which (because of our assumption of exponentially distributed waiting times) occurs
at rate i
. Similarly one can determine three ways in which a server can enter (i; j).
The following equations include the boundary cases:
dP 0;0 (t)
dt
dP 0;j (t)
dt
dP i;0 (t)
dt
dP i;j (t)
dt
4.1 The Fixed Point
Just as in the periodic update model the system converges to a fixed cycle, simulations
demonstrate that the continuous update model quickly converges to a fixed point,
where dP i;j (t)
dt
We therefore expect that in a suitably large finite system,
in equilibrium the distribution of server states is concentrated near the distribution
given by the fixed point. Hence, by solving for the fixed point, one can the estimate
system metrics such as the expected time in the queue (using, for example, Little's
Law). The fixed point can be approximated numerically by simulating the differential
equations, or it can be solved for using the family of equations dP i;j (t)
dt
In fact,
this approach leads to predictions of system behavior that match simulations quite
accurately, as we will detail in Section 4.3.
Using techniques discussed in [16, 17], one can prove that, for all the strategies we
consider here, the fixed point is stable, which informally means that the trajectory
remains close to its fixed point (once it gets close). We omit the straightforward proof
here. Our simulations suggest that in fact the limiting system converges exponentially
to its fixed point; that is, that the distance between the fixed point and the trajectory
decreases geometrically quickly over time. (See [16, 17].) Although we can prove this
for some special cases, proving exponential convergence for these systems in general
remains an open question.
4.2 Continuous Update, Constant Time
In theory, it is possible to extend the continuous update model to approximate the
behavior of a system where the bulletin board shows load information from T seconds
ago; that is, where X is a constant random variable of value T . The customer's
time in the waiting room must be made (approximately) constant; this can be done
effectively using Erlang's method of stages. The essential idea is that we replace our
single waiting room with a series of r consecutive waiting rooms, such that the time
a task spends in each waiting room is exponentially distributed with mean T=r. The
expected time waiting is then T , and the variance decreases with in the limit as
r !1, it is as though the waiting time is constant. Taking a reasonable sized r can
lead to a good approximation for constant time. Other distributions can be handled
similarly. (See, e.g., [17].)
In practice, this model is difficult to use, as the state of a server must now be
Board T seconds behind
Update interval T
Average
Choices
3 Choices
Shortest

Figure

5: Each task sees the loads from T seconds ago.
represented by an r 1-dimensional vector that keeps track of the queue length and
number of customers at each of the r waiting rooms. Hence the number of states to
keep track of grows exponentially in r. It may still be possible to use this approach in
some cases, by truncating the state space appropriately; however, for the remainder,
we will consider this model only in simulations.
4.3 Simulations
As in Section 3.4, we present results from simulating the actual queueing systems.
We have chosen the case of 0:9 as a representative case for
illustrative purposes. As one might expect, the limiting system proves more accurate
as n increases, and the differences among the strategies grow more pronounced with
the arrival rate.
We first examine the behavior of the system when X, the waiting room time, is a
fixed constant T . In this case the system demonstrates behavior remarkably similar to
the periodic update model, as shown in Figure 5. For example, choosing the shortest
server performs poorly even for small values of T , while two choices performs well
over a broad range for T .
When we consider the case when X is an exponentially distributed random variable
with mean T , however, the system behaves radically differently (Figure 6). All
three of the strategies we consider do extremely well, much better than when X is
Board Z seconds behind, Z exponential with mean T
Update interval T
Average
Choices
3 Choices
Shortest

Figure

Each task sees the loads from X seconds ago, where the X are independent
exponential random variables with mean T .
the fixed constant T . We found that the deviation between the results from the simulations
and the limiting system are very small; they are within 1-2% when two or
three choices are used, and 5-20% when tasks choose the shortest queue, just as in
the case of periodic updates (Section 3.4).
We suggest an interpretation of this surprising behavior, beginning by considering
when customers choose the shortest queue. In the periodic update model, we saw
that this strategy led to "herd behavior", with all tasks going to the same small set
of servers. The same behavior is evident in this model, when X is a fixed constant;
it takes some time before entering customers become aware that the system loads
have changed. In the case where X is randomly distributed, however, customers
that enter at almost the same time may have different views of the system, and thus
make different choices. Hence the "herd behavior" is mitigated, improving the load
balancing. Similarly, performance improves with the other strategies as well.
We justify this interpretation by considering other distributions for X; the cases
where X is uniformly distributed on [T=2; 3T=2] and on [0; 2T ] are given in Figures 7
and

Figures

8. Both perform noticeably better than the case where X is fixed at
T . That the larger interval performs dramatically better suggests that it is useful to
have some tasks that get very accurate load information (i.e, where X is close to 0);
this also explains the behavior when X is exponentially distributed.
Board Z seconds behind, Z uniform on [T/2,3T/2]
Update interval T
Average
Choices
3 Choices
Shortest

Figure

7: Each task sees the loads from X seconds ago, where the X are independent
uniform random variables from [T=2; 3T=2].
Board Z seconds behind, Z uniform on [0,2T]
Update interval T
Average
Choices
3 Choices
Shortest

Figure

8: Each task sees the loads from X seconds ago, where the X are independent
uniform random variables from [0; 2T ].
This setting demonstrates how randomness can be used for symmetry breaking. In
the periodic update case, by having each task choose from just two servers, one introduces
asymmetry. In the continuous update case, one can also introduce asymmetry
by randomizing the age of the load information.
This setting also demonstrates the danger of assuming that a model's behavior
does not vary strongly if one changes underlying distributions. For example, in many
cases in queueing theory, results are proven for models where service times are exponentially
distributed (as these results are often easier to obtain), and it is assumed
that the behavior when service times are constant (with the same mean) is similar.
In some cases there are even provable relationships between the two models (see, for
example, [14, 20]). In this case, however, changing the distribution of the random
variable X causes a dramatic change in behavior.
5 Individual updates
In the models we have considered thus far, the bulletin board contains load information
from the same time t for all the servers. It is natural to ask what happens
when servers update their load information at different times, as may be the case in
systems where servers individually broadcast load information to clients. In an individual
update system, the servers update the load information at the bulletin board
individually. For convenience we shall assume the time between each update for every
server is independent and exponentially distributed with mean T . Note that, in this
model, the bulletin board contains only the load information and does not keep track
of when the updates have occurred.
The state of the system will again be represented by a collection of ordered pairs.
In this case, P i;j will be the fraction of servers with true load j but load i posted
on the bulletin board. We let q i (t) be the arrival rate of tasks to servers with load
i posted on the bulletin board; the expression for q i will depend on the strategy for
choosing a queue. We let S i (t) be the total fraction of servers with true load i at time
t, regardless of the load displayed on the bulletin board; note S i
The true load of a server and its displayed load on the bulletin board match
when an update occurs. Hence when considering how P i;i changes, there will a term
corresponding to when one of the fraction S i of servers with load i generates an update.
The following equations are readily derived in a similar fashion as in previous sections.
dP i;0 (t)
dt
dP i;j (t)
dt
Individual updates every Z seconds, Z
exponentially distributed with mean T
Update interval T
Average
Choices
3 Choices
Shortest

Figure

9: Each server updates the board every X seconds, where X is exponentially
distributed with mean T .
dP 0;0 (t)
dt
dP i;i (t)
dt
As with the continuous update model, in simulations this model converges to
a fixed point, and one can prove that this fixed point is stable. Qualitatively, the
behavior appears similar to the periodic update model, as can be seen in Figure 9.
6 Competitive Scenarios
We have assumed thus far in our models that all tasks adopt the same underlying
strategy, and the goal has been to reduce the expected time for all tasks. In a
more competitive environment, tasks may instead independently act in their own
best interests, and it is necessary to consider the effects of anti-social, competitive
clients who may not follow the proposed universal strategy.
We consider briefly a specific example. Suppose we have a system where each
task is supposed to choose from the shortest of two randomly chosen servers. In this
case, an anti-social task may attempt to improve its own situation by obtaining the
entire bulletin board and proceeding to a server with the smallest posted load. Do
such tasks do better than other tasks? If so, in a competitive environment tasks have
little motivation to follow the suggested strategy.
We study the problem by examining the situation where each customer adopts
the anti-social strategy with probability p. With such a model it is possible to set
up a corresponding limiting system, since each task's strategy can be expressed as a
probabilistic mixture of two strategies; for example, in this case,
Some simulations where all customers see load information from exactly T seconds
ago are revealing. Table 1 provides numerical results based on simulations for
servers. When T is small or the fraction p of competitive customers is
sufficiently small, competitive tasks reduce their average time by acting against the
standard strategy. In cases where choosing two servers performs poorly, introducing
competitive customers can actually reduce the average time for everyone, although
more often anti-social customers do better at the expense of other tasks. For larger
values of T or p, system performance degrades for all customers, and the average time
anti-social customers spend in the system can grow much larger than that of other
customers. In this sense, tasks are motivated not to choose the shortest, for if too
many do so, their average time in the system will be larger than those that do not.
The situation becomes even more interesting, however, if the measure of performance
in not the average time in the system, but a more complicated measure. For
example, it may be important for some tasks to finish by a certain deadline, and in
this case the goal is to maximize the probability that it finishes by its deadline. Our
simulations have also shown that in the model described above, even when p and T
are such that choosing the server with the shortest posted queue increases the average
time for a task, the variance in the time in the system of customers who adopt this
strategy can be lower than other customers (Table 1). Intuitively, this is probably
because some customers that make only two choices will be quite unlucky, and choose
two very long queues. Hence, tasks with deadlines may be motivated to try another
strategy, even though it appears worse in terms of the average time in the system.
We believe there are many open questions to consider in this area, and we discuss
them further in the conclusion.
Avg. Time Avg. Time Avg. Time Variance Variance Variance
All Tasks 2 Choices Shortest All Tasks 2 Choices Shortest

Table

1: Comparing simulation results for anti-social tasks (who choose the shortest)
against those that choose two, for
7 Open Questions and Conclusions
We have considered the question of how useful old information is in the context of
load balancing. In examining various models, we have found a surprising rule of
thumb: choosing the least loaded of two random choices according to the old load
information performs well over a large range of system parameters and is generally
better than similar strategies, in terms of the expected time a task spends in the
system. We have also seen the importance of using some randomness in order to
prevent customers from adopting the same behavior, as demonstrated by the poor
performance of the strategy of choosing the least loaded server in this setting.
We believe that there is a great deal more to be done in this area. Generally, we
would like to see these models extended and applied to more realistic situations. For
example, it would be interesting to consider this question with regard to other load
balancing scenarios, such as in virtual circuit routing, or with regard to metrics other
than the expected time in the system, such as in a system where tasks have deadlines.
A different theoretical framework for these problems, other than the limiting system
approach, might be of use as well. In particular, it would be convenient to have a
method that yields tighter bounds in the case where n, the number of servers, is
small. Finally, the problem of handling more realistic arrival and service patterns
appears quite difficult. In particular, it is well known that when service distributions
are heavy-tailed, the behavior of a load balancing system can be quite different than
when service distribution are exponential; however, we expect our rule of thumb
performs well in this scenario as well.
An entirely different flavor of problems arises from considering the problem of
old information in the context of game theory. We have generally assumed in our
models that all tasks adopt the same underlying strategy, and the goal has been to
reduce the expected time for all tasks. In a more competitive environment, tasks
may instead independently act in their own best interests, and hence in Section 6 we
considered the effects of anti-social clients who may not follow the proposed strategy.
More generally, we may think of these systems as multi-player games, which leads to
several interesting questions: if each task is an individual player, what is the optimal
strategy for a self-interested player (i.e., a player whose only goal is to minimize their
own expected time in the system, say)? How easily can this strategy be computed
on-line? Is this strategy different than the optimal strategy to minimize the average
expected time, and if so, how? Are there simple stable strategies, in which no player
is motivated to deviate from the strategy for their own gain?

Acknowledgments

The author thanks the many people at Digital Systems Research Center who offered
input on this work while it was in progress. Special thanks go to Andrei Broder, Ed
Lee, and Chandu Thekkath for their many helpful suggestions.



--R

"Analysis of Simple Algorithms for Dynamic Load Balancing"
"Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time"
"Balanced Allocations"

"Adaptive load sharing in homogeneous distributed systems"
"A comparison of receiver-initiated and sender-initiated adaptive load sharing"
Characterization and Convergence
Private communication.
"Cluster- Based Scalable Network Services"
"Efficient PRAM Simulation on a Distributed Memory Machine"
Approximation of Population Processes
"Analysis of the Effects of Delays on Load Sharing"
"Adaptive Load Sharing in Heterogeneous Distributed Systems"
"Constant Time per Edge is Optimal on Rooted Tree Net- works"
"Load Balancing and Density Dependent Jump Markov Pro- cesses"
"The Power of Two Choices in Randomized Load Balancing"
"On the Analysis of Randomized Load Balancing Schemes"
"Constant Time per Edge is Optimal on Rooted Tree Net- works"
Large Deviations for Performance Analysis
"The Efficiency of Greedy Routing in Hypercubes and Butterflies"
"The Effect of Communication Delays on the Performance of Load Balancing Policies in Distributed Systems"
"On the Optimal Assignment of Customers to Parallel Servers"
"Deciding Which Queue to Join: Some Counterexamples"
"Optimality of the Shortest Line Discipline"
"Differential Equations for Random Processes and Random Graphs"
"Queueing System with Selection of the Shortest of Two Queues: an Asymptotic Approach"
--TR

--CTR
Alok Shriram , Anuraag Sarangi , Avinash S., ICHU model for processor allocation in distributed operating systems, ACM SIGOPS Operating Systems Review, v.35 n.3, p.16-21, July 1 2001
Avinash Shankaranarayanan , Frank Dehne , Andrew Lewis, A template based static coalition protocol: a3P viGrid, Proceedings of the 2006 Australasian workshops on Grid computing and e-research, p.55-62, January 16-19, 2006, Hobart, Tasmania, Australia
Nelly Litvak , Uri Yechiali, Routing in Queues with Delayed Information, Queueing Systems: Theory and Applications, v.43 n.1-2, p.147-165, January-February
K. S. Ho , H. V. Leong, Improving the scalability of the CORBA event service with a multi-agent load balancing algorithm, SoftwarePractice & Experience, v.32 n.5, p.417-441, 25 April 2002
Hanhua Feng , Vishal Misra , Dan Rubenstein, Optimal state-free, size-aware dispatching for heterogeneous M/G/-type systems, Performance Evaluation, v.62 n.1-4, p.475-492, October 2005
Giovanni Aloisio , Massimo Cafaro , Euro Blasi , Italo Epicoco, The Grid Resource Broker, a ubiquitous grid computing framework, Scientific Programming, v.10 n.2, p.113-119, April 2002
Adam Kirsch , Michael Mitzenmacher, Simple summaries for hashing with choices, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.218-231, February 2008
Mauro Andreolini , Michele Colajanni , Ruggero Morselli, Performance study of dispatching algorithms in multi-tier web architectures, ACM SIGMETRICS Performance Evaluation Review, v.30 n.2, September 2002
Michael E. Houle , Antonios Symvonis , David R. Wood, Dimension-exchange algorithms for token distribution on tree-connected architectures, Journal of Parallel and Distributed Computing, v.64 n.5, p.591-605, May 2004
Changxun Wu , Randal Burns, Handling Heterogeneity in Shared-Disk File Systems, Proceedings of the ACM/IEEE conference on Supercomputing, p.7, November 15-21,
Walfredo Cirne , Francine Berman, When the Herd Is Smart: Aggregate Behavior in the Selection of Job Request, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.181-192, February
Raffaella Grieco , Delfina Malandrino , Vittorio Scarano, SEcS: scalable edge-computing services, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001
Mauro Andreolini , Sara Casolari, Load prediction models in web-based systems, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
Yu-Kwong Kwok , Lap-Sun Cheung, A new fuzzy-decision based load balancing system for distributed object computing, Journal of Parallel and Distributed Computing, v.64 n.2, p.238-253, February 2004
Michael Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000
Changxun Wu , Randal Burns, Tunable randomization for load management in shared-disk clusters, ACM Transactions on Storage (TOS), v.1 n.1, p.108-131, February 2005
Yu, The state of the art in locally distributed Web-server systems, ACM Computing Surveys (CSUR), v.34 n.2, p.263-311, June 2002
large deviations;old information;load balancing;queuing theory;stale information