2
$\begingroup$

$\newcommand{\length}{\textrm{length}}$I have queues of packets of different sizes. The probability of choosing queue $i$ where I pop the first packet is

$p(i) = \frac{\length(i)}{ \sum_j \length(j)}$

The probability that I don't choose queue $i$ is $1-p(i)$. It should thus follow a Bernoulli distribution. I calculate these probabilities at the beginning and stick to them until the end.

My goal is have for each queue an approximation of a Poisson Process. Is this possible?

Example:

I have queues $a$,$b$,$c$ each with with packets 1, 2, 3, etc. Say that I get the following output:

$a_1, b_1, b_2, c_1, a_2, b_3, a_3, c_2, b_4, a_4, b_5,\dots$

I want to approximate the arrival times for elements from queue $a$ by some exponential random variable with a certain intensity. Same thing for queues $b$ and $c$. Is this possible?

  • 0
    Any idea as to how I can go about it?2012-04-13

1 Answers 1

1

First consider the case when none of the queues is empty. You have probability $p_i$ of picking from queue $i$. The sequence of 0s and 1s that indicates whether an element came from queue $i$ or not is therefore a Bernoulli process with probability $p_i$.

The waiting time $W_i$ between arrival of packets from queue $i$ therefore follows a Geometric distribution with parameter $p_i$, i.e.

$P(W_i=w) = (1-p_i)^{w-1}p_i$

which is the exponential-like process you are after (a geometric distribution is the discrete version of the exponential distribution - if there are $n$ packets per second and you let $n\rightarrow \infty$ and $p\rightarrow 0$ in such a way that $\lambda=np$ remains constant, then you get an exponential distribution with parameter $\lambda$).

If you want to consider the case of finite queues, then I think that the simplest thing to do is to reset the model whenever one of the queues becomes empty. If queue $j$ empties, then one option is to shift all the probabilities by

$p_j \rightarrow 0, \qquad p_i \rightarrow \frac{p_i}{1-p_j} \textrm{ for }i\neq j$

and carry on as before (you now have zero probability of selecting from queue $j$, which is equivalent to ignoring that queue if it is selected with the previous probabilities). Another option is to re-evaluate the probabilities according to the current length of each queue.