Queueing models

[CTK]

TL;DR Summary

What is the generator matrix for the following two different Queueing models?

Hello there,

If we have M/M/C/K = M/M/2/2 (where note that the first M stands for memoryless arrival times for the packets (thus described by a Poisson process(lambda)), the second M stands for memoryless service times (i.e. described by an exponentially distributed(mu)), the number 2 for C means that there are two servers handling the packets and the number 2 for K is the maximum size of the queue, which is 2. Note that arrivals to a full queue are simply rejected.

What is the generator matrix (Q) for a system of M/M/2/2? What about for M/M/2/4?

My attempt: I know what is it for M/M/2/4 given that K > C (just included it to explain what I am exactly after), but is there any way to have a canonical form of the generator matrix for M/M/C/C such as M/M/2/2? Any help would be appreciate it.



Thanks for your help in advance

 

[pbuk]

I know what is it for M/M/2/4.

Can you show what this is? I don't understand why you have a difficulty using the same logic for M/M/2/2.

 

[CTK]

Can you show what this is? I don't understand why you have a difficulty using the same logic for M/M/2/2.

So for M/M/2/4 it is simply Erlang-C model because c is not equal to k (I have attached a picture of that, which is just from Wikipedia). But when we are dealing with M/M/2/2 then here c = k, so we are dealing with Erlang-B model, and I couldn't find anything about Erlang-B model's canonical form matrix anywhere. So any help would be appreciate it.

 

[CTK]

So for M/M/2/4 it is simply Erlang-C model because c is not equal to k (I have attached a picture of that, which is just from Wikipedia). But when we are dealing with M/M/2/2 then here c = k, so we are dealing with Erlang-B model, and I couldn't find anything about Erlang-B model's canonical form matrix anywhere. So any help would be appreciate it.

And just to give you more context. This is the problem that I am trying to solve:

A system comprises two single-server queues (X(t) : t ≥ 0) and (Y (t) : t ≥ 0), each with capacity K = 2 (i.e. the number of customers in each system is either 0, 1 or 2). Each queue has customers arriving according to a Poisson process with rate λ, independently of the other queue and of past history. When a queue is at full capacity, arrivals to that queue are turned away and do not return, and nor do they join the other queue. Service times are mutually independent within and between queues, and they are independent of the arrival processes and of past history. Service times for each queue are Exp(µ) random variables. The state of the system at time t is represented by the vector (X(t), Y (t)). Suppose that the queues are both at full capacity initially (i.e. X(0), Y (0) = (2, 2)).
We are interested in the expected time until either one of the two servers becomes idle: that is, the expected time until the system first reaches one of the states A = {(0, 0), (0, 1), (0, 2), (1, 0), (2, 0)}.
Also, label the states (1, 1), (1, 2), (2, 1), (2, 2) as 1, 2, 3, 4 respectively.

(a) Determine ri , for each of the states i = 1, 2, 3, 4, and write down the matrix RA = (ri,j : i, j = 1, 2, 3, 4).

If you could help me with this one, then I would really appreciate it, because it is such a struggle, thanks.

 

[pbuk]

• How many rows does the M/M/2/2 matrix have?
• Do you think there is any reason the first, second and third rows should be different from the one in Wikipedia?
• What do you think the last row should look like?

 

[CTK]

• How many rows does the M/M/2/2 matrix have?
• Do you think there is any reason the first, second and third rows should be different from the one in Wikipedia?
• What do you think the last row should look like?

1-) Would the matrix just be 4x4?
2-) In my opinion, all of the matrix in Wikipedia should still be exactly the same for all of the rows even if k = c, is that correct?
3-) I think it would still look like the same, am I right?

 

[CTK]

And just to give you more context. This is the problem that I am trying to solve:

A system comprises two single-server queues (X(t) : t ≥ 0) and (Y (t) : t ≥ 0), each with capacity K = 2 (i.e. the number of customers in each system is either 0, 1 or 2). Each queue has customers arriving according to a Poisson process with rate λ, independently of the other queue and of past history. When a queue is at full capacity, arrivals to that queue are turned away and do not return, and nor do they join the other queue. Service times are mutually independent within and between queues, and they are independent of the arrival processes and of past history. Service times for each queue are Exp(µ) random variables. The state of the system at time t is represented by the vector (X(t), Y (t)). Suppose that the queues are both at full capacity initially (i.e. X(0), Y (0) = (2, 2)).
We are interested in the expected time until either one of the two servers becomes idle: that is, the expected time until the system first reaches one of the states A = {(0, 0), (0, 1), (0, 2), (1, 0), (2, 0)}.
Also, label the states (1, 1), (1, 2), (2, 1), (2, 2) as 1, 2, 3, 4 respectively.

(a) Determine ri , for each of the states i = 1, 2, 3, 4, and write down the matrix RA = (ri,j : i, j = 1, 2, 3, 4).

If you could help me with this one, then I would really appreciate it, because it is such a struggle, thanks.

Ok I think I am confusing myself here. Just to double check, is this problem about M/M/2/2 or M/M/2/4?

 

[pbuk]

