Concurrency related problems in $n$ independent, parallel $M/M/1$ queues

Question

Queueing Model:

Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rate $\lambda$ and service rate $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline and if there is some customer in service, no more customers can enter it.

For each customer $c$, its start time, finish time, service interval are denoted by $c_{.st}$, $c_{.ft}$, and $[c_{.st}, c_{.ft}]$, respectively.

Problem:

I want to study some concurrency-related problems in such queueing system in the long run.

(1). Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of some customer $c'$ served by $Q_j$ (i.e., $c_{.st} \in [c'_{.st}, c'_{.ft}]$)?

Notice that $c'$ will be unique if $c_{.st} \in [c'_{.st}, c'_{.ft}]$ holds (see the figure below).

(2). Given a customer $c'$ served by $Q_j$, what is the probability that there are exactly $m$ customers each of which (denoted $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

Notice that there may be more than one customer in $Q_k$ ($Q_k \neq Q_j$) satisfying the condition $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$ (see the figure below).

(3) Combine problems (1) and (2):
Given two different $M/M/1$ queues $Q_i$ and $Q_j$ and a customer $c$ served by $Q_i$, let $c'$ be the customer served by $Q_j$ satisfying $c_{.st} \in [c'_{.st}, c'_{.ft}]$ (i.e., $c$ starts during the service interval of $c'$).
The set of customers that finishes before $c$ starts is denoted by $c^{\prec} = \{c'': c''_{.ft} \le c_{.st} \}$.
What is the probability that there are exactly $k$ customers in $c^{\prec}$ each of which (denoted by $c''$) finishes during the service interval of $c'$ (i.e., $c''_{.ft} \in [c'_{.st}, c'_{.ft}]$)?

parallelmm1_threeproblems http://i1.tietuku.com/5eeddcb2557fb93c.png

In addition, are such concurrency-related problems are the typical ones studied in the literature on queueing theory? Any references related to similar problems are also well appreciated.

Answer 1

Let $Y(t)=(X^{(1)}(t), X^{(2)}(t))$ be the vector of the number of customers in queues $1$ and $2$ at time $t$. Then, $Y(t)$ is a Continuous Time Markov chain with four states $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$. The stationary distribution of this chain is: \begin{align*} \mathbb{P}(Y(\infty) = (0,1)) = \frac{\lambda}{\mu+\lambda}\frac{\mu}{\mu+\lambda} =: \pi_{0,1} \\ \mathbb{P}(Y(\infty) = (1,0)) = \frac{\lambda}{\mu+\lambda}\frac{\mu}{\mu+\lambda} =: \pi_{1,0} \\ \mathbb{P}(Y(\infty) = (1,1)) = \frac{\lambda}{\mu+\lambda}\frac{\lambda}{\mu+\lambda} =: \pi_{1,1} \end{align*}

For your first question, using the Poisson Arrivals See Time Averages (PASTA) property of arrivals, the probability that a customer starts during the service period of another customer is the probability that one queue is empty and the other is full which is $$ \frac{1}{2}(\pi_{1,0} + \pi_{0,1}) $$.

For the second question, first condition on whether the customer which starts at $c_{st}$ (called the tagged customer) sees the other queue as empty or not. If it sees the other queue empty, then the number of departures, $D$, during its service interval, will have the distribution: $$ \mathbb{P}(D = m) = P\left(\sum_{i=1}^m (A_i + S_i) < Z < \sum_{i=1}^{m+1} (A_i + S_i) \right), $$ where $A_i$ are i.i.d. $exponential(\lambda)$ random variables corresponding to the inter-arrival times of customers in the other queue, $S_i$ are i.i.d. $exponential(\mu)$ corresponding to the service times of these customers, and $Z$ is $exponential(\mu)$ is the service time of the tagged customer. The probability of the case when tagged customer sees the other queue busy can also be written in a similar way.