Some Dynamical Routing Algorithms in Large Systems

Nikita D. Vvedenskaya

Institute of Information Transmission Problems
Russian Academy of sciences
Moscow 101447, GSP-4, 19 Bolshoi Karetnyi
Russia

Algorithms Seminar

November 3, 1997

[summary by Philippe Robert]

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).

Abstract
We consider a system with N servers and messages arriving according to a Poisson process. The service time of a message is exponentially distributed. Two strategies to process the messages are compared. In the first strategy, an arriving message is sent randomly to one of the servers. In the second strategy, for each message two servers are selected randomly, and the message is directed to the least busy one. The queue length distribution is investigated as N tends to infinity.

1   Introduction

We assume that we have a set of N servers with N queues, these servers process a stream of jobs arriving to that system. Once an arriving job has been allocated to the queue of one of the servers, it cannot switch to another queue. We assume that the arrivals are Poisson with rate l N and the processing times are exponentially distributed with rate 1. Inside the queues, the service discipline is First In First Out. We shall assume that l < 1, with this condition the system will not explode with the service disciplines which we consider.

The simplest strategy, Sind say, to allocate the jobs is to distribute them at random to the servers. In this case the system is equivalent to a set of N independent queues with arrival rate l and service rate 1. It is well known that, at equilibrium, in each queue the number of jobs has geometric distribution with parameter l, in particular the probability that there is at least k jobs in a queue is lk.

A more efficient strategy Ssh, consists in choosing the shortest queue at the arrival of the job. Unfortunately, this kind of discipline is very difficult to analyze, in particular it would be desirable to compare it quantitatively with our first discipline. The exact analysis has been carried out by Flatto and Mac Kean [2] in the case N=2, using uniformisation techniques. This approach does not seem to extend to a higher dimension.

The object of this talk is to analyze an intermediate discipline, Sint, for which it is possible to derive some quantitative results. An arriving job takes two servers at random and chooses the one with the shortest queue. Notice that for Ssh, there is a tight correlation between the queues, all of them are considered to allocate an arriving job. Here, only two of them determine the destination of the job. For a fixed N, a quantitative analysis remains difficult; however, as N goes to infinity, a given queue depends weakly of any other queue. As we shall see, asymptotically the queues behave independently. This phenomenon allows to write down one-dimensional equations. This approach is called the mean field method in statistical physics.

2   The Differential Equations

For this model, it is convenient to describe the queues in the following way: uk,N(t) will denote the fraction of the N queues which have at least k jobs at time t. Clearly
1=u0,N(t)³ u1,N(t)³··· uk,N(t)³ uk+1,N(t)³...,
and 0£ uk,N(t)£ 1, the vector UN(t)=(uk,N(t)) belongs to the state space S=[0,1]N which is compact for the point-wise convergence. It is easily seen that (UN(t)) is a Markov process since the vector of the number of jobs in each queue is a Markov process and the order of the queues does not matter. If F is a measurable functional on S, then F(UN(t)) satisfies the stochastic differential equation,
dF(UN)(t)=
+¥
å
k=1
   N(uk,N(t)-uk+1,N(t)) æ
ç
ç
è		 F(UN(t)-
ek
N
)-F(UN(t)) ö
÷
÷
ø		 dt
+
+¥
å
k=1
   l N(uk-1,N2(t)-uk,N2(t)) æ
ç
ç
è		 F(UN(t)+
ek
N
)-F(UN(t)) ö
÷
÷
ø		 dt + dMN(t),
    (1)
where ek is the vector (1{i=k}). The first term in the right hand side is the contribution of departures, N (uk(t)-uk+1(t)) is the number of queues with k jobs hence the rate at which UN(t)® UN(t)-ek/N. The second term concerns the arrivals, (uk-12(t)-uk2(t)) is the probability that two queues chosen at random have a size ³ k. The last term MN(t) is a martingale (which depends on F), i.e. roughly speaking, a stochastic perturbation; in particular E(MN(t))=E(MN(0)) for all t³ 0. It is easily seen using standard results concerning Poisson processes that
E( MN2(t))£
Kt
N
,
this simply means that the stochastic perturbation is vanishing as N® +¥. Taking F(U)=uk, this suggests that the equation (1) becomes a deterministic differential equation,
duk(t)
dt
= -(uk(t)-uk+1(t)) + l (uk-12(t)-uk2(t)),  k³ 1.     (2)
If (uk(0))Î L1, that is åk=0+¥uk(0)<+¥, using a truncation procedure, it can be proved that (2) has a unique solution. So, as N® +¥, the (uk,N(t)) should converge to a solution of this equation.

Rigorously, Doob's inequality [1] tells us that
P æ
ç
ç
è
 
sup
0£ s£ t
|MN(s)| >a ö
÷
÷
ø		 £
Kt
a2N
,
hence
P æ
ç
ç
è
 
sup
0£ s£ t
|
uk,N(s)-uk,N(0)+
ó
õ
s


0
 (uk,N(x)-uk+1,N(x))-l (uk-1,N2(x)-uk,N2(x))dx
½
½
½
½
½
½		 >a ö
÷
÷
÷
÷
ø		 £
Kt
a2N
.
    (3)
It is easy to check that if (uk,N(0)) converges to (uk(0)) as N® +¥, then the sequence of processes
(uk,N(s))
 
0£ s£ t
, NÎN
is relatively compact. The identity (3) gives that any limit (uk(s))0£ s£ t (in distribution) satisfies the differential equation (2) with probability one. We deduce that if (uk(0))Î L1 then (uk,N(s)) converges in distribution to the unique solution of (2).

3   The Convergence of the Invariant Measures

Up to now, we have only looked at the transient behavior of the queues. That is, for a fixed t, we proved that the state at time t converges in distribution. For NÎ N, the model of size N has an equilibrium distribution pN; the (delicate) question is: as N® +¥ does the sequence (pN) converge to a stable point of (2) ?

If U(0)Î L1, then it is easily seen that (l2k) is the unique stable point of (2). Notice that the pN are probability measures on a compact space, thus the sequence is relatively compact. If one can show that every limit point is a stable point of (2) which belongs to L1, then necessarily the sequence converges to (l2k). This is done using the following estimation: for any continuous function f:L1® R,
 
lim
N® +¥
 
sup
vÎ L1
||Ev(f(UN(t)))-f(uv(t))||=0,
where Ev denotes the expectation with the initial condition UN(0)=v and uv is the solution of (2) with u(0)=v. This gives a kind of uniform convergence of the processes UN.

4   Conclusion

For the strategy Sint, the queue length has a super exponential tail. We have seen that for Sind, the tail was only exponential. It is remarkable that with a little improvement of Sind, the tail distribution drops significantly. For the optimal discipline Ssh, asymptotically, it is easy to see that there will be an unbounded number of empty queues.

References

[1]
Ethier (S.N.) and Kurtz (T.G.). -- Markov Processes, characterization and convergence. -- John Wiley & Sons Ltd, 1986, Probability and mathematical statistics.

[2]
Flatto (L.) and McKean (H.P.). -- Two queues in parallel. Communications in Pure and Applied Mathematics, vol. XXX, 1977, pp. 255--263.

[3]
Vvedenskaya (N. D.), Dobrushin (R. L.), and Karpelevich (F. I.). -- A queueing system with a choice of the shorter of two queues --an asymptotic approach. Problemy Peredachi Informatsii, vol. 32, n°1, 1996, pp. 20--34.
This document was translated from LATEX by HEVEA.