1
$\begingroup$

Given a cyclic queue of two servers of exponential service rates, if there are N customers at one server at time t, how do i start about showing that N can be modeled as a birth and death process? and then find the BD rates??

Totally have no idea how to begin. what are we supposed to show to prove it can be modeled as a BD process?

$\endgroup$
10
  • 1
    $\begingroup$ Assume that at time $t$ there are $N$ customers at server $A$ and $n-N$ at server $B$. What events can happen next (there are at most two)? How much time before these happen? What state $(N,n-N)$ of the process just after that time? $\endgroup$
    – Did
    Apr 15 '12 at 8:11
  • $\begingroup$ events that can happen next will be that the arrival rate of server B will be service rate of server A and arrival rate of server A will be service rate of server B? So the time taken will be dependent on the arrival rate? State after tt time will be (n-N, N)? Still a bit confused by what it is asking for though. $\endgroup$
    – user29146
    Apr 15 '12 at 10:04
  • $\begingroup$ These are not events (and you are merely restating hypotheses). So, you have N customers at server A and n-N at server B until either ____ and then ____ or ____ and then ____. $\endgroup$
    – Did
    Apr 15 '12 at 11:22
  • $\begingroup$ hmm i dont really understand. if its a closed system, there will be N customers at server A and n-N at server B, so after that server A will be processing the N+1 customer and n-N+1 customer at server B. is this what you are referring to? $\endgroup$
    – user29146
    Apr 15 '12 at 14:42
  • $\begingroup$ If server A ends serving a customer, this one goes to server B hence the state (N,n-N) is replaced by (N-1,n-N+1) (and not what you wrote). But server B could end serving one of its customers first, in which case (N,n-N) is replaced by _____ . That is, unless N=____ or N=____, in which case only ____ can happen. Now, at which rate do the transitions from (N,n-N) to (N+1,n-N-1) and to ____ occur? $\endgroup$
    – Did
    Apr 15 '12 at 15:23
1
$\begingroup$

Suppose server 1 serves at rate $\mu_1$ and server 2 at rate $\mu_2$ and that each server can only serve a single job at a time. All other jobs at the service node are waiting.

As the system is closed and cyclic, if there are $k$ customers at node 1 we know that there are $N-k$ customers at node 2. Write $X_t$ for the number of customers at node 1 at time $t$. This can take values in $\{0,1,2,3,\ldots,N\}$.

In states $\{0,1,2,3,\ldots,N-1\}$ arrivals can happen as there are jobs at node 2 to be served. These arrivals happen at rate $\mu_2$. In state $N$ no arrivals are possible as all jobs are at node 2.

In state $0$ there can be no departures/services because all the jobs are at node 2, there are no jobs at node 1 to serve. In states $\{1,2,3,\ldots,N\}$ departures are possible (as a job completes service) and happen at rate $\mu_1$. Therefore the transition rate matrix $Q$ is (zeroes in the blanks) $$Q=\begin{pmatrix} -\mu_2 & \mu_2 \\ \mu_1 & -\mu_1 -\mu_2 & \mu_2 \\ &\mu_1 & -\mu_1 -\mu_2 & \mu_2 \\ &&\mu_1 & -\mu_1 -\mu_2 & \mu_2 \\ &&&& \ddots \\ &&&&\mu_1 & -\mu_1 -\mu_2 & \mu_2 \\ &&&&& \mu_1 & -\mu_1 \end{pmatrix}.$$

The model $X_t$ is a finite capcity M/M/1 queue. The process is a birth-death process because the transition rate matrix is a tridiagonal matrix; it has non-zero elements only on the main diagonal, on the first diagonal above this and the first below this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy