tailieunhanh - Lecture Networking theory & fundamentals - Chapter 4&5

The following will be discussed in this chapter: Markov chains, M/M/1 queue, poisson arrivals see time averages, M/M/* queues, introduction to sojourn times. | Lecture Networking theory & fundamentals - Chapter 4&5 TCOM 501: Networking Theory & Fundamentals Lectures 4 & 5 February 5 and 12, 2003 Prof. Yannis A. Korilis 1 4&5-2 Topics Markov Chains M/M/1 Queue Poisson Arrivals See Time Averages M/M/* Queues Introduction to Sojourn Times 4&5-3 The M/M/1 Queue 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 µ µ µ µ 4&5-4 Exponential Random Variables 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} = parameter µ = e− λt e− µt = e− ( λ + µ ) t ⇒ 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 λ+µ 0 0 ∞ y = ∫ µ e− µ y ∫ λ e− λ x dx dy = 2. P{X4&5-5 M/M/1 Queue: Markov Chain Formulation 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 4&5-6 M/M/1 Queue: Stationary Distribution λ λ λ λ 0 1 2 n n+1 µ µ µ µ Birth-death process → DBE µ pn = λ pn −1 ⇒ λ pn = pn −1 = ρ pn −1 = . = ρ n p0 µ

• Quản trị mạng
• Networking theory
• Queueing Theory
• Lecture Networking theory
• Markov Chains
• Sojourn Times
• Time Averages