Network of Queues��Reversibility & Burke Theorem�Jackson Networks (Classed or not)�Closed Networks & Mean Value Analysis
REVERSIBILITY & BURKE THEOREM
2
Network of Queues
3
μ1
μ2
λ
0,0
1,0
0,1
1,1
b,1
λ
λ
μ1
μ1
μ2
μ2
μ2
Network of Queues
4
μ1
μ2
λ
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
μ
μ
μ
λ
λ
λ
μ
μ
μ
λ
λ
λ
λ
μ
μ
μ
μ
μ
μ
μ
μ
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
μ
μ
μ
λ
λ
λ
μ
μ
μ
λ
λ
λ
λ
μ
μ
μ
μ
μ
μ
μ
μ
Network of Queues�(Open System – 3)
7
Network of Queues�(Closed System – 1)
8
μ
μ
N
0,N
1,N-1
2,N-2
N-1,1
μ
μ
μ
μ
μ
μ
N,0
μ
μ
μ
μ
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
For Any Network of k Queues
10
Network of Queues
11
Developing a “General” Solution
12
Quickly Revisiting Reversible CTMCs
13
Burke’s Theorem
14
Poisson Departures in M/M/1�(Partial “Brute-Force” Derivation)
15
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
Revisiting our Tandem Network Example
17
μ2
λ
μ1
ρ1 = λ/μ1
ρ2 = λ/μ2
Generalization to Acyclic Networks�(with probabilistic routing)
18
μ2
Poisson(λ)
μ1
μ3
μ4
μ5
Limit of Burke’s Theorem
Only holds for acyclic networks
Jackson’s Theorem addresses this limitation
19
The Case of Cyclic Networks
The independent increment property is clearly not valid (probability of another arrival is much higher just following an arrival
20
μ
fast
0.99
0.01
Poisson(λ≈0)
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μ
JACKSON NETWORKS
22
Jackson Networks
23
An Open Network Example
24
Poisson(ri)
Server i
Server j
Server k
Poisson(rj)
Poisson(rk)
Pij
Pik
Pki
Pi,out
Pj,out
A Closed Network Example
25
Server i
Server j
Server k
Pij
Pik
Pki
N jobs
26
Rate leaving (n1,n2,…,nk)
Rate entering (n1,n2,…,nk)
=
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
Local Balance Equations for 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’
Jackson Networks – Main Results
29
Jackson Networks – Notes
30
Open Network Example
⇒ ⇒
31
μ1
1–p
p
Poisson(λ)
μ2
I/O
CPU
Closed Network Example
32
μ1=5
0.5
μ2=4
0.4
0.5
0.6
N = 2
Another Closed Network Example
33
μ1=4
0.5
μ4=4
0.5
N = 10
μ2=2
μ3=2
(OPEN) CLASSED NETWORKS
34
Open Classed Networks – Definition
35
Open Classed Networks – State
36
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
Open Classed Networks – State
38
Aggregate State Probabilities�(at a queue)
39
Two Classes Example – (2)
40
Two Classes Example – (3)
41
Prob. s type 2 jobs given ni jobs
Mean of Binomial(ni ,p2)
Prob ni jobs
CPU & I/O Bound�Jobs (18.6.3*)
⇒ λ1C = 0.2 + 0.65λ1C + λ2C
⇒ λ2I = 0.25 + 0.95λ1I + 0.5λ2I
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
CLOSED NETWORKS & MVA
43
Back to Closed Networks
44
Arrival Theorem
Note that E[Tj(M)] is the expected response time for a single visit to queue j
45
Mean Value Analysis – Recursion
46
Mean Value Analysis – Recursion
47
Simple MVA Example
48
μ=1
M = 3
2μ
More on MVA
49
μ=1
M
2μ