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
    I assume that there are a finite number of packets in each queue?2012-04-12
  • 0
    yes, queues are finite.2012-04-12
  • 0
    It's not as simple as you make out, because the probability of choosing queue $i$ changes every time a new element is popped. In general the rates after every popped element will be a complicated function of the initial sizes of the queues and the elements that have been popped so far. There may be a rough approximation though. I'll try to look at it later.2012-04-12
  • 0
    Thank you. I forgot to emphasize that the probabilities of choosing each queue are fixed. I calculate them at the beginning based on the initial size of each queue and stick to them until the end. Does this make things any easier?2012-04-12
  • 0
    Ah, okay. That makes it easier (what happens when you pick a queue with nothing in it though?)2012-04-12
  • 0
    Hmm. My goal here is to spread packets in the output according to the size of the flow they belong to. I think the easiest way here would be to keep selection probabilities intact even when queues run out and pick the first non-empty queue that gets selected. Would this make any sense?2012-04-12
  • 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.