4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note: This problem is related with that in Probabilistic model of parallel web servers in Mathematics. The difference is that I have tried to express in term of queueing theory in a more precise way. In addition, more details about the background of the model are abstracted in this post. $\endgroup$
    – hengxin
    Apr 20, 2014 at 14:36

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @Hengxin : The question appears in math.stackexchange as well. Please provide a link to that question. I did not post this under the question because I do not have sufficient reputation points. $\endgroup$
    – user137846
    Apr 20, 2014 at 14:25
  • $\begingroup$ Thanks. According to your suggestion, I have provided a link (and some explanations on the differences) to that question in math.stackexchange in the comment to this post. I have to spend some time (one day or two) understanding your answer before making any comments or accepting it. Thanks again. $\endgroup$
    – hengxin
    Apr 20, 2014 at 14:51
  • $\begingroup$ Unfortunately, I realized that the queueing model I gave two days ago was a little misleading: The requirement if there is some customer in service, no more customers can enter it is not what I really want, and I have modified it to that the customer joins the queue if the server is busy. I am trying to figure out whether your approach is still feasible. In addition, a third problem is added. Thanks for your efforts. $\endgroup$
    – hengxin
    Apr 24, 2014 at 14:32
  • $\begingroup$ After a 2-week learning of basic queue theory, I tend to think that your approach to the original model is not feasible in the new one since the PASTA property talks about arrival times instead of served times. What do you think? In addition, if we are keeping to the original model (i.e., if there is some customer in service, no more customers can enter it), how to solve the third problem (i.e., What is the probability that there are exactly $k$ customers in $c^{\prec}$ each of which finishes during the service interval of $c′$)? Any suggestions? Thanks. $\endgroup$
    – hengxin
    May 5, 2014 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.