3
$\begingroup$

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is:

R = S + QS
  • S is service time
  • Q is number of customers ahead
  • R is residence time

Then he describes a case with a single queue and two servers and says that the equation becomes

R = S + 1/2 SpQ
  • p is per-server utilization 0 < p < 1.

I don't understand why p is a factor here. Wouldn't all servers be busy whenever there are customers waiting in line? Why is this different from the single-server case? The explanation given in the book is copied on slide 25 here. I don't understand the reasoning. Why do we need p?

$\endgroup$
1
$\begingroup$

$Q$ represents the average of a discrete random variable. Sometimes there are no customers waiting in line, sometimes there's one, and sometimes there are many. So there is some probability distribution for $Q$. The difference between a two-server queue and a single-server queue that's twice as fast, is the expected service time when the queue is empty except for the one customer receiving service. That's the transition from state 1 to state 0 in the Markov chain:

enter image description here

Intuitively, when a customer reaches the head of the queue the service in the two-server system will take twice as long as with the single server that's twice as fast. The expected service time with the two-servers is $S$, while the expected service time with the single fast server is $S/2$. What's less intuitive is that customers will, on average, spend somewhat less time waiting to get to the head of the queue with the two-server system.

To see this, consider the case of a customer that arrives when there is one customer currently being serviced. In the two-server case the arriving customer immediately gets the other server. The total expected response time in this case is $S$, but that's all service time, no waiting time. In the fast single-server case the arriving customer waits, on average $S/2$ time for the preceding customer to finish and then gets, on average, $S/2$ amount of service. The total expected response time in this case is also $S$, but it's half service time and half waiting time. Let's work out the exact difference:

Fast Single-Server

This is an M/M/1 queue with arrival rate $X$ and completion rate $S/2$. The steady state distribution, $\pi_i$ for the Markov chain in the fast single-server case is $$\pi_i = (1-U)U^i$$ where $U$, the server utilization, is $XS/2$.

Then the expected number of customers in the queue is $$ Q_f = \sum_{i=0}^\infty \pi_i i = \sum_{i=0}^\infty (1-U)U^i i = (1-U)U\sum_{i=0}^\infty U^{i-1} i = \frac{(1-U)U}{(1-U)^2} = \frac{U}{1-U}.$$

Then by Little's law $$ R_f = \frac{Q_f}{X} = \frac{U}{X(1-U)} = \frac{XS/2}{X(1-U)} = \frac{S/2}{1-U}, $$ but we want to represent $R$ as service time + waiting time, so $$ R_f = \frac{S}{2} - \frac{S}{2} + \frac{S/2}{1-U} = \frac{S}{2} + \frac{-S/2 + SU/2 + S/2}{1-U} = \frac{S}{2} + \frac{US/2}{1-U} = \frac{S}{2} + \frac{S}{2}Q_f. $$

So we have that the waiting time is $$ W_f = \frac{S}{2}Q_f = \frac{SU}{2(1-U)}.$$

Two Slow Servers

This is an M/M/2 queue. We will again let $U = S X/2$ (this is Little's law for the utilization of each of the two servers, the reason the result is the same as in the fast-server case is that now $X$ is halved rather than $S$ being halved.) The steady state distribution is: $$ \pi_0 = \frac{1-U}{1+U} $$ and $$ \pi_i = 2 U^i \pi_0, \;\;\; i \geq 1.$$

Now $$ Q_s = \sum_{i=0}^\infty \pi_i i = \frac{2U}{1-U^2}.$$ (Derivation left as an exercise.)

Then by Little's law we get $$ R_s = \frac{Q_s}{X} = \frac{S}{1-U^2} = \frac{2}{1+U}R_f, $$ which we want to represent as service time ($S$) plus waiting time.

$$ R_s = S - S + \frac{S}{1-U^2} = S + \frac{SU^2}{1-U^2} = S + \frac{S}{2} U Q_s, $$ and the waiting time is $$ W_s = \frac{S}{2} U Q_s = \frac{SU^2}{1-U^2} = \frac{2U}{1+U} W_f.$$

Summary

The two slow servers always have a service time twice that of the fast server. The two slower servers have a total response time that is $2/(1+U)$ times the fast servers' total response time. ($0\leq U<1$, so the response time is always worse.) But the two slow servers have a waiting time that is $2U/(1+U)$ times the fast server's waiting time, and so there's less waiting time with two slow servers.

$\endgroup$

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.