Networking Theory and Fundamentals - Lecture 4 & 5

Tham khảo tài liệu 'networking theory and fundamentals - lecture 4 & 5', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Networking Theory and Fundamentals - Lecture 4 & 5 TCOM 501: Networking Theory & Fundamentals Lectures 4 & 5 February 5 and 12, 2003 Prof. Yannis A. Korilis 1 Topics 4&5-2 Markov Chains M/M/1 Queue Poisson Arrivals See Time Averages M/M/* Queues Introduction to Sojourn Times The M/M/1 Queue 4&5-3 Arrival process: Poisson with rate λ Service times: iid, exponential with parameter µ Service times and interarrival times: independent Single server Infinite waiting room N(t): Number of customers in system at time t (state) λ λ λ λ 0 1 2 n n+1 µ µ µ µ Exponential Random Variables 4&5-4 X: exponential RV with Proof: parameter λ P{min{ X , Y } > t} = P{ X > t , Y > t} = Y: exponential RV with = P{ X > t}P{Y > t} = = e− λt e− µt = e− ( λ + µ ) t ⇒ parameter µ P{min{ X , Y } ≤ t} = 1 − e− ( λ + µ ) t X, Y: independent Then: ∞ y P{ X < Y } = ∫ ∫ f XY ( x, y ) dx dy = 0 0 1. min{X, Y}: exponential RV ∞ y =∫ ∫ λ e− λ x ⋅ µ e− µ y dx dy = with parameter λ+µ 00 ∞ y = ∫ µ e− µ y ∫ λ e− λ x dx dy = 2. P{X M/M/1 Queue: Markov Chain Formulation 4&5-5 Jumps of {N(t): t ≥ 0} triggered by arrivals and departures {N(t): t ≥ 0} can jump only between neighboring states Assume process at time t is in state i: N(t) = i ≥ 1 Xi: time until the next arrival – exponential with parameter λ Yi: time until the next departure – exponential with parameter µ Ti =min{Xi,Yi}: time process spends at state i Ti : exponential with parameter νi= λ+µ Pi,i+1=P{Xi < Yi}= λ/(λ+µ), Pi,i-1=P{Yi < Xi}= µ/(λ+µ) P01=1, and T0 is exponential with parameter λ {N(t): t ≥ 0} is a continuous-time Markov chain with qi ,i +1 = ν i Pi ,i +1 = λ , i ≥ 0 qi ,i −1 = ν i Pi ,i −1 = µ , i ≥ 1 qij = 0, | i − j |> 1 M/M/1 Queue: Stationary Distribution 4&5-6 λ λ λ λ 0 1 2 n n+1 µ µ µ µ Birth-death process → DBE µ pn = λ pn −1 ⇒ λ pn = pn −1 = ρ pn −1 = ... = ρ n p0 µ Normalization constant   ∞ ∞ ∑ pn = 1 ⇔ p0 1 + ∑ ρ n  = 1 ⇔ p0 = 1 − ρ , if ρ < 1  n =1  n=0 Stationary distribution pn = ρ n (1 − ρ ), n = 0,1, ... The M/M/1 Queue 4&5-7 Average number of customers in system ∞ ∞ ∞ N = ∑ npn = (1 − ρ )∑ n ρ =(1 − ρ ) ρ ∑ nρ n −1 n n =0 n =0 n =0 ρ λ 1 ⇒ N = ρ (1 − ρ ) = = (1 − ρ ) 2 1 − ρ µ − λ Little’s Theorem: average time in system λ N 1 1 T= = = λ λ µ −λ µ −λ Average waiting time and number of customers in the queue – excluding service ρ ρ2 1 and N Q = λW = W =T − = µ µ −λ 1− ρ The M/M/1 Queue 4&5-8 ρ=λ/µ: utilization factor 10 Long term proportion of 8 time that server is busy 6 N ρ=1-p0: holds for any 4 M/G/1 queue 2 Stability condition: ρ M/M/1 Queue: Discrete-Time Approach 4&5-9 Focus on times 0, δ, 2δ,… (δ arbitrarily small) Study discrete time process Nk = N(δk) lim P{N (t ) = n} = lim P{N k = n} t →∞ k →∞ Show that transition probabilities are P00 = 1 − λδ + ο (δ ) Pii = 1 − λδ − µδ + ο (δ ), i ≥ 1 Pi ,i +1 = λδ + ο (δ ), i≥0 Pi ,i −1 = µδ + ο (δ ), i≥0 Pij = ο (δ ), |i − j |> 1 Discrete time Markov chain, omitting o(δ) λδ λδ λδ λδ 0 1 2 n n+1 µδ µδ µδ µδ 1 − λδ 1 − λδ − µδ 1 − λδ − µδ 1 − λδ − µδ M/M/1 Queue: Discrete-Time Approach 4&5-10 λδ ...