0
$\begingroup$

In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a rate $\lambda$ and are served at rate $\mu$ (using the Poisson distribution).

My attempt at a solution:

Probability of packet loss = Probability that the system has exactly $n$ packets (i.e., it is at its capacity)?

I also have a formula from my notes where probability of packet loss is approximated at $(1 - \frac{\lambda}{\mu})(\frac{\lambda}{\mu})^z$ (so this is most likely correct but can someone please explain why?).

I'm not sure how to calculate the rate at which packets are dropped. I already know the probabilities $P(n)$ that there are $n$ packets in the system where $n = 0, 1, ..., z$ packets.

$\endgroup$
1
$\begingroup$

If you study M/M/1 queuing systems you'll probably know that such a queuing system can be seen as a markovian chain with birth rate λ and death rate $\mu$; that is to say that you change your state (and in an M/M/1 the state is the number of clients in the system) by unitary steps: $-1$ with rate $\mu$ and $+1$ with rate $\lambda$.

It is quite hard and long to explain in a thread like this and for this reason I suggest you to take a look at the markovian chains theory to understand why it works like this. Anyway, I'll try to give you an idea: you can set a basic fluxus equation to describe the system:

$$P[x(t)=k] \mu = P[x(t)=k-1] \lambda$$

and analyzing the transition probabilities you will find: $$ P[x(t+h)=k+1 | x(t)=k] = \lambda h + o(h) \\ P[x(t+h)=k-1 | x(t)=k] = \mu h + o(h)\\ P[x(t+h)=k | x(t)=k] = 1-\lambda h-\mu h + o(h)\\ P[x(t+h)=k+j | x(t)=k] = h + o(h)$$

with $h$ defined as very little piece of time.

So, defined $ρ=\frac{\lambda}{\mu}$ as the load factor of the system, you will find that (recalling the total probability theorem):

$$ P[x(t)=k] = (1-ρ) ρ^k $$

If you take a look at this result, you will recognize the answer to your question: if the system is a blocking system with blocking capacity $z$, the probability of packet loss is the following:

$$P[z\,\text{clients in the system}] = P[k\,\text{clients in the system}] = P[x(t)=k] = (1-ρ) ρ^k$$

Is it ok? :)

$\endgroup$
  • $\begingroup$ Thank you! This explanation really helped but now how would I go about calculating the packet loss rate? I am thinking it may be proportional to $\rho$? $\endgroup$ – 0kB Feb 7 '15 at 20:34
  • $\begingroup$ Given that this is a finite queue and packets will be dropped $P_0$ is no longer $1-\rho$ but is $(1-\rho)/(1-\rho^{N+1})$. Therefore $P[x(t)=k]=\rho^n (1-\rho)/(1-\rho^{N+1})$. Happy to be corrected, as I'm a little rusty on this stuff - please let me know if you agree. $\endgroup$ – jsaven Feb 13 at 5:14
0
$\begingroup$

Ok! Now if you have the "packet loss probability" (or in other words "the packet blocking probability", that from now I will call $P_\mathrm{blk}$) you can simply calculate the packet loss rate as: $$\lambda P_\mathrm{blk}$$

Otherwise, if you want to calculate the average rate of admitted packets you can simply do: $$\lambda (1 - P_\mathrm{blk})$$

I think it should be clear why I can do this simple calculation. Knowing the $P(n)$ probabilities you can calculate $P_\mathrm{blk}$ as: $$P[x(t)=k]=(1−\rho)\rho k$$

as I said before. Of course the rate is proportional to the load factor because this parameter gives how much the system is "load" in terms of occupation and traffic during the time, in stationary conditions. If you have a load factor very close to 1 you are much more likely to be in an unstable condition and go to the blocking condition. For M/M/1 systems it is good to have very low load factor :)

I hope you can now solve your problem!

$\endgroup$
  • $\begingroup$ Rather than posting a second answer, please edit your existing answer to add this material to it. It doesn't benefit anyone to have the material split across two answers. $\endgroup$ – D.W. Feb 9 '15 at 6:31

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.