CCE1030 Computer Networking
Lecture 18
Link-State / Distance Vector Routing
Usama Arusi
January 2019 CCE1030 Usama Arusi 1
Lecture Content
• Link-State Routing
• Protocols
• Distance Vector Routing
• Protocols
• Distance Vector Routing Protocols Algorithms
• Network Discovery
• Routing Table Maintenance
• Routing Loops
January 2019 CCE1030 Usama Arusi 2
Link-State Routing
• Link state routing protocols
• are one of the two main classes of routing protocols used
in packet switching networks
• also known as shortest path first algorithms
January 2019 CCE1030 Usama Arusi 3
Link-State Routing
• These protocols are built around Dijkstra’s SPF
• every node constructs a map of the connectivity to the
network, in the form of a graph, showing which nodes are
connected to which other nodes
• each node then independently calculates the next best
logical path from it to every possible destination in the
network
January 2019 CCE1030 Usama Arusi 4
Link-State Routing
• The shortest path to a destination is not necessarily
the path with the least number of hops
January 2019 CCE1030 Usama Arusi 5
Link-State Routing
Link-State Routing Process
How routers using Link State Routing Protocols reach
convergence
• each router learns about its own directly connected networks
• exchange hello packet to “meet” other directly connected link state
routers
January 2019 CCE1030 Usama Arusi 6
Link-State Routing
Link-State Routing Process cont…
• each router then builds its own Link State Packet (LSP) which includes
information about neighbours such as neighbour ID, link type, &
bandwidth
January 2019 CCE1030 Usama Arusi 7
Link-State Routing
Link-State Routing Process cont…
• after the LSP is created the router floods it to all neighbours who then
store the information and then forward it until all routers have the same
information
January 2019 CCE1030 Usama Arusi 8
Link-State Routing
Link-State Routing Process cont…
• once all the routers have received all the LSPs, they then construct a topological
map of the network which is used to determine the best routes to a destination
January 2019 CCE1030 Usama Arusi 9
Link-State Routing
Constructing a link state data base
• Routers use a database to construct a topology map of the
network
January 2019 CCE1030 Usama Arusi 10
Link-State Routing
Once the SPF algorithm has determined the shortest
path routes, these routes are placed in the routing table
January 2019 CCE1030 Usama Arusi 11
Link-State Routing Protocols
Advantages of a Link-State Routing Protocol
1. Builds a topological map
2. Routers can independently determine the shortest path to
every network
3. Fast convergence time
4. A periodic / event driven routing updates
5. Use of Link State Packets (LSP)
January 2019 CCE1030 Usama Arusi 12
Link-State Routing Protocols
Requirements for using a link state routing protocol
• Memory
• Typically link state routing protocols use more memory
• Processing
• More CPU processing is required of link state routing protocols
• Bandwidth
• Initial startup of link state routing protocols can consume lots of
bandwidth
• Examples of link state routing protocols
• Open Shortest Path First (OSPF)
• Intermediate System-Intermediate System (IS-IS)
January 2019 CCE1030 Usama Arusi 13
Distance Vector Routing
Protocols
• Is the second of the two major classes of intra
domain routing protocols
• Routes are advertised as vectors of (distance,
direction), where distance is defined in terms of a
metric and direction is defined in terms of the next-
hop router
• For example:
• Destination A is a distance of 5 hops away, in the direction of
next-hop router X
January 2019 CCE1030 Usama Arusi 14
Distance Vector Routing
Protocols
Characteristics of Distance Vector routing protocols:
• Periodic updates
• These are time intervals in which a router sends out its entire routing
table
• ranges from 10 seconds to 90 seconds. The issue is if updates are sent too
frequently, congestion may occur; if updates are sent too infrequently,
convergence time may be unacceptably high
January 2019 CCE1030 Usama Arusi 15
Distance Vector Routing
Protocols
Characteristics of Distance Vector routing protocols:
• Neighbours
• A DV routing protocol sends its updates to neighbouring routers and
depends on them to pass the update information along to their
neighbours
January 2019 CCE1030 Usama Arusi 16
Distance Vector Routing
Protocols
Characteristics of Distance Vector routing protocols:
• Broadcast updates
• On becoming active on a network a router announce its own presence sending
the updates to the broadcast address. Neighbouring routers speaking the same
routing protocol will hear the broadcasts and take appropriate action
• Full Routing Table Updates
• Most distance vector routing protocols take the very simple approach of telling
their neighbours everything they know by broadcasting their entire route table.
Neighbours receiving these updates glean the information they need and discard
everything else
January 2019 CCE1030 Usama Arusi 17
Distance Vector Routing
Protocols Algorithms
An algorithm is a procedure for accomplishing a certain
task
January 2019 CCE1030 Usama Arusi 18
Distance Vector Routing
Protocols Algorithms
• Distance-vector routing protocols use the Bellman–
Ford algorithm, Ford–Fulkerson algorithm, or DUAL
FSM to calculate paths
January 2019 CCE1030 Usama Arusi 19
Network Discovery
• Router initial start up (Cold Starts)
• Initial network discovery
• Directly connected networks are initially placed in routing table
January 2019 CCE1030 Usama Arusi 20
Network Discovery
• Initial Exchange of Routing Information
• Routers will exchange routing information
• Router checks update for new information
• New information is stored in routing table
January 2019 CCE1030 Usama Arusi 21
Network Discovery
• Router convergence is reached when
• All routing tables in the network contain the same network
information and no new information is found
January 2019 CCE1030 Usama Arusi 22
Network Discovery
• Convergence must be
reached before a network
is considered completely
operable
• Speed of achieving
convergence consists of 2
interdependent
categories:
• Speed of broadcasting
routing information
• Speed of calculating routes
January 2019 CCE1030 Usama Arusi 23
Routing Table Maintenance
Different protocols use different processes to maintain the
routing table.
• RIP uses 4 update timers
• Update timer
• Send out the contents of its entire routing table every 30 (default)
• Invalid timer
• If a router does not receive an advertisement for a route in 180 seconds, the
route is marked as unreachable and goes into holddown
• Holddown timer
• The number of seconds that waited before accepting any new updates for
the route that is in holddown
• Flush timer
• how many seconds since we received the last valid update until we throw
the route away
January 2019 CCE1030 Usama Arusi 24
Routing Table Maintenance
• Bounded Updates: EIGRP
• Updates are sent only when the metric for a route changes. They
are:
• Partial updates - the update only includes information about the route changes
• Bounded - the propagation of partial updates sent only to those routers that are
affected by the change
• Triggered by topology changes - sends these incremental updates when the state
of a destination changes
• Non periodic
January 2019 CCE1030 Usama Arusi 25
Routing Loops
• A condition in which a packet is continuously transmitted within
a series of routers without ever reaching its destination
• Causes:
• Incorrectly configured static routes
• Incorrectly configured route redistribution
• Slow convergence
• Incorrectly configured discard routes
• Resulting issues
• Excess use of bandwidth
• CPU resources may be strained
• Network convergence is degraded
• Routing updates may be lost or not processed in a timely manner
January 2019 CCE1030 Usama Arusi 26
Routing Loops
This endless loop in the network is called Count to Infinity
• DV protocols set a specified metric value to indicate
infinity - Once a router “counts to infinity” it marks the
route as unreachable
January 2019 CCE1030 Usama Arusi 27
Routing Loops
• Preventing loops with holddown timers
• Holddown timers allow a router to not accept any changes to a
route for a specified period of time
• Allows routing updates to propagate through network with the most
current information
January 2019 CCE1030 Usama Arusi 28
Routing Loops
Preventing loops with the Split Horizon Rule
• A router should not advertise a network through the
interface from which the update came
January 2019 CCE1030 Usama Arusi 29
