1 of 32

Matrix Analytic Techniques

1

2 of 32

General Distributions

  • Recall the exponential distribution Exp(μ): E[X] = 1/μ and Var(X) = 1/μ2
    • The coefficient of variation C2 =Var(X)/E[X]2 = 1
  • We can combine exponential random variables in series an in parallel
    • Series of k (identical) exponential random variables Exp(kμ) has Ck2 = 1/k (Erlang-k distribution)
      • Can be generalized to use different exponential random variables
    • Parallel combination of Exp(μ1) and Exp(μ2) with probabilities p and (1–p), respectively (two-phase Hyper-exponential distribution) has CH2 > 1 for μ1 ≠ μ2
    • Phase-type (PH) distributions: Arbitrary combination in series and parallel (plus absorbing state)
      • Can approximate any non-negative distribution arbitrarily closely using a phase-type distribution
    • Coxian distributions: Series of exponentials with arbitrary probability of exiting at each stage
      • Also “dense” in the class of non-negative distributions
  • They all involve combinations of exponential stages, so they still give rise to Markov chains (more details on what this means soon)
  • Can we leverage their structure to solve the corresponding Markov chains?

2

3 of 32

Two-Stage Coxian Distribution Example

  •  

3

μ1

μ2

p

1–p

4 of 32

Note

  •  

4

5 of 32

Solving Queues with Coxian/Phase-type Service Time Distributions

  • Basic idea is to use a state representation that includes the phase of the job in service
    • πi,j is probability that there are i jobs in the system (or the queue), and the job in service, if any, is in the jth phase of its service time
  • Because each phase is exponentially distributed (and arrivals are Poisson), we can still represent the system evolution using a Markov chain

5

6 of 32

Similar Approach for Arrival Processes That Preserve The Markov Property

  • Coxian (rather than exponential) inter-arrival times
    • Non-Poisson arrival process, but random sequence of exponential times
    • System state (i,j) tracks number i of jobs in the system, and phase j of the arrival process (time to the next job arrival). System state still evolves according to a Markov chain
  • Markov-modulated Poisson process (MMPP)
    • Arrival process is Poisson, but with rate that varies according to an underlying Markov chain
    • System state (i,j) tracks number i of jobs in the system, and the state j of the chain driving the arrival process (Poisson with rate λj). System state again evolves according to Markov chain

6

7 of 32

The M/E2/1 Queue as an Example

  • Poisson arrivals of rate λ
  • Service time with two exponential stages in series: Exp(μ1) and Exp(μ2) – (Coxian with p = 1)
  • Markov chain (i,j) includes service phase
    • i is number in the queue, and j is phase of job in service

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

8 of 32

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

λ

λ

λ

9 of 32

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

λ

λ

λ

10 of 32

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

λ

λ

λ

11 of 32

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

12 of 32

Matrix Analytic Methods

  • Numerical in nature for any Markov chain that
    • Is unbounded in at most one dimension (typically #jobs), and
    • With a structure that repeats after some point
      • Non-exponential service times, e.g., Coxian, hyper-exponential, phase-type
      • Non-Poisson arrivals, e.g., E2/M/1 and Mt/M/1 chains (see Sections 21.2 & 21.4)

​

  • Solution is based on “guessing” that πi+1 = πi⋅R (after some initial transient phase), where πi is the state probability vector for “level” i in the unbounded dimension, and R is a matrix that can be computed iteratively (more on this in a minute)
    • Convergence is usually fast
    • Accurate except for high C2 values (unbalanced)

12

13 of 32

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

14 of 32

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

15 of 32

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

​

=

16 of 32

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

17 of 32

Matrix Balance Equations�(for M/E2/1 Queue – Option 1)

  • Matrix balance equation π⋅Q = 0

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

  • Guessing a solution of the form

πM+i = πM⋅Ri, i ≥ 0, for some M

  • Given choices for⋅L0, B0, F0, and π0, M = 1, so πi = π1⋅Ri-1, i ≥ 1,

“Regular” structure starts at M = 1, (it starts at M = 0 for the time-varying load example of Sec. 21.4)

  • Using πi+1 = πi⋅R, i ≥ 1, in the recursive part of the balance equations gives

0 = π1⋅F + π1⋅RL + π1⋅R2B

0 = π2⋅F + π2⋅RL + π2⋅R2B

  • Hence, 0 = F + RL + R2B or

R = – (R2B + F)L –1

​

  • Solving for R is then based on the following recursion

Rn+1 = – (Rn2B + F)L–1

  • Start with R = 0 or some other guess and stop when ||Rn+1– Rn|| ≤ ε, where usually ||M|| = ||M||∞ = max{mij}

​

17

(initial)

(recursive)

18 of 32

Why is F + RL + R2B = 0?

  • Recursive balance equations give

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

19 of 32

Finding π0 and π1 – Option 1

  •  

19

 

20 of 32

Deriving π0⋅1+π1(I – R)–1⋅1 = 1

  • π⋅1 =1 gives π0⋅1 + Σi=1 πi⋅1 = 1
  • π0⋅1 + Σi=1 π1Ri-1⋅1 = 1 (because πi = π1⋅Ri-1, i ≥ 1)

π0⋅1 + π1(Σi=0 Ri)⋅1 = 1

π0⋅1 + π1(I – R)–1⋅1 = 1

​

​

​

20

21 of 32

Performance Metrics

  •  

21

22 of 32

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

23 of 32

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

24 of 32

Matrix Balance Equations�(for M/E2/1 Queue)

  • Matrix balance equation π⋅Q = 0

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

  • Guessing a solution of the form

πM+i = πM⋅Ri, i ≥ 0, for some M

  • Given choices for⋅L0, B0, F0, and π0,0, M = 0, so πi = π0⋅Ri, i ≥ 0

“Regular” structure now starts at M = 0 rather than M = 1 under option 1

  • Using πi+1 = πi⋅R, i ≥ 0, in the recursive part of the balance equations gives

0 = π0⋅F + π0⋅RL + π0⋅R2B

0 = π1⋅F + π1⋅RL + π1⋅R2B

  • Hence, 0 = F + RL + R2B or

R = – (R2B + F)L –1 as before

​

  • Solving for R is again based on the following recursion

Rn+1 = – (Rn2B + F)L–1

  • Start with R = 0 or some other guess and stop when ||Rn+1– Rn|| ≤ ε, where usually ||M|| = ||M||∞ = max{mij}

​

24

(initial)

(recursive)

25 of 32

Why is F + RL + R2B = 0?

  • Recursive balance equations give

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

26 of 32

Finding π0,0 and π0 – Option 2

  •  

26

 

27 of 32

Deriving π0,0+π0(I – R)–1⋅1 = 1

  • π⋅1 =1 gives π0,0 + Σi=0 πi⋅1 = 1
  • π0,0 + Σi=0 π0Ri⋅1 = 1 (because πi = π0⋅Ri, i ≥ 0)

π0,0 + π0(Σi=0 Ri)⋅1 = 1

π0,0 + π0(I – R)–1⋅1 = 1

​

​

​

27

28 of 32

Performance Metrics

  •  

28

29 of 32

The Mt/M/1 Queue

  •  

29

0H

0L

 

 

 

μ

μ

1H

1L

μ

μ

2H

2L

μ

μ

3H

3L

 

 

 

 

 

 

 

 

 

 

 

30 of 32

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

​

=

 

31 of 32

Balance Equations

31

 

32 of 32

Performance Metrics for Mt/M/1

  •  

32