4
$\begingroup$

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,

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

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

$\endgroup$
  • 2
    $\begingroup$ nice ! I didn't know Little's law. $\endgroup$ – Suresh Venkat Jan 9 '11 at 20:10
  • $\begingroup$ This answer cannot be correct. $\endgroup$ – David Jones Jan 9 '11 at 20:26
  • $\begingroup$ 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. $\endgroup$ – David Jones Jan 9 '11 at 20:32
  • $\begingroup$ @David: Oops, you're right! See the corrected answer. $\endgroup$ – M.S. Dousti Jan 9 '11 at 21:30
  • $\begingroup$ @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. $\endgroup$ – M.S. Dousti Jan 9 '11 at 23:01

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.