INSTITUT FÜR KOMMUNIKATIONSNETZE UND RECHNERSYSTEME Universität Stuttgart Prof. Dr.-Ing. Andreas Kirstädter Sample Solution "Teletraffic Theory and Engineering" (TTE) "Performance Modelling & Simulation" (PMS) Date: March 10, 2010 Problem 1 Markovian Service Systems Part 1 Single Server Queuing Systems Question 1 18 Points a) State Transition Diagram for Model A λ 0 b) µ λ 1 µ λ x µ µ λ x+1 µ State Transition Diagram for Model B λ 0 λ (1–q)ε λ ... 1 qε c) λ ... qε λ x qε (1–q)ε λ x+1 qε (1–q)ε qε (1–q)ε Probability distribution for Model A i p A ( i ) = P { X = i } = ( 1 – ρ A )ρ A , i = 0, 1, ..., where ρ A = λ ⁄ µ d) e) f) Probability distribution for Model B ρ ρ i p A ( i ) = P { X = i } = 1 – -----B- -----B- , i = 0, 1, ..., where ρ B = λ ⁄ ( µε ) q q Comparison ρB p A ( i ) = p B ( i ) ⇒ ρ A = ------ ⇒ µ = qε q Model A: ∞ E[ X] = ∑ x ⋅ pA ( x ) x=0 ρA ρA = … = Ω + A = ρ A ( 1 – ρ A ) ----------------------2- + ρ A = --------------1 – ρA ( 1 – ρA ) 1 1 E [ T F ] = --------------- ⋅ --1 – ρA µ Model B: ρB ⁄ q ρB E[X] 1 1 E [ X ] = ---------------------- = --------------- ; E [ T F ] = ------------- = --------------- ⋅ --1 – ρB ⁄ q q – ρB λ q – ρB ε Question 2 13 Points Delay Analysis of Models A and B a) Probability density function of waiting times WRT all requests for Model A From eq. (3.1) of chapter 4.1 where W = ρA: w A ( t ) = ( 1 – W )δ ( t ) + Wµ ( 1 – ρ A )e – µ ( 1 – ρ A )t = ( 1 – ρ A )δ ( t ) + ρ A ( 1 – ρ A )µe b) ( 1 – ρ A )µ LST φ A ( s ) = ( 1 – ρ A ) ⋅ 1 + ρ A --------------------------------s + ( 1 – ρ A )µ c) 1st moment: (1) wA = wA dφ ( s ) = – ------------ds ;2 nd – µ ( 1 – ρ A )t moment: s=0 (2) wA 2 d φ( s) = --------------2 ds s=0 – ( 1 – ρ A )µ ⋅ 1 ρ A ( 1 – ρ A )µ ρA dφ ( s ) 1 ------------- = ρ A ---------------------------------------2- = – ---------------------------------------2- ⇒ w A = --------------- ⋅ --ds 1 – ρA µ [ s + ( 1 – ρ A )µ ] [ s + ( 1 – ρ A )µ ] 2 2ρ A ( 1 – ρ A )µ d φ(s ) --------------= --------------------------------------2 3 ds [ s + ( 1 – ρ A )µ ] d) Output Processes: Model A:The output process is Markov, i.e. the inter-departure time CDF is P{TD ≤ t} = 1 – e–λt, due to the Output Theorem by P. J. Burke. Model B:The output process is more complicated due to correlated departures. Part 2 Markovian Queuing Networks Question 3 State Analysis 16 Points 2ρ A 1 (2) ⇒ w A = ---------------------- ⋅ -----2 2 ( 1 – ρA ) µ a) State X = (X1, X2, X3), where Xi = number of jobs in station i, i = 1, 2, 3 b) Conservation of flow equations: Station 1: λ1 = λ0 + λ2 + λ3q31 Station 2: λ2 = λ1q12 Station 3: λ3 = λ1(1 – q12) λ0 ⇒ λ 1 = ---------------------------------------------------- ; λ2 = q12λ1 ; λ3 = (1 – q12)λ1 1 – q 12 – q 31 ( 1 – q 12 ) c) Utililzation factors: ρ1 = λ1/µ1, ρ2 = λ2/µ2, ρ3 = λ3/µ3 Stability condition: ρi < 1, i = 1, 2, 3 ⇒ q 12 λ 0 ⁄ µ 2 ( 1 – q 12 )λ 0 ⁄ µ 3 λ0 ⁄ µ1 ---------------------------------------------------- < 1 ; ---------------------------------------------------- < 1 ; ---------------------------------------------------- < 1 1 – q 12 – q 31 ( 1 – q 12 ) 1 – q 12 – q 31 ( 1 – q 12 ) 1 – q 12 – q 31 ( 1 – q 12 ) µ µ3 ⇒ λ 0 < min µ 1 D, ------2-D, ---------------D , where D = 1 – q 12 – q 31 ( 1 – q 12 ) q 12 1 – q 12 Problem 1 Page 2 d) Individual state probability distributions: x x x p 1 ( x 1 ) = ( 1 – ρ 1 )ρ 1 1 ; p 2 ( x 2 ) = ( 1 – ρ 2 )ρ 22 ; p 3 ( x 3 ) = ( 1 – ρ 3 )ρ 33 e) Overall state distribution: 3 p ( x 1, x 2, x 3 ) = ∏ pi ( xi ) x x x = ( 1 – ρ 1 ) ( 1 – ρ 2 ) ( 1 – ρ 3 )ρ 1 1 ρ 22 ρ 33 i=1 f) Average number of jobs ρ1 ρ2 ρ3 per station: E [ X 1 ] = -------------- , E [ X 2 ] = -------------- , E [ X 3 ] = -------------1 – ρ1 1 – ρ2 1 – ρ3 ρ1 ρ2 ρ3 in system: E [ X ] = E [ X1 ] + E [ X 2 ] + E [ X3 ] = -------------- + -------------- + -------------1 – ρ 1 1 – ρ2 1 – ρ 3 Question 4 Delay Analysis 8 Points a) b) ρ1 ρ2 ρ3 E[X] 1 E [ T F ] = ------------- = … = ----- -------------- + -------------- + -------------- λ0 λ 0 1 – ρ 1 1 – ρ 2 1 – ρ 3 Consideration of one specific job: First i disk I/Os (station 2), then j I/Os (station 3) b1) pi,j = q12i (1 – q12)j q31j–1 (1 – q31) b2) The job is serviced i+j times in station 1. 1 1 1 1 1 1 b3) E [ T F ] i, j = ( i + j ) ⋅ -------------- ⋅ ----- + i ⋅ -------------- ⋅ ----- + j ⋅ -------------- ⋅ ----1 – ρ1 µ1 1 – ρ2 µ2 1 – ρ3 µ3 Problem 1 Page 3 Problem 2 Random Processes in Networks Part 1 Network Transfer Delays Question 1 Modeling Transfer Delays 16 Points a) Phase model for TF (with TV1): k phases D ... M M 1/ε 1/ε M 1/ε (Erlang-k) b) Phase model for TF (with TV2): M 1/ε1 M 1/ε2 q D 1–q (H2) c) Probability density functions and Laplace-Stieltjes Transforms: φC(s) = 1·e–sd TC: fC(t) = δ(t – d); k–1 ε k φ V1 ( s ) = ----------- s + ε ( εt ) – εt TV1: f V1 ( t ) = s ( t ) ⋅ ε ------------------e ; ( k – 1 )! TV2: f V2 ( t ) = s ( t ) ⋅ ( qε 1 e –ε1 t + ( 1 – q )ε 2 e – ε2 t ); ε2 ε1 φ V2 ( s ) = q ------------- + ( 1 – q ) ------------s + ε1 s + ε2 d) Sketches of PDFs fF(t) log(fF(t)) D + Ek D + H2 qε 1 + ( 1 – q )ε2 qε 1 ( 1 – q )ε2 0 Problem 2 d k --- + d ε t 0 t d Page 4 Question 2 18 Points Characteristic Values a) b) E[TF] = E[TC] + E[TV1] = d + k · 1/ε VAR[TF] = VAR[TC] + VAR[TV1] = 0 + k · VAR[1 phase] = k · 1/ε2 –ε 1 –ε2 dφ ( s ) φ' V2 ( s ) = ------------- = q --------------------2 + ( 1 – q ) -------------------2 ds ( s + ε1 ) ( s + ε2 ) 2 2ε 1 2ε 2 d φ( s) φ'' V2 ( s ) = --------------= q --------------------3- + ( 1 – q ) --------------------32 ds ( s + ε1 ) ( s + ε2 ) E [ T V2 ] = – φ' V2 ( 0 ) = q ⁄ ε 1 + ( 1 – q ) ⁄ ε 2 2 2 2 E [ T V2 ] = φ'' V2 ( 0 ) = 2q ⁄ ε 1 + 2 ( 1 – q ) ⁄ ε 2 2 q ( 2 – q ) 1 – q 2q ( 1 – q ) 2 2 VAR [ T V2 ] = E [ T V2 ] – ( E [ T V2 ] ) = ------------------- + ------------- – ----------------------2 2 ε1 ε2 ε1 ε2 c) E[TF] = E[TC] + E[TV2] = d + q / ε1 + (1 – q) / ε2 2 q ( 2 – q ) 1 – q 2q ( 1 – q ) VAR [ T F ] = VAR [ T C ] + VAR [ T V2 ] = 0 + ------------------- + ------------- – ----------------------2 2 ε1 ε2 ε2 ε1 ∞ d) BD = ∞ ∫ f F ( t ) dt = t0 = qe ∞ ∫ t0 – d –ε1 ( t0 – d ) ∫ f V2 ( τ ) dτ = [ qε 1 e –ε1 τ + ( 1 – q )ε 2 e – ε2 τ ] dτ t0 – d + ( 1 – q )e –ε2 ( t0 – d ) –ε2 ( t0 – d ) Remark: B D ≈ ( 1 – q )e Illustratration (not required): for ε1 >> ε2, q in reasonable range f(t) qε 1 + ( 1 – q )ε2 prob. mass BD 0 d t0 0 t0 – d Part 2 Sensor Networks Question 3 State Analysis of a Limited Buffer Sensor Node 12 Points τ τ=t–d i a) Problem 2 t ( λt ) –λt (Poisson distribution) p i ( t ) = -----------e i! Page 5 ∞ b) ∑ i ⋅ pi( c ) E[N ] = = … = λc (see chapter 2.2) i=0 ∞ 2 E[N ] = ∑i 2 2 ⋅ p i ( c ) = … = ( λc ) + λc i=0 c) d) pj ( c ) qj ( c ) = ∞ s–1 pi ( c ) = 1 – ∑ pi ( c ) ∑ i=s i=0 for j = 0, 1, …, s – 1 for j = s Mean number of data units transferred per polling period (i.e. queued at s time c): E [ X ] = ∑j = 0 j ⋅ q j ( c ) Mean number of arriving data units per polling period: E[N] = λc The probability of loss corresponds to the fraction of untransmitted data units: s E[N ] – E[X ] 1 B = -------------------------------- = 1 – ------ ⋅ ∑ j ⋅ qj ( c ) E[N ] λc j=0 Note: B > 0 since ∞ E[N ] = ∑i = 0 i ⋅ pi ( c ) > ∑ s i=0 i ⋅ pi( c ) + ∑ ∞ i = s+1 s ⋅ pi ( c ) = E [ X ] , i ( λc ) –λc where p i ( c ) = ------------e > 0 for i = 0, 1, …, ∞ i! Question 4 10 Points State Analysis of an Unlimited Buffer Sensor Node a) Moment Method: mean queue length: Ω mean waiting time: w balance equation: w = c / 2 + Ω · c, where c / 2 is mean of residual time to next polling instant Little’s law: Ω = λ · w b) c ⇒ w = c / 2 + λw · c ⇒ w (1 – λc) = c / 2 ⇒ w = ----------------------2 ( 1 – λc ) Comparison with M/D/1 ρ λc w M ⁄ D ⁄ 1 = -------------------- ⋅ h = ----------------------- ⋅ c 2(1 – ρ ) 2 ( 1 – λc ) 2 wM ⁄ C ⁄ 1 – wM ⁄ D ⁄ 1 c λc c ( 1 – λc ) c = ----------------------- – ----------------------- = ----------------------- = --2 ( 1 – λc ) 2 ( 1 – λc ) 2 ( 1 – λc ) 2 ⇒ wM/C/1 = c/2 + wM/D/1 Reason: In wM/D/1 service starts immediately when the server is available. In wM/C/1 service starts only at the next clock instant; the mean time to the next clock instant is c/2. Problem 2 Page 6 Problem 3 Discrete Event Simulation Method Remark This problem is based on a lecture part on simulation which differs from the contents taught since winter term 2010/2011. Consequently, its questions may not be covered by current lectures. Part 1 Generation of Stochastic Variables Question 1 Inversion Method 9 Points a) Derivation of T from RN in CDF time diagram: Remarks: Known for F(t): F(t) P{t1 < T ≤ t2} = F(t1) – F(t2) ↔ F(t1) < RN ≤ F(t2) 1 RN RN F(t1) F(t2) t 0 t1 t2 Mapping Process: RN = F(T) ⇒ T = F–1(RN) (inversion method) T b) Inversion method: b1) F(t) = 1 – e–λt ⇒ RN = 1 – e–λT ⇒ T = –1/λ · ln(1 – RN) Note: As (1 – RN) is also uniformly distributed in (0, 1]: T = –1/λ · ln( RN) (This avoids a substraction!) 1 b2) F ( t ) = ----------- ( t – a ) for a ≤ t ≤ b b–a T–a F(T) = RN ⇒ ------------ = RN ⇒ T = a + RN · (b – a) b–a Illustration: F(t) 1 RN 0 a b t T c) t F ( t ) = 1 – exp --- β α ⇒ RN = 1 – e T --- β α ⇒ T = β ⋅ ( ln ( 1 – R N ) ) Note: We can again substitute 1 – RN by RN: T = β ⋅ ( ln ( RN ) ) Problem 3 1 --α 1 --α Page 7 Question 2 8 Points Generator Method a) Phase model for T: M 1/ε1 M 1/ε2 q1 1–q1 b) CDF: F ( t ) = 1 – q 1 e –ε1 t Remark: RN = 1 – q 1 e – ( 1 – q 1 )e –ε1 T – ε2 t – ( 1 – q 1 )e –ε2 T cannot be inverted analytically Generator method: T is ( 1 ⁄ ε 1 ) ln ( RN 1 ) with probability q1 ( 1 ⁄ ε 2 ) ln ( RN 2 ) with probability 1 – q1 c) Flow Chart: Start RN := RNG true RN ≤ q1 RN := RNG false RN := RNG 1 ε1 1 ε2 T := ----- ln(RN) T := ----- ln(RN) End Part 2 Measurement of Variables in an Event-by-Event System Simulation Question 3 Measurement of TW 10 Points Problem 3 a) - Waiting time samples are taken when a customer is taken out of the queue. - The arrival time (i.e. the instant when the customer is placed in the queue). - Sample value TW := departure time (dequeue) – arrival time (enqueue) b) - Variables: STW = sum of all waiting times during the batch run NW = number of customers having to wait during batch run - Updating for each new sample value TW: STW := STW + TW NW := NW + 1 - Mean waiting time at the end of the batch run: E[TW] := STW / NW Page 8 c) Question 4 9 Points - Additional variable STW2 = sum of squares of waiting times - Updating: STW2 := STW2 + TW2 - Variance computation (at end of batch): E[TW2] := STW2 / NW VAR[TW] := E[TW2] – (E[TW])2 Measurement of State Distribution and Average Number of Customers in the System a) - Samples are taken on each state change, i.e. on arrival and departure events - Sample value TS = the duration of the last state - TS = time ω of current state change – time α of previous state change - The time α of the last state change must be registered (auxiliary variable) Illustration: X ... 0 ... α ω t b) - Variable S[X] = array of sums of the periods where the system is in state x - Updating: S[X] := S[X] + TS (where X is the state between α and ω) c) P[X] := S[X] / Tbatch, where Tbatch = duration of the batch d) E[X ] = ∑ X ⋅ P[ X] all X Problem 3 Page 9

© Copyright 2020