1 of 49

Network of Queues��Reversibility & Burke Theorem�Jackson Networks (Classed or not)�Closed Networks & Mean Value Analysis

2 of 49

REVERSIBILITY & BURKE THEOREM

2

3 of 49

Network of Queues

  • A basic example
    • Poisson arrivals
    • Two service facilities in tandem, no storage but station 1 can hold finished jobs if service 2 is busy
      • Service facility has 3 states:
        • Idle (0), server i serving (1), server 1 holding (b)
    • We can construct and solve a Markov chain for this system

3

μ1

μ2

λ

0,0

1,0

0,1

1,1

b,1

λ

λ

μ1

μ1

μ2

μ2

μ2

 

4 of 49

Network of Queues

  •  

4

μ1

μ2

λ

5 of 49

Network of Queues�(Open System – 1)

  •  

5

μ

μ

λ

0,0

0,1

0,2

0,3

μ

λ

1,0

1,1

1,2

1,3

μ

μ

μ

μ

μ

μ

μ

μ

λ

λ

λ

λ

2,0

2,1

2,2

2,3

μ

μ

μ

λ

λ

λ

μ

μ

μ

λ

λ

λ

λ

μ

μ

μ

μ

μ

μ

μ

μ

6 of 49

Network of Queues�(Open System – 2)

  •  

6

0,0

0,1

0,2

0,3

μ

λ

1,0

1,1

1,2

1,3

μ

μ

μ

μ

μ

μ

μ

μ

λ

λ

λ

λ

2,0

2,1

2,2

2,3

μ

μ

μ

λ

λ

λ

μ

μ

μ

λ

λ

λ

λ

μ

μ

μ

μ

μ

μ

μ

μ

7 of 49

Network of Queues�(Open System – 3)

  •  

7

8 of 49

Network of Queues�(Closed System – 1)

  •  

8

μ

μ

N

0,N

1,N-1

2,N-2

N-1,1

μ

μ

μ

μ

μ

μ

N,0

μ

μ

μ

μ

9 of 49

Network of Queues�(Closed System – 2)

  •  

9

μ2

μ1

N

0,N

1,N-1

2,N-2

N-1,1

μ2

μ2

μ2

μ1

μ1

μ1

N,0

μ2

μ1

μ2

μ1

10 of 49

For Any Network of k Queues

  •  

10

11 of 49

Network of Queues

  • We can, therefore, still represent and analyze network of queues (infinite or finite) with Markov chains
  • The challenge is that the chains are now systematically multi-dimensional
    • The number of states explodes
    • Identifying structure to make them amenable to non-numerical solutions is increasingly difficult
  • But there is clearly some structure at work, at least for certain types of chains. Can we leverage it?

​

11

12 of 49

Developing a “General” Solution

  • Guessing solutions for the balance equations, as we did
    • Is often impossible for both open and closed systems
      • Dimensionality grows with the number of queues
  • Things could be simpler if we could analyze each queue in isolation
    • Is that possible and when?
  • The answer is yes in many cases
    • We will start by establishing the result for a specific class of network of queues whose Markov chain is reversible

12

13 of 49

Quickly Revisiting Reversible CTMCs

  •  

13

14 of 49

Burke’s Theorem

  • Consider a stable M/M/k system with arrival rate λ. At steady state, the following holds
    1. The departure process is Poisson(λ) – (because of time reversibility)
    2. At all times t, the number of jobs in the system at t, N(t), is independent of the sequence of departures times prior to time t
  • Implications
    • Tandem M/M/k queues can be analyzed as a sequence of independent M/M/k queues
    • Acyclic networks of M/M/k queues with probabilistic routing can be analyzed as networks of independent M/M/k queues
      • Arrival process to each queue remains Poisson

14

15 of 49

Poisson Departures in M/M/1�(Partial “Brute-Force” Derivation)

  •  

15

16 of 49

Revisiting our Tandem Network Example

  •  

16

μ2

λ

μ1

ρ1 = λ/μ1

ρ2 = λ/μ2

0,0

0,1

0,2

0,3

μ1

λ

1,0

1,1

1,2

1,3

μ2

μ2

μ2

μ1

μ1

μ1

μ1

μ1

λ

λ

λ

λ

2,0

2,1

2,2

2,3

μ1

μ1

μ1

λ

λ

λ

μ1

μ1

μ1

λ

λ

λ

λ

μ2

μ2

μ2

μ2

μ2

μ2

μ2

μ2

17 of 49

Revisiting our Tandem Network Example

  •  

17

μ2

λ

μ1

ρ1 = λ/μ1

