Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 The Stochastic Knapsack Model objects from K different classes arrive at random and share C resource units.An object departs after its holding times Assumption:Poisson Arrival with rate exponentially distributed holding time with mean 1/ 1 2 Stochastical Knapsack n=(1,nk) K ·Sate space: S=aeIK:bn≤C} Where I:the set of non-negative integers 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.16
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.16 The Stochastic Knapsack • Model : objects from K different classes arrive at random and share C resource units. An object departs after its holding times • Assumption: Poisson Arrival with rate exponentially distributed holding time with mean Stochastical Knapsack nK ,..., 1 n n . . . . . . 1 2 K k k 1/ • Sate space: C K S : nI :b n Where I : the set of non-negative integers
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Equilibrium Behavior of the Stochastical Knapsack Notations: -z(n):probability that the knapsack is in state n the long-run fraction of time that the knapsack is in state n) -P=:the offered load for class-k objects The equilibrium distribution for the stochastical knapsack: n∈S where -赋 nEs k=1 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.17
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.17 Equilibrium Behavior of the Stochastical Knapsack • Notations: - : probability that the knapsack is in state ( the long-run fraction of time that the knapsack is in state ) - : the offered load for class-k objects • The equilibrium distribution for the stochastical knapsack: (n) n k k k / S n , n ! 1 ( ) 1 K k k n k G n k n where n S 1 K k k n k n ρ G k !
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Blocking Probability and Throughput Notations: B.:Class-k blocking probability Throughput of class-k objects:TH=(1-B) Let be the random variable denoting the number of class-k objects in the system in equilibrium -Letx:=()be the random state vector so that π(n)=P(X=n) Utilization of the knapsack in equilibrium: U :=b X+...+bkxk) Average utilization of the knapsack: UTIL:=E(U) 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.18
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.18 Blocking Probability and Throughput • Notations: - : Class-k blocking probability - Throughput of class-k objects: - Let be the random variable denoting the number of class-k objects in the system in equilibrium - Let be the random state vector so that - Utilization of the knapsack in equilibrium: - Average utilization of the knapsack: Bk (1 ) THk k Bk Xk : ( ,..., ) X X1 X K (n) P(X n) : ... ) 1 1 K X K U b X b UTIL: E(U)
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Performance Evaluation Let &x be the subset of the states in which the knapsack admits an arriving class-k object S4=a∈S:bn≤C-b} An example:2 classes,C=8,b1=1,b2=2 The set $is the collection of all the points The set S is the collection of points below the dotted line 2 3 5 67 8 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.19
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.19 Performance Evaluation • Let be the subset of the states in which the knapsack admits an arriving class-k object • An example: 2 classes, C=8, b1=1, b2=2 Sk : nS : b n C bk n2 n1 1 2 3 4 1 2 3 4 5 6 7 8 The set S is the collection of all the points The set S2 is the collection of points below the dotted line k S
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Performance Evaluation(cont'd) Assuming the arrivals are Poisson,the probability of blocking a class- k object is Bs=1-∑π(n) nE.Sk where Sk=a∈S:bn≤C-b} An explicit expression for blocking probability: ∑Πpn B=1- n∈Sk ∑ΠP/n, Dilemma impractical to brute-force sum the terms in the numerator and denominator: the discrete state spaces and Sk are prohibitively large for moderate values of C and K nl≈n1v2e"√2元 2616009:Network Traffic Engineering 2:Call-level Models and Admission Control Page.20
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 2: Call-level Models and Admission Control Page.20 Performance Evaluation(cont’d) • Assuming the arrivals are Poisson, the probability of blocking a classk object is where • An explicit expression for blocking probability: • Dilemma impractical to brute-force sum the terms in the numerator and denominator: the discrete state spaces S and Sk are prohibitively large for moderate values of C and K k Bk n S 1 (n) Sk : nS : b n C bk S S n n K j j n j K j j n j k n n B j k j 1 1 / ! / ! 1 ! 2 n 1/ 2 n n n e