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?

  • $\begingroup$ I'd say you need to restrict $\rho$ to the positive integers $\mathbb{N}$ since jobs are discrete entities. Concerning the question, first thing you should do is draw the transition rate diagram for a system of two queues where everything is exponential and see if you can say anything about the equilibrium distribution. $\endgroup$ – Ritz Jan 18 '16 at 8:09
  • $\begingroup$ Consider the case of 3 jobs in, and 1 job out. For example, the queuing station take three "packets" in, and emits one out for a special kind of router. In this case, $\rho$ is $\frac{1}{3}$. I'll modify the question to more accurately reflect that $\rho$ should be rational, $\rho \in \mathbb{Q}$. By "transition rate diagram", do you mean a DTMC? If not, can you please elaborate? Thanks. $\endgroup$ – Alan Jan 18 '16 at 10:56

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.

  • $\begingroup$ Thank you for your thoughts. With regard to "the rate going in should be equal to the rate going out", I guess that's the root of my problem. If server 1 takes in one job and emits three, doesn't this violate this principle? Yet, this is a very real-world scenario. Indeed, server 2 would need to have a service rate that could accommodate the 3x "speed-up" of server 1 to maintain balance, but the arrival and departure rates will be different at each server. This asymmetry of rates is the core of the question. Do queuing model assumptions work in this case? They never seem to address this. $\endgroup$ – Alan Jan 18 '16 at 13:43
  • $\begingroup$ Yes, they definitely still work! The balance principle of ``the rate going in should be equal to the rate going out'' is a very basic method in the analysis of Markov processes. Since you have trouble with that, I think it is best not to go in that direction. Instead, we can look at approximations for the mean waiting time and the mean number of jobs at each server. A reference with which you can start is Chapter 3 of these lecture notes. $\endgroup$ – Ritz Jan 18 '16 at 13:51
  • 1
    $\begingroup$ A quick skim through your reference enlightens me with concept of "batches", which were foreign to me in this area. This appears that it will address my questions. Thank you so much. $\endgroup$ – Alan Jan 18 '16 at 14:01

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.