1-) Would the matrix just be 4x4?
2-) In my opinion, all of the matrix in Wikipedia should still be exactly the same for all of the rows even if k = c, is that correct?
3-) I think it would still look like the same, am I right?

Edit: this is wrong, I will replace with another post.
1 - Yes
2 - The first two rows are the same, but the coefficient of 3 in the third row assumes 3 servers so cannot be right.
3 - Yes

 

[pbuk]

Ok I think I am confusing myself here. Just to double check, is this problem about M/M/2/2 or M/M/2/4?

Neither. It is about two independent M/M/1/2 queues.

 

[CTK]

1 - Yes
2 - The first two rows are the same, but the coefficient of 3 in the third row assumes 3 servers so cannot be right.
3 - Yes

2-) But the coefficient of 3 doesn't take place in the third row, but fourth row.

 

[CTK]

Neither. It is about two independent M/M/1/2 queues.

oh ok! So how can I combine them both in one matrix then?

 

[pbuk]

1-) Would the matrix just be 4x4?

2-) In my opinion, all of the matrix in Wikipedia should still be exactly the same for all of the rows even if k = c, is that correct?
3-) I think it would still look like the same, am I right?

Sorry, I gave wrong answers to this before.
1-) No, there are five states (with ${0, 1, 2, 3 \text{ or } 4}$ customers in the system).
2-) No, there are only $c$ processors so the maximum coefficient of $\mu$ appearing in the matrix must be $c$.
3-) Yes, the last row is the same.

oh ok! So how can I combine them both in one matrix then?

You can't, you need to work from first principles.

What is the transition rate from state 1 (1, 1) to state 2 (1, 2)?

Where did this question come from by the way?

 

[CTK]

1-) Would the matrix just be 4x4?

Sorry, I gave wrong answers to this before.
1-) No, there are five states (with ${0, 1, 2, 3 \text{or} 4}$ customers in the system).
2-) No, there are only $c$ processors so the maximum coefficient of $\mu$ appearing in the matrix must be $c$.
3-) Yes, the last row is the same.


You can't, you need to work from first principles.

What is the transition rate from state 1 (1, 1) to state 2 (1, 2)?

Where did this question come from by the way?

Thanks for the correction.
The question comes from one of my statistics and probability units from uni, it's about markov chains and processes.
So from (1,1) to (1,2), is it just \lambda?
And I will tell you for the rest and please let me know if I am wrong?
(1,1) to (2,1) is \lambda as well because we only have an increase of one customer?
(1,1) to (2,2) is 2\lambda because we have an increase of two customers?
(1,2) to (1,1) is \mu because it is the death (by death I mean has been served) of one customer?
(1,2) to (1,2) is zero?
(1,2) to (2,1) is \lambda * \mu?
(1,2) to (2,2) is \lambda?
(2,1) to (1,1) is \mu?
(2,1) to (1,2) is \mu * \lambda?
(2,1) to (2,2) is \lambda?
(2,2) to (1,1) is 2 * \mu?
(2,2) to (1,2) is \mu?
(2,2) to (2,1) = \mu?
(2,2) to (2,2) is just zero?

I would really appreciate it if you could check me and correct me if I am wrong?

Thank you very much.

 

[pbuk]

The question comes from one of my statistics and probability units from uni, it's about markov chains and processes.

Thanks for this information.

So from (1,1) to (1,2), is it lambda(mu + 2)?

Do you think it makes sense to multiply two rates together?

We are looking at the transition rate from state 1 (1, 1) to state 2 (1, 2): this is simply the rate of arrivals in queue 2 i.e. $\lambda$. So $r_{1,2} = \lambda$.

What about $r_{1,3}$?

And $r_{1,4}$?

Spoiler: hint

Is it possible for people to arrive at two independent queues at exactly the same time?[/hint]

 

[CTK]

Thanks for this information.


Do you think it makes sense to multiply two rates together?

We are looking at the transition rate from state 1 (1, 1) to state 2 (1, 2): this is simply the rate of arrivals in queue 2 i.e. $\lambda$. So $r_{1,2} = \lambda$.

What about $r_{1,3}$?

And $r_{1,4}$?

Spoiler: hint

Is it possible for people to arrive at two independent queues at exactly the same time?[/hint]

So the reason I was multiplying both rates is because for (1,1) to (1,2) we could have a scenario for server 1 to have served one customer and a new customer has come (so that's $\mu * \lambda$) and for server 2, we have one customer has arrived OR one customer has been served and 2 arrived (so that's 2 * $\mu * \lambda$ + $\lambda$)...so $r_{1,2} = (2 * \lambda * \mu) * (1+ \lambda)$.
But it seems I have been thinking about it incorrectly.

So in this case, would we have the following scenarios:

$r_{1,1} = 0$ because 2 things can't happen simultaneously\
$r_{1,2} = \lambda$
$r_{1,3} = \lambda$
$r_{1,4} = 0$ because we can't have a situation where two customers arriving at two independent queues at exactly the same time

$r_{2,1} = \mu$.
$r_{2,2} = 0$.
$r_{2,3} = \lambda * \mu$ because we have an increase in one server and a decrease in another server (or is it 0 because we can't have 1 customer being served in one server and another one just arrived at another server, both at the exact same time?)
$r_{2,4} = \lambda$.

$r_{3,1} = \mu$.
$r_{3,2} = 0$ because 2 things can't happen simultaneously
$r_{3,3} = 0$
$r_{3,4} = \lambda$.

$r_{4,1} = 0$ because 2 things can't happen simultaneously
$r_{4,2} = \mu$
$r_{4,3} = \mu$
$r_{4,4} = 0$

Is that correct?

 

[pbuk]

So in this case, would we have the following scenarios:

It's pretty close! I'll start at the end...

$r_{4,1} = 0$ because 2 things can't happen simultaneously
$r_{4,2} = \mu$
$r_{4,3} = \mu$

All good, but $r_{4,4}$ is not zero, it is the (negative) rate of transition from state 4 to other states so $r_{4,4} = \Sigma_{j \ne 4} r_{4,j} = -2 \mu$.

$r_{3,1} = \mu$.
$r_{3,2} = 0$ because 2 things can't happen simultaneously
$r_{3,3} = 0$
$r_{3,4} = \lambda$.

Good except for $r_{3,3}$ as above.

$r_{2,1} = \mu$.
$r_{2,2} = 0$.
$r_{2,3} = \lambda * \mu$ because we have an increase in one server and a decrease in another server (or is it 0 because we can't have 1 customer being served in one server and another one just arrived at another server, both at the exact same time?)
$r_{2,4} = \lambda$.

$r_{2,3} = 0$ as per your second argument as for $r_{3,2}$. $r_{2,2}$ again makes the row sum to zero.

$r_{1,2} = \lambda$
$r_{1,3} = \lambda$
$r_{1,4} = 0$ because we can't have a situation where two customers arriving at two independent queues at exactly the same time

These are good, but $r_{1,1}$ is troublesome. If we follow the rule that rows must sum to 0 then it should be $-2 \lambda$, but note that it is also possible to transition from (1,1) to (0,1) or (1,0), and I think you will have to take account of these as well in order to answer the rest of the question (I don't see how you can get the time to the first idle state otherwise).

Oh, I have seen a problem - it is also possible to transition from (1,2) (state 2) to (0,2) so perhaps $r_{2,2} = -(\lambda + \mu)$, and the same for $r_{3,3}$? This is not how transition matrices normally work (we normally include all states) so I think you will have to try this and see how it goes.

 

[CTK]

It's pretty close! I'll start at the end...


All good, but $r_{4,4}$ is not zero, it is the (negative) rate of transition from state 4 to other states so $r_{4,4} = \Sigma_{j \ne 4} r_{4,j} = -2 \mu$.


Good except for $r_{3,3}$ as above.


$r_{2,3} = 0$ as per your second argument as for $r_{3,2}$. $r_{2,2}$ again makes the row sum to zero.


These are good, but $r_{1,1}$ is troublesome. If we follow the rule that rows must sum to 0 then it should be $-2 \lambda$, but note that it is also possible to transition from (1,1) to (0,1) or (1,0), and I think you will have to take account of these as well in order to answer the rest of the question (I don't see how you can get the time to the first idle state otherwise).

Oh, I have seen a problem - it is also possible to transition from (1,2) (state 2) to (0,2) so perhaps $r_{2,2} = -(\lambda + \mu)$, and the same for $r_{3,3}$? This is not how transition matrices normally work (we normally include all states) so I think you will have to try this and see how it goes.

Firstly, thanks for your help, you are a very helpful person
Secondly, I think we don't need to worry about (1,0), etc. according to the question.
Thirdly, I think r{2,2} should be $-(\lambda + \mu)$ anyway to make the row sum up to zero, even if there is no transition from (1,2) to (0,2).
Lastly, for $r_{i}$; where $i = 1,2,3,4$, is it the following:

$r_{1}$ is a transition from (2,2) to (1,1), so it is equal to 0 because we can't have 2 things happening simultaneously in 2 different servers?
$r_{2}$ is a transition from (2,2) to (1,2), so it is equal to $\mu$?
$r_{3}$ is a transition from (2,2) to ( 2,1), so is it equal to $\mu$ as well?
$r_{4}$ is a transition from (2,2) to (2,2), so is it equal to $-2\mu$?

 

[pbuk]

Lastly, for $r_{i}$; where $i = 1,2,3,4$, is it the following:

$r_{1}$ is a transition from (2,2) to (1,1), so it is equal to 0 because we can't have 2 things happening simultaneously in 2 different servers?
$r_{2}$ is a transition from (2,2) to (1,2), so it is equal to $\mu$?
$r_{3}$ is a transition from (2,2) to ( 2,1), so is it equal to $\mu$ as well?
$r_{4}$ is a transition from (2,2) to (2,2), so is it equal to $-2\mu$?

I'm not sure what you mean by $r_{i}$ but these entries are correct for $r_{4,i}$.

 

[CTK]

I'm not sure what you mean by $r_{i}$ but these entries are correct for $r_{4,i}$.

yeah it's for $r_{4,i}$ cheers.