This chapter is from the book
This chapter is from the book
This chapter is from the book
Distance Vector Routing
Routing protocols fall into two main categories, Distance Vector or Link State. Generally speaking Distance Vector protocols determine best path on how far the destination is, while Link State protocols are capable of using more sophisticated methods taking into consideration link variables, such as bandwidth, delay, reliability and load. We will discuss Distance Vector protocols and their characteristics first and then move on to Link State protocols. We will address specific routing protocols in later chapters.
Distance Vector protocols judge best path on how far it is. Distance can be hops or a combination of metrics calculated to represent a distance value. The following lists the IP Distance Vector routing protocols still in use today and the metric that they use for determining the best path:
RIP v1 (hops)
RIP v2 (hops)
IGRP (combined metric, bandwidth and delay)
The best known and most popular Distance Vector protocol to date is IP RIP (Routing Information Protocol). There are two versions IP RIP, one and two. IGRP was originally developed by Cisco Systems and also supports the routing of IP traffic. You will find a detailed discussion about IP RIP v1 and v2 in Chapter 4 and IGRP in Chapter 5.
Route Updates
All routing protocols exchange information about networks and subnets through route updates. Route updates carry the reachability information routers need to build and maintain their route tables. Some routing protocols transmit these updates as broadcasts to everyone on the subnet while others send them out as multicasts (addressed to devices belonging to a multicast group).
Broadcasts are addressed to 255.255.255.255 and are received and processed by all hosts and routers on the local subnet. This adds unnecessary overhead and processing to hosts that do not function as routers. For instance, IP RIPv1 and IGRP both use broadcasts to exchange route information. RIPv2 addresses these issues by multicasting route updates. Multicast routing is discussed in Chapter 11, "IP Multicast Routing." All of the routing protocols mentioned here use period timers to time the transmission of their updates.
Upon initialization, all routers (regardless of routing protocol) send out their entire route tables to neighbor routers. Thereafter updates (depending on routing protocol) are either sent using periodic timers or sent when an event, such as a change in the network occurs causing (triggering) the update to be sent. Routing protocols that send periodic updates, send them even though no change has occurred in the network, wasting bandwidth. When a new route becomes available or one fails, the entire table is sent.
The constant broadcasting of route information adds unnecessary traffic to the network and wastes bandwidth. Multicasts are in essence broadcasts in that everyone on the subnet receives them. However, only those devices that belong to the multicast group fully process the datagram and therefore multicasts reduce the overhead hosts incur by processing datagrams they do not care about.
Metrics
Metric values were discussed earlier in this chapter. Metrics are values routing protocols use to determine the best path to a destination, when multiple paths exist. The metric(s) used depends on the routing protocol implemented. For instance, IP RIP v1 and v2 both use hops as their distance value. IGRP uses a combined metric value consisting of bandwidth and delay. While IGRP is capable of using bandwidth, delay, reliability and load, it generally is not configured to do so.
VLSM
If you recall from our discussion of IP addressing and VLSM in Chapter 2, VLSMs are the extension of standard classful masks (A, B, and C) to include subnets. Some routing protocols understand subnetting through the use of VLSMs, while others do not. Routing protocols that carry the subnet mask within their route updates are able to recognize subnets and forward datagrams within networks that have been subnetted. Routing protocols that do not carry these masks are considered classful routing protocols; that is, they only understand major classful networks (A, B, and C).
By including the subnet mask within a routing update, the receiving router not only knows what network is being advertised, but the exact subnet mask to use with this mask. If you recall from our Chapter 2 discussion, the subnet mask is used to determine which part of an IP address is the network or subnet. If no mask is included, this information is unknown and only the classful major network can be assumed. This causes problems when a classful routing protocol is implemented within a network that has been subnetted.
ToS
Routing protocols that are ToS-capable are able to make routing decisions based on the bits contained within the ToS filed of the IP header. These bits are set by end systems requesting a specific level of datagram forwarding.
The Type of Service bits contained within the IP header of datagrams were discussed in Chapter 2. Chapter 10, "Type of Service and Quality of Service Routing," has also been devoted to further exploring ToS and QoS. Please refer to those chapters for more detailed information.
Load Balancing
Load balancing is a feature a router can employ when multiple paths exist to a destination. There are two main types of load balancing, equal and unequal. When both paths have equal cost (for example, both are two hops away) datagrams may alternately be forwarded across both paths evenly distributing the traffic load.
All dynamic routing protocols support this type of load balancing. However, when unequal cost paths exist there must be a configured threshold by which a routing protocol can determine whether the variance between the paths is similar enough to justify or even perform load balancing across them. Some routing protocols can support load balancing across two to six active paths simultaneously.
Maximum Network Diameter
Distance Vector networks such as RIP are limited in scope (diameter). These routing protocols were not designed to operate in medium to large internetworks with hundreds of links and routers connecting hundreds or even thousands of hosts. The maximum network diameter specifies the distance a datagram may travel (for example, the maximum number of hops) before the destination is considered unreachable, causing the datagram to be discarded. This maximum distance is measured in hops from transmitter to receiver. You can think of the maximum rule as "No two devices can communicate through more than x hops."
Note
IP RIP v1 and v2 both have a maximum hop count of 15, which means anything beyond that is unreachable. IGRP's maximum is 255 hops.
As datagrams traverse the network routers forward them and increment the hop count by one before passing it on to the next hop router. Using RIP as an example, when a datagram reaches the 15th router, that router must discard the datagram because a value of 16 or greater is considered too far by RIP. The router discarding the datagram generates an ICMP message back to the source indicating that the destination is unreachable.
Routers also use this maximum hop count value to maintain their route tables. When a network link fails, the router sends news of this failure in its next route update. It relays this news by applying a hop count one higher than the maximum (16 for RIP and 256 for IGRP) to the failed link, which indicates the distance to this network as infinity (unreachable). Routers receiving this news know to remove this route from their route table.
Authentication
Routing updates can easily be intercepted by unauthorized routers placed on the network. Some routing protocols do not have any means of authenticating a neighbor router before giving up route information. Others have simple clear text passwords, which offer some security but can be learned by hackers scanning the network with any protocol analysis tool. More sophisticated routing protocols can be configured to use clear text or encrypted authentication. The configuration and use of authentication varies. However, when used, all routers must share the same password to exchange route information.
Convergence
Convergence is achieved when all routers within a routing domain agree on reachability information. Distance Vector routing protocols require that each router send its entire route table to all of its neighboring routers. Timers control how often updates are sent. When the router receives updates, it must recompute all routes and update their route tables before they can forward traffic.
Distance Vector routing protocols are slow in converging and therefore are highly susceptible to routing loops. Routing loops and loop avoidance mechanisms will be discussed later in this chapter.
The time that elapses before all routers have processed route updates and modified their tables is called convergence time. Convergence is an important concept because when a link or a router fails, no data passes within the internetwork until all the router's tables are fully updated.
Distance Vector Characteristics
In the previous sections we discussed Distance Vector routing characteristics. Table 3.1 provides a quick list comparing the characteristics of RIP v1, RIP v2 and IGRP. As a network engineer implementing a routing protocol, it is necessary to be familiar with the characteristics of the routing protocols you are evaluating prior to implementation. For example, if IP hosts on your network are separated by more than 15 subnets, RIP v1 or v2 would not be your choice. RIP v1 and v2 are limited to a maximum distance (hop count) of 15, whereas IGRP supports up to a maximum of 255 hops.
Table 3.1 Distance Vector Characteristics
Characteristic |
Routing Protocol |
|
|
|
|
RIP v1 |
RIP v2 |
IGRP |
|
Route Updates: |
|
|
|
|
Broadcasts |
X |
|
X |
|
Multicasts |
|
X |
|
|
Includes entire route table |
X |
X |
X |
|
Periodic timer |
30 seconds |
30 seconds |
90 seconds |
|
Metrics: |
|
|
|
|
Hops |
X |
X |
|
|
Combined Metrics: |
|
|
|
|
Bandwidth and Delay |
|
|
X |
|
VLSM |
|
X |
|
|
ToS |
|
|
X |
|
Load balancing: |
|
|
|
|
Equal Cost |
X |
X |
X |
|
Unequal Cost |
|
|
X |
|
Maximum network diameter |
15 hops |
15 hops |
255 hops* |
|
Authentication |
|
X |
|
Although IGRP observes a maximum network diameter of 255 hops, it does not use this as a distance value in path selection.
In the previous sections each routing characteristic was discussed. This chart is meant to summarize the characteristics supported by RIP v1, v2 and IGRP.
Routing Loops and Remedies
One of the main problems inherent with Distance Vector routing protocols is routing loops. Routing loops occur in networks when old (bad) route information exists in a route table. The problem stems primarily from the periodic scheduled route updates that result in slow convergence.
For example, IP RIP updates are broadcast every 30 seconds by default. This allows enough time to elapse, causing slow convergence. Because of the intervals between the periodic route updates, routers may not learn about topology changes in a timely manner. In this case, they may be relying on outdated or incorrect route information. Slow convergence can result in routing loops, causing datagrams to bounce between routers endlessly if not detected, causing the routers to start a count to infinity. Routing protocols can take advantage of one or more loop avoidance mechanisms to minimize the impact a loop has on the network.
These techniques, or combinations of these techniques, can minimize routing loops passing on incorrect routing information. The different techniques are count to infinity, split horizon, poison reverse and holddown timers.
-
Count to infinity (maximum hop count, see Figure 3.23)
Holddowns
-
Split horizon (see Figure 3.24)
-
Poison reverse (see Figure 3.25)
){kind=link}
){kind=link}
){kind=link}
Implementations vary based on vendor support and routing protocol.
Count to Infinity
Count to infinity is a loop avoidance mechanism that sets a maximum hop count value, that, when exceeded, equates to infinity hops (or destination unreachable). The maximum hop count for RIP is 15 and IGRP is 255. Any value above this is considered infinity (unreachable).
To understand this mechanism you need to understand how routers handle datagrams when forwarding them. As a router processes and forwards a datagram, it decrements two values within the IP header, the TTL timer and increment the hop count. TTL was discussed in Chapter 2. Each router assumes, from its perspective, the destination network exists one hop further than the router that sent them the datagram.
If a loop exists in the network, this process would go on forever without some way of controlling it. Luckily, Distance Vector routing protocols specify an infinity value (RIP = 16 and IGRP = 256) that, when reached, causes an endlessly circulating datagram to be dropped.
If for some reason datagrams continue to be forwarded after the maximum hop has been exceeded (infinity has been reached), then a fall back method, the TTL timer, deals with the vigilante datagram. When the TTL timer within an IP header reaches zero, the router trashes the datagram. With an infinity value and TTL timer providing a backup, this combination provides a viable remedy to most routing loops.
Figure 3.23 Distance-vector protocols limit the distance (hops) a datagram may traverse. If a route loop exists within the topology, the router automatically trashes the datagram when it exceeds the maximum hop (for RIP the maximum is 15, for IGRP the maximum is 255), stopping the count to infinity.
Split Horizon
Split horizon prevents information being sent back in the direction from which that information was received (see Figure 3.24). When a change occurs in the network, routers only advertise that change in one direction, which means that they send the update out to all other ports except the one from which it was learned.
With split horizon, any router is the starting point. split horizon sends only information learned from other ports. Split horizon never sends information out the same port it learned it from.
Figure 3.24 Routing information learned from an interface is never advertised back out that same interface.
The split horizon rule states that "route information learned through an interface may not be transmitted out that same interface." In Figure 3.23, the middle router learns about networks 12.0.0.0 and 14.0.0.0 from the interface on the right and can only propagate this information out the opposite interface. It learns about networks 11.0.0.0 and 15.0.0.0 from the interface on the left and can only propagate this information out the opposite interface.
Poison Reverse
Poison reverse allows routers to break the split horizon rule by advertising information learned from an interface out the same interface. However, it can advertise routes learned from an interface out the same interface with a 16 hop count, which indicates a destination unreachable, "poisoning" the route. Routers with a route with a better metric (hop count) to the network ignore the destination unreachable update.
Poison reverse prevents updates with inconsistencies from spreading. Routers poison a route by sending out a broadcast with an infinity hop count, or destination unreachable. While the other routers slowly converge, the router maintains the poisoned route in its table and ignores updates from other routers about better routes to the network.
Poison reverse when implemented takes precedence over split horizon. When a router learns that a route has become unavailable, it overrides split horizon by advertising the failed route with an infinity hop count (destination unreachable) out all the interfaces including the one it was received on (see Figure 3.25). This allows a router to advertise out the same interface it learned information on, but poisons the route by using a value greater than the maximum hop count. Routers receiving this advertisement assume the destination network is unreachable.
Figure 3.25 A router advertising information out the same interface it learned the information from with an infinity hop value, indicating the route is unreachable.
Holddown Timers
Another technique typically used in combination with route poisoning is holddown timers. Holddown timers start as soon as a router receives an update from a neighbor indicating that an attached network has gone down. Until the timer elapses, the router ignores updates regarding this route from other routers unless it receives an update from the neighboring router that initially informed the network of the downed link. The timer stops if it receives a message from the neighboring router. At that point, the network is marked as reachable again and the route table is updated. .
Routers use holddown timers after they have learned that a route is unavailable to ensure that this route will not be mistakenly reinstated by an advertisement received from another router that has not yet learned about this route being unavailable. Typically this timer is greater than the total convergence time, providing time for accurate information to be learned, consolidated, and propagated through the network by all routers.
The holddown timer causes the router to ignore any new updates to invalid destination routes that contain a similar or less favorable metric value than its own. This prevents an unavailable route from being reinstated inadvertently. Routers accept and reinstate invalid routes if it receives a new update with a better metric than their own or the holddown timer has expired.