LM CCN Section 2.1: Link State and Distance Vector Routing
Computer and Communication Networks
Link State and Distance Vector Routing John Easton
1
Learning Objectives
! Understand the basics of (interior) routing – How do we identify possible routes?
– How do we determine cost?
– How do we deal with failures?
2
What is Routing?
! Routing is the process of figuring out how to get from A to B
! How do you pick a route when driving? – Fastest?
– Least complex?
– Avoid congestion?
– Spend the smallest amount in tolls?
! All these have equivalents in network routing
– Minimise packet delay
– Minimise hop count
– Maximise available bandwidth
– Minimise financial cost (charges from infrastructure
providers)
3
1
LM CCN Section 2.1: Link State and Distance Vector Routing
Internet Topology
! The Internet is a network of networks communicating via the IP protocol
– Each network is an Autonomous System (AS)
– Routing within an AS is performed by an Interior Gateway (routing) Protocol (IGP)
– Examples of IGPs include IS-IS, OSPF (link-state) and RIP (distance vector)
4
Within an Autonomous System
! Internally, Autonomous Systems are dynamic – They change structure, add and loose
devices
! IGPs require flexible approaches to routing
– Links are constantly changing
– You can’t pre-configure all the possible
paths
– Compact methods of storing and updating
path information is required to maximise scalability
! Speed and storage at routers
5
Functions of a Routing System
! What functions must a good network routing protocol provide?
! Essential
– Routing: path identification and selection
– Forwarding: transfer of packets from Network Element
(NE) inputs to outputs
– Priority and scheduling: Determination of packet transmission order
! Optional
– Congestion control, segmentation and reassembly, security
6
2
LM CCN Section 2.1: Link State and Distance Vector Routing
Routing Table
! How to implement an IGP?
! Create a routing table on each
device
– Table stores minimal information needed to pass packet along the right path
! To construct, we may need to know:
– State of links, congestion, delays, etc. of network
! The network must distribute state information
– What, how often, how far (flood vs. neighbours)?
! Single vs. multiple route approaches
Destination
C
D
E
R
Next Hop Distance
A2
C4
R5
C4
7
Approaches
! What we store and exchange depends on approach ! Distance Vector Protocols
– Neighbours exchange lists of distances to known destinations
– Best next-hop determined at each node
– Example is distributed Bellman-Ford ! Link State Protocols
– Link state information flooded to all routers in network – Routers have complete topology information
– Route calculated based on desired criteria
! Likely a minimal cost of some kind (e.g. shortest path) – Example is Dijkstra (centralised)
8
The Routing Problem
! Route diversity
! The graph shows three routes from 1 to 6
– Many others are available ! Which route do we pick?
! Classic graph theory problem
– Shortest path
! How do we apply criteria?
– Weights on edges may all be 1 (minimal hop)… – …or 1/bandwidth (widest pipes)…
– …or an access charge (minimal financial cost)
9
3
LM CCN Section 2.1: Link State and Distance Vector Routing
All Roads Lead to Rome
! To find the shortest path to Rome from another city (say Pompeii), simply add local costs
– Cost of reaching neighbour (say Naples)
– Cost from Naples to Rome ! Select the minimum
! DPompeii = DNaples + CPompeii>>Naples
CPompeii>>Naples = 2 Naples
Rome
Pompeii
DNaples = Total cost to Rome = 7
10
Shortest Paths
! Many algorithmic solutions, Dijkstra’s algorithm is the most famous – Path between two specified nodes
– O(V2), later implementations in O(E + V*log(V))
! Link-state approach, requires known topology
! Originally used for inter-city transport optimisation in Netherlands
– Later used to minimise wiring length on computer back panel
! Forms a shortest-path tree
– Trace back to find actual route
! No negative edge weights
– Slower alternatives include Bellman-Ford
3
44
21
2 3
11
Dijkstra’s Algorithm
! Set-up:
– Setdist[v]to∞andprev[v]toundefinedforallv – Addallvtoqueue
– Setdist[source]to0
! Whilequeuenotempty:
– Selectthenode,u,withtheminimumdist[u]fromthequeue(vin
first instance due to set-up step) and remove from queue
– Foreachneighbour,v,ofu:
! Set temp = dist[u] + length(u,v) //Add distance (u to v) to dist[u] ! If temp < dist[v] //new shorter route to v
– dist[v] = temp
– prev[v] = u ! returndist[],prev[]
12
4
LM CCN Section 2.1: Link State and Distance Vector Routing
Worked Example
Source
2
3
B
1
C
E
D
3
4
2
A
4
F
Target
13
Dijkstra’s Algorithm – Worked Example
14
Bellman-Ford Algorithm
! Findshortestpathsfromallnodestodestination ! Set-up
– Create“columnpernode”nexthop/distancetable
– Set“Initial”Di=∞,next=-1forallnodes
– ForIteration1,setDandnextfornodesdirectlyconnectedtotarget
! Update
– Basedonpreviousiteration,ifneighbourdistance+costto
neighbour < previous iteration cost to target, update cost and next
hop
– Repeatuntilnochanges
! Pathcanbereadfromfinaliteration
15
5
LM CCN Section 2.1: Link State and Distance Vector Routing
Worked Example
Source
2
3
B
1
C
E
D
3
4
2
A
4
F
Target
16
Bellman-Ford – Worked Example
17
Link Failures
! Link failures mean routes need to be updated
! On detecting a link failure, most protocols flood an
update to all routers
– Triggers recalculation of routes
! Algorithms such as Bellman-Ford can recover gracefully – Iterate from previous cycle
! Link state protocols require complete recalculation
18
6
LM CCN Section 2.1: Link State and Distance Vector Routing
Worked Example
Source
2
3
B
1
C
E
D
3
4
2
A
4
F
Target
19
Link Failures – Worked Example
20
Summary
! Understand the basics of (interior) routing – How do we identify possible routes?
– How do we determine cost?
– How do we deal with failures?
21
7