5
$\begingroup$

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.

  • 0
    I think that depends on exactly how you compare "overall performance". $F$rom 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.2012-01-19

3 Answers 3

6

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

  • 0
    it seams that you assume \rho>1 which may not hold2016-10-12
1

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]

1

To answer the question we will compare a few parameters of the systems:

  1. $\rho$ - the servers utilization: In general the utilization for an $M/M/c$ system is $ \rho=\frac{\lambda}{c\mu} $ For the $M/M/1$ system: $ \rho=\frac{\lambda}{\mu} $

for the $M/M/2$ system we have a rate of $2\lambda$ so $ \rho=\frac{2\lambda}{2\cdot\mu}=\frac{\lambda}{\mu} $

so the utilization is the same.

  1. $P_{0}$ - the probability that there are no costumers in the queue (all servers are available): for the $M/M/1$ system: $ P_{0}=(1-\rho)\rho^{0}=1-\rho $ for the $M/M/2$ system:

$ P_{0}=\frac{1}{\sum_{n=0}^{c-1}\frac{(c\rho)^{n}}{n!}+(c\rho)^{c}\cdot\frac{1}{c!}\cdot\frac{1}{1-\rho}} $

for $c=2$ $ P_{0}=\frac{1}{\sum_{n=0}^{1}\frac{(c\rho)^{n}}{n!}+(2\rho)^{2}\cdot\frac{1}{2}\cdot\frac{1}{1-\rho}} $ $ P_{0}=\frac{1}{1+2\rho+2\rho^{2}\cdot\frac{1}{1-\rho}} $ $ =\frac{1}{1+2\rho+\frac{2\rho^{2}}{1-\rho}} $ $ =\frac{1}{\frac{1-\rho+2\rho(1-\rho)+2\rho^{2}}{1-\rho}} $ $ =\frac{1-\rho}{1-\rho+2\rho(1-\rho)+2\rho^{2}} $ $ =\frac{1-\rho}{1-\rho+2\rho-2\rho^{2}+2\rho^{2}} $ $ =\frac{1-\rho}{1+\rho} $

we have concluded that both systems have the same utilization $\rho$ thus, since $1+\rho>1$ (unless $\lambda=0$ and in that case the entire discussion is degenerated) $ P_{0,M/M/2}=\frac{1-\rho}{1+\rho}<1-\rho=P_{0,M/M/1} $

thus the system is more empty in the $M/M/1$ system!

  1. $L$ - the average number of customers in the system: In the $M/M/1$ system:

$ L_{M/M/1}=\frac{\rho}{1-\rho} $

In the $M/M/2$ system $ L=2\rho+\frac{(2\rho)^{3}}{2\cdot2\cdot(1-\rho)^{2}}\cdot\frac{1-\rho}{1+\rho} $ $ =2\rho+\frac{2\rho^{3}}{1-\rho}\cdot\frac{1}{1+\rho} $ $ =2\rho+\frac{2\rho^{3}}{1-\rho^{2}} $ $ =\frac{2\rho}{1-\rho^{2}}=\frac{2}{1+\rho}\cdot\frac{\rho}{1-\rho} $

thus $ L_{M/M/2}=\frac{2}{1+\rho}\cdot L_{M/M/1} $

the question of $ L_{M/M/2}>L_{M/M/1} $

comes down to does $\lambda>\mu$ .

  1. $w$ - the average time a costumer is in the system: $ w_{M/M/1}=\frac{1}{\mu(1-\rho)}=\frac{\rho}{\lambda(1-\rho)} $ $ w_{M/M/2}=\frac{L_{M/M/2}}{2\lambda}=\frac{\rho}{\lambda(1-\rho)(1+\rho)}=\frac{1}{1+\rho}W_{M/M/1} $

thus, on average, a customer waits more in an $M/M/2$ system.

  1. $W_{Q}$ - the average time a customer is in a queue $ W_{Q,M/M/1}=w_{M/M/1}-\frac{1}{\mu} $

and $ W_{Q,M/M/2}=w_{M/M/2}-\frac{1}{\mu} $

and $ W_{Q,M/M/2}>W_{Q,M/M/2} $

iff $ w_{M/M/2}>w_{M/M/1} $

  1. $L_{Q}$ - the average number of customers in queue $ L_{Q,M/M/1}=\frac{\rho^{2}}{1-\rho} $

and $ L_{Q,M/M/2}=2\lambda W_{Q,M/M/2}=2\lambda(w-\frac{1}{\mu}) $ $ =2\lambda w-2\frac{\lambda}{\mu} $ $ =2\lambda(\frac{\rho}{\lambda(1-\rho)(1+\rho)})-2\rho $ $ =\frac{2\rho}{(1-\rho)(1+\rho)}-2\rho $ $ =\frac{2\rho-2\rho(1-\rho^{2})}{(1-\rho)(1+\rho)} $ $ =\frac{2\rho-2\rho+2\rho^{3}}{(1-\rho)(1+\rho)} $ $ =\frac{2\rho^{3}}{(1-\rho)(1+\rho)} $

thus $L_{Q,M/M/2}>L_{Q,M/M/1}$ iff $ \frac{L_{Q,M/M/2}}{L_{Q,M/M/1}}>1 $

iff $ \frac{2\rho^{3}}{(1-\rho)(1+\rho)}\cdot\frac{1-\rho}{\rho^{2}}>1 $

iff $ \frac{2\rho}{1+\rho}>1 $

iff $ 2\rho>1+\rho $

iff $ \rho>1 $

iff $ \lambda>\mu $

To conclude - the utilization of both systems are the same, the system is more empty in the $M/M/1$ system and the average number of customers in the system, the average time a costumer is in the system, the average time a customer is in a queue and the average number of customers in queue are greater in the $M/M/2$ system iff $\lambda>\mu$.