复法 票 hanghai Jiao Tong University DELAY MODELS IN DATA NETWORKS
Communication Networks DELAY MODELS IN DATA NETWORKS Shanghai Jiao Tong University 1
Data Networks and Queueing IIIIIO
Communication Networks Data Networks and Queueing R R R R R R R S 2
Queueing Analysis We are given Packet arrival behavior Packet length distribution Packet routing/ handlingpolicies We want to deduce Packet delay Queue length Packet loss Queueing theory can also be applied in other areas, such as in analyzing Circuit Switched Network
Communication Networks Queueing Analysis • We are given: – Packet arrival behavior – Packet length distribution – Packet routing / handling policies • We want to deduce: – Packet delay – Queue length – Packet loss • Queueing theory can also be applied in other areas, such as in analyzing Circuit Switched Network 3
In this chapter · Little's law Poisson process MMX Queueing systems Burke's Theorem and Jackson's Theorem ·MG/1 Reservation systems and priority queue
Communication Networks In this Chapter • Little’s Law • Poisson process • M/M/x Queueing systems • Burke’s Theorem and Jackson’s Theorem • M/G/1 • Reservation systems and priority queue 4
票 hanghai Jiao Tong University LITTLES LAW
Communication Networks LITTLE’S LAW Shanghai Jiao Tong University 5
Little’sLaw Named after John Little, an MiT sloan professor Little.D. C "A proof of the Queueing Formula l- nw, " Operation Research, 9, 383-387(961) A queueing system (N,T) ·N=AT 1: arrival rate of customers into the system N: number of customers in the system T: average amount of time a customer spends in the system
Communication Networks Little’s Law • Named after John Little, an MIT Sloan professor Little J. D. C. “A proof of the Queueing Formula L= λw,” Operation Research, 9, 383-387 (1961) A queueing system 𝑁, 𝑇 𝜆 • 𝑁 = 𝜆𝑇 – 𝝀: arrival rate of customers into the system – 𝑵: number of customers in the system – 𝑻: average amount of time a customer spends in the system 6
About little's law The result is very useful because of its generality System should be stationary without any other assumptions 150 Arrival process can be anything Treat system as a black box 之100 Can be applied to whole system or Any part of the system It can naturally explain why stationary On rainy days. traffic moves slower 10.0 and the streets are more crowded t(×103s) a fast-food restaurant needs a smaller waiting room
Communication Networks About Little’s Law • The result is very useful because of its generality – System should be stationary – Without any other assumptions • Arrival process can be anything • Treat system as a black box • Can be applied to whole system • or Any part of the system • It can naturally explain why – On rainy days, traffic moves slower and the streets are more crowded – A fast-food restaurant needs a smaller waiting room 7 0.0 2.0 4.0 6.0 8.0 10.0 0 50 100 150 200 N t (103 s) =1.1 =0.9 stationary
Observation 1 3 a() z 5月z N() Delay t custom B() custom I Shaded Area N(Tdt= [a(t)-Bcoldt 0
Communication Networks Number of Arrivals a(t) Number of Departures b(t) custom 1 Delay T1 custom 2 Delay T2 a(t) b(t) N(t) t t Observation 1 8 Shaded Area = න 0 𝑡 𝑁 𝜏 𝑑𝜏 = න 0 𝑡 𝛼 𝜏 − 𝛽 𝜏 𝑑𝜏
Observation 2 下四 dI) z Delay t custom 2 B() custom I t2 13 t67 Shaded Area= total time that all the customs spend in the system B(t) T;+ B(t)+1
Communication Networks Observation 2 9 Shaded Area = total time that all the customs spend in the system 𝑖=1 𝛽 𝑡 𝑇𝑖 +𝛽 𝑡 +1 𝛼 𝑡 𝑡 − 𝑡𝑖 Number of Arrivals a(t) Number of Departures b(t) custom 1 Delay T1 custom 2 Delay T2 a(t) b(t) t1 t2 t3 t4 t5 t6 t7 t t
Proof We thus have β(t 「Mor=∑ n+∑ 1 β(t)+1 Dividing by t on both sides, we obtain N(r)dr∑e (0T;+∑(,(t N β(t)+1 λ×T a(t)t re Nt, nt and lt are the average number of customs in the system, the average arrival rate and the average sojourn time during[0,t」. Suppose there is a steady state,ie,Nt→N,λt→λ, and Tt>T when t>o. The above equation immediately yields N=nT
Communication Networks Proof 10 We thus have න 0 𝑡 𝑁 𝜏 𝑑𝜏 = 𝑖=1 𝛽 𝑡 𝑇𝑖 +𝛽 𝑡 +1 𝛼 𝑡 𝑡 − 𝑡𝑖 Dividing by 𝑡 on both sides, we obtain 𝑁𝑡 = 0 𝑡 𝑁 𝜏 𝑑𝜏 𝑡 = σ𝑖=1 𝛽 𝑡 𝑇𝑖 + σ𝛽 𝑡 +1 𝛼 𝑡 𝑡 − 𝑡𝑖 𝑡 𝛼 𝑡 𝛼 𝑡 = 𝜆𝑡 × 𝑇𝑡 where 𝑁𝑡 , 𝜆𝑡 and 𝑇𝑡 are the average number of customs in the system, the average arrival rate and the average sojourn time during 0,𝑡 . Suppose there is a steady state, i.e., 𝑁𝑡 → 𝑁, 𝜆𝑡 → 𝜆, and 𝑇𝑡 → 𝑇 when 𝑡 → ∞. The above equation immediately yields 𝑁 = 𝜆𝑇