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.

Consider the following problem:

We have a simple queueing system with $\lambda%$ - probabilistic intensity of queries per some predefined time interval.

Now, we can arrange the system as a single high-end server ($M/M/1$, which can handle the queries with the intensity of $2\mu$) or as two low-end servers ($M/M/2$, each server working with intensity of $\mu$).

So, the question is - which variant is better in terms of overall performance?

I suspect that it's the first one, but, unfortunately, my knowledge of queuing / probability theory isn't enough.

Thank you.

share|improve this question
    
I think that depends on exactly how you compare "overall performance". From a practical point of view the two-server configuration has the significant advantage that it can still function at lower capacity in the event of one server breaking down. The problem with it is more that it can be more work to get a multi-server system to work correctly in the first place. But neither of those considerations are mathematics. –  Henning Makholm Jan 19 '12 at 21:51

2 Answers 2

up vote 4 down vote accepted

You need to specify what you mean by "overall performance", but for most measures the two server system will have better performance. Intuitively, a "complicated" customer, one that has a long service time will shut down the M/M/1 queue but only criple the M/M/2 queue.

If we let the utiliztion be $$\rho=\frac{\lambda}{2\mu}$$ then some of the usual performance measures are $L_q$ the average length of the queue, $W_q$ the average waiting time, and $\pi_0$ the probability that the queue is empty. For the M/M/1 queue these measures are $$L_q=\frac{\rho^2}{1-\rho}$$ $$W_q=\frac{\rho^2}{\lambda(1-\rho)}$$ $$\pi_0=1-\rho$$

and for the M/M/2 queue

$$L_q=\frac{2\rho^3}{1-\rho^2}$$ $$W_q=\frac{2\rho^3}{\lambda(1-\rho^2)}$$ $$\pi_0=\frac{1-\rho}{1+\rho}$$

So, the system is empty more often in the M/M/1 queue, but the expected wait time and the expected queue length are less for the M/M/2 (as $\frac{2\rho}{1+\rho}<1$).

share|improve this answer
    
Thank you very much. By the way, where can I find the $L_q, W_q$ formulas for the $M/M/k$ case? And how is the utilization defined for the $M/M/k$ queue (so that we get $\rho=\frac{\lambda}{2\mu}$ in both cases, even though we have $2\mu$ per-server in the first and $\mu$ per-server in the second case)? –  Yippie-Kai-Yay Jan 20 '12 at 0:20
    
The M/M/k queueing equations can be found in any Operations Research text (I got mine from my decades old notes.) Online, you can get them from Larson and Odoni's Urban OR text at web.mit.edu/urban_or_book/www/book (I'm pretty sure that the queuing equations are in there, but not certain). –  deinst Jan 20 '12 at 3:12
    
@Yip For the utilization note that we have twice as many servers each working half as fast, so the total amount being done is the same. For a general M/M/n queue the utiliztion is $\rho=\frac{\lambda}{n\mu}$ –  deinst Jan 20 '12 at 3:15

If "overall performance" is the expected time a client/customer/query spend in the M/M system, then the single server system outperforms the second one.

The reasoning is simple: the M/M/1 system functions in "full" intensity even with a single query at the system; the M/M/2 system needs two queries present to reach the highest service intensity.

So, queries arriving at an empty system spend less time on the M/M/1. [Queries arriving at a system with at least one query present spend them same time on average]

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.