Slow Convergence with RIP
RIP (Routing Information Protocol) is a distance vector protocol. A RIP router periodically broadcasts a routing update message, which contains an entry for each network it can reach and the cost to that network. RIP routers listen to all RIP broadcast messages. Each entry in a received routing update message is added to the local routing table. The router that sends the routing update message is remembered as the next router or hop on the route to the network in the entry. If a router learns about two routes to a network, it keeps the one with the lower cost. Cost is often defined in RIP in terms of hop count, or the number of routers along the path to the destination. RIP allows a maximum cost or hop count of 15.
Once a route is learned, it must be refreshed at certain intervals, thereby ensuring that the route is still valid. RIP routers usually broadcast a routing update message containing known routes every 30 seconds. A timer is started when a route is learned from a routing update message. If subsequent routing update messages do not refresh the route within 180 seconds, the route is assumed to be unusable. Then the route is removed from the routing table.
RIP II is an enhancement to RIP I. It includes the subnet mask in its routes; consequently, RIP II can support subnet topologies better than RIP I. The lack of subnet mask information limits RIP I to advertising only network routes or requires RIP I routers to make assumptions about the subnet mask. When RIP I is used in a network with subnets, all the subnets are usually required to use the same subnet mask. Both versions of RIP support subnet zero.
RIP II can be used in network topologies requiring variable length subnet masks. It can also authenticate routing message exchanges. RIP II uses multicast addresses instead of broadcast addresses. Not all routers support both RIP I and RIP II.
RIP routers can experience inconsistencies in their routing tables. This is due to the convergence time, the length of time it takes for all the RIP routing tables to synchronize with each other when a change occurs in the network. The most serious reason for RIP's slow convergence, known as the count-to-infinity problem, is illustrated in the scenario shown in Figure 2-17.
Figure 2-17.
Slow Convergence with RIP
In Figure 2-17, the arrows show the route to destination D. Router R2 has learned its route to destination D from router R3. If R3's link to destination D goes down, R3 drops the route to D from its routing table. Because R2 still has a valid route to D, R2 will send to R3 a RIP update stating that it can reach destination D at a cost of two hops. R3 calculates that it can reach destination D in three hops, one hop to reach R2 and then two more hops to destination D. Then R3 enters a new route to destination D into its routing table.
This process creates a routing loop. In this scenario, any data packet that is destined for destination D, received by either R3 or R2, is routed back and forth until its time-to-live counter expires.
As R3 and R2 continue to update each other, the updating process takes some time to resolve. Because R2 does not learn the route to D with a cost of one from R3 anymore, its route to D with a cost of two eventually expires. Then R2 learns that R3's distance from destination D is three, and it calculates a new cost for its route to destination D, with a cost of four. In the next round, R3 increases its cost to five. Both routers continue to increase their cost to destination D until a cost of 16 is finally reached. Once the cost reaches 16, the route is considered invalid and removed from the routing table. The synchronization of routing tables can take several minutes.
Novell Internet Access Server 4.1 employs several techniques for solving slow convergence caused by the count-to-infinity problem: split horizon, poison reverse, and triggered updates.
Split horizon is enabled automatically. When this feature is used, routes are not propagated back onto the same interface from which they are learned. To solve the problem shown in Figure 2-17, split horizon prevents R2 from advertising a route for destination D to R3. Because R3 does not receive misleading information about the route to D, it does not update its routing table with a route to D through R2. R3 stops advertising a route to D; consequently, R2 eventually times out its route to D.
With poison reverse, instead of not being propagated, routes that are learned from an interface are advertised with a cost of 16 on the same interface from which they were learned.
Split horizon does not solve the slow convergence problem if more than two routers are involved in the routing loop, as for example, when R3 is one hop away from destination D and routers R1 and R2 are two hops away from destination D, as shown in Figure 2-18. If the link to destination D goes down, R3 learns that destination D is unreachable and stops advertising to R1 and R2.
The split horizon rule does not allow R1 or R2 to tell R3 about its distance to destination D. As a result, R1 and R2 might conclude that destination D is reachable in the following scenario.
Figure 2-18.
Slow Convergence with Three Routers in a Loop
R1 and R2 do not learn the route to D anymore. Consequently, the route to D on both routers times out. Suppose the route times out on R1 before it does on R2. Within the time that R2 has the route but R1 does not, if R2 advertises the route to R1, R1 takes it and concludes it is three hops from destination D (based on information from R2 that it is two hops from D). Then R1 informs R3 that it is three hops from D. R3 assumes that it is four hops from D and that D is in the direction of R1. The route with a cost of two eventually times out on R2. Because R3 informs R2 that it is four hops from D, R2 concludes that it is five hops from D and adds a new route for D with a cost of five. The loop continues.
The count-to-infinity problem still exists in this loop of three routers. To avoid this problem, RIP uses triggered updates.
Triggered updates cause the router to send a RIP update as soon as a new route is learned or an existing route is lost or changed. The triggered update contains only the affected routes, for example, the route with a cost of 16 if it is lost, or with a new cost if it is changed, or a new route. This way, the router minimizes the amount of time it retains outdated routes. To solve the slow convergence problem shown in Figure 2-18, triggered updates cause R3 to advertise destination D as unreachable as soon as the last link to destination D fails. Then R1 and R2 immediately lose the route to D, and the chance of R2 and R1 updating each other is reduced.
Both RIP I and RIP II support subnetting. RIP I only partially supports subnetting because it does not include subnet mask information in its advertisements. However, a RIP router can derive subnet mask information from its interfaces. By assuming that the subnet masks are fixed for all subnets of the same network, RIP I applies the derived subnet mask to all remote subnets in the same network.
This method of subnet support requires a fixed subnet mask for a given network. Therefore, RIP I does not support variable length subnet masks. See "Variable Size Subnets.” In addition, the subnet mask information derived from the interface is applied only to the network to which the interface belongs. Subnet information from remote networks is not available to the RIP I router. Consequently, RIP I does not support subnets of remote networks.
Because the RIP I routers external to the network do not know the subnets used within a network, RIP I requires that all subnet routes are aggregated into a single network route when they are advertised externally. To accomplish this, all subnets must be contained within a single network boundary.
Unlike RIP I, RIP II fully supports subnetted networks and variable size subnets.