Lectures 5&6 6263/1637 Introduction to Queueing Theory Eytan Modiano MIT LIDS
Lectures 5 & 6 6.263/16.37 Introduction to Queueing Theory Eytan Modiano MIT, LIDS Eytan Modiano Slide 1
Packet Switched Networks Messages broken into Packets that are routed To their destination 一烟 Packet Network APS Buffer Packet →工m Switch
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 Eytan Modiano Slide 2
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 In circuit switched networks want to know call blocking probability How many circuits do we need to limit the blocking probability?
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 ? • In circuit switched networks want to know call blocking probability – How many circuits do we need to limit the blocking probability? Eytan Modiano Slide 3
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)=n8+oo) P(O arrivals)=1-n8+o(8 P(more than one arrival =08 Where0(6y6→>08→>0. It can be shown that: 27 P(n arrivalsininterval T (r)e
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(δ) Where 0(δ)/ δ −> 0 �� δ −> 0. – It can be shown that: P(n arrivalsininterval T)= ( λT)n e−λT n! Eytan Modiano Slide 4
The poisson process P(n arrivalsinintervalT) (A”e n= number of arrivals in t It can be shown that EIn= nT E[r21]=T+(T)2 2=E[(n-E[n)2]=E[n2]-E[m]2=T
The Poisson Process P(n arrivalsininterval T) = ( λT ) n e − λT n! n = number of arrivals in T It can be shown that, E[n] = λT E[n 2 ] = λT + (λT) 2 σ 2 = E[(n -E[n]) 2 ] = E[n 2 ] - E[n] 2 = λT Eytan Modiano Slide 5