close

Вход

Log in using OpenID

embedDownload
Multi-class Queues and Stochastic Networks
LNMB - 2014
Richard J. Boucherie & Werner Scheinhardt
department of Applied Mathematics
University of Twente
1
Multi-class Queues and Stochastic Networks
Detailed content:
1.  reversibility, stationarity, basic queues, output theorem, feedforward
networks
2.  partial balance, Jackson network, Kelly-Whittle netwerk, arrival
theorem
3.  quasi-reversibility, customer types, BCMP networks, bandwidth
sharing networks
4.  blocking, aggregation, decomposition
5.  loss networks, insensitivity via supplementary variables
6.  sojourn time distribution in networks
7.  MVA, AMVA, QNA
8.  fluid queues, basic models
9.  feedback fluid queues, networks of fluid queues
2
Lecure 5 : Loss networks (bandwidth sharing networks)
1  Motivation: multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary and exercises"
"
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
University of Twente - Stochastic Operations Research
GSM /HSCSD: High Speed Circuit Switched Data
33
University of Twente - Stochastic Operations Research
32
"
HSCSD characteristics (LB)
Multiple types (speech, video, data)
circuit switched: each call gets number of channels
"
GSM speech: 1 channel"
data: 1 channel (CS, data rate 9.6 kbps)"
"
GSM/HSCSD speech: 1 channel "
data: 1≤ b,...,B ≤ 8 channels (technical requirements, data rate 14.4 kbps)"
"
Call accepted iff minimum channel requirement b is met: loss system"
"
Up / downgrading: data calls may use more channels (up to B) when other services are not using these channels"
"
video: better picture quality, but same video length"
data: faster transmission rate, thus smaller transmission time "
"
University of Twente - Stochastic Operations Research
"
Other applications
Telephone switch"
"
IC bed planning"
"
Ambulance planning"
"
Parking "
"
"
32
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
31
University of Twente - Stochastic Operations Research
Generalised stochastic knapsack: model"
number of resource units
C"
λ2 (n)
λ1 (n)
n' = n − e1
number of object classes
K"
class k arrival rate
λk (n)"
class k mean holding time (exp)
1 / µ k (n) "
bk
class k size"
n' = n + e2
n
µ1 (n)
state (number of objects)"
n = (n1 ,..., nK )
state space"
S = {n ∈ N 0K : b ⋅ n ≤ C}
object of class k accepted only if"
bk ≤ C − b ⋅ n
state of process at time t"
X (t ) = ( X1 (t ),..., X K (t ))
stationary Markov process"
{ X (t ), t ≥ 0}
"
transition rates"
n' = n + e1
µ2 (n)
n' = n − e2
⎧λk (n)1(bk ≤ C − b ⋅ n) n' = n + ek
q(n, n' ) = ⎨
µ k ( n)
n' = n − ek
⎩
30
University of Twente - Stochastic Operations Research
Generalised stochastic knapsack: equilibrium distribution"
Theorem 1:"
For the generalised stochastic knapsack, a necessary and sufficient condition for
reversibility of X (t ) = ( X1 (t ),..., X K (t )) is that"
"
λk (n)
Ψ (n + ek )
=
µ k (n + ek )
Ψ ( n)
for some function
"
for all " n ∈ S \ Tk , k = 1,..., K
Ψ : S → [0, ∞). Moreover, when such a function Ψ
exists, the
equilibrium distribution for the generalised stochastic knapsack is given by"
"
"
"
Ψ ( n)
π ( n) =
,
∑ Ψ ( n)
n∈S
n∈S
University of Twente - Stochastic Operations Research
Generalised stochastic knapsack: equilibrium distribution"
Proof:"
We have to verify detailed balance:"
π (n)q(n, n + ek ) = π (n + ek )q(n + ek , n)
"
⇔
"
π (n)λk (n) = π (n + ek ) µ k (n + ek )
"
⇔
λk ( n )
"
µ k (n + ek )
"
If
=
π (n + ek )
π ( n)
π exists that satisfies the last expression, then π satisfies detailed balance. As the
right hand side of this expression is independent of the index k it must be that the
Ψ : S → [0, ∞)is satisfied. Conversely, assume
Ψ : S → [0, ∞) is satisfied. Then "
condition of the theorem involving
that the condition involving
"
Ψ ( n)
π ( n) =
,
∑ Ψ ( n)
n∈S
n∈S
is the equilibrium distribution.
29
University of Twente - Stochastic Operations Research
Generalised stochastic knapsack: examples"
Stochastic knapsack"
"λk (n) = λk 1(bk ≤ C − b ⋅ n) n' = n + ek
" µ k (n) = nk µ k n' = n − ek
K
Ψ ( n) = ∏
k =1
ρ knk
1(b ⋅ n ≤ C )
nk !
"
"
"
Finite source input"
k (n) = ( M k − nk )λk 1(nk ≤ M k ) n' = n + ek
"λ
"µ
k (n) = nk µ k n' = n − ek
K
Ψ ( n) = ∏
k =1
⎛ M k ⎞ nk
⎜⎜ ⎟⎟ ρ k
⎝ nk ⎠
"
State space constraints"
K
λk (n) = λk 1(bk ≤ C − b ⋅ n; nk ≤ Ck ) n' = n + ek Ψ (n) =
∏
k =1
µ k (n) = nk µ k n' = n − ek
ρ knk
1(b ⋅ n ≤ C; nk ≤ Ck )
nk !
28
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
University of Twente - Stochastic Operations Research
27
Admission control"
Admission class k whenever sufficient room bk ≤ C − b ⋅ n Complete sharing
"
"
Simple, but"
"
may be unfair (some classes monopolize the knapsack resources)"
"
may lead to poor long-run average revenue (admitted objects may not contribute to revenue)"
"
admission policies: restrict access even when sufficient room available"
"
calculate performance under policy"
"
determine optimal policy"
"
Coordinate convex policies"
"
In general: Markov decision theory"
University of Twente - Stochastic Operations Research
Stochastic knapsack under admission control"
Admission policy"
f = ( f1 ,..., f K )
"
⎧1 class k accepted in state n
f k (n) = ⎨
⎩0 class k rejected in state n
"
"
f k : S → {0,1}
"
⎧λk f k (n)1(bk ≤ C − b ⋅ n) n' = n + ek
q(n, n' ) = ⎨
nk µ k
n' = n − ek
⎩
Recurrent states"
S ( f ) ⊆ S = {n : b ⋅ n ≤ C}
Transition rates"
"
Examples: complete sharing"
"
"
"
trunk reservation"
⎧1 b ⋅ n ≤ C − bk
f k (n) = ⎨
otherwise
⎩0
⎧1 b ⋅ n ≤ C − bk − t k
f k (n) = ⎨
otherwise
⎩0
26
University of Twente - Stochastic Operations Research
Stochastic knapsack under trunk reservation"
"
trunk reservation admits class k object iff after admittance at least t k resource units
remain available"
C=4
K =2
b1 = b2 = 1
t1 = 0
t2 = 2
⎧1 b ⋅ n ≤ C − bk − t k
f k (n) = ⎨
otherwise
⎩0
Not reversible: so that equilibrium distribution usually not available in closed form
25
24
University of Twente - Stochastic Operations Research
Stochastic knapsack coordinate convex policies"
"
Coordinate convex set "
Ω ⊆ S : n ∈ Ω, nk > 0 ⇒ n − ek ∈ Ω
Coordinate convex policy: admit object iff state process remains in "Ω
"
f k (n) = 1 iff n + ek ∈ Ω
Theorem:"
Under the coordinate convex policy f "
the state process
X (t ) = ( X (t ),..., X (t ))
f
1
K
is reversible, and
1
π f ( n) =
Gf
K
∏
k =1
ρ kn
k
nk !
,
n∈Ω
23
University of Twente - Stochastic Operations Research
Coordinate convex policies: examples "
"
Note: Not all policies are coordinate convex, e.g. trunk reservation"
"
Complete sharing: always admit if room available"
Complete partitioning: accept class k iff"
"
"
C" 2
"
"
Ω
C1
S
Threshold policies: accept class k iff"
"
Ω=S
bk (nk + 1) ≤ Ck
⎢ C1 ⎥
⎢ C K
Ω = {0,..., ⎢ ⎥} × ... × {0,..., ⎢
⎣ b1 ⎦
⎣ bK
C1 + ... + C K ≤ C
⎥
⎥}
⎦
bk (nk + 1) ≤ Ck
b ⋅ n + bk ≤ C
C2
Ω
C1
S
⎢ C ⎥
Ω = {n : b ⋅ n ≤ C , nk ≤ ⎢ k ⎥, k = 1,..., K }
⎣ bk ⎦
22
University of Twente - Stochastic Operations Research
Coordinate convex policies: revenue optimization "
"
revenue in state n "
r (n) = ∑ rk nk
"
long run average revenue "
"
W ( f ) = ∑ r (n)π f (n)
K
k =1
n∈Ω
rk = bk
rk = µ k
example: long run average utilization"
long run average throughput"
"
Intuition:optimal policy in special cases"
λ k ↓ 0 ∀k
blocking obsolete ⇒ complete sharing"
""
complete partitioning with" Ck = bk sk*
""λk → ∞ ∀k
""
""
where
"
(s1* ,..., sK* ) is the optimal solution of the knapsack problem
""
""
K
K
""
max
rk sk
subject to
bk sk ≤ C sk ∈ N 0
""
""
k =1
k =1
*
""
⎧
r
/
b
for
k
=
k
*
k
k
*
"
If C / b * integer,
where k maximizes per unit revenue rk / bk then " sk = ⎨
∑
k
∑
⎩ 0
otherwise
University of Twente - Stochastic Operations Research
Coordinate convex policies: optimal policies "
"
number of coordinate convex policies is finite"
thus
for each coordinate convex policy f compute W(f)"
and select f with highest W(f)
infeasible as number of policies grows as "O(C1...CK )
"
show that optimal policy is in certain class"
often threshold policies"
"
b ⋅ n + bk ≤ C
"
⎢ Ck ⎥
Ω = {n : b ⋅ n ≤ C , nk ≤ ⎢ ⎥, k = 1,..., K }
⎣ bk ⎦
C" 2
"
Ω
C1
S
"
then problem reduces to finding optimal thresholds"
"
in full generality: Markov decision theory "
21
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
University of Twente - Stochastic Operations Research
Loss networks"
So far: stochastic knapsack"
equilibrium distribution"
blocking probabilities"
throughput"
admission control"
coordinate convex policy -- complex state space"
"
model for multi service single link "
"
multi service multiple links / networks
20
University of Twente - Stochastic Operations Research
PSTN / ISDN"
C4
C1
C3
C5
C2
C6
C7
Link: connection between switches"
Route: number of links"
Capacity Ci of link i"
Call class: route, bandwidth requirement per link"
"
Stochastic knapsack: special case = model for single link"
But: is special case of generalised stochastic knapsack
18
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
17
University of Twente - Stochastic Operations Research
C1
Loss network : notation"
number of links
J"
capacity (bandwidth units) link j"
Cj
number of object classes
K"
class k arrival rate
λk "
C4
C3
C2
C5
C6
C7
n' = n + e2
λ2
λ1
n' = n − e1
class k mean holding time (exp)
1/ µk "
bandwidth req. class k on link j
b jk
Route"
Rk ⊆ {1,..., J }
n
`n1µ1
n' = n + e1
n2 µ 2
Class k admitted iff b jk bandwidth units free in each link" j ∈ Rk
n' = n − e2
"
Otherwise call is blocked and cleared"
"
Admitted call occupies b jk bandwidth units in each link j ∈ Rk for duration of its
holding time "
University of Twente - Stochastic Operations Research
Loss network : notation"
Set of classes"
K = {1,..., K }
set of classes that uses link j"
K j = {k ∈ K : j ∈ Rk }
state"
n = (n1 ,..., nK )
"
state space"
"
"
S = {n ∈ N 0K :
∑
b jk nk ≤ C j , j = 1,..., J }
k∈K j
S = {n ∈ N0K : An ≤ C} A = (b jk )
"
class k blocked
Tk = {n ∈ S : ∑ b jℓ nℓ + b jk > C j , some j}
ℓ∈K j
Tk = {n ∈ N 0K : An ≤ C , A(n + ek ) ≤
/ C}
16
15
University of Twente - Stochastic Operations Research
Loss network : notation"
state of process at time t"
stationary Markov process"
X (t ) = ( X1 (t ),..., X K (t ))
{ X (t ), t ≥ 0}
aperiodic,irreducible"
equilibrium state"
X = ( X1 ,..., X K )
"
U j :=
b jk X k
utilization of link j"
k∈K j
"
long run fraction of blocked calls"
Bk = 1 − Pr{U j ≤ C j − b jk , j ∈ Rk }
"
long run throughput"
TH k = λk (1 − Bk ) = µ k E[ X k ]
"
unconstrained cousin (∞ capacity)" X ∞ = ( X ∞1 ,..., X ∞ K )
"
ρ k = λk / µ k
Poisson r.v. with mean"
"
unconstrained cousin of utilization U ∞ j :=
b jk X ∞ k
∑
∑
k∈K j
PASTA
Little
University of Twente - Stochastic Operations Research
Equilibrium distribution"
Theorem: Product form equilibrium distribution "
"
n
"
K
1 K ρ k k Pr{ X ∞ = n}
ρ k nk
" Pr{ X = n} =
=
,
n∈S
G=
,
n∈S
∞
G
n
!
Pr{
U
≤
C
}
nk !
k =1
k
n∈S k =1
"
"
Blocking probability of class k call"
"
nℓ
K
ρ
ℓ
"
Pr{X = n}
nℓ !
"
n∈S \Tk
n∈S \Tk ℓ =1
V, C vectors
B
=
1
−
=
1
−
k
n
K
"
Pr{X = n}
ρℓ ℓ
"
n∈S
nℓ !
n∈S ℓ =1
"
"
The Markov chain is reversible, PASTA holds, and the equilibrium distribution (and the
blocking probabilities) are insensitive."
"
PROOF: special case of generalised stochastic knapsack!"
∏
∑∏
∑
∑∏
∑
∑∏
14
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
University of Twente - Stochastic Operations Research
Computing blocking probabilities"
"
Direct summation is possible, but complexity" O( KC1...CJ )
"
Recursion is possible (KR), but complexity "
O( KC1...CJ )
"
"
Bounds for single service loss networks ( b jk ∈ {0,1} )"
"
For link j in loss network: probability that call on link j is blocked"
"
"
ρ Cj / C !
L j ≤ Er ( ρ j , C j ) =
j
Cj
∑
j
ρ j k / k!
,
ρj =
∑
k∈K j
"
k =0
"
Call of class k blocked if not accepted at all links"
"
"
B ≤ 1−
(1 − Er ( ρ j , C j ))
" k
"j∈R
"
"
"
∏
k
ρ k = ∑ b jk ρ k load offered to link j
k∈K
"
facility bound "
"
product bound"
13
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
University of Twente - Stochastic Operations Research
Computing blocking probabilities: single service networks
Reduced load approximation"
"
Facility bound " L j ≤ Er (
ρk , C j )
k∈K j
"
"
ρ k blocked on other links :"
L j = Er ( tk ( j ) ρ k , C j )
Part of offered load
k∈K j
k∈K j
"
tk ( j ) probability at least one unit of bandwidth available in each link in " Rk \ { j}
"
ρ k tk ( j ) reduced load"
"
approximation: blocking independent from link to link"
tk ( j ) =
(1 − Li )
i∈Rk \{ j }
"
"
reduced load approximation"
L j = Er(
ρk
(1− Li ),C j ),
j = 1,...,J
"
k ∈K j
i∈R k \{ j}
existence, uniqueness fixed point"
Bk = 1−
(1− L j ), k = 1,...,K
repeated substitution"
j ∈R k
accuracy"
∑
∑
∑
∏
∑
∏
∏
12
University of Twente - Stochastic Operations Research
11
Reduced load approximation: existence and uniqueness"
Notation:" L := ( L1 ,..., LJ )
"
T j ( L) := Er (
ρk
(1 − Li ), C j )
"
k∈K j
i∈Rk \{ j }
"
T ( L) := (T1 ( L),..., TJ ( L))
"
"
"
Theorem There exists a unique solution L* to the fixed point equation" L = T (L)
"
Proof The mapping T : [0,1]J → [0,1]J is continuous, so existence from Brouwer’s theorem"
"
"
"
T is not a contraction! "
∑
∏
10
University of Twente - Stochastic Operations Research
Reduced load approximation: uniqueness"
Notation:"
Er −1 j ( B) inverse of Er for capacity C j : value of ρ such that" B = Er ( ρ , C j )
is strictly increasing function of B "
B
"
Therefore
Er −1 j ( z )dz is strictly convex function of B for " B ∈ [0,1]
"
0
Proof of uniqueness:"
consider fixed point L = T (L) and apply Er −1 j : Er
" −1 j (L j ) :=
ρk
(1− Li )
"
k ∈K j
i∈R k \{ j}
J
Define " ∀L ∈[0,1]
Lj
J
"
ψ (L) :=
ρk
(1− Li ) +
Er−1 j (z)dz
"
k ∈K j
i∈R k
j=1 0
"
€
which is strictly convex."
∂ψ ( L)
*
J
Thus, if L ∈[0,1] is solution of "
= 0, i = 1,..., J
∂Li
"
€
Then L* is unique minimum of ψ over [0",1]J
"
writing out the partial derivatives yields (*) "
∫
∑
∑ ∏
∑ ∫
∏
(*)
9
University of Twente - Stochastic Operations Research
Reduced load approximation: repeated substitution"
J
Start" L ∈ [0,1]
T j (L) := Er(
ρk
(1− Li ),C j )
"
k ∈K j
i∈R k \{ j}
Repeat" L0 := L
"
Lm := T ( Lm−1 ), m = 1,2,...
"
"
€
0
Theorem Let" L = (1,...,1)
"
Then" (0,...,0) = L1 < L2 n +1 < L2 n +3 < L* < L2 n + 2 < L2 n < L0 = (1,...,1)
"
"
2n
+
2 n +1
−
−
*
+
"And"
L
→
L
,
L
→
L
,
L
≤
L
≤
L
""
Proof
"
"
T is decreasing operator:" T(L) < T(L') if L'< L componentwise
"
Thus " T 2n (L) < T 2n (L') and
"
T 2n +1 (L) > T 2n +1 (L') if L'< L componentwise
€
∑
∏
8
University of Twente - Stochastic Operations Research
Reduced load approximation: accuracy"
"
T j (L) := Er(
ρk
(1− Li ),C j )
Corollary" L * ≤ Er(
ρ k ,C j )
k ∈K j
i∈R k \{ j}
j
"
k ∈K j
"
*
so that"
Bk = 1−
(1− L j ) ≤ 1−
Er(
ρ k ,C j ), k = 1,...,K
"
j ∈R k
j ∈R k
k€
∈K j
" €
"
2
Proof " T j (1...1) = T(0...0) = Er(
ρ k ,C j )
k ∈K j
" €
"
(0,...,0) = L1 < L2n+1 < L* < L2n < L0 = (1,...,1)
"
"
L2 = T (0,...,0)
€"
"
"
Indeed Bk from reduced load approximation does not violate the upper bound "
∑
∑
∏
∏
∑
∑
∏
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
7
University of Twente - Stochastic Operations Research
Monte Carlo summation"
For performance measures: compute equilibrium distribution "
"
K
nk
ρ
"
k
"
nk!
k=1
Pr{X
=
n}
=
n∈S
K
nk ,
"
ρk
"
n k!
K
"
n ∈S k=1
ρ n
"
n !
n ∈Tk =1
for blocking probability of class k call"
Bk =
K
"
ρ n
€ "
n!
n ∈S =1
"
"
"
K
ρ n
In general: evaluate"
€
"
n!
n ∈U =1
"
"
difficult due to size of the state space : use Monte Carlo summation
"
∏
∑∏
∑∏
∑∏
∑∏
€
"
University of Twente - Stochastic Operations Research
Monte Carlo summation"
Example: evaluate integral"
"
c
d
b
"
f ( x)dx
"
a
"
"
"
a
b
Monte Carlo summation:"
draw points at random in box abcd"
# points under curve / # points is measure for surface //// = value integral"
"
Method" d
d
Let" X = U (a, b) Y = U (0, c) indep, and let Z = 1(Y ≤ f ( X ))
"
draw n indep. Samples" Z ,..., Z
1
n
b
1
"
Z + ... + Z n unbiased estimator of"
f ( x)dx
Then Z = 1
c(b − a) a
n
"
with 95% confidence interval
Z ±" 1.96 S 2 (n) /n
"
Powerful method: as accurate as desired"
∫
∫
[
]
6
University of Twente - Stochastic Operations Research
Monte Carlo summation"
K
∑∏
ρ n
n ! e − ρ ℓ
ρ n e − ρℓ
n!
For blocking probabilities "
"
Bk = n ∈Tk =1
K
"
"
n ∈S =1
"
ratio of multidimensional Poisson( ρ) distributed r.v. "
"
d
Pr{ X ( ρ ) ∈ Tk }
Let X = Poisson( ρ ) then"
B
=
k
€
Pr{ X ( ρ ) ∈ S}
"
"
"
Estimate enumerator and denominator via Monte Carlo summation:"
"
"draw Vi from Poisson( ρ ), i = 1,...,n iid
"
Let g(Vi ) = 1(Vi ∈ U)
for" U = Tk and U = S
K
n
"
ρ −ρ 
Eg(V ) = Pr{X(
ρ
)
∈
U}
=
e
"
"
"
"
"
confidence interval?"
n !
n ∈U =1
"
∑∏
∑∏
5
University of Twente - Stochastic Operations Research
Monte Carlo summation"
K
∑∏
ρ n
n ! e − ρ ℓ
ρ n e − ρℓ
n!
For blocking probabilities "
"
Bk = n ∈Tk =1
K
"
"
n ∈S =1
"
Estimate enumerator and denominator via Monte Carlo summation:"
"
confidence interval? Harvey-Hills method (acceptance rejection method HH)"
€
"
" B = Pr{ X ( ρ ) ∈ Tk } = Pr{ X ( ρ ) ∈ T | X ( ρ ) ∈ S}
k
k
"
Pr{X ( ρ ) ∈ S}
"
"
"
draw
Vi from Poisson( ρ ), i = 1,..., n iid
unbiased estimator!"
if" sample ∉ S ignore
∑∏
if sample ∈ S count
if sample also ∈ Tk count as succes
g (Vi ) = 1(Vi ∈ Tk | Vi ∈ S )
Eg (V ) = Bk
4
"
Plan for today
1  multiple services, single cell / link -- HSCSD"
2  Generalised stochastic knapsack"
3  Admission control"
4  GSM network / PSTN network "
5  Model, Equilibrium distribution"
6  Blocking probabilities"
7  Reduced load approximation"
8  Monte-Carlo summation"
9  Summary"
3
University of Twente - Stochastic Operations Research
Summary loss network models and applications:!
GSM network architecture
 Loss networks - circuit switched telephone"
 
wireless networks"
 
"
TELEPHONE
Markov chain"
equilibrium distribution"
blocking probabilities"
throughput"
admission control"
"
Evaluation of performance measures:"
recursive algorithms"
reduced load method"
Monte Carlo summation
"
"
MS
(G)MSCPSTN/ISDN
BTS
BSC
RADIO
INTERFACE
GSM/HSCSD
C1
C2
C4
C3
C5
C6
C7
University of Twente - Stochastic Operations Research
"
Other applications
IC bed planning"
"
Ambulance planning"
"
Parking "
"
Bandwidth sharing"
"
"
32
University of Twente - Stochastic Operations Research
References:!
  . Ross, sections 5.1, 5.2, 5.5 (reduced load method)"
K
 
"
 Kelly: "
 lecture notes (on website of Kelly)"
  elly"
K
 F.P. Kelly Loss networks, Ann. Appl. Prob 1, 319-378, 1991 "
  H"
H
 C. Harvey and C.R. Hills "
 Determining grades of service in a network. "
 Presented at the 9th International Teletraffic Conference, 1979."
  R"
K
 J.S. Kaufman and K.M. Rege Blocking in a shared resource environment with batched
Poisson arrival processes. Performance Evaluation, 24, 249-263, 1996"
 BvD: chapter 16 – Loss networks, chapter 17 – bandwidth sharing networks
0
1/--pages
Пожаловаться на содержимое документа