I have a real-life situation that can be solved using Queueing Theory.
This should be easy for someone in the field. Any pointers would be appreciated.

There is a single Queue and N Servers.
When a server becomes free, the Task at the front of the queue gets serviced.
The mean service time is T seconds.
The mean inter-Task arrival time is K * T (where K is a fraction < 1)
(assume Poisson or Gaussian distributions, whichever is easier to analyze.)

At steady state, what is the length of the queue? (in terms of N, K).

Related Question:
What is the expected delay for a Task to be completed?

Here is the real-life situation I am trying to model:
I have an Apache web server with 25 worker processes.
At steady-state there are 125 requests in the queue.
I want to have a theoretical basis to help me optimize resources and understand quantitatively how adding more worker processes affects the queue length and delay.

I know the single queue, single server, Poisson distribution is well analyzed.
I don't know the more general solution for N servers.

thanks in advance,
-- David Jones

  • $\begingroup$ For future reference, from the FAQ: "Please don't use signatures or taglines in your posts. Every post you make is already "signed" with your standard user card, which links directly back to your user page. Your user page belongs to you — fill it with interesting information about your interests, links to cool stuff you've worked on, or whatever else you like!" $\endgroup$ – Qiaochu Yuan Jan 9 '11 at 17:35

Probably you'll find this one very useful. Chapter 5 ($M/M/C$ queue) corresponds to your model, where it is assumed that there are $c$ servers, the service time is exponentially distributed, and so are the interarrival times (of course, with different means). Anyway, the key is $M/M/C$ (or $M/M/N$, etc.) queue.

  • $\begingroup$ +1. I can't believe nobody has upvoted this answer yet. The paper in the link given by Shai Covo contains explicit formulas for the expected queue length and the expected time through the system for an $M/M/N$ queue in steady-state. There are also software packages available that will allow you to vary the parameters to quickly see how the values of the queue length and time through the system change as the values of $N$ and $K$ changes. An internet search should produce some of these. $\endgroup$ – Mike Spivey Jan 18 '11 at 18:32

You describe a model describe a model similar to the M/M/c queue. In this queueing model service times are exponentially distributed with parameter $\mu$ and inter-arrival times are exponentially distributed with parameter $\lambda$. $c=25$ in your situation.

The steady state distribution for such a queueing system ($\pi_k$ is the steady state probability of there being $k$ customers) is

$$\pi_k = \begin{cases} \pi_0\dfrac{(c\rho)^k}{k!}, & \mbox{if }0 < k < c \\[10pt] \pi_0\dfrac{\rho^k c^c}{c!}, & \mbox{if } c \le k. \end{cases}$$


$$\pi_0 = \left[\sum_{k=0}^{c-1}\frac{(c\rho)^k}{k!} + \frac{(c\rho)^c}{c!}\frac{1}{1-\rho}\right]^{-1}.$$

The average response time in such a model is $$\frac{\text{ C}(c,\lambda/\mu)}{c \mu - \lambda} + \frac{1}{\mu}$$

where $\text{C}(c,\lambda/\mu)$ is Erlang's C formula

$$\text{ C}(c,\lambda/\mu)=\frac{\left( \frac{(c\rho)^c}{c!}\right) \left( \frac{1}{1-\rho} \right)}{\sum_{k=0}^{c-1} \frac{(c\rho)^k}{k!} + \left( \frac{(c\rho)^c}{c!} \right) \left( \frac{1}{1-\rho} \right)}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.