Distance-Vector Routing Protocols

Introduction

Static Routing Protocols

Dynamic routing protocols

 

Two Examples: Routing Information Protocol (RIP) & Internet Gateway Routing Protocol (IGRP).

 

RIP is open standard and easy to implement – uses the number of hops to determine the best route to a destination. RIP is Classful, i.e. it is unable to work with CIDR and VLSM. A revision in 1993 allows RIP to become Classless, this is RIP version 2.

IGRP is Cisco proprietary – uses a variety of methods to find the best route but is never used today due to its inability to work with CIDR and VLSM.

Routing Updates

The updates used in Distance-Vector routing algorithms are sent either at regular intervals (RIP, every 30 secs) or when the topology of the network changes. Each router will send its entire routing table to its immediate neighbour. If the table is large, the table may need to be sent in more than one update.

 

The routing tables hold information about the total path cost as defined by the metrics (RIP and IGRP use hops) that are being used and the logical address of the first router encountered (or the interface to leave the originating router) on the path to each network contained in the table.

Routing Problems with Distance Vector – Routing loops

When all routers have the same view of the network, the network is said to have converged. Because the updates are sent at fixed time intervals in some cases, there can exist a period of time during which the routing tables of some routers will be different from that of others. This can cause routing problems.

 

Due to the slow updating process, it is possible for routing loops to occur when using a distance-vector routing protocol. This happens when one router has a different idea of the topology of the network than its neighbour(s).

 

An example will help to illustrate this problem. Please refer to the diagram below.


Imagine that the network has been stable for a period of time and that all routing tables have converged.
This means that all packets will be delivered correctly.
The route that B has in its routing table to get packets to Network X is via router C.

 

Now, Network X connected to ISP fails and becomes unreachable.
ISP sends an update to reflect this change to router D.
Router D no longer sends packets to Network X.

 

Routers A, B and C continue sending packets towards Network X because they have not yet received an update.
While this state of confusion exists, any packets destined for Network X are dropped by router D.

 

After a short period, router D sends an update to routers A and C.
They will no longer forward packets to network X.

Router B still has old information in its routing table. It still believes that it has a path to Network X.
It sends an update to routers A and C advertising its route to Network X via router C.

 

Routers A and C update their routing tables and indicate that they can reach Network X via router B.
Routers A and C now inform Router D that they can reach Network X via router B.

 

A user on an Ethernet network attached to router A now sends a packet to  Network X.
A forwards this to B.
B forwards this to C.
C now sends this back to B and B sends to C again.


This would carry on infinitely unless some method were in place to prevent the propagation of incorrect routing information.

 

When routers get into this situation, it is called counting to infinity.

Count to Infinity Problem

To get round this problem, the maximum number of hops that a packet may make in a RIP network is 15. If the packet makes one more hop, it is discarded.
This is why there is a maximum network diameter specified for some routing protocols.

 

Although the problem is not solved, it prevents a potential problem taking place where thousands of packets destined for network X continue to loop around the network. This would bring the routers involved to a standstill if this was unchecked.

 

When a router discovers a packet has reached its 16th hop towards a certain destination, that network is now deemed unreachable.

 

Split Horizon

This adjustment to the routing process prevents a router from sending information back towards the router that originally supplied that information. Referring to the diagram above, it means that routers A and C cannot inform router D about the route to Network X.

 

The split horizon rule is based on the theory that it is not useful to send information about a route back in the direction from which it came. In some network configurations, it may be necessary to disable split horizon.

Route Poisoning

Another useful technique is to poison the route to a certain destination. This means marking it as unreachable.
With RIP, this can be accomplished by setting the hop count to 16.

 

In the diagram above, ISP router would make its distance to Network X equal to 16 hops. It sends the poisoned route back to Router D.
Route poisoning is often used with triggered updates. This forces a router to send an update if it hears of a topology change.
Router D will inform A and C of the unreachability of network X and also sends a poison reverse update back to the ISP router.

 

Poison reverse is often used with triggered updates to speed up the convergence process. Routers do not have to wait (e.g. 30 seconds) to send out the news of an unreachable network.

Triggered Updates

This technique bypasses the timed updates and forces a router to send an update when it hears of a topology change.
If a router hears of an unreachable network via serial line 0, it will immediately send an update out via its other interfaces towards other routers which will do the same in turn.
This ensures that all routers know of failed routes before any holddown timers have had the chance to expire.

Preventing Loops by using Holddown timers

The count to infinity problem can be avoided by using holddown timers.
This is a clock that is set within the router to help ensure network stability. It operates as follows:

 

When router D receives an update from ISP indicating that a previously accessible network (Network X) is now inaccessible, router D marks the route as inaccessible and starts its holddown timer.

 

If at any time before the holddown timer expires an update is received from ISP indicating that the network is again accessible, router D marks the network as accessible and removes the holddown timer.

 

If an update arrives from a different neighbouring router (either A or C) with a better metric than originally recorded for the network, the router marks the network as accessible and removes the holddown timer. In this example, there is no other route to Network X so a lower metric cannot arrive from either A or C.

 

If at any time before the holddown timer expires an update is received from neighbouring routers A or C with a poorer metric, the update is ignored. Ignoring an update with a poorer metric when a holddown timer is in effect allows more time for the knowledge of a disruptive change to propagate through the entire network.

 

The default holddown for RIP is 180 seconds. This will prevent any inferior or incorrect route from being updated but may also prevent a valid alternative route from being installed. The holddown timer can be decreased to speed up convergence but should be done with caution. The ideal setting would be to set the timer just longer than the longest possible update time for the entire internetwork.

Summary of Loop prevention Methods

The following methods are useful in preventing routing loops in a network that uses distance-vector routing protocols.

 

RIP – Routing Information Protocol

RIP, sometimes referred to as IP RIP, is formally detailed in two separate documents - RFC 1058 and Internet Standard (STD) 56.

 

RIP version 1 is a classful routing protocol and does not carry subnet information nor does it use authentication.
It also broadcasts its updates which can make it susceptible to spoofing of routing information by determined students!

 

When setting RIP as the routing protocol on a router, the command:

Router(config)#router rip

is applied at the global configuration prompt.

RIP Version 2

For these reasons, it has been updated to RIP version 2 which is classless, does allow for VLSM and carries the subnet mask for a destination and also has provision for authentication.
It also carries the address of the next hop for each of its routes and multicasts its routing table updates rather than broadcasting them.

 

RIP has a maximum hop count of 15 (16 is considered unreachable) and implements split horizon and holddown mechanisms to prevent incorrect routing information from being transmitted throughout the network.

 

When setting RIP as the routing protocol on a router, the command:

Router(config)#router rip

Router(config-router)#version 2

is applied at the global configuration prompt.

 

Now it is necessary to specify the interfaces that will take part in the RIP routing process. This is done with the

network command and the participating network interfaces must be specified

e.g.

Der(config)#router rip

Der(config-router)#version 2

Der(config-router)#network 192.168.1.0

 

When a network command is issued for a given network, RIP will immediately begin sending advertisements via all interfaces within the specified network address range.

 

To control the set of interfaces that will exchange routing updates, the network administrator can disable the sending of routing updates on specified interfaces by configuring the passive-interface command at the (config-router) prompt and specifying the appropriate interface. Although the router will no longer send updates through that interface, the router continues to listen to and use routing updates arriving on that interface.

 

RIP sends routing-update messages at regular intervals of (default) 30 seconds. When a router receives a routing update that includes changes to an entry, it updates its own routing table to incorporate the changed route.

 

If the information received is for a new network, the received metric value for the path to the new network is increased by 1, and the source interface of the update (the interface that received the update) is indicated as the next hop in the routing table.

 

RIP routers maintain only the best (lowest hop count) route to a destination but can maintain multiple equal-cost paths to the same destination.

 

Once RIP has been enabled on a router, there are several optional tasks that may need to be configured.

 

ip classless Command

A router by default assumes that all subnets of a directly connected network should be present in the routing table. If a packet is received with an unknown destination address within an unknown subnet of a directly attached network, the router assumes that the subnet does not exist. This causes the router will drop the packet even if there is a default route.

 

Configuring ip classless on the router resolves this problem by allowing the router to ignore the classful boundaries of the networks in its routing table and simply route to the default route.

 

The ip classless command is enabled by default in IOS 11.3 and above.

Load Balancing with RIP

RIP can balance loads over a maximum of 6 different routes. If more than one path exists to the same destination, RIP will list them all in its routing table and send each arriving packet for that destination through each route in turn in a round-robin fashion.

 

Because RIP only uses hop count as its metric, it cannot differentiate between a 56kbps line and an E1 line, for instance.

 

When a router learns of multiple routes to a specific network, the route with the lowest administrative distance is installed in the routing table.

Administrative Distance

How route was learned

Administrative Distance

Directly connected interface

0

Static Route

1

EIGRP summary route

5

EBGP

20

Internal EIGRP

90

IGRP

100

OSPF

110

ISIS

115

RIP

120

EIGRP external route

170

IBGP

200

Unknown

255

 

Sometimes the router must select a route from several that have been learnt via the same routing process with the same administrative distance. In this case, the router chooses the path with the lowest cost or metric to the destination. Each routing process calculates its cost differently and the costs may need to be manually configured in order to achieve load balancing as the administrator requires.

Static Routes

A static route is a user-defined route to a destination that may not be discovered with the routing protocol. This is useful in a stub network that has only one exit point to the Internet. Here, any address that does not lie within the scope of the stub network must lie outside that network so a static route should be set up to direct external traffic to the boundary router for the network.

 

If a static route is assigned to an interface that is not defined in the RIP process via a network command, RIP will not advertise the route unless a redistribute static command is specified in the RIP process.

 

An administrative distance can be applied to the static route to influence its use. Remember that the lowest administrative distance will be used first.

 

Assume that a network has learned its exit point to the Internet dynamically, but we also have an alternative route to the Internet via an ISDN serial line. The drawback here is that the ISDN route is metered and we pay for the traffic that uses this line. We would only want to use the ISDN line in times of failure of our usual route.

 

To achieve this, we can use a floating static route. Assume our normal exit route to our ISP has been learnt via RIP. Referring to the table above, it can be seen that the administrative distance for RIP is 120. By choosing a higher value for our floating static route, we can ensure that the only time that the ISDN line gets used is when the normal route fails and has been removed from the routing table.

Interior Gateway Routing Protocol – IGRP


Please note that IGRP is rarely used these days, however it is included here for comparison purposes.

IGRP is a distance vector routing protocol developed by Cisco. IGRP sends routing updates at 90 second intervals, advertising networks for a particular autonomous system. An autonomous system is a set of networks under the control of one company or organisation. The key design characteristics of IGRP are as follows:

 

 

By default, the IGRP routing protocol uses bandwidth and delay as its metrics. Additionally, IGRP can be configured to use a combination of several variables to determine a composite metric. Those extra variables are:

 

IGRP Metrics

By default the metrics for load, reliability and MTU are set to zero, but the administrator can set these if needed.

 

IGRP uses a composite metric, defaulting to bandwidth and delay. The entire metric may be calculated as a function of bandwidth, delay, load, reliability and MTU. By default, only bandwidth and delay are considered. The other parameters are used only if enabled via configuration. Delay and bandwidth are not measured values, but are set via the delay and bandwidth interface commands.

IGRP Advertised Routes

IGRP advertises three types of routes:

 

 

Interior

Interior routes are routes between subnets of a network that is attached to a router interface. If the network attached to a router is not subnetted, IGRP does not advertise interior routes.

 

System

System routes are routes to networks within an autonomous system. The Cisco IOS software derives system routes from directly connected network interfaces and system route information provided by other IGRP-speaking routers or access servers. System routes do not include subnet information.

 

Exterior

Exterior routes are routes to networks outside the autonomous system that are considered when identifying a gateway of last resort. The Cisco IOS software chooses a gateway of last resort from the list of exterior routes that IGRP provides. The software uses the gateway (router) of last resort if a better route is not found and the destination is not a connected network. If the autonomous system has more than one connection to an external network, different routers can choose different exterior routers as the gateway of last resort.

Stability with IGRP

IGRP has a number of features that are designed to enhance its stability, such as:

 

 

Holddowns

Holddowns are used to prevent regular update messages from wrongly reinstating a route that may not be up. When a router (or link to a router) fails, neighbouring routers detect this via the lack of regularly scheduled update messages.

 

Split horizons

Split horizons are derived from the premise that it is usually not useful to send information about a route back in the direction from which it came. The split horizon rule helps prevent routing loops.

 

Poison reverse updates

Split horizons prevent routing loops between adjacent routers, but poison reverse updates are necessary to defeat larger routing loops. Generally speaking, increases in routing metrics indicate routing loops. Poison reverse updates then are sent to remove the route and place it in holddown. With IGRP, poison reverse updates are sent only if a route metric has increased by a factor of 1.1 or more.

 

IGRP also maintains a number of timers and variables containing time intervals. These include

 

 

The update timer specifies how frequently routing update messages should be sent. The IGRP default for this variable is 90 seconds.

 

The invalid timer specifies how long a router should wait (in the absence of routing-update messages about a specific route) before declaring that route invalid. The IGRP default for this variable is three times the update period i.e. 270 seconds.

 

The holddown timer specifies the amount of time for which information about poorer routes is ignored. The IGRP default for this variable is three times the update timer period plus 10 seconds i.e. 280 seconds.

 

Finally, the flush timer indicates how much time should pass before a route is flushed from the routing table. The IGRP default is seven times the routing update timer i.e. 630 seconds.

 

Today, IGRP is showing its age and it lacks support for variable length subnet masks (VLSM). Rather than develop an IGRP version 2 to correct this problem, Cisco has built upon IGRP's legacy of success with Enhanced IGRP (EIGRP).

Conclusion

This lecture has examined the basic features of distance-vector routing algorithms. We have seen that they use some value to express the distance to a certain destination and that they send their entire routing table to their neighbours at specified intervals.

 

This can cause network instability when a certain part of a network fails. This can lead to routing loops.

 

Solutions to routing loops are:

 

 

We have also introduced two distance vector routing protocols, RIP and IGRP.