When network 10.4.0.0 fails, Router C detects the failure and stops routing packets out its E0 interface. However, Routers A and B have not yet received notification of the failure. Router A still believes it can access 10.4.0.0 through Router B. The routing table of Router A still reflects a path to network 10.4.0.0 with a distance of 2.
Because the routing table of Router B indicates a path to network 10.4.0.0, Router C believes it has a viable path to network 10.4.0.0 through Router B. Router C updates its routing table to reflect a path to network 10.4.0.0 with a hop count of 2, as illustrated in Figure 3-10.
Inconsistent Path Information Between Routers
Router B receives a new update from Router C (3 hops). Router A receives the new routing table from Router B, detects the modified distance vector to network 10.4.0.0, and recalculates its own distance vector to 10.4.0.0 as 4, as shown in Figure 3-11.
Inconsistent Data Continues to Propagate
Because Routers A, B, and C conclude that the best path to network 10.4.0.0 is through each other, packets from Router A destined to network 10.4.0.0 continue to bounce between Routers B and C, as illustrated in Figure 3-12.
Routing Loop Exists Because of Erroneous Hop Count
Continuing the example in Figure 3-12, the invalid updates about network 10.4.0.0 continue to loop. Until some other process can stop the looping, the routers update each other inappropriately, considering that network 10.4.0.0 is down.
This condition, called count-to-infinity, causes the routing protocol to continually increase its metric and route packets back and forth between the devices, despite the fundamental fact that the destination network, 10.4.0.0, is down. While the routing protocol counts to infinity, the invalid information enables a routing loop to exist, as illustrated in Figure 3-13.
Count-to-Infinity Condition
Without countermeasures to stop this process, the distance vector of hop count increments each time the routing update is broadcast to another router. This causes data packets to be sent through the network because of incorrect information in the routing tables. The following sections cover the countermeasures that distance vector routing protocols use to prevent routing loops from running indefinitely.
Troubleshooting Routing Loops with Maximum Metric Settings
IP packets have inherent limits via the Time-To-Live (TTL) value in the IP header. In other words, a router must reduce the TTL field by at least 1 each time it gets the packet. If the TTL value becomes 0, the router discards that packet. However, this does not stop the router from continuing to attempt to send the packet to a network that is down.
To avoid this prolonged problem, distance vector protocols define infinity as some maximum number. This number refers to a routing metric, such as a hop count.
With this approach, the routing protocol permits the routing loop until the metric exceeds its maximum allowed value. Figure 3-14 shows this unreachable value as 16 hops. After the metric value exceeds the maximum, network 10.4.0.0 is considered unreachable.
Maximum Metric
Preventing Routing Loops with Split Horizon
One way to eliminate routing loops and speed up convergence is through the technique called split horizon. The split horizon rule is that sending information about a route back in the direction from which the original update came is never useful. For example, Figure 3-15 illustrates the following:
Router B has access to network 10.4.0.0 through Router C. It makes no sense for Router B to announce to Router C that Router B has access to network 10.4.0.0 through Router C.
Given that Router B passed the announcement of its route to network 10.4.0.0 to Router A, it makes no sense for Router A to announce its distance from network 10.4.0.0 to Router B.
Having no alternative path to network 10.4.0.0, Router B concludes that network 10.4.0.0 is inaccessible.
Split Horizon
Preventing Routing Loops with Route Poisoning
Another operation complementary to split horizon is a technique called route poisoning. Route poisoning attempts to improve convergence time and eliminate routing loops caused by inconsistent updates. With this technique, when a router loses a link, the router advertises the loss of a route to its neighbor device. Route poisoning enables the receiving router to advertise a route back toward the source with a metric higher than the maximum. The advertisement back seems to violate split horizon, but it lets the router know that the update about the down network was received. The router that received the update also sets a table entry that keeps the network state consistent while other routers gradually converge correctly on the topology change. This mechanism allows the router to learn quickly of the down route and to ignore other updates that might be wrong for the hold-down period. This prevents routing loops.
Figure 3-16 illustrates the following example. When network 10.4.0.0 goes down, Router C poisons its link to network 10.4.0.0 by entering a table entry for that link as having infinite cost (that is, being unreachable). By poisoning its route to network 10.4.0.0, Router C is not susceptible to incorrect updates from neighboring routers, which may still have an outdated entry for network 10.4.0.0.
Route Poisoning
When Router B sees the metric to 10.4.0.0 jump to infinity, it sends an update called a poison reverse to Router C, stating that network 10.4.0.0 is inaccessible, as illustrated in Figure 3-17. This is a specific circumstance overriding split horizon, which occurs to make sure that all routers on that segment have received information about the poisoned route.
Poison Reverse
Route Maintenance Using Hold-Down Timers
Hold-down timers prevent regular update messages from inappropriately reinstating a route that might have gone bad. Hold-downs tell routers to hold any changes that might affect routes for some period of time. The hold-down period is usually calculated to be just greater than the time necessary to update the entire network with a routing change.
Hold-down timers perform route maintenance as follows:
When a router receives an update from a neighbor indicating that a previously accessible network is now inaccessible, the router marks the route as inaccessible and starts a hold-down timer.
If an update arrives from a neighboring router with a better metric than originally recorded for the network, the router marks the network as accessible and removes the hold-down timer.
If at any time before the hold-down timer expires, an update is received from a different neighboring router with a poorer metric, the update is ignored. Ignoring an update with a higher metric when a holddown is in effect enables more time for the knowledge of the change to propagate through the entire network.
During the hold-down period, routes appear in the routing table as "possibly down."
Figure 3-18 illustrates the hold-down timer process.
Hold-Down Timers
Route Maintenance Using Triggered Updates
In the previous examples, routing loops were caused by erroneous information calculated as a result of inconsistent updates, slow convergence, and timing. If routers wait for their regularly scheduled updates before notifying neighboring routers of network catastrophes, serious problems can occur, such as loops or traffic being dropped.
Normally, new routing tables are sent to neighboring routers on a regular basis. A triggered update is a new routing table that is sent immediately, in response to a change. The detecting router immediately sends an update message to adjacent routers, which, in turn, generate triggered updates notifying their adjacent neighbors of the change. This wave propagates throughout the portion of the network that was using the affected link. Figure 3-19 illustrates what takes place when using triggered updates.
Triggered Updates
Triggered updates would be sufficient with a guarantee that the wave of updates reached every appropriate router immediately. However, two problems exist:
Packets containing the update message can be dropped or corrupted by some link in the network.
The triggered updates do not happen instantaneously. A router that has not yet received the triggered update can 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.
Coupling triggered updates with holddowns is designed to get around these problems.
Route Maintenance Using Hold-Down Timers with Triggered Updates
Because the hold-down rule says that when a route is invalid, no new route with the same or a higher metric will be accepted for the same destination for some period, the triggered update has time to propagate throughout the network.
The troubleshooting solutions presented in the previous sections work together to prevent routing loops in a more complex network design. As depicted in Figure 3-20, the routers have multiple routes to each other. As soon as Router B detects the failure of network 10.4.0.0, Router B removes its route to that network. Router B sends a trigger update to Routers A and D, poisoning the route to network 10.4.0.0 by indicating an infinite metric to that network.
Implementing Multiple Solutions
Routers D and A receive the triggered update and set their own hold-down timers, noting that the 10.4.0.0 network is "possibly down." Routers D and A, in turn, send a triggered update to Router E, indicating the possible inaccessibility of network 10.4.0.0. Router E also sets the route to 10.4.0.0 in holddown. Figure 3-21 depicts the way Routers A, D, and E implement hold-down timers.
Route Fails
Router A and Router D send a poison reverse to Router B, stating that network 10.4.0.0 is inaccessible. Because Router E received a triggered update from Routers A and D, it sends a poison reverse to Routers A and D. Figure 3-22 illustrates the sending of poison reverse updates.
Route Holddown
Routers A, D, and E will remain in holddown until one of the following events occurs:
The hold-down timer expires.
Another update is received, indicating a new route with a better metric.
A flush timer, which is the time a route will be held before being removed, removes the route from the routing table.
During the hold-down period, Routers A, D, and E assume that the network status is unchanged from its original state and attempt to route packets to network 10.4.0.0. Figure 3-23 illustrates Router E attempting to forward a packet to network 10.4.0.0. This packet will reach Router B. However, because Router B has no route to network 10.4.0.0, Router B will drop the packet and return an Internet Control Message Protocol (ICMP) network unreachable message.
Packets During Holddown
When the 10.4.0.0 network comes back up, Router B sends a trigger update to Routers A and D, notifying them that the link is active. After the hold-down timer expires, Routers A and D add route 10.4.0.0 back to the routing table as accessible, as illustrated in Figure 3-24.
Network Up
Routers A and D send Router E a routing update stating that network 10.4.0.0 is up, and Router E updates its routing table after the hold-down timer expires, as illustrated in Figure 3-25.
Network Converges
Link-State and Advanced Distance Vector Protocols
In addition to distance vector–based routing, the second basic algorithm used for routing is the link-state algorithm. Link-state protocols build routing tables based on a topology database. This database is built from link-state packets that are passed between all the routers to describe the state of a network. The shortest path first algorithm uses the database to build the routing table. Figure 3-26 shows the components of a link-state protocol.
Link-State Protocols
Understanding the operation of link-state routing protocols is critical to being able to enable, verify, and troubleshoot their operation.
Link-state-based routing algorithms—also known as shortest path first (SPF) algorithms—maintain a complex database of topology information. Whereas the distance vector algorithm has nonspecific information about distant networks and no knowledge of distant routers, a link-state routing algorithm maintains full knowledge of distant routers and how they interconnect.
Link-state routing uses link-state advertisements (LSA), a topological database, the SPF algorithm, the resulting SPF tree, and, finally, a routing table of paths and ports to each network.
Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are classified as link-state routing protocols. RFC 2328 describes OSPF link-state concepts and operations. Link-state routing protocols collect routing information from all other routers in the network or within a defined area of the internetwork. After all the information is collected, each router, independently of the other routers, calculates its best paths to all destinations in the network. Because each router maintains its own view of the network, it is less likely to propagate incorrect information provided by any one particular neighboring router.
Link-state routing protocols were designed to overcome the limitations of distance vector routing protocols. Link-state routing protocols respond quickly to network changes, send triggered updates only when a network change has occurred, and send periodic updates (known as link-state refreshes) at long intervals, such as every 30 minutes. A hello mechanism determines the reachability of neighbors.