ρ2 = λ/μ2

18 of 49

Generalization to Acyclic Networks�(with probabilistic routing)

  •  

18

μ2

Poisson(λ)

μ1

μ3

μ4

μ5

 

 

 

 

 

19 of 49

Limit of Burke’s Theorem

Only holds for acyclic networks

​

​

Jackson’s Theorem addresses this limitation

  • Extends product form solution to cyclic networks
  • But does not extend to temporal properties or independence/Poisson properties of departures

19

20 of 49

The Case of Cyclic Networks

  • Burke’s Theorem does not hold for cyclic networks, and that includes closed networks (the arrival process is easily seen not to be Poisson)
  • Consider the following example
    • Very low external arrival rate
    • Very fast server
    • Most jobs repeat

The independent increment property is clearly not valid (probability of another arrival is much higher just following an arrival

  • Arrival process is, therefore, not Poisson
  • However, the system can still be represented by a (reversible) Markov chain (a resubmitted job is indistinguishable from a new one), so a product form may still hold

20

μ

fast

0.99

0.01

Poisson(λ≈0)

21 of 49

Markov Chain for Cyclic Network

  •  

21

μ

fast

0.99

0.01

Poisson(λ≈0)

0

1

2

3

4

λ

0.01μ

λ

λ

λ

0.01μ

0.01μ

0.01μ

λ

0.01μ

22 of 49

JACKSON NETWORKS

22

23 of 49

Jackson Networks

  • A general set of queues with infinite waiting rooms, probabilistic routing, and exponentially distributed service times
    • External arrivals, if any (open networks) are Poisson
    • Total arrival rates at individual queues are sum of external arrival rates and fraction of internal departures rates headed for that queue
  • As mentioned before, Markov chain representation is still possible even if complex (multi-dimensional state, one dimension per queue)

23

24 of 49

An Open Network Example

  •  

24

Poisson(ri)

Server i

Server j

Server k

Poisson(rj)

Poisson(rk)

Pij

Pik

Pki

Pi,out

Pj,out

25 of 49

A Closed Network Example

  •  

25

Server i

Server j

Server k

Pij

Pik

Pki

N jobs

26 of 49

 

  • Global balance equations tells us that rate of leaving state (n1,n2,…,nk) equals rate of entering it

​

​

  • But attempting a direct solution is unwieldy to say the least
    • We need to guess some additional structure

26

Rate leaving (n1,n2,…,nk)

Rate entering (n1,n2,…,nk)

=

27 of 49

 

  •  
  •  

27

Need to “guess” a solution that satisfies all balance equations!

Unwieldy in general

Breaking things down into “local” balance equations offers a possible approach

28 of 49

Local Balance Equations for Jackson Networks

  • We replace global balance equations with “local” ones, e.g., leveraging reversibility
    • The “art” is in figuring what should balance what
  • Guess solution for simpler, local, balance equations and verify that it satisfies all of them
    • Assume product form and check that it satisfies all the local balance equations
  • Approach can be extended to closed Jackson networks and classed Jackson networks

28

Rate leaving (n1,n2,…,nk)

Due to departure from

Due to outside arrival

Rate entering (n1,n2,…,nk)

Due to an arrival at

Due to outside departure

Queue 1

Queue 1

Queue 2

Queue 2

Queue k

Queue k

=

=

=

=

B

A

B1

B2

Bk

B’1

B’2

B’k

B’

A’

29 of 49

Jackson Networks – Main Results

  •  

29

30 of 49

Jackson Networks – Notes

  • Individual queues behave like M/M/* queues, but need not be (arrivals are not Poisson whenever cycles are present)
  • Individual queues behave as if they are independent even though they may not be
  • Generalization
    • Product form holds as long as the local balance equations are satisfied. This extends to Process Sharing and Last-Come-First-Served service disciplines with Coxian service times
    • Result also holds for state-dependent service rates and multiple job classes (we’ll cover this next)

30

31 of 49

Open Network Example

  • Rate equations:
    • λ1 = λ + λ2 λ1 = λ/p ρ1= λ/(pμ1)

⇒ ⇒

    • λ2 = (1–p)λ1 λ2 = λ(1–p)/p ρ2= λ(1–p)/(pμ2)
  • State probabilities
    • πn1,n2 = ρ1n1ρ2n2 (1–ρ1)(1–ρ2), n1, n2 = 0,1,2,…
  • E[N] = E[N1]+E[N2] = ρ1/(1–ρ1) + ρ2/(1–ρ2)

​

31

μ1

1–p

p

Poisson(λ)

μ2

I/O

CPU

32 of 49

Closed Network Example

  • Rate equations:
    • λ1 = 0.5λ1+ 0.4λ2 ⇒ λ2 = 4/5⋅λ1
    • λ2 = 0.5λ1 + 0.6λ2 ⇒ λ2 = 4/5⋅λ1 (only one independent equation)
    • Choose λ1 = 5 and therefore λ2 = 4, so that ρ1 = ρ2 = 1
  • State probabilities (for N = 2)
    • πn1,n2 = C ρ1n1ρ2n2 = C, where n1+n2 = 2, i.e., (0,2); (2,0); (1,1)
    • π(0,2) + π(2,0) + π(1,1) = 3C = 1 ⇒ C = 1/3

​

32

μ1=5

0.5

μ2=4

0.4

0.5

0.6

N = 2

33 of 49

Another Closed Network Example

  •  

33

μ1=4

0.5

μ4=4

0.5

N = 10

μ2=2

μ3=2

34 of 49

(OPEN) CLASSED NETWORKS

34

35 of 49

Open Classed Networks – Definition

  •  

35

36 of 49

Open Classed Networks – State

  •  

36

37 of 49

Two Classes Example – (1)�Distribution of job classes at queue i

37

 

Prob. s+t jobs at server i

Prob. s class 1 jobs and t class 2 jobs at server i, given s+t jobs at server i

38 of 49

Open Classed Networks – State

  •  

38

39 of 49

Aggregate State Probabilities�(at a queue)

  •  

39

40 of 49

Two Classes Example – (2)

  •  

40

41 of 49

Two Classes Example – (3)

  •  

41

Prob. s type 2 jobs given ni jobs

Mean of Binomial(ni ,p2)

Prob ni jobs

42 of 49

CPU & I/O Bound�Jobs (18.6.3*)

  • Rate equations:
    • λ1C = rC1+ λ1C⋅PC1,1 + λ2C⋅ PC2,1

⇒ λ1C = 0.2 + 0.65λ1C + λ2C

    • λ2C = rC2+ λ1C⋅PC1,2 + λ2C⋅ PC2,2 ⇒ λ2C = 0.05λ1C
    • λ1I = rI1+ λ1I⋅PI1,1 + λ2I⋅ PI2,1 ⇒ λ1I = 0.05λ1I+ 0.1λ2I
    • λ2I = rI2+ λ1I⋅PI1,2 + λ2I⋅ PI2,2

⇒ λ2I = 0.25 + 0.95λ1I + 0.5λ2I

  • Solving those two systems of equations yields:
    • λ1C = 2/3, λ2C = 1/30, λ1I = 5/76, λ2I = 5/8
    • λ1 = λ1C + λ1I = 0.7325, ρ1 = λ1/μ1= 0.3663
    • λ2 = λ2C + λ2I = 0.6583, ρ2 = λ2/μ2= 0.6583
  • Which immediately gives for i = 1,2
  • E[Ni] = ρi/(1–ρi) and E[Ti] = E[Ni]/λi

​

  • More interestingly, what is E[TC] or E[TI]?

​

​

42

μ1=2

μ2=1

I/O

CPU

PC1,out=0.3

PI1,2=0.95

PC1,2=0.05

PI1,1=0.05, PC1,1=0.65

rC1=0.2

rI2=0.25

PI2,2=0.5

PI2,out=0.4

PI2,1=0.1

PC2,1=1

 

* See Unit U4 practice problems for a full solution

43 of 49

CLOSED NETWORKS & MVA

43

44 of 49

Back to Closed Networks

  •  

44

45 of 49

Arrival Theorem

  • In a closed Jackson network with M > 1 jobs, an arrival to (any) server j sees a distribution of the number of jobs at server j equal to the steady-state distribution of the number of jobs at the server in the same network, but with only M – 1 jobs.
    • In a system with M jobs, the mean number of jobs an arrival sees at server j is equal to E[Nj(M – 1)]

​

  • Applying the Arrival Theorem at server j
    • E[Tj(M)] = 1/μj + E[Nj(M–1)]/μj (thanks to the memorylessness property of the exponential distribution)
  • We can then combine the Arrival Theorem and Little’s Law to derive a recursion for the mean response time at server j

​

Note that E[Tj(M)] is the expected response time for a single visit to queue j

45

46 of 49

Mean Value Analysis – Recursion

  •  

46

47 of 49

Mean Value Analysis – Recursion

  •  

47

48 of 49

Simple MVA Example

  •  

48

μ=1

M = 3

2μ

 

49 of 49

More on MVA

  •  

49

μ=1

M

2μ