Continuous markov chain example

Question

Hi I found the following question in a paper. I'm unable to find the answer for part c and d. Can someone please help me.

Data packets are temporarily stored in a buffer having space only for $S$ packets at a time till they are transferred for further processing. Single packets arrive according to a Poisson arrival process with constant arrival rate $λ$. Every $t$ time units, buffer is checked for presence of packets. In case of non-empty buffer a single packet is taken away and transferred for processing. If the buffer is empty at the time of checking nothing happens and the next checking is done after $t$ time units. This means that the inter-departure time is constant and equal to $t$ in case of non-empty buffer. The transfer time, that is the time taken to move data away from the buffer, is assumed to be negligible. Due to limited space in the buffer some packets are lost and need to be retransmitted. In order to estimate the loss probability of the packets following calculation steps are done:

a) Express the probability for exactly $k$ packet arrivals during the time interval $t$ denoted by $α_k$.

b) Calculate $α_0$, $α_1$ and $α_2$ for $λt=0.8$ accurate to $2$ decimal places.

c) What is the number of packets taken away from the non-empty buffer during time interval $t$?

d) We define the state of the buffer to be the number of packets in buffer immediately after a completed checking. Draw the corresponding Markov chain for $S=3$. Indicate all the transition probabilities using $α_0$, $α_1$ and $α_2$.

Answers:

a) $α_k=(( λt)^k/k!)e^{(-λt)}$

b) By assigning the values, $α_0=0.45$, $α_1=0.36$, $α_2=0.14$

c) I'm not clear how the get the answer for $c$ and $d$, how can I find the number of packets taken away ?

d) Can someone please give me a clue to find the probability of transferring from $3$ to $2$, and so on.

Answer 1

The idea is that, by default, the number of packets in the buffer decreases by $1$ over a time interval, as one packet is taken away for processing. (I think that's what part (c) is getting at.) But new packets may arrive to make up for it.

As a result, in a nonempty buffer, the number of packets will go down by $1$ if no new packets arrive: with probability $\alpha_0$. With probability $\alpha_1$, a single new packet arrives to make up for the packet taken away for processing: the total number of packets doesn't change. If multiple new packets arrive, the total number of packets can increase up to the maximum buffer size; beyond that, new packets don't help.

To help illustrate this, here are the transitions from state $1$ (that is, $1$ packet in the buffer) in the $S=3$ case:

• With probability $\alpha_0$, no new packets arrive, and the number of packets goes down to $0$ when the remaining packet is processed.
• With probability $\alpha_1$, a new packet arrives to replace the packet currently in the buffer.
• With probability $\alpha_2$, two new packets arrive while one gets processed, increasing the number of packets in the buffer by a total of $1$.
• In all other cases, enough packets arrive to fill the buffer, so it doesn't matter how many that is: we end up with the maximum number of $3$ packets in the buffer.

(Note: I'm assuming that the state - number of packets in the buffer - is measured before a packet is taken away for processing. If we do it after, we lose some information: e.g., it's never possible to be in state $3$.)

I'll leave it to you to figure out what happens starting from states $0$, $2$, and $3$.