上海交通厌：《通信网络》课程教学资源（PPT讲稿）DELAY MODELS IN DATA NETWORKS、LITTLE’S LAW、ARRIVAL MODEL、M/M/X QUEUING MODELS

复法 票 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 𝑁 = 𝜆𝑇