1.10 Convergence

In a routed network, the routing process in each router must maintain a loop-free, single path to each possible destination logical network. When all of the routing tables are synchronized and each contains a usable route to each destination network, the network is described as being ‘converged'. Convergence is the time it takes for all routers to agree on the network topology after a change in the network.

Convergence efforts are different within different routing protocols. There are at least two different detection methods used by all routing protocols. The first method is used by the Physical Layer (Layer 1) and the Data Link Layer (Layer2) protocols. When the network interface on the router does not receive three consecutive keepalives, the link will be considered down. The second method is that when the routing protocol at the Network/Transport Layer (Layer 3) fails to receive three consecutive Hello messages, the link will be considered down.

Routing protocols have timers that are used to stop network loops from occurring on a network when a link failure has been detected. Hold-down timers are used to give the network stability while new route calculations are being performed. They also allow all the routers a chance to learn about the failed route to avoid routing loops and counting to infinity problems. Since a network cannot converge during this holddown period, this can cause a delay in the routing process of the network. Because of this slow convergence time, link-state routing protocols do not use hold-down timers.

1.10.1 Distance-Vector Routing Convergence

1.10.1.1 RIP and IGRP Convergence

Convergence time is one of the problems associated with distance-vector protocols, such as RIPv1 and IGRP. When a router detects a link failure between itself and a neighbor, it sends a flash update with a poisoned route to it other neighbors. These neighbors in turn create a new flash update and send it to all of its neighbors, and so on. The Router that detected the link failure purges the entry for the failed link and removes all routes associated with that link from the routing table. The router then sends a query to its neighbors for the routs that have been removed. If a neighbor responds with a route, it is immediately installed in the routing table. The router does not go into hold-down because the entry was already purged. However, its neighbors are in hold-down for the failed route, thus ignoring periodic advertisement for that route. As the other routers come out of hold-down, the new route announced by the router that detected the failed link will cause their routing table entries to be updated.

1.10.1.2 EIGRP Convergence

Enhanced IGRP (EIGRP) convergence differs slightly. If a router detects a link failure between itself and a neighbor, it checks the network topology table for a feasible alternate route. If it does not find a qualifying alternate route, it enters in an active convergence state and sends a Query out all interfaces for other routes to the failed link. If a neighbor replies to the Query with a route to the failed link, the router accepts the new path and metric information, places it in the topology table, and creates an entry for the routing table. It then sends an update about the new route out all interfaces. All neighbors acknowledge the update and send updates of their own back to the sender. These bi-directional updates ensure the routing tables are synchronized and validate the neighbor's awareness of the new topology. Convergence time in this event is the total of detection time, plus Query and Reply times and Update times.

1.10.2 Link-State Convergence

The convergence cycle used in Link-State Routing Protocols, such as OSFP and IS-IS, differs from that of the distance-vector protocols. When a router detects a link failure between itself and a neighbor, it tries to perform a Designated Router (DR) election process on the LAN interface, but fails to reach any neighbors. It then deletes the route from the routing table, builds a link-state advertisement (LSA) for OSFP or a link-state PDU (LSP) for IS-IS, and sends it out all other interfaces. Upon receipt of the LSA, the other neighbors that are up copy the advertisement and forward the LSA packet out all interfaces other than the one upon which it arrived. All routers, including the router that detected the failure, wait five seconds after receiving the LSA and run the shortest path first (SPF) algorithm. There after the router that detected the failure adds the new route to the routing table, while its neighbors update the metric in their routing table. After approximately 30 seconds, the failed router sends an LSA after aging out the topology entry from router that detected the failure. After five seconds, all routers run the SPF algorithm again and update their routing tables to the path to the failed link. Convergence time is the total of detection time, plus LSA flooding time, plus the five seconds wait before the second SPF algorithm is run.