Distance Vector Routing Protocols

Distance vector routing protocols include RIP, IGRP, and EIGRP.

RIP

Over the years, RIP has evolved from a classful routing protocol (RIPv1) to a classless routing protocol (RIPv2). RIPv2 is a standardized routing protocol that works in a mixed vendor router environment. Routers made by different companies can communicate using RIP. It is one of the easiest routing protocols to configure, making it a good choice for small networks. However, RIPv2 still has limitations. Both RIPv1 and RIPv2 have a route metric that is based only on hop count and which is limited to 15 hops.

Features of RIP:

• Supports split horizon and split horizon with poison reverse to prevent loops.
• Is capable of load balancing up to six equal cost paths . The default is four equal cost paths.

RIPv2 introduced the following improvements to RIPv1:

• Includes the subnet mask in the routing updates, making it a classless routing protocol.
• Has authentication mechanism to secure routing table updates.
• Supports variable length subnet mask (VLSM).
• Uses multicast addresses instead of broadcast.
• Supports manual route summarization.

IGRP

Interior Gateway Routing Protocol (IGRP) is a proprietary protocol developed by Cisco. IGRP has the following 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.

EIGRP

Enhanced IGRP (EIGRP) was developed from IGRP, another distance vector protocol. EIGRP is a classless, distance vector routing protocol with features found in link-state routing protocols. However, unlike RIP or OSPF, EIGRP is a proprietary protocol developed by Cisco and only runs on Cisco routers.

EIGRP features include:

• Triggered updates (EIGRP has no periodic updates).
• Use of a topology table to maintain all the routes received from neighbors (not only the best paths).
• Establishment of adjacencies with neighboring routers using the EIGRP hello protocol.
• Support for VLSM and manual route summarization. These allow EIGRP to create hierarchically structured large networks.

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, which are used in case the primary route fails. Because it is a local procedure, the switchover to the backup route is immediate and does not involve the action in any other routers.
• 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.

Periodic Updates: RIPv1 and IGRP

In addition to the update timer (every 30 seconds), the IOS implements three additional timers for RIP:

• Invalid (180 seconds)
• Flush (180 seconds)
• Holddown (240 seconds)
  

Invalid Timer. If an update has not been received to refresh an existing route after 180 seconds (the default), the route is marked as invalid by setting the metric to 16. The route is retained in the routing table until the flush timer expires.

Flush Timer. By default, the flush timer is set for 240 seconds, which is 60 seconds longer than the invalid timer. When the flush timer expires, the route is removed from the routing table.

Holddown Timer. This timer stabilizes routing information and 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. By default, the holddown timer is set for 180 seconds. The timer values can be verified with two commands: show ip route and show ip protocols. Notice in the output from show ip route that each route learned through RIP shows the elapsed time since the last update, expressed in seconds.

Unlike other distance vector routing protocols, EIGRP does not send periodic updates. Instead, EIGRP sends bounded updates about a route when a path changes or the metric for that route changes. When a new route becomes available or when a route needs to be removed, EIGRP sends an update only about that network instead of the entire table. This information is sent only to those routers that need it.

Triggered Updates

To speed up the convergence when there is a topology change, RIP uses triggered updates. A triggered update is a routing table update that is sent immediately in response to a routing change. Triggered updates do not wait for update timers to expire. The detecting router immediately sends an update message to adjacent routers. The receiving routers, in turn, generate triggered updates that notify their neighbors of the change.

Triggered updates are sent when one of the following occurs:

• An interface changes state (up or down)
• A route has entered (or exited) the "unreachable" state
• A route is installed in the routing table

Using only triggered updates would be sufficient if there were a guarantee that the wave of updates would reach every appropriate router immediately. However, there are two 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.

Random Jitter

To prevent the synchronization of updates between routers, the Cisco IOS uses a random variable, called RIP_JITTER, which subtracts a variable amount of time to the update interval for each router in the network. This random jitter, or variable amount of time, ranges from 0% to 15% of the specified update interval. In this way, the update interval varies randomly in a range from 25 to 30 seconds for the default 30-second interval.

Routing Loops

A routing loop is a condition in which a packet is continuously transmitted within a series of routers without ever reaching its intended destination network. A routing loop can occur when two or more routers have routing information that incorrectly indicates that a valid path to an unreachable destination exists.

The loop may be a result of:

• Incorrectly configured static routes
• Incorrectly configured route redistribution
• Inconsistent routing tables not being updated due to slow convergence in a changing network
• Incorrectly configured or installed discard route

There are a number of mechanisms available to eliminate routing loops, primarily with distance vector routing protocols. These mechanisms include:

• Defining a maximum metric to prevent count to infinity
• Holddown timers
• Split horizon
• Route poisoning or poison reverse
• Triggered updates

Count to Infinity

Count to infinity is a condition that exists when inaccurate routing updates increase the metric value to "infinity" for a network that is no longer reachable. To eventually stop the incrementing of the metric, "infinity" is defined by setting a maximum metric value. For example, RIP defines infinity as 16 hops - an "unreachable" metric. Once the routers "count to infinity," they mark the route as unreachable.

Holddown timers are used to prevent regular update messages from inappropriately reinstating a route that may have gone bad. Holddown timers instruct routers to hold any changes that might affect routes for a specified period of time. If a route is identified as down or possibly down, any other information for that route containing the same status, or worse, is ignored for a predetermined amount of time (the holddown period). This means that routers will leave a route marked as unreachable in that state for a period of time that is long enough for updates to propagate the routing tables with the most current information.

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. Thus, more time is allowed for the information about the change to be propagated.
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. 

Split Horizon Rule

Another method used to prevent routing loops caused by slow convergence of a distance vector routing protocol is split horizon. The split horizon rule says that a router should not advertise a network through the interface from which the update came. Split horizon = routes learned through an interface are not advertised out that same interface.


Split Horizon with Poison Reverse (or Route Poisoning)

Route poisoning is yet another method employed by distance vector routing protocols to prevent routing loops. Route poisoning is used to mark the route as unreachable in a routing update that is sent to other routers. Unreachable is interpreted as a metric that is set to the maximum. For RIP, a poisoned route has a metric of 16. Route Poisoning = routes learned through an interface are advertised back out the same interface as unreachable.

Poison reverse can be combined with the split horizon technique. The method is called split horizon with poison reverse. The rule for split horizon with poison reverse states when sending updates out a specific interface, designate any networks that were learned on that interface as unreachable.

The concept of split horizon with poison reverse is that explicitly telling a router to ignore a route is better than not telling it about the route in the first place. Poison reverse is a specific circumstance that overrides split horizon. Split horizon is enabled by default. However split horizon with poison reverse may not be the default on all IOS implementations.

IP and TTL

Time to Live (TTL) is an 8-bit field in the IP header that limits the number of hops a packet can traverse through the network before it is discarded. The purpose of the TTL field is to avoid a situation in which an undeliverable packet keeps circulating on the network endlessly. With TTL, the 8-bit field is set with a value by the source device of the packet. The TTL is decreased by one by every router on the route to its destination. If the TTL field reaches zero before the packet arrives at its destination, the packet is discarded and the router sends an Internet Control Message Protocol (ICMP) error message back to the source of the IP packet.