Matrix Analytic Techniques
1
General Distributions
2
Two-Stage Coxian Distribution Example
3
μ1
μ2
p
1–p
Note
4
Solving Queues with Coxian/Phase-type Service Time Distributions
5
Similar Approach for Arrival Processes That Preserve The Markov Property
6
The M/E2/1 Queue as an Example
7
0,1
0,2
0,0
μ2
1,2
2,2
1,1
2,1
λ
λ
λ
λ
μ1
μ1
μ1
μ2
μ2
μ2
λ
λ
λ
μ1
μ2
p=1
Balance Equations – (1)
8
0,1
0,2
0,0
μ2
1,2
2,2
1,1
2,1
λ
λ
λ
λ
μ1
μ1
μ1
μ2
μ2
μ2
λ
λ
λ
Balance Equations – (2)
9
0,1
0,2
0,0
μ2
1,2
2,2
1,1
2,1
λ
λ
λ
λ
μ1
μ1
μ1
μ2
μ2
μ2
λ
λ
λ
Balance Equations – (3)
10
0,1
0,2
0,0
μ2
1,2
2,2
1,1
2,1
λ
λ
λ
λ
μ1
μ1
μ1
μ2
μ2
μ2
λ
λ
λ
Balance Equations & Generator Matrix
11
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | 3,1 | 3,2 |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | 0 | 0 |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | 0 | 0 |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | 0 | 0 |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ |
3,1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 |
3,2 | 0 | 0 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 |
Matrix Analytic Methods
12
Choosing Initial States & Levels
13
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | … |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | … |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | … |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | … |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | … |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | … |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | … |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | … |
… | … | … | … | … | … | … | … | … |
initial
level
level
initial
level
level
level
Generator Matrix Q for M/E2/1 Queue �Two Possible Decompositions
14
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | 3,1 | 3,2 |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | 0 | 0 |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | 0 | 0 |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | 0 | 0 |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ |
3,1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 |
3,2 | 0 | 0 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 |
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | 3,1 | 3,2 |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | 0 | 0 |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | 0 | 0 |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | 0 | 0 |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ |
3,1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 |
3,2 | 0 | 0 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 |
Option 1
15
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | 3,1 | 3,2 |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | 0 | 0 |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | 0 | 0 |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | 0 | 0 |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ |
3,1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 |
3,2 | 0 | 0 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 |
| 3 | 2 | 2 | 2 | 2 |
3 | L0 | F0 | 0 | 0 | 0 |
2 | B0 | L | F | 0 | 0 |
2 | 0 | B | L | F | 0 |
2 | 0 | 0 | B | L | F |
2 | 0 | 0 | 0 | B | |
=
Balance Equations: πQ = 0
16
| 3 | 2 | 2 | 2 | 2 |
3 | L0 | F0 | 0 | 0 | 0 |
2 | B0 | L | F | 0 | 0 |
2 | 0 | B | L | F | 0 |
2 | 0 | 0 | B | L | F |
2 | 0 | 0 | 0 | B | |
π = [π(0,0),π(0,1),π(0,2),π(1,1),π(1,2), …,π(i,1),π(i,2), …]
π
π0
π1
πi
π0⋅L0 + π1⋅B0
π0⋅F0 + π1⋅L + π2⋅B
π1⋅F + π2⋅L + π3⋅B
πi⋅F + πi+1⋅L + πi+2⋅B
=
= 0
Matrix Balance Equations�(for M/E2/1 Queue – Option 1)
0 = π0⋅L0 + π1⋅B0
0 = π0⋅F0 + π1⋅L + π2⋅B
0 = π1⋅F + π2⋅L + π3⋅B
0 = π2⋅F + π3⋅L + π4⋅B
πM+i = πM⋅Ri, i ≥ 0, for some M
“Regular” structure starts at M = 1, (it starts at M = 0 for the time-varying load example of Sec. 21.4)
0 = π1⋅F + π1⋅RL + π1⋅R2B
0 = π2⋅F + π2⋅RL + π2⋅R2B
R = – (R2B + F)L –1
Rn+1 = – (Rn2B + F)L–1
17
(initial)
(recursive)
Why is F + RL + R2B = 0?
0 = π1⋅F + π1⋅RL + π1⋅R2B ⇒ π1(F + RL + R2B) = 0
0 = π2⋅F + π2⋅RL + π2⋅R2B ⇒ π2(F + RL + R2B) = 0
0 = π3⋅F + π3⋅RL + π3⋅R2B ⇒ π3(F + RL + R2B) = 0
which implies that F + RL + R2B = 0
18
Finding π0 and π1 – Option 1
19
Deriving π0⋅1+π1(I – R)–1⋅1 = 1
π0⋅1 + π1(Σi=0 Ri)⋅1 = 1
π0⋅1 + π1(I – R)–1⋅1 = 1
20
Performance Metrics
21
Option 2
22
| 1 | 2 | 2 | 2 | 2 |
1 | L0 | F0 | 0 | 0 | 0 |
2 | B0 | L | F | 0 | 0 |
2 | 0 | B | L | F | 0 |
2 | 0 | 0 | B | L | F |
2 | 0 | 0 | 0 | B | |
=
| 0,0 | 0,1 | 0,2 | 1,1 | 1,2 | 2,1 | 2,2 | 3,1 | 3,2 |
0,0 | -λ | λ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0,1 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 | 0 | 0 |
0,2 | μ2 | 0 | -a2 | 0 | λ | 0 | 0 | 0 | 0 |
1,1 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 | 0 | 0 |
1,2 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ | 0 | 0 |
2,1 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 | λ | 0 |
2,2 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 | 0 | λ |
3,1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -a1 | μ1 |
3,2 | 0 | 0 | 0 | 0 | 0 | μ2 | 0 | 0 | -a2 |
Balance Equations: πQ = 0
23
| 1 | 2 | 2 | 2 | 2 |
1 | L0 | F0 | 0 | 0 | 0 |
2 | B0 | L | F | 0 | 0 |
2 | 0 | B | L | F | 0 |
2 | 0 | 0 | B | L | F |
2 | 0 | 0 | 0 | B | |
π = [π(0,0),π(0,1),π(0,2),π(1,1),π(1,2), …,π(i,1),π(i,2), …]
π
π0
π1
πi
π0,0⋅L0 + π0⋅B0
π0,0⋅F0 + π0⋅L + π1⋅B
π0⋅F + π1⋅L + π2⋅B
πi⋅F + πi+1⋅L + πi+2⋅B
=
= 0
Matrix Balance Equations�(for M/E2/1 Queue)
0 = π0,0⋅L0 + π0⋅B0
0 = π0,0⋅F0 + π0⋅L + π1⋅B
0 = π0⋅F + π1⋅L + π2⋅B
0 = π1⋅F + π2⋅L + π3⋅B
πM+i = πM⋅Ri, i ≥ 0, for some M
“Regular” structure now starts at M = 0 rather than M = 1 under option 1
0 = π0⋅F + π0⋅RL + π0⋅R2B
0 = π1⋅F + π1⋅RL + π1⋅R2B
R = – (R2B + F)L –1 as before
Rn+1 = – (Rn2B + F)L–1
24
(initial)
(recursive)
Why is F + RL + R2B = 0?
0 = π0⋅F + π0⋅RL + π0⋅R2B ⇒ π0(F + RL + R2B) = 0
0 = π1⋅F + π1⋅RL + π1⋅R2B ⇒ π1(F + RL + R2B) = 0
0 = π2⋅F + π2⋅RL + π2⋅R2B ⇒ π2(F + RL + R2B) = 0
which again implies that F + RL + R2B = 0
25
Finding π0,0 and π0 – Option 2
26
Deriving π0,0+π0(I – R)–1⋅1 = 1
π0,0 + π0(Σi=0 Ri)⋅1 = 1
π0,0 + π0(I – R)–1⋅1 = 1
27
Performance Metrics
28
The Mt/M/1 Queue
29
0H
0L
μ
μ
1H
1L
μ
μ
2H
2L
μ
μ
3H
3L
Matrix Q
30
| | | | | | | | |
| | | | 0 | 0 | 0 | 0 | 0 |
| | | 0 | | 0 | 0 | 0 | 0 |
| | 0 | | | | 0 | 0 | 0 |
| 0 | | | | 0 | | 0 | 0 |
| 0 | 0 | | 0 | | | | 0 |
| 0 | 0 | 0 | | | | 0 | |
| 0 | 0 | 0 | 0 | | 0 | | |
| 0 | 0 | 0 | 0 | 0 | | | |
| 2 | 2 | 2 | 2 | 2 |
2 | L0 | F | 0 | 0 | 0 |
2 | B | L | F | 0 | 0 |
2 | 0 | B | L | F | 0 |
2 | 0 | 0 | B | L | F |
2 | 0 | 0 | 0 | B | |
=
Balance Equations
31
Performance Metrics for Mt/M/1
32