Inter-arrival times Time that elapses between arrivals(A) P(A<=t)=1-P(A>t) =1-P(0 arrivals in time t This is known as the exponential distribution Inter-arrival CDF FIA(t=1-e-t Inter-arrival PDF d/dt Fa(t=he-t The exponential distribution is often used to model the service times(e the packet length distribution
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 = 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) Eytan Modiano Slide 6
Markov property( Memoryless) P(T≤6+|T>t0)=P(T≤1) Pr oof P(T≤+|7>10) P(t<T≤+1) P(T>to he- dt e e A(0) A(0) P(T≤t) 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!
Markov property (Memoryless) P ( T ≤ t0 + t | T > t0 ) = P ( T ≤ t) Pr oof : P ( T ≤ t0 + t | T > t0 ) = P ( t0 < T ≤ t0 + t) P ( T > t0 ) t 0 +t ∫ λe − λtdt − e − λt |t0 t0 + t − e − λ ( t +t 0 ) + e − λ ( t0 ) t 0 = ∞ = = ∞ e − λ ( t0 ) ∫ λe− λtdt − e − λt | t 0 t0 = 1 − e − λt = P ( T ≤ t) • 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
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 ha appened?
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? Eytan Modiano Slide 8
Properties of the Poisson process Merging property )→∑k k Let A1, A2,... Ak be independent Poisson Processes of rate 2122..k A=∑A1 is also poisson of rate=∑41 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 Ph and (1-P)h respectively 入P 入 p(1-P)
Properties of the Poisson process • Merging Property λ1 λ2 ∑ λi λk Let A1, A2, … Ak be independent Poisson Processes of rate λ1, λ2, … λk A = ∑ Ai is also Poisson of rate = ∑ λi • Splitting property – Suppose that every arrival is r andomly 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 P 1-P λP λ λ(1−P) Eytan Modiano Slide 9
Queueing Models Customers server Queue/buffer Model for Customers waiting in line Assembly line Packets in a network(transmission line) Want to know Average delay experienced by a customer 3 Average number of customers in the syster 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)
Queueing Models Customers Queue/buffer • 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 Eytan Modiano Slide 10