Analyzing a multiple-queue single-server model

Question

Consider the following multiple-queue single-server model of a packet network problem. At each discrete time $t=0,1,\ldots,n$, a packet may arrive at the server R with probability $1-\epsilon_1$. The arrived packet enters one of the queues $l=0,\ldots,L-1$ randomly with equal probability $\frac{1}{L}$. In the same time slot, one of the queues is then uniformly randomly chosen by the server. With probability $1-\epsilon_2$, a packet in the selected queue will be departed. The event that the selected queue is empty (and therefore no packet is departed) is referred to as wasted. Assume that before $t=0$ the system is empty. My questions is, what is the expected fraction of the number of wasted times, $W_n/n$, as a function of $L$, for given $n$, $\epsilon_1$ and $\epsilon_2$? I'm in particular interested in the order of the function.

I have performed some simulations. It is seen that

1. $W_n/n$ is a monotonically increasing function of $L$.
2. The order of the function seems to be different for $\epsilon_1>\epsilon_2$, $\epsilon_1=\epsilon_2$, and $\epsilon_1<\epsilon_2$.
3. The function doesn't seem to change for different pairs of $\epsilon_1,\epsilon_2$ if $\frac{1-\epsilon_1}{1-\epsilon_2}$ is the same.

It is highly appreciated if someone can point me to some references of similar problems.

Answer 1

Let $\lambda:=1-\epsilon_1$, $\mu:=1-\epsilon_2$; also, denote $p_L:=\frac{\lambda}{L}(1-\frac{\mu}{L})$ and $q_L:=\frac{\mu}{L}(1-\frac{\lambda}{L})$. Consider a fixed queue (one of those $L$), then it is a (discrete-time) birth and death process with birth probability $p_L$ and death probability $q_L$. You only have to analyse the expected number of wasted times for one queue (for all of them it's just $L\times$ that).

Then the limiting behaviour is clear: $W_n/n$ goes to $0$ as $n\to\infty$ for the case $p_L\geq q_L$ (which is equivalent to $\lambda\geq \mu$), since the walk is not positive recurrent. For $\lambda<\mu$ a quick calculation seems to show that it goes to $\mu-\lambda$. If you want exact values for a finite $n$, well, you need to calculate $k$-step transition probabilities from $0$ to $0$ for the above random walk. I think the exact formulas should be available.