Eytan Modiano Slide 1 16.36: Communication Systems Engineering Lecture 17/18: Delay Models for Data Networks Eytan Modiano Eytan Modiano Slide 2 Packet Switched Networks Packet Network PS PS PS PS PS PS PS Buffer PacketSwitch Messages broken intoPackets that are routed To their destination 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 ? 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(n arrivals in interval T) = ? () ! λ λ Te n nT Eytan Modiano Slide 5 The Poisson Process P(n arrivals in interval T) = ? () ! λ λ Te n nT 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 22 22 2 2 λ λλ σλ Eytan Modiano Slide 6 Inter-arrival times ? Time that elapses between arrivals (IA) P(IA <= t) = 1 - P(IA > t) = 1 - P(0 arrivals in time t) = 1 - e - λλλλ t ? This is known as the exponential distribution – Inter-arrival CDF = F IA (t) = 1 - e - λλλλ t – Inter-arrival PDF = d/ dt F IA (t) = λλλλ e - λλλλ t ? The exponential distribution is often used to model the servicetimes (I.e., the packet length distribution) 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 ofwhen the last arrival occurred! PT t t T t PT t oof PT t t T t Pt T t t PT t ed t ed t e e ee t t tt t t t t tt t t tt (| ) ( ) Pr : (| ) () () | | () ≤+ > = ≤ ≤+ > = <≤ + > == ? ? = ?+ ? + ? ∞ ? + ?∞ ?+ ∫ ∫ 0000 00 0 0 0 0 0 0 0 0 λ λ λ λ λ λ λ ?? ? ? =? = ≤ λ λ λ () () () t t t e eP T t 0 0 1 Eytan Modiano Slide 8 Example ? Suppose a train arrives at a station according to a Poisson processwith average inter-arrival time of 20 minutes ? When a customer arrives at the station the average amount of timeuntil 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 trainarrived and an average of 20 minutes until the next train, then anaverage 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 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 tostream 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 = ii ∑∑ λ λ P 1-P λ P λ(1? P) λ 1 λ 2 λ k λ i ∑ Eytan Modiano Slide 1 0 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 serveper unit time) server Queue/buffer Customers Eytan Modiano Slide 1 1 Analyzing delay in networks (queueing theory) ? Little ’s theorem – Relates delay to number of users in the system – Can be applied to any system ? Simple queueing systems (single server) – M/M/1, M/G/1, M/D/1 – M/M/m/m ? Poisson Arrivals => – λλλλ = arrival rate in packets/second ? Exponential service time => – μμμμ = service rate in packets/second P e ( ( n arrivals in interval T) = T) n! nT λ λ ? P (service time < T) = 1 - e -T μ Eytan Modiano Slide 1 2 Little’ s theorem ? N = average number of packets in system ? T = average amount of time a packet spends in the system ? λλλλ = arrival rate of packets into the system (not necessarily Poisson) ? Little ’s theorem: N = λλλλ T – Can be applied to entire system or any part of it – Crowded system √√√√ long delays On a rainy day people drive slowly and roads are more congested! Network (system) (N,T) λλλλ packet per second Eytan Modiano Slide 1 3 Proof of Little’s Theorem ? A(t) = number of arrivals by time t ? B(t) = number of departures by time t ? t i = arrival time of i th customer ? T i = amount of time i th customer spends in the system ? N(t) = number of customers in system at time t = A(t) - B(t) A(t), B(t) t1 t2 t3 t4 A(t) T1 T2 T3 T4 B(t) N T t T T At TA t T N T t At t T At T t i i At t i i At i i At i i At i i At == ? = == = →∞ = →∞ = = == ∑∑ ∑ ∑∑ lim , lim () () ( () ) () () () () () () 11 1 11 λ Eytan Modiano Slide 1 4 Application of little ’s Theorem ? Little ’s Theorem can be applied to almost any system or part of it ? Example: 1) The transmitter: D TP = packet transmission time – Average number of packets at transmitter = λλλλ D TP = ρρρρ = link utilization 2) The transmission line: D p = propagation delay – Average number of packets in flight = λλλλ D p 3) The buffer: D q = average queueing delay – Average number of packets in buffer = N q = λλλλ D q 4) Transmitter + buffer – Average number of packets = ρρρρ + N q server Queue/buffer Customers Eytan Modiano Slide 1 5 Single server queues ? M/M/1 – Poisson arrivals, exponential service times ? M/G/1 – Poisson arrivals, general service times ? M/D/1 – Poisson arrivals, deterministic service times (fixed) Server μμμμ packet per second ???? Service time = 1/ μμμμ λλλλ packet per second buffer Eytan Modiano Slide 1 6 Markov Chain for M/M/1 system ? State k => k customers in the system ? P(I,j) = probability of transition from state I to state j – As δδδδ => 0, we get: P(0,0) = 1 - λλλλ δδδδ , P(j,j+1) = λλλλ δδδδ P(j,j) = 1 - λλλλ δδδδ ???? μμμμ δδδδ P(j,j-1) = μμμμ δδδδ P(I,j) = 0 for all other values of I,j. ? Birth-death chain: Transitions exist only between adjacent states – λλλλ δδδδ ,,,, μμμμ δδδδ are flow rates between states 0 1 2 k λδ λδ λδ λδ μδ μδ μδ μδ 1?λδ Eytan Modiano Slide 1 7 Equilibrium analysis ? We want to obtain P(n) = the probability of being in state n ? At equilibrium λλλλ P(n) = μμμμ P(n+1) for all n – P(n+1) = ( λλλλ //// μμμμ )P(n) = ρρρρ P(n), ρρρρ ==== λλλλ //// μμμμ ? It follows: P(n) = ρρρρ n P(0) ? Now by axiom of probability: Pn P P P Pn i n i n () () () () () ( ) = ?= ? = ?= ? =? = ∞ = ∞ ∑ ∑ 1 0 0 1 1 01 1 0 0 ρ ρ ρ ρρ Eytan Modiano Slide 1 8 Average queue size ? N = Average number of customers in the system ? The average amount of time that a customer spends in thesystem can be obtained from Little’ s formula (N= λλλλ T => T = N/ λλλλ ) ? T includes the queueing delay plus the service time (Service time = D TP = 1/ μμμμ ) – W = amount of time spent in queue = T - 1/ μμμμ => ? Finally, the average number of customers in the buffer can beobtained from little ’ s formula Nn P n n N n n n == ? = ? = ? = ? = ? = ∞ = ∞ ∑∑ () ( ) / / 00 1 1 11 ρρ ρ ρ ρ ρ λμ λμ λ μλ W = ? ? 11 μλ μ T = ? 1 μλ NW N Q == ? ?= ? λ λ μλ λμ ρ Eytan Modiano Slide 1 9 Example (fast food restaurant) ? Customers arrive at a fast food restaurant at a rate of 100 per hourand take 30 seconds to be served. ? How much time do they spend in the restaurant? – Service rate = μμμμ = 60/0.5=120 customers per hour – T = 1/ μμμμ ???? λλλλ = 1/(120-100) = 1/20 hrs = 3 minutes ? How much time waiting in line? – W = T - 1/ μμμμ = 2.5 minutes ? How many customers in the restaurant? – N = λλλλ T = 5 ? What is the server utilization? – ρρρρ = λλλλ //// μμμμ = 5/6 Eytan Modiano Slide 2 0 Packet switching v s . Circuit switching 1 2 3 N 12 N Packets generated at random times TDM, Time Division MultiplexingEach user can send μμμμ /N packets/sec and has packet arriving at rate λλλλ /N packets/sec 1 2 3 N D =+ ? 1/ (/ ) () μ λμ μλ DN N =+ ? / (/ ) () μ λμ μλ λλλλ /N λλλλ /N λλλλ /N λλλλ /N λλλλ /N Statistical Mutliplexer Buffer μμμμ packets/sec λλλλ M/M/1 formula M/M/1 formula Eytan Modiano Slide 2 1 Circuit (tdm/fdm) vs . Packet switching Av e r a g e P a c k e t Se r v i c e T i m e (s l o t s ) 1 10 10 0 00 . 2 0 . 4 0 .6 0 . 8 1 Tot a l t r af f i c l o a d , pa c k e t s p e r s l o t Average Service Time TD M w i t h 2 0 so u r ces Id e a l S t at i s t i cal Mu l t ipl e x i n g (M / D /1 ) Eytan Modiano Slide 2 2 Delay formulas ? M/G/1 ? M/M/1 ? M/D/1 DX =+ ? λμ μλ / DX =+ ? λμ μλ / () 2 DX X =+ ? λ λμ 2 21 (/ ) Delay components:Service (transmission) time (LHS)Queueing delay (RHS) Use Little’ s Theorem to compute N, the average number of customersin the system Eytan Modiano Slide 2 3 Blocking Probability ? A circuit switched network can be viewed as a Multi-serverqueueing system – Calls are blocked when no servers available - “busy signal ” – For circuit switched network we are interested in the call blockingprobability ? M/G/m/m system – Poisson call arrivals and General call duration distribution – m servers => m circuits – Last m indicated that the system can hold no more than m users ? Erlang B formula – Gives the probability that a caller finds all circuits busy P m n B m n n m = = ∑ (/ ) / ! (/ ) / ! λμ λμ 0 Eytan Modiano Slide 2 4 Erlang B formula ? Used for sizing transmission line – How many circuits does the satellite need to support? – The number of circuits is a function of the blocking probability that wecan tolerate Systems are designed for a given load predictions and blocking probabilities(typically small) ? Example – Arrival rate = 4 calls per minute, average 3 minutes per call – How many circuits do we need to provision? Depends on the blocking probability that we can tolerate Circuits P B 20 1 % 15 8 % 7 3 0 %