University of Cambridge > > Isaac Newton Institute Seminar Series > Stability criteria and applications for randomised load balancing schemes

Stability criteria and applications for randomised load balancing schemes

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Stochastic Processes in Communication Sciences

In this takl, we consider randomised load balancing schemes where an arriving job joins the shortest of $d$ randomly chosen queues from among a pool of $n$ queues. Vvekenskaya, Dobrushin and Karpelevich (1996) considered the case with Poisson imput and exponentially distributed service times and derived an explicit formula for the equilibrium distribution for fixed $d$ as $n$ goes to infinity. Since its tail decays doubly exponentially fast, this distribution is useful in various applications.

Relatively little work has been done for general service times or input. For general service times, the behaviour of the service rule at each queue will now play a role in the behaviour of the system. In particular, the question of under which conditions the system is stable (ie, its underlyign Markov process is positive recurrent) for fixed $n$ is no longer obvious. Ideally one would like to understand the limiting behaviour for such equilibria (provided they exist) as $n$ goes to infinity, as in the first paragraph.

Here, we discuss results that show that for fiex $n$ such systems are always stable for the appropriate notion of traffic intensity. These results also show that the associated equilibria are tight when restricted to a finite number of queues and hence subsequential limits exist as $n$ goes to infinity. It is anticipated that this behaviour will provide a general framework for examining the behaviour of such limits under difference service rules. In this context, we briefly discuss joint work with Y Lu and B Prabhakar on the limiting behaviour of the equilibria when service at each queue is given by the standard first-in, first-out rule.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2021, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity