Queuing systems with different arrival and departure job multiplicities

404 Views Asked by At

Consider the following. A queue has an arrival rate of $\lambda$, where a single job enters the queue. Next, the job is processed by the service at rate $\mu$, and it emits three jobs in response to the single input job. This case can be generalized to $j$ ingress jobs emitting $\rho j$ egress jobs, where $\rho \in \mathbb{Q}$ is some coefficient reflecting the egress job multiplicity.

Finally, consider a network (Jackson or Gordon-Newell) of such queues, each with the same generality of asymmetric ingress-egress job multiplicity. I'm seeking to solve the Traffic (Balance) Equations of such a queuing network, where this ingress and egress asymmetry exists.

All the literature I've seen always assumes that one input job to a queue emits one output job (or is dropped if buffering cannot accommodate).

What methods are used to solve such a problem?

1

There are 1 best solutions below

3
On BEST ANSWER

An example to start with

Consider a system of two exponential single-server queues in series. Jobs arrive according to a Poisson process with rate $\lambda$. Service times at server $i$ are exponentially distributed with mean $1/\mu_i$. Let $X_i(t)$ denote the number of jobs in queue $i$ at time $t$ (including the one in service). The state space of the associated Markov process (continuous time Markov chain) is $\{ (n_1,n_2) \mid n_i \in \mathbb{N}_0, ~ i = 1,2 \}$.

Let us assume that a single departing job from server $1$ creates $3$ jobs at server $2$, as per your question. Note that in this case the interpretation should be that server $1$ serves batches of size $3$ and server $2$ serves the jobs one by one.

We can write down the transition rates as follows, where we use the notation $\text{from state} \overset{\text{with rate}}{\longrightarrow} \text{to state}$,

\begin{align} (n_1,n_2) &\overset{\lambda}{\longrightarrow} (n_1 + 1, n_2), \quad n_1,n_2 \ge 0, \\ (n_1,n_2) &\overset{\mu_1}{\longrightarrow} (n_1 - 1, n_2 + 3), \quad n_1 \ge 1, ~n_2 \ge 0, \\ (n_1,n_2) &\overset{\mu_2}{\longrightarrow} (n_1, n_2 - 1), \quad n_0 \ge 0, ~ n_2 \ge 1. \\ \end{align}

You can easily draw a transition rate diagram from the description of these transition rates to visualize the problem.

I assume you are interested in the equilibrium probabilities

\begin{equation} p(n_1,n_2) := \lim_{t \to \infty} \mathbb{P}(X_i(t) = n_1, ~ X_2(t) = n_2). \end{equation}

Can you write down the balance equations for each state $(n_1,n_2)$ by using the principle that in stability the rate going in should be equal to the rate going out?

I am not claiming that you can get a closed form solution for the equilibrium probabilities $p(n_1,n_2)$, but this should be the way to go if you want to try.