Queueing Theory: How to estimate steady-state queue length for single queue, N servers?

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.

Scenario:
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 > 1)
(assume Poisson or Gaussian distributions, whichever is easier to analyze.)

Question:
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.

• I edited the original post to remove the sig – Suresh Venkat Jan 9 '11 at 20:09
• updated question to emphasize "K > 1", since average inter-arrival time must be longer than average service time in order to reach steady-state. – David Jones Jan 9 '11 at 20:36
• You're not emphasizing "K > 1"; you're correcting your first assumption that "K is a fraction < 1". – M.S. Dousti Jan 9 '11 at 20:48
• yes, corrected. – David Jones Jan 10 '11 at 0:23

You need to apply Little's law:

The long-term average number of customers in a stable queue L is equal to the long-term average arrival rate, λ, multiplied by the long-term average time a customer spends in the queue, W; or expressed algebraically: L = λW.

The beauty of this law is that it does not depend on the distribution of arrivals or the service time (whether it is Markovian or not, etc.). More technically, and in Kendall's notation, it is true for the general GI/G/m queues.

We now assume that service time follows an exponential distribution (with parameter μ), and the arrivals follow a Poisson distribution (with parameter λ). In addition, we assume there's only one server. That is, our queue is modeled as M/M/1.

Using Little's Law, it can be shown (see formula (6.15) on page 247 of this book) that:

$W = \frac{\lambda/\mu^2}{1-\lambda/\mu}$

Note that the book uses different notations than here. It also states the formula holds for M/G/1-PS and M/G/1-LCFS queues.

Using Little's Law, we have $L = {\lambda^2 \over \mu^2-\lambda\mu}$.

In your case, λ = 1/(KT), and μ = 1/T. Hence L = 1/K(K-1).

PS: Little's Law has 3 variants. It can be applied to the whole system, to the queue itself, or to the service center. See pages 259-260 of this book for more info.

Edit: The case for M/M/c queues is much trickier. Here, you need to apply Erlang C formula.

To derive the following formulas, you can take a look at Section 5.2.3 of this book.

Let $a := \lambda/\mu$ and $\rho := a/c$, where c denote the number of servers. Then Erlang C formula, $C[c,a]$ is obtained by:

$C[c,a] = \frac{a^c}{c!} / ((1-\rho)\sum\limits_{n=0}^{c-1}\frac{a^n}{n!}+\frac{a^c}{c!})$

Now we have: $L = \rho C[c,a] / (1- \rho)$.

As a sanity check, note that for $c=1$ we derive the previous answer: $L = {\lambda^2 \over \mu^2-\lambda\mu}$.

• nice ! I didn't know Little's law. – Suresh Venkat Jan 9 '11 at 20:10
• This answer cannot be correct. – David Jones Jan 9 '11 at 20:26
• This answer cannot be correct. ... There error is that you have made a mistake in assuming "W = T". "T" is the service time (Task being processed by server). Let "D" be the time a Task waits in the queue before coming to the front and being serviced. Therefore, "W = D + T". In our case, we don't know "D" directly. In fact, knowing "D", and thus "W", would tell us "L" very easily, as you have noted. ... so this question remains unanswered. – David Jones Jan 9 '11 at 20:32
• @David: Oops, you're right! See the corrected answer. – M.S. Dousti Jan 9 '11 at 21:30
• @David: Also, note that I changed the definition of W to be the waiting time. This is due to the fact that you want to know the average queue length, rather than the average number of customers in the system (which also includes the customers being serviced). See the discussion about variants of Little's Law at the end of my answer. – M.S. Dousti Jan 9 '11 at 23:01