Stability criteria and applications for randomised load balancing schemes

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

• Bramson, M (Minnesota)
• Thursday 22 April 2010, 16:00-17:00
• Seminar Room 1, Newton Institute.

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.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.