Derivation of fraction of time when system has k requests

Question

I was going through Distributed Systems by Maarten van Steen & Andrew S. Tanenbaum. While going through size scalability of systems, I came across this in a note.

I want to know the derivation of this formula. Also, for $\left ( 1 -\frac{\lambda }{\mu} \right )$ to be greater than zero, $\lambda$ should be less than $\mu$. That means system rate of processing requests is faster than request arrival rate, then how come requests would accumulate at any moment? Even if the system starts processing after the first request arrives and meanwhile second request is already being buffered, the system would finish processing the first request before the second request completes arrival. So no request would remain in buffer then.

Answer 1

I have to admit that this is pretty unintuitive. I calculated many equations today, not reaching any formula close to what it says in the book. However, I managed to get my hands on the book and a few other resources, and with a little digging, I found something that might help you.

Let's look at the equation from a statistics point of view. Let's say that the mean rate of request arrival is $\lambda$ and the mean process calculation rate is $\mu$. Now you can argue that the probability that you find a certain process in the system itself is $\frac{\lambda}{\mu}$.
Hence, the probability of finding $k$ processes in the system is equal to $$ \Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ But at any given time, there are packages arriving in the system and packages going out of the system. So at the interval that we are interested in viewing the system, no new packages should be found in the system. The probability of that equals $(1-\frac{\lambda}{\mu})$. Putting everything together we get the formula: $$ p_k = \Bigl(1-\frac{\lambda}{\mu}\Bigr)\Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ This is actually equal to the probability of finding exactly $k$ packages in the system.

I'll keep digging and update the answer if anything new comes up.

Answer 2

It took some time but I finally found how to derive the above equation. This thing requires the knowledge of continuous Markov chains. I learned about them from these two videos which was enough to understand the concept.

• Video 1
• Video 2

Now the derivation is here on Wikipedia. Basically, our system is an M/M/1 queue and can be modeled as in the following pic.

Each number represents the number of processes in the system. The rate matrix is written as follows.

$$ Q = \begin{pmatrix} -\lambda & \lambda & & & & \\ \mu & -(\mu+\lambda) & \lambda & & & \\ & \mu & -(\mu+\lambda) & \lambda & & \\ & & \mu & -(\mu+\lambda) & \lambda & \\ & & & & \ddots & \end{pmatrix} $$ In steady state ($Q \pi = 0$, where $\pi$ is just the probability distribution $P_{0}, P_{1}, P_{2}, \ldots$), the equations are $$ \begin{eqnarray*} \mu P_{1} &=& \lambda P_{0} \\ \lambda P_{0} + \mu P_{2} &=& (\lambda + \mu) P_{1} \\ \lambda P_{n-1} + \mu P_{n+1} &=& (\lambda + \mu) P_{n} \end{eqnarray*} $$ which gives $$ P_{n} = \frac{\lambda}{\mu} P_{n-1},\quad\text{$n=1,2,...$} $$ and the fact that system is going to be in any one of the following states at any moment of time leads to $$ P_{0} + P_{1} + P_{2} + \ldots = 1 $$ So, finally we have $$ P_{n} = \rho^{n}(1-\rho) $$ where $\rho = \cfrac{\lambda}{\mu}$ in steady state.