1
$\begingroup$

I'm trying to prove that the expected total time spent in an $M/M/n$ queue is less than the expected total time spent in a system with $n$ independent $M/M/1$ queues.

Let $\lambda$ be the arrival rate of customers to both systems (i.e. customers arrive with rate $\frac{\lambda}{n}$ to each independent $M/M/1$ queue) and let the service rate of each server be $\mu > \frac{\lambda}{n}$.

I can't seem to prove that the expectedtotal time spent in an $M/M/n$ queue is less than the expected total time spent in a system with $n$ independent $M/M/1$ queues.

Can anyone help me do this?

$\endgroup$
2
$\begingroup$

You can do it by a pairing argument.

If there are $k$ jobs in the system, then the M/M/$n$ queue will process them at a rate of $\min\{k,n\}\mu$, whereas the system with $n$ independent M/M/$1$ queues will process them at a rate of $j\mu$, where $j \le \min\{k,n\}$ is the number of active queues.

So, no matter how many jobs are in the system (and how they are distributed between the M/M/$1$ queues) the system with independent queues will process them at most at the same rate as the M/M/$n$ queue, and sometimes slower.

(For example, if $2$ jobs arrive into the same queue, the system with independent queues will only process them at a rate of $\mu$, while the M/M/$n$ queue would process them at a rate of $2\mu$.)

$\endgroup$
0
$\begingroup$

Or you can do it directly.

  1. expected total time spent by a customer in the M/M/n queue with service rate $\mu$ and arrival rate $\lambda$ is equal to $1/(n\mu-\lambda)$.

  2. expected total time spent by an arbitrary arriving (at rate $\lambda$) customer in the system composed of $n$ parallel running M/M/1 queues each with service rate $\mu$ is equal to (of the custmer chooses a queue randomly among $n$): $$ \sum_{i=1}^n {1 \over n} {1 \over \mu-{\lambda \over n}}={n \over n \mu - \lambda}. $$

Right now you can see that (1) is $n$ times faster than (2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy