UNIX System Administration Handbook - Evi Nemeth [209]
Routing protocols have a major advantage over static routing systems in that they can react and adapt to changing network conditions. If a link goes down, the routing daemons can quickly discover and propagate alternate routes to the networks that link served, if any exist.
Routing daemons collect information from three sources: configuration files, the existing routing tables, and routing daemons on other systems. This information is merged to compute an optimal set of routes, and the new routes are then fed back into the system routing table (and possibly fed to other systems through a routing protocol). Because network conditions change over time, routing daemons must periodically check in with each other to reassure themselves that their routing information is still current.
The exact way that routes are computed depends on the routing protocol. Two types of protocols are in common use: distance-vector protocols and link-state protocols.
Distance-vector protocols
Distance-vector (aka “gossipy”) protocols are based on the general idea, “If router X is five hops away from network Y, and I’m adjacent to router X, then I must be six hops away from network Y.” You announce how far you think you are from the networks you know about. If your neighbors don’t know of a better way to get to each network, they mark you as being the best gateway. If they already know a shorter route, they ignore your advertisement.3
Over time, everyone’s routing tables are supposed to converge to a steady state.
This is really a very elegant idea. If it worked as advertised, routing would be relatively simple. Unfortunately, this type of algorithm does not deal well with changes in topology. In some cases, infinite loops (e.g., router X receives information from router Y and sends it on to router Z, which sends it back to router Y) can prevent routes from converging at all. Real-world distance-vector protocols must avoid such problems by introducing complex heuristics or by enforcing arbitrary restrictions such as the RIP (Routing Information Protocol) notion that any network more than 15 hops away is unreachable.
Even in nonpathological cases, it can take many update cycles for all routers to reach a steady state. Therefore, to guarantee that routing will not jam for an extended period, the cycle time must be made short, and for this reason distance-vector protocols as a class tend to be talkative. For example, RIP requires that routers broadcast all of their routing information every 30 seconds. IGRP and EIGRP send updates every 90 seconds.
On the other hand, BGP, the Border Gateway Protocol, transmits the entire table once and then transmits changes as they occur. This optimization substantially reduces the potential for “chatty” (and mostly unnecessary) traffic.
Table 14.1 lists the distance-vector protocols that are in common use today.
Table 14.1 Common distance-vector routing protocols
Link-state protocols
Link-state protocols distribute information in a relatively unprocessed form. The records traded among routers are of the form “Router X is adjacent to router Y, and the link is up.” A complete set of such records forms a connectivity map of the network from which each router can compute its own routing table. The primary advantage that link-state protocols offer over distance-vector protocols is the ability to quickly converge on an operational routing solution after a catastrophe occurs. The tradeoff is that maintaining a complete “map” of the network at each node requires memory and CPU power that would not be needed by a distance-vector routing system.
Because the communications among routers in a link-state protocol are not part of the actual route-computation algorithm, they can be implemented in such a way that transmission loops do not occur. Updates to the topology database propagate across the network efficiently, at a lower cost in