Distance Vector
Routing Protocols
Routing Protocols and Concepts – Chapter 4
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 1
Objectives
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 2
Dynamic Routing
Dynamic routing protocols help the network administrator
overcome the time-consuming and exacting process of
configuring and maintaining static routes.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 3
Distance Vector Routing Protocols
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 4
Distance Vector Routing Protocols - RIP
Routing Information Protocol (RIP – RFC 1058) - key
characteristics:
Hop count is used as the metric for path selection.
If the hop count for a network is greater than 15, RIP
cannot supply a route to that network.
Routing updates are broadcast or multicast every 30
seconds, by default.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 5
Distance Vector Routing Protocols - IGRP
Interior Gateway Routing Protocol (IGRP) - Cisco
proprietary protocol - key design characteristics:
Bandwidth, delay, load and reliability are used to create
a composite metric.
Routing updates are broadcast every 90 seconds, by
default.
IGRP is the predecessor of EIGRP and is now obsolete.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 6
Distance Vector Routing Protocols - EIGRP
Enhanced IGRP (EIGRP) - Cisco proprietary distance vector
routing protocol - key characteristics:
It can perform unequal cost load balancing.
It uses Diffusing Update Algorithm (DUAL) to calculate
the shortest path.
There are no periodic updates as with RIP and IGRP
--Routing updates are sent only when there is a change in
the topology.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 7
Distance Vector Technology
•A router using distance vector routing protocols
knows 2 things:
Distance to final destination
Vector, or direction, traffic should be directed
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 8
Characteristics of Distance Vector routing
protocols:
Periodic updates – (30 seconds for RIP and 90 seconds for
IGRP) - inefficient because consume bandwidth and router
CPU resources - not aware of the network topology.
Neighbors - share a link and use the same routing protocol -
aware of remote network addresses through its neighbors.
Broadcast updates - sent to [Link] - Neighboring
routers with the same routing protocol will process the
updates - All other devices also process the update up to
Layer 3 before discarding it - Some distance vector routing
protocols multicast instead of broadcast.
Entire routing table is included with routing update
(exceptions) - Neighbors receiving these updates must
process the entire update to find pertinent information and
discard the rest.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 9
Routing Protocol Algorithm:
• Defines procedure for accomplishing following tasks:
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 10
Routing Protocol Characteristics
Criteria used to compare routing protocols includes:
Time to convergence
Scalability
Resource usage
Implementation & maintenance
Classless (Use of VLSM) or Classful
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 11
Routing Protocol Characteristics
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 12
Distance Vector Routing Protocols
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 13
Network Discovery - Cold Starts
Initial network discovery
Directly connected networks are initially placed in
routing table
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 14
Network Discovery - Initial Exchange of Routing
Information
If a routing protocol is configured then
Routers will exchange routing information
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 15
Network Discovery – Next Update
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 16
Network Discovery - Convergence
Routers continue to exchange routing information
If no new information is found then All routing tables in the
network contain the same network information -
Convergence state.
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 best path routes using update
information
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 17
Routing Table Maintenance - Periodic Updates:
RIPv1 & IGRP
These are time intervals in which a router sends out its entire
routing table.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 18
Routing Table Maintenance
RIP uses 4 timers
-Update timer
-Invalid timer
-Update has not been received to refresh an existing route after 180 seconds
(the default), route is marked as invalid by setting the metric to 16.
-route is retained in the routing table until the flush timer expires.
-Holddown timer
- Helps prevent routing loops during periods when the topology is
converging on new information.
- Once a route is marked as unreachable, it must stay in holddown long
enough for all routers in the topology to learn about the unreachable
network.
-Flush timer
- Default is set for 240 seconds - 60 seconds longer than the invalid timer. -
When the flush timer expires, the route is removed from the routing table.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 19
Routing Table Maintenance
RIP Timers - elapsed time since the last update
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 20
Routing Table Maintenance – Verifying Timer
Values
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 21
Routing Table Maintenance - Bounded Updates:
EIGRP
Partial updates triggered by topology changes containing
only the changes.
Bounded - only those that need the information are
updated.
Non periodic
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 22
Routing Table Maintenance - Triggered Updates
- For RIP When There is Topology Change.
Conditions in which triggered updates are sent
Interface changes state
Route entered/exited unreachable state
Route is placed in routing table
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 23
Routing Table Maintenance - Triggered Updates
Using only triggered updates would be sufficient if there
were a guarantee that the wave of updates would reach
every appropriate router immediately.
Problems with triggered updates:
Packets containing the update message can be dropped or
corrupted by some link in the network.
The triggered updates do not happen instantaneously.
It is possible that a router that has not yet received the
triggered update will issue a regular update at just the
wrong time, causing the bad route to be reinserted in a
neighbor that had already received the triggered update.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 24
Routing Table Maintenance - Random Jitter
Synchronized updates
- A condition where multiple routers on multi
access LAN segments transmit routing updates
at the same time.
Problems with synchronized updates
-Bandwidth consumption
-Packet collisions
Solution to problems with synchronized updates
- Use of random variable
called RIP_JITTER (0-15%)
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 25
Routing Loops
A condition in which a packet is continuously transmitted within a
series of routers without ever reaching its destination.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 26
Routing Loops
Routing loops may be caused by:
Incorrectly configured static routes
Incorrectly configured route redistribution
Slow convergence
Incorrectly configured discard routes
Routing loops can create the following 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
Packets may get lost in "black holes."
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 27
Routing Loops
Mechanisms available to eliminate Routing loops:
Defining a maximum metric to prevent count to
infinity
Holddown timers
Split horizon
Route poisoning or poison reverse
Triggered updates
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 28
Routing Loops - Count to Infinity
This is a routing loop whereby packets bounce infinitely
around a network - inaccurate routing updates increase the
metric value to "infinity"
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 29
Routing Loops - Setting a maximum
Distance Vector routing protocols set a specified metric
value to indicate infinity
Once a router “counts to infinity” it marks the route as
unreachable
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 30
Routing Loops - Holddown timers
Loops can be caused by:
Flapping route - triggered updates might react too
quickly and unknowingly create a routing loop.
Periodic update that is sent by the routers during the
instability.
Holddown timers allow a router not to accept any changes
to a route for a specified period of time.
Holddown timers also help prevent the count to infinity
condition.
Holddown timers are used to prevent regular update
messages from inappropriately reinstating a route that may
have gone bad.
Allows routing updates to propagate through network with
the most current information.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 31
Routing Loops - Holddown timers
Holddown timers work in the following way:
1. A router receives an update from a neighbor indicating that a
network that previously was accessible is now no longer accessible.
2. The router marks the network as possibly down and starts the
holddown timer.
3. If an update with a better metric for that network is received from
any neighboring router during the holddown period, the network is
reinstated and the holddown timer is removed.
4. If an update from any other neighbor is received during the
holddown period with the same or worse metric for that network,
that update is ignored.
5. Routers still forward packets to destination networks that are
marked as possibly down. This allows the router to overcome any
issues associated with intermittent connectivity.
If the destination network truly is unavailable and the
packets are forwarded, black hole routing is created and
lasts until the holddown timer expires.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 32
Routing Loops - Split Horizon Rule
A router should not advertise a network through the
interface from which the update came.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 33
Routing Loops - Route poisoning
Route poisoning is used to mark the route as unreachable
in a routing update that is sent to other routers.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 34
Routing Loops - Split horizon with poison Reverse
The rule for split horizon with poison reverse states that
when sending updates out a specific interface, designate
any networks that were learned on that interface as
unreachable.
Split horizon is enabled by default.
However split horizon with poison reverse may not be the
default on all IOS implementations.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 35
Routing Loops - TTL
TTL field ensures that even in the case of a routing loop
packets will not loop endlessly in the network.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 36
Routing Protocols Today
Only two choices for distance vector routing protocols – RIP or EIGRP
Factors used to determine whether to use RIP or EIGRP include
Network size
Compatibility between models of routers
Administrative knowledge
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 37
Routing Protocols Today - RIP
Features of RIP:
Supports split horizon & split horizon with poison reverse
Capable of load balancing up to six equal cost paths. (default is
four)
Easy to configure
Works in a multi vendor router environment
RIPv2 introduced the following improvements to RIPv1:
Includes the subnet mask in the routing updates, making it a
classless routing protocol that Supports variable length subnet mask
(VLSM).
Has authentication mechanism to secure routing table updates.
Uses multicast addresses instead of broadcast.
Supports manual route summarization.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 38
Routing Protocols Today - EIGRP
Features of EIGRP:
Triggered updates
EIGRP hello protocol used to establish neighbor
adjacencies
Supports VLSM & manual route summarization - create
hierarchically structured large networks.
Use of topology table to maintain all routes (not only
the best path
Classless distance vector routing protocol
Cisco proprietary protocol
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 39
Routing Protocols Today - EIGRP
Advantages of EIGRP:
Although routes are propagated in a distance vector
manner, the metric is based on minimum bandwidth and
cumulative delay of the path rather than hop count.
Fast convergence due to Diffusing Update Algorithm
(DUAL) route calculation - DUAL allows the insertion of
backup routes into the EIGRP topology table.
Bounded updates mean that EIGRP uses less bandwidth,
especially in large networks with many routes.
EIGRP supports multiple network layer protocols through
Protocol Dependent Modules, which include support for IP,
IPX, and AppleTalk.
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 40
Summary
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 41
ITE PC v4.0
Chapter 1 © 2007 Cisco Systems, Inc. All rights reserved. Cisco Public 42