A properly typeset version of this document is available in postscript and in pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
1 Introduction
This talk considers a problem of load sharing. A set of N processors
are the vertices of some graph G and each of them has a buffer of
finite capacity K. A flow of requests (which may be thought of as tasks
to be processed) arrives at each vertex. In the case where the
vertices do not cooperate in some way, this model is simply a set of
N independent finite capacity buffers. In order to optimize the use
of total capacity of the network, it is desirable to design a policy
which transfers a fraction of the load of highly loaded nodes to
under-used processors.
These problems are generic in the sense that they occur very
frequently in many mathematical models as soon as finite capacity and
possibility of cooperation is assumed. A classical example is the
telephone network: If a call from A wants to reach B and all the
links between A and B are used, it is possible to use the
alternative routing strategy: a node C is chosen at random, a link
between A and C an a link between C and B are reserved if
possible. If this succeeds, the call between A and B is finally
accepted. Notice however that this algorithm has a cost: two links are
required instead of one [1]. Another example, again for
routing, is Valiant's algorithm [2]. It is often
quite easy to guess some reasonable load sharing algorithm, however it
is more difficult to estimate its impact on the performances of the
system. Moreover, in some cases, load sharing is worst than no sharing
at all [1, 4]!
In this talk, our basic assumptions are:
(i). The requests arrive at each node according to a Poisson process
with parameter l;
(ii). Each processor works at unit speed the requests which are
assumed to be exponentially distributed with parameter 1;
(iii). A request arriving at a node which is already full (i.e. with
K requests) is rejected.
To estimate the performances of a load sharing algorithm, one can use
the following parameters:
the rejection probability;
the average use of each processor, or equivalently the average
free space in the buffer;
the mean response time.
2 The load sharing algorithm
We describe the state of the network as a vector (h(x)) on the
set of vertices, h(x) is the number of requests at node x.
The algorithm considered here is defined as follows:
If a request arrives at some node x, then
if h(x)=K, the request is lost;
If h(x)<K and h(x) £ inf{h(y)/yÎ
N(x)}, where N(x) denotes the set of neighbours of x,
then the request is assigned to the node x and h(x)®
h(x)+1;
If K>h(x) > inf{h(y)/yÎ N(x)}, then the
request is sent to a node Y, chosen at random in the set
{yÎ N(x)/h(y)<h(x)}. At node Y, the request
follows the same procedure and 3. is applied until case 2. is
satisfied. Hence the request will finally be assigned to a processor
which is a local minimum in terms of the number of requests in the
buffer.
A departure from the node x has the same consequences: a request
chosen at random among the nodes with a higher load level is
transferred to the node x and so on.
The probabilistic assumptions make the state process (ht(x)) at
time t, a Markov process. The transition rates can be defined as
follows:
Let a(x,h) be the rate of the requests through node
x when the state of the process is h, then a(x,h) is
defined recursively:
If h(x) ³ sup{h(y)/yÎ N(x)}, then
a(x,h)=l if h(x)<K,
a(x,h)=0 otherwise.
h(x) < sup{h(y)/yÎ N(x)}, then
a(x,h)=l+åyÎN(x), h(y)>h(x)
a(y,h)/n(y,h),
where n(y,h)=|{z/h(z)<h(y)}|.
These transitions are quite straightforward according to the
description we gave. The term 1/n(y,h) is a
consequence of the fact that if y is not a local minimum, then the
request is sent at random to some neighbour with a lower load.
The parameter a(y,h) is not the real rate of requests
in the buffer of y. This rate is 0 if y is not a local minimum
and a(y,h) otherwise. The departure rates are defined in a
similar way, using the local minima of h.
3 Results
The Markov process we defined above has a local interaction, i.e. any
event concerns only a bounded neighbourhood. The local interaction
comes from the fact that a local minimum is at most at distance K
from any node. This is a special case of interacting particle
systems [3]. One of the first non trivial problems for
this
class of models is the existence of such a process. Given a generator,
that is, the transitions, does there exist a semi-group, i.e. a Markov
process, with this generator? Standard techniques show that this is the
case. The second problem is the asymptotic behaviour: does there exist
an equilibrium measure, a unique one? and if not what are the extreme
points of the convex set of equilibrium measures?
In the case where the graph is the lattice Zd, the result is the
following
Theorem 1
There is a unique equilibrium measure and the state of the network
converges exponentially fast to that equilibrium measure.
The proof of this theorem is based on a coupling argument: if h,
z denote two possible states for the network such that
h£z, i.e. h(x)£z(x) for all the nodes x,
then it is possible to construct two processes ht, zt
with initial state h, z such that ht£ zt for
all t³ 0. The proof uses this coupling to prove that all the
processes stick to the stationary process after some time T with an
exponential moment.
3.1 The case of the complete graph
When the nodes are all connected, it is then easy to see that the total
number of requests X(t) in the system is a birth and death process
with birth rate nl if X(t)£ (K-1)N and (KN-j)l if
(K-1)N<X(t) £ KN-1. The death rates are given by X(t) if
X(t)£ N, and N otherwise. Asymptotic results are easily derived
when N®+¥.