5
$\begingroup$

I have been able to find, and understand reasonably well, expressions and derivations for the average wait times for (1) $s$ independent $M/M/1$ queues each with arrival rate $\lambda/s$ and service rate $\mu$, and (2) an $M/M/s$ queue with arrival rate $\lambda$ and service rate $\mu$. (See this recent discussion for details. Motivation for this question is the anecdotal result that "one long line" is better than "many individual lines.")

But what if customers arrive with rate $\lambda$ and join the shortest of $s$ queues, each with service rate $\mu$? Is there an expression (preferably with derivation as well, I'm not looking for a recipe) for the average wait time in this case? Simulation of this approach suggests that the average wait time is worse than $M/M/s$... but not that much worse. I would like to figure out how to tackle this analytically.

Perhaps a side effect of an answer might simply be recommendation of a good queuing theory text. My challenge has been that there seems in some cases (online sources, etc.) to be no distinction, or at least confusion, between this "join the shortest line" situation and the $s$ x $M/M/1$ case. But simulation and my intuition at least suggests that they are very different.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ keyword: "shortest queue problem". A quick research reveals that the policy that consists in choosing the shortest queue has been proven to be optimal (maximum throughput) - nevertheless, even in the case of only 2 servers, the invariant distribution is not tractable. $\endgroup$
    – Alekk
    Commented Dec 28, 2010 at 23:14
  • 1
    $\begingroup$ See papers citing jstor.org/pss/3213954 $\endgroup$
    – Steve Huntsman
    Commented Dec 29, 2010 at 1:42
  • $\begingroup$ Both of these comments are helpful; I am new here, and would like to "accept an answer" but these seem to be comments vs. answers. Let me know if I'm missing something. I would like to understand "optimal maximum throughput" better. How does throughput vary at all as long as $\lambda < s\mu$? E.g., consider the policy of choosing a queue at random instead of the shortest queue. This yields worse latency (I think this is equiv. to (1) in the OP), but throughput hasn't changed. That is, I may still get a newspaper every morning, but they might always be two weeks old. $\endgroup$
    – possiblywrong
    Commented Dec 29, 2010 at 12:23

1 Answer 1

Reset to default
1
$\begingroup$

There is also a paper by Vvedenskaya, Dobrushin, and Karpelevich "Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach" (Problems of Information Transmission, 1996, 32:1, 15–27; a Russian original is freely available at http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=298&option_lang=eng).

They consider a policy in which each customer chooses two queues at random and then, among them, the shortest one. Considering the limit of a large number of servers they are then able to derive an equation for the asymptotic stationary distribution, which turns out to be a discrete approximation to the Hopf (inviscid Burgers) equation.

As far as I know there was some development of this work for the case of more than two queues, but it is better to ask Nikita Vvedenskaya directly (ndv AT iitp DOT ru; I've asked her permission to post this address).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .