LM CCN Section 3.1: Modelling Delay
Computer and Communication Networks
Modelling Delay John Easton
1
Learning Objectives
! Understanding capacity utilisation – Packet vs. circuit switching
! Delay and loss performance of a network – Little’s formula
2
Capacity Utilisation
! Packet-switchingvs.circuitswitching
– Whypacketswitchingcansupportmoreusersinthesame
capacity?
! Circuit switching
– Capacityisallocatedregardlessoftransmissionstate – TotalCapacity=numberofusers
User Capacity
! Packet switching
– Capacityisnotallocatedperuser
– Toomanyusersalltransmittingsimultaneouslywillcausepackets
to back up on NEs
– Unlikelythatalluserstransmit100%ofthetime
– Effectiveincreaseinusers
3
1
LM CCN Section 3.1: Modelling Delay
Delay Analysis
! Communication networks share key resources
– Bandwidth, storage, processing capacity (e.g. on routers)
! Demand is largely unscheduled
– Peaks in traffic profile
– Congestion control techniques
! Inevitably, resources may be unavailable – Introduces delay
! Delay analysis is the process of modelling and understanding delays
4
Main Types of Delay
! Processingdelay
– Readingpacketheaders,performingchecksums,
routing decisions
– Orderofmicroseconds
! Queuingdelay
– Timewaitingforoutboundlinktobecomeavailable – Orderofmicrosecondstomilliseconds
! Transmissiondelay
– Timetakentopushpacketbitsontothelink – Orderofmicrosecondstomilliseconds
! Propagationdelay
– Timeforpackettotraverselink
– Distance/mediumpropagationspeed – Orderofmilliseconds(WAN)
5
Basics of Delay Modelling
! Delayscanappearatanylevelofabstractionofanetwork – IndividualNEs
– Subnet
– Network
! Keyperformance
measures:
Message, packet, etc. arrives
Delay Box
Router, switch, network
Time: T seconds
Message departs
– Timespentinsystem:T
– Numberofcustomersin system: N(t)
Lost / blocked messages
– Fractionofcustomersblocked:Pb
– Messages/secondpassingthroughthesystem:throughput ! Arrivalanddeparturearerandomprocesses
6
2
LM CCN Section 3.1: Modelling Delay
Number of Customers
! Number of customers at time t
! Fundamentally determined by
number of customers joining and leaving the network
– By design or through blocking
! If we assume:
Message, Delay Box
packet, Router, switch, Message
etc. departs network
– A(t) is number of arrivals (from time = 0 to time = t)
– B(t) is the number of blocked customers (same interval) – D(t) is the number of departing customers (same interval)
𝑁𝑡 =𝐴𝑡 −𝐷𝑡 −𝐵(𝑡)
arrives
Lost / blocked messages
Time: T seconds
7
Long-term Arrival and Departure
Message, Delay Box
packet, Router, switch, Message
etc. network departs
! Long term arrival rate, λ: 𝐴(𝑡)
𝜆 = lim customers/second !→# 𝑡
arrives
Lost / blocked messages
Time: T seconds
! Long term departure rate, throughput:
𝑡h𝑟𝑜𝑢𝑔h𝑝𝑢𝑡 = lim 𝐷(𝑡) customers/second !→# 𝑡
erf(x)
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
0 0.5 1 1.5 2 2.5 3 x
8
Blocking and Occupancy
! Fraction of blocked customers, Pb:
Message, Delay Box
packet, Router, switch, Message
etc. network departs
𝐵(𝑡) !→# 𝐴(𝑡)
𝑃 = lim $
arrives
Lost / blocked messages
Time: T seconds
! Average occupancy (number of customers in system) at any time:
1!
𝐸[𝑁] = lim C 𝑁 𝑡′ 𝑑𝑡′ customers !→# 𝑡 %
9
3
LM CCN Section 3.1: Modelling Delay
Long-term Arrival (Alternative)
! Consider typical sample of arrivals to the system, A(t)
! The time between the previous arrival and the arrival of customer n is 𝜏!
! The avg. arrival rate up to customer n is given by the number of customers / the total of the arrival intervals, so, the long term rate
is given by: 𝑛 𝜆 = lim
=
1
(𝜏’+𝜏( +⋯+𝜏&)/𝑛
=
1 𝐸[𝜏]
&→#𝜏’ +𝜏( +⋯+𝜏&
! Or, more simply, long-term arrival rate = 1 / mean inter-arrival time
10
Little’s Formula
! Determine average delay performance of complex systems
! Relates average time in system, E[T], to the long-term arrival rate, λ, and the average number of customers in the system, E[N]
𝐸𝑁 =𝜆𝐸[𝑇]
! This assumes no customers are blocked
T
Delay Box
A(t) D(t) N(t)
11
Derivation of Little’s Formula
T
! We know for non-blocking system that:
𝑁 𝑡 =𝐴 𝑡 −𝐷 𝑡 A(t) DelayBox D(t)
! For FIFO system: N(t) 𝑁𝑡 ≥0⟹𝐷(𝑡)≤𝐴𝑡
! Let T1 be the time between customer 1 arriving
(A(t) transitioning to 1), and departing (D(t) transitioning to 1)
– Likewise up to Tn
12
4
LM CCN Section 3.1: Modelling Delay
Derivation of Little’s Formula (Cont.)
! Plot A(t) & D(t) against time
! The time customer 1 spends in the system must then be the area T1, as the height of the rectangle is 1
! Assume at time tr A(t)=D(t) e.g. C5out
– Time average of customers in system up to time tr must be:
Time Average= ‘ ∑+(!”) 𝑇 !” )*’ )
13
Derivation of Little’s Formula (Cont.)
! From charts to right instantaneous area of arrivals / departures equivalent to occupancy integral from earlier, therefore:
1 !” 1+(!”)
𝑡 C 𝑁 𝑡′ 𝑑𝑡′ = 𝑡 P 𝑇)
. % . )*’
! By multiplying top & bottom by A(tr) we see:
𝐴(𝑡.) 1 !” 𝐴(𝑡.) 1 +(!”) 𝐴(𝑡)𝑡C𝑁𝑡′𝑑𝑡′= 𝑡 𝐴(𝑡)P𝑇)
..% . .)*’
! This states that the avg. number of customers up to time tr is the product of avg. arrival rate (RHS frac. 1) and the avg. time spent in system by first A(tr) customers (remainder of RHS)
5
4
3
2
1
T1
T2
T3
T4
T5
1
2
3
Time
4
5
6
7
3
2
4
5
7
8
10
2
11
13
1
1
3
6
9
12
14
15
1
2
3
Time
4
5
6
7
14
Derivation of Little’s Formula (Cont.)
! If we then assume the limiting case of the far RHS portion of the expression on the previous slide gives E[T]:
1 +(!”)
𝐸[𝑇]= lim P𝑇) +(!”)→# 𝐴(𝑡.) )*’
! Then Little’s Formula follows, as frac. 1 of the RHS in the limiting case becomes the long-term arrival rate giving:
𝐸𝑁 =𝜆𝐸[𝑇]
! Little’s Formula also be used for blocking systems, if the probability of blocking is included:
𝐸𝑁 =𝜆(1−𝑃$)𝐸[𝑇]
15
5
Occupancy
# of Arrivals # of Departures
LM CCN Section 3.1: Modelling Delay
Application of Little’s Formula
! Little’s formula can be applied to any system
– Single Tx line, a switch, or even a network
! Consider a non-blocking network of queuing systems
– Apply Little’s formula to find the average packet delay
! Little’s formula states that:
𝐸 𝑁&/! = 𝜆&/!𝐸[𝑇&/!]
! Thus, the expected delay is given by: 𝐸 𝑇&/! = 𝐸 𝑁&/! /𝜆&/!
16
Application of Little’s Formula (Cont.)
! For the mth NE (switch, etc.): 𝐸𝑁0 =𝜆0𝐸[𝑇0]
! The total packets in the network is the total of the packets in the individual NEs:
𝐸𝑁&/! =P 𝐸𝑁0 =P 𝜆0𝐸[𝑇0] 00
! Combined with expression from previous slide gives:
𝐸𝑇&/! = 1 P 𝜆0𝐸[𝑇0] 𝜆&/! 0
! The overall delay of the network depends on the overall arrival rate to network (offered traffic), the arrival rate to individual NEs (determined by internal routing), and the delay in each NE (determined by arrival rate, switching, and link capacity)
17
Summary
! Understanding capacity utilisation
! Delay and loss performance of a network – Little’s formula
18
6