<p>You need to apply <a href="http://en.wikipedia.org/wiki/Little%27s_law" rel="nofollow">Little's law</a>: </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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 <a href="http://en.wikipedia.org/wiki/Kendall%27s_notation" rel="nofollow">Kendall's notation</a>, it is true for the general GI/G/m queues.</p>

<p>We now assume that <strong>service time</strong> 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 <strong>M/M/1</strong>. </p>

<p>Using <strong>Little's Law</strong>, it can be shown (see formula (6.15) on page 247 of <a href="http://rads.stackoverflow.com/amzn/click/0471565253" rel="nofollow">this book</a>) that:</p>

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

<p>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.</p>

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

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

<hr>

<p><strong>PS:</strong> 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 <a href="http://rads.stackoverflow.com/amzn/click/0120510510" rel="nofollow">this book</a> for more info.</p>

<hr>

<p><strong>Edit:</strong> The case for <strong>M/M/c</strong> queues is much trickier. Here, you need to apply <a href="http://en.wikipedia.org/wiki/Erlang_unit#Erlang_C_formula" rel="nofollow">Erlang C formula</a>. </p>

<p><em>To derive the following formulas, you can take a look at Section 5.2.3 of <a href="http://rads.stackoverflow.com/amzn/click/0120510510" rel="nofollow">this book</a>.</em></p>

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

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

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

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

CC BY-SA 2.5
2011-01-09T20:10:01.677Z
nice ! I didn't know Little's law.
Suresh Venkat
CC BY-SA 2.5
2011-01-09T20:26:10.027Z
This answer cannot be correct.
David Jones
CC BY-SA 2.5
2011-01-09T20:32:28.417Z
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
CC BY-SA 2.5
2011-01-09T21:30:39.810Z
@David: Oops, you're right! See the corrected answer.
Sadeq Dousti
CC BY-SA 2.5
2011-01-09T23:01:06.210Z
@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.
Sadeq Dousti
CC BY-SA 2.5
2011-01-10T00:28:18.990Z
@Sadeq In your answer, you changed the problem to "assume there's only one server".  I specifically need to find an answer for the case of **N=25** servers.  Is there an easy generalization of your answer to "**M/M/C**", where **C=25** ?
David Jones
CC BY-SA 2.5
2011-01-10T01:10:07.527Z
@David: You're right. I forgot to mention the M/M/c case. Please take a look at the edited answer. Note that it requires much computation now!
Sadeq Dousti
CC BY-SA 2.5
2011-01-12T15:25:54.147Z
@Sadeq - thanks for sticking with it and giving a complete answer.  Much appreciated!
David Jones
CC BY-SA 2.5
2011-01-12T19:45:16.570Z
@David: You're welcome. You can accept the answers so that other people know it's no longer open.
Sadeq Dousti
CC BY-SA 2.5
2011-02-14T20:00:48.837Z
I found http://www.tkn.tu-berlin.de/curricula/ws0203/ue-kn/qt.pdf to be very useful in understanding some of the math in the answer.
Jon Bringhurst
CC BY-SA 2.5
2011-01-09T16:53:56.290Z
2011-01-10T01:13:32.327Z
2011-01-10T01:13:32.327Z
Sadeq Dousti
<p>I have a real-life situation that can be solved using Queueing Theory.<br>
This should be easy for someone in the field.  Any pointers would be appreciated.</p>

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

<p><strong>Question:</strong><br>
At steady state, what is the length of the queue?  (in terms of <strong>N</strong>, <strong>K</strong>).</p>

<p><strong>Related Question:</strong><br>
What is the expected delay for a Task to be completed?</p>

<p>Here is the real-life situation I am trying to model:<br>
I have an Apache web server with 25 worker processes.<br>
At steady-state there are 125 requests in the queue.<br>
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.</p>

<p>I know the single queue, single server, Poisson distribution is well analyzed.<br>
I don't know the more general solution for <strong>N</strong> servers.</p>

<p>thanks in advance,  </p>

CC BY-SA 2.5
2011-01-09T17:00:07.317Z
As per FAQ, you are advised NOT to sign your posts: *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!*
Sadeq Dousti
CC BY-SA 2.5
2011-01-09T20:09:40.037Z
I edited the original post to remove the sig
Suresh Venkat
CC BY-SA 2.5
2011-01-09T20:36:34.890Z
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
CC BY-SA 2.5
2011-01-09T20:48:56.227Z
You're not **emphasizing** "K > 1"; you're **correcting** your first assumption that "K is a fraction < 1".
Sadeq Dousti
CC BY-SA 2.5
2011-01-10T00:23:52.800Z
yes, corrected.
David Jones
<network-modeling><queueing-theory>
Queueing Theory: How to estimate steady-state queue length for single queue, N servers?
David Jones
# Queueing Theory: How to estimate steady-state queue length for single queue, N servers?

(Asked by: username_0 on 2011-01-09)

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.

thanks in advance,

**Tags:** network-modeling, queueing-theory

> **Comments:**
> **username_1**: As per FAQ, you are advised NOT to sign your posts: *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!*  
> **username_2**: I edited the original post to remove the sig  
> **username_0**: updated question to emphasize "K > 1", since average inter-arrival time must be longer than average service time in order to reach steady-state.  
> **username_1**: You're not **emphasizing** "K > 1"; you're **correcting** your first assumption that "K is a fraction < 1".  
> **username_0**: yes, corrected.  

---

## 1 answers

### Answer by username_1 on 2011-01-09. Score: 6

You need to apply [Little's law](http://en.wikipedia.org/wiki/Little%27s_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](http://en.wikipedia.org/wiki/Kendall%27s_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](http://rads.stackoverflow.com/amzn/click/0471565253)) 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](http://rads.stackoverflow.com/amzn/click/0120510510) for more info.

---

**Edit:** The case for **M/M/c** queues is much trickier. Here, you need to apply [Erlang C formula](http://en.wikipedia.org/wiki/Erlang_unit#Erlang_C_formula).

*To derive the following formulas, you can take a look at Section 5.2.3 of [this book](http://rads.stackoverflow.com/amzn/click/0120510510).*

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}$.

> **Comments:**
> **username_2**: nice ! I didn't know Little's law.  
> **username_0**: This answer cannot be correct.  
> **username_0**: 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.  
> **username_1**: @David: Oops, you're right! See the corrected answer.  
> **username_1**: @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.  
> **username_0**: @Sadeq In your answer, you changed the problem to "assume there's only one server".  I specifically need to find an answer for the case of **N=25** servers.  Is there an easy generalization of your answer to "**M/M/C**", where **C=25** ?  
> **username_1**: @David: You're right. I forgot to mention the M/M/c case. Please take a look at the edited answer. Note that it requires much computation now!  
> **username_0**: @Sadeq - thanks for sticking with it and giving a complete answer.  Much appreciated!  
> **username_1**: @David: You're welcome. You can accept the answers so that other people know it's no longer open.  
> **username_3**: I found http://www.tkn.tu-berlin.de/curricula/ws0203/ue-kn/qt.pdf to be very useful in understanding some of the math in the answer.  

---

