Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 is a fraction < 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,
-- David Jones
dxjones@gmail.com

share|improve this question
    
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!" –  Qiaochu Yuan Jan 9 '11 at 17:35

2 Answers 2

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.

share|improve this answer
    
+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. –  Mike Spivey Jan 18 '11 at 18:32
    
@Mike: Thanks a lot! –  Shai Covo Jan 18 '11 at 19:25

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

where

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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