Consider a queue with a Poisson-distributed arrival rate of packets (with the mean $\lambda$). Now the packets are not served immediately, but only in chunks of size $N$ (i.e., once $N$ packets are accumulated).

Hence, there are two questions:

1) Assuming instantaneous serving of the chunks, how to determine the distribution of the chunk departures? (output process of the queue). It seems to me that it will be also Poisson with the rate $\lambda_{out} = \lambda/N$, but is there a way to prove its Poisson nature?

2) How to determine waiting time for the individual packets?

Thanks in advance for help!


(1) I think the departure times have an Erlang$(N,\lambda)$ distribution because they are the same as the $N^{th}$ arrival time of the arrival process.

The departure times would be Poisson if they were randomly on average every $N^{th}$ arrival instead of fixed at each $N^{th}$ arrival. That is, if every arrival had probability $1/N$ to cause a departure.

(2) Assuming you mean any random packet without knowing its position in the queue. Then, it is equally likely to take any of the $N$ queue positions. If it has queue position $i$ then the waiting time is the same as the arrival time of the $(N-i)^{th}$ packet (which has distribution Erlang$(N-i,\lambda)$). So the packet's waiting time $W$ has the same distribution as

$$\dfrac{X_0 + X_1 + \cdots + X_{N-1}}{N}$$

where $X_i$ is the arrival time of the $i^{th}$ packet and $X_0=0$ is for each $N^{th}$ packet which has $0$ waiting time. So there is a point mass probability: $P(W=0) = 1/N$.

Otherwise, for $t>0,\; W$ has density

\begin{align} f_W(t) &= \dfrac{1}{N}\left[f_{X_1}(t) + \cdots + f_{X_{N-1}}(t) \right] \\ & \\ &= \dfrac{1}{N}\left[\sum_{n=1}^{N-1} \dfrac{\lambda^n t^{n-1}}{(n-1)!}e^{-\lambda t} \right] \qquad\qquad\qquad\text{using the Erlang pdf} \\ & \\ &= \dfrac{\lambda}{N}e^{-\lambda t} \sum_{n=0}^{N-2} \dfrac{(\lambda t)^{n}}{n!}. \\ \end{align}

  • $\begingroup$ thanks for the answer, I even build up a small simpy simulation to confim... it is indeed exactly like you said. Although it is a little sad for me, since Erlang distribution is much harder for further analysis. $\endgroup$ – mck Mar 26 '16 at 13:09
  • $\begingroup$ @user1821955 Yes, when I was doing (2) I was hoping it would simplify more but it doesn't seem to. You probably noticed that the sum in that result is the first $N-2$ terms of the Taylor series for $e^{\lambda t}$. $\endgroup$ – Mick A Mar 26 '16 at 13:23

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.