Dynamic Routing

Internetworking – Lecture 6
Dynamic Routing
 An automated routing solution
 Defining a routing Protocol
 Design Considerations
 Metrics of Routing Protocols
 Categorising Routing protocols
An Automated Routing Solution
 We established that static routing is
unworkable;
 The more complex the networks the harder it

would be to manually manipulate the routing

tables;
 Therefore an automated approach to the

problem is required
Key Features of Dynamic Routing
 Key features of dynamic routing are:
◦ They learn about the network
◦ Automatically modify the routing tables
◦ Dynamically routing should be deployed on any
sized network
What is a Routing Protocol?
 A set of rules that allow 2 or more routers to
exchange information about the networks
they are connected to.
 It is based on an algorithm to solve the

communication problem
 Therefore it is a process that runs on the

router
 Algorithms used are based on graph theory

◦ e.g. the router is the dot and they link the

networks
Historical Links
 Early protocols are based on work by
R.Bellman; L.R.Ford; Edsger Dijkstra
 Bellman-Ford – Distance Vector algorithms
 Dijkstra – Shortest Path first algorithm

 No one protocol has solved all the routing

problems to-date!
Routing Protocols
Design Considerations
 What networking issues need to be taken into
consideration?
 How does the router collate the network data to
populate the routing table?
◦ The router needs to be able to communicate with others
◦ It needs to pass its own knowledge of networks to
another router
◦ It must be able to receive this data
◦ Therefore a common language of communication is
required
◦ Needs to communicate with routers, identify its status
and its known routes
Routing communication
 The language and vocabulary used is unique
to a particular protocol
 Therefore communication can only be

between routers using the same protocol

 Routers using different protocols can’t

communicate between each other

Routing Paths
 If more than one path is discovered to the same
destination the router has to evaluate the best
route to use in its table.
 What factors can you think of to do this?
 If a router crashes it can have a serious impact on
the network.
 A router needs to act quickly to this
 If a change to the network means the routing table
needs updating the delay until this is completed is
crucial – called “convergence”
Routing Paths
 Key problem in routing is a routing-loop
◦ – a packet going endlessly around the network without
reaching its destination delay in convergence is often the
cause of this.
 To route packets correctly the protocol must identify
if a network is utilising classless addressing and still
forward packets to the correct subnet.
 Generally subnets are ignored and the focus is on

single routes
 Protocols should use the bandwidth efficiently
 Traffic generated for router communication must be

limited to reduce the use of the bandwidth.

Characteristics of a Routing Protocol
 A routing Protocol must incorporate:
◦ -Robustness
◦ -Optimisation
◦ -Flexibility
◦ -Speed of convergence
◦ -Avoidance of routing loops
◦ -Support for classless addressing
◦ -Simplicity
Metric of Routing Protocols
 How a routing protocol decides which route is
best especially if more than 1 route is
discovered
◦ Each route is assigned a metric value
◦ There are a number of factors that the protocols
may take into consideration when assigning a
metric route
Metric of Routing Protocols
 Hop Count:
 Number of routers to traverse in order to reach the destination
 Path Length:
 A refinement of the hop count, Sum of per-link costs
 Bandwidth:
 Speed of the link between routers
 Delay:
 Time in milliseconds to cross a link
 Load:
 Congestion on link due to traffic
 Reliability:
 Based on bit error rates of path

 Not all routing protocols use all the variables

Categorising Dynamic Routing
Protocols
 Routing protocols are categorised by its
designed purpose
 Most protocols are interior protocols
◦ (Autonomous Systems is a system under a single
administration control)
 Interior Gateway Protocols:
◦ Developed to facilitate routing within autonomous
systems
 Exterior Gateway Protocols:
◦ Developed to facilitate routing between autonomous
systems
Distance Vector
“Routing by Rumour”
 Routing information is received from

immediate router neighbours only

 Sent as routing update packets
 These updates are then added to the router

tables
 Then communicate this information to their

own neighbouring routers

 Finally all routers learn the path to all

networks
View of Distance Vector Protocol
Communication

 Each router informs its neighbour of its directly connected

network
 Includes networks the router has learned from other

neighbours
 Share the metrics of the routes it knows
 In distance vector protocols the metrics is distance initially

hop count – e.g. how many routers the packet has to cross to
reach its destination, 3 hops = the metric 3
Distance Vector Protocol
 If two or more paths are discovered for the
same destination, the route with the lowest
hop count would win and be added to the
routing table

 Others have used bandwidth and delay to

determine the metric value
Vectors
 In distance vector protocols, vectors are
direction of the next hop
 Router stores the IP address of the router

with lower cost path

 Next hop is the next location packets will be

forwarded towards the destination

 Metric = distance Therefore

 Direction = vector Distance Vector
Metric
 Some protocols use hope count as the
determinate of the distance to the
destination, e.g. the lower the hop count the
better the route
 Works well on networks with a stable

transmission speed on network links –

smaller controlled systems
 In larger complex systems with varying

bandwidth, hop counts in isolation does not

work.
Network Diagram with two paths from
Network 1 to Network 4
Router A
 What does router A know?
 Its connected to network 1 via Ethernet 0
 Its connected to subnet1 via serial 0
 Its connected to subnet 4 via serial 1
 Network 2 is 1 hop away via serial 0
 Network 2 is 4 hops away via serial 1
 Network 3 is 2 hops away via serial 0
 Network 3 is 3 hops away via serial 1
 Network 4 is 3 hops away via serial interface 0
 Network 4 is 2 hops away via serial 1
Determine the Path
 If packet X is at network 1 and its destination is
network 4

 Router A identifies 2 paths:

◦ Path 1: 3 hops away serial 0
◦ Path2: 2 hops away serial 1
 With distance vector protocols path 2 will be
chosen based on hop count even though path 1
is faster as this is not a consideration.
 The limitations of this was identified therefore
bandwidth was used
Determine the best path now using
both hop and bandwidth
Router A
 Its connected to network 1 via Ethernet 0
 Its connected to subnet1 via serial 0
 Its connected to subnet 4 via serial 1
 Network 2, 1,544kbps via serial 0
 Network 2, 2 X 56K links and two 1,544kbps via
serial 1
 Network 3 1,544kbps via serial 0
 Network 3 2 X 56k, 1 X 1,544kbps via serial 1
 Network 4 3 X 1,544kbps serial 0
 Network 4 2 X 56K via serial 1
 Using bandwidth and hops, the 3 hops on
1,544kbps links would be selected
Other problems
 Hop count and bandwidth does improve the efficiency of
the routing
 One problem is distance vector consume network

resources since the full routing tables can be broadcast

every 30 seconds by default
 Routing tables can be very large
 This process can also impinge on convergence due to delay

incurred in sending so many update packets

 Distance vector protocols are prone to loops
 Routing loops are when two routers point to each other as

the path to a network

 Therefore the packets bounce to and fro between the

routers
Link state Routing Protocols
 Known as shortest path first
 Based on the Dijkstra algorithm
 Works on first hand information not “routing by
Rumours”
 Data is transmitted via Link State Advertisement
(LSA)
 It includes the state of the directly connected
routers Links
 Link state determines how many routers are out
there and what networks are connected to them
 Each router ends up with a topology map of the
system
Link-State Routing Protocols
 As only the link state is communicated and not the
whole routing table, therefore convergence is improved
 Also communication is initiated on a change of a link

state only
 The metric is bandwidth
 Therefore when the Dijkstra algorithm are run the

shortest quickest route is determined to populate the

routing table
 This is less prone to routing loops as each router has a

complete map of the system

 Routers are not tricked into routing packets back to

themselves.
Link state Routing Protocols
Improvements over Distance Vector
 Updated packets can be sent via multicast
rather than broadcast
 Reduces processing on devices that are not

routers
 Can be configured in a hierarchical fashion
 Reduces unnecessary traffic
Link state v Distance Vector
 Link state protocols calculate the distance to
another network
 Distance vector needs to be told this

information by another router

Routing Paths
 Multiple paths to a network may exist
 Not all routing protocols can actually install
multiple paths
 If only one path can be installed into the routing
table it should be the best path if this failed then
the next best would be installed
 If the multipath routing protocol is used a primary
path can be identified also packets can be routed
via multipaths to reduce throughput and load
balancing – multiplexing
 This improved network performance and reliability
Hierarchical Routing
 To reduce routing update on network
bandwidth routers can be configured in a
hierarchical topology
 Thereby routers are grouped into areas and
some of the updates are confined to those
areas
 Areas will communicate as well but the updates
are segregated on a need to know basis
 Helps with the management of the network
resources
Route Summarisation
 The concept of reducing the number of entries in
route tables while still facilitating paths to all known
networks
 Using subnetting means the route table increases

 Collating the data takes up network resources e.g.

bandwidth
 Large route tables means the lookup process takes

longer
 It also requires larger memory and CPU resources

 Route summarisation defines a single path to multiple

subnets
◦ Reduces the table size
Route Summarisation
 This has become a critical function of modern
networking
 Summarisation can be employed at the address

assignment level and organisation level

 Auto-summarisation is the term used when a routing

protocol summarises routes by default

 It only occurs when a router advertises a subnet of a

major network across network boundary

 Auto-summarisation can be disabled

 Route summarisation in discontinuous networks must

be employed with extreme caution to avoid dropped

routes or incorrectly routed packets
Summary
 An automated routing solution
 Defining a routing Protocol
 Routing Protocol Design Considerations
 Metrics of Routing Protocols
 Categorising Routing protocols