美国麻省理工大学：《Communication Systems Engineering（通讯系统工程）》Lecture 17/18: Delay Models for Data

16.36: Communication Systems Engineering Lecture 17/18: Delay Models for Data Networks Eytan Modiano

Eytan Modiano Slide 1 16.36: Communication Systems Engineering Lecture 17/18: Delay Models for Data Networks Eytan Modiano

Packet Switched Networks Messages broken into Packets that are routed To their destination Packet Network Buffer Packet Switch

Eytan Modiano Slide 2 Packet Switched Networks Packet Network PS PS PS PS PS PS PS Buffer Packet Switch Messages broken into Packets that are routed To their destination

Queueing systems Used for analyzing network performance In packet networks, events are random Random packet arrivals Random packet lengths While at the physical layer we were concerned with bit-error-rate, at the network layer we care about delays How long does a packet spend waiting in buffers? How large are the buffers

Eytan Modiano Slide 3 Queueing Systems • Used for analyzing network performance • In packet networks, events are random – Random packet arrivals – Random packet lengths • While at the physical layer we were concerned with bit-error-rate, at the network layer we care about delays – How long does a packet spend waiting in buffers ? – How large are the buffers ?

Random events Arrival process Packets arrive according to a random process Typically the arrival process is modeled as Poisson The Poisson process Arrival rate of n packets per second Over a small interval s P(exactly one arrival)=78 P(O arrivals)=1-78 P(more than one arrival)=0 It can be shown that P(narrivalsinintervalT) (T'e

Eytan Modiano Slide 4 Random events • Arrival process – Packets arrive according to a random process – Typically the arrival process is modeled as Poisson • The Poisson process – Arrival rate of λ packets per second – Over a small interval δ, P(exactly one arrival) = λδ P(0 arrivals) = 1 - λδ P(more than one arrival) = 0 – It can be shown that: P(narrivalsinintervalT)= − ( ) ! λ λ T e n n T

The poisson process P(narrivalsinintervalT)-(Te-7 n number of arrivals in t It can be shown that E[]=T En]=AT +T). 02=El(n-E(OJ)2 ]=En21-E[n]=AT

Eytan Modiano Slide 5 The Poisson Process P(narrivalsinintervalT) = − ( ) ! λ λ T e n n T n = number of arrivals in T It can be shown that, E[n] = T E[n ] = T + ( T) = E[(n -E[n]) ] = E[n ] -E[n] = T 2 2 2 2 22 λ λ λ σ λ

Inter-arrival times Time that elapses between arrivals (A) P(At) =1-P(0 arrivals in time t =1-et This is known as the exponential distribution Inter-arrival CDF=FIA(t)=1-e-it Inter-arrival PDF d/dt Fa(t)=e-lt The exponential distribution is often used to model the service times (Le, the packet length distribution

Eytan Modiano Slide 6 Inter-arrival times • Time that elapses between arrivals (IA) P(IA t) = 1 - P(0 arrivals in time t) = 1 - e-λt • This is known as the exponential distribution – Inter-arrival CDF = FIA (t) = 1 - e-λt – Inter-arrival PDF = d/dt FIA(t) = λe-λt • The exponential distribution is often used to model the service times (I.e., the packet length distribution)

Markov property(Memoryless) P(T≤b+1|7>t)=P(T≤0 Proof P≤1+1> (tto he dt u to+I A(+0)⊥-A(o e he dt (0) e P(T≤D Previous history does not help in predicting the future! Distribution of the time until the next arrival is independent of when the last arrival occurred!

Eytan Modiano Slide 7 Markov property (Memoryless) • Previous history does not help in predicting the future! • Distribution of the time until the next arrival is independent of when the last arrival occurred! PT t t T t PT t oof PT t t T t Pt T t t PT t e dt e dt e e e e t t t t t t t t t t t t t t ( | )( ) Pr : ( |) ( ) ( ) | | ( ) ≤+ > = ≤ ≤+ > = = = − − = − + − + − ∞ − + − ∞ − + ∫ ∫ 0 0 0 0 0 0 0 0 0 0 0 0 0 λ 0 λ λ λ λ λ λ − − − =− = ≤ λ λ λ ( ) ( ) ( ) t t t e e PT t 0 0 1

Example Suppose a train arrives at a station according to a Poisson process with average inter-arrival time of 20 minutes When a customer arrives at the station the average amount of time until the next arrival is 20 minutes Regardless of when the previous train arrived The average amount of time since the last departure is 20 minutes Paradox: If an average of 20 minutes passed since the last train arrived and an average of 20 minutes until the next train, then an average of 40 minutes will elapse between trains But we assumed an average inter-arrival time of 20 minutes! What happened? Answer: You tend to arrive during long inter-arrival times If you don't believe me you have not taken the t

Eytan Modiano Slide 8 Example • Suppose a train arrives at a station according to a Poisson process with average inter-arrival time of 20 minutes • When a customer arrives at the station the average amount of time until the next arrival is 20 minutes – Regardless of when the previous train arrived • The average amount of time since the last departure is 20 minutes! • Paradox: If an average of 20 minutes passed since the last train arrived and an average of 20 minutes until the next train, then an average of 40 minutes will elapse between trains – But we assumed an average inter-arrival time of 20 minutes! – What happened? • Answer: You tend to arrive during long inter-arrival times – If you don’t believe me you have not taken the T

Properties of the Poisson process Merging Property A2●→∑ Let A1, A2,... Ak be independent Poisson Processes of rate 21. 72....nk A=∑ A is also poisson of rate=∑ Splitting property Suppose that every arrival is randomly routed with probability pto stream 1 and (1-P) to stream 2 Streams 1 and 2 are Poisson of rates Ph and (1-p)n respectively AP 入 1-P

Eytan Modiano Slide 9 Properties of the Poisson process • Merging Property Let A1, A2, … Ak be independent Poisson Processes of rate λ1, λ2, … λ k • Splitting property – Suppose that every arrival is randomly routed with probability P to stream 1 and (1-P) to stream 2 – Streams 1 and 2 are Poisson of rates P λ and (1-P) λ respectively A = A is also Poisson of rate = ∑ ∑ i i λ λ P 1-P λ P λ(1−P) λ1 λ 2 λ k λ ∑ i

Queueing Models Customers server Que eue/buiter Model for Customers waiting in line Assembly line Packets in a network(transmission line Want to know Average number of customers in the system Average delay experienced by a customer Quantities obtained in terms of Arrival rate of customers (average number of customers per unit time) Service rate average number of customers that the server can serve per unit time Slide 10

Eytan Modiano Slide 10 Queueing Models • Model for – Customers waiting in line – Assembly line – Packets in a network (transmission line) • Want to know – Average number of customers in the system – Average delay experienced by a customer • Quantities obtained in terms of – Arrival rate of customers (average number of customers per unit time) – Service rate (average number of customers that the server can serve per unit time) server Queue/buffer Customers