How to calculate probability of packet loss and drop rate?

Problem Detail: 

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.

Asked By : 0kB

Answered By : arcticriki

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? :)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37975