Distance Vector Protocols

Distance vector protocols such as RIP version 1 were mainly designed for small network topologies. The term distance vector derives from the fact that the protocol includes in its routing updates a vector of distances (hop counts). By using hop counts, distance vector protocols do not factor into the routing equation the overhead of sending information over a particular link. Low-speed links are treated equally or sometimes preferred over a high-speed link, depending on the calculated hop count in reaching a destination. This would lead to suboptimal and inefficient routing behaviors.

Consider, for example, the RTA routing tables shown in figure 4-1. In the RIP case, RTA has listed the direct link between RTA and RTB to reach network 192.10.5.0. RTA prefers this link because it requires just one hop via RTB versus two hops via RTC and then RTB. But the preferred route is inefficient because the total cost of the routing path via RTC and then RTB (60 + 60 = 120) is much less than the cost of crossing the RTA-RTB link (2,000).

Another issue with hop counts is the count to infinity restriction: distance vector protocols have a finite limit of hops (15) after which a route is considered unreachable. This would restrict the propagation of routing updates and would cause problems for large networks.

The reliance on hop counts is one deficiency of distance vector protocols; another deficiency is the way that the routing information gets exchanged. Distance vector algorithms work on the concept that routers exchange all the network numbers they can reach via periodic broadcasts of the entire routing table. In large networks, the routing table exchanged between routers becomes very large and very hard to maintain, leading to slower convergence.

Convergence refers to the point in time at which the entire network becomes updated to the fact that a particular route has appeared or disappeared. Distance vector protocols work on the basis of periodic updates and hold-down timers: If a route is not received in a certain amount of time, the route goes into a hold-down state and gets aged out of the routing table. The hold-down and aging process translates into minutes in convergence time before the whole network detects that a route has disappeared. The delay between a route's becoming unavailable and its aging out of the routing tables can result in routing loops and black holes.

Another major drawback of distance vector protocols is their classfull nature and their lack of support of Variable Length Subnet Masks or CIDR. Distance vector protocols do not exchange mask information in their routing updates. A router that receives a routing update on a certain interface will apply to this update its locally defined subnet mask. This would lead to confusion, in case the interface belongs to a network that is variably subnetted, and a misinterpretation of the received routing update.

Finally, distance vector networks are considered to be flat. They present a lack of hierarchy, which translates into a lack of aggregation. This flat nature has made distance vector protocols incapable of scaling to larger and more efficient enterprise networks.

RIP version 2 has added support for VLSM and CIDR, but it still carries most of the other deficiencies that its predecessor, RIP version 1, has.

Link State Protocols

Link state protocols, such as the Open Shortest Path First (OSPF) [1] and Intermediate System-to-Intermediate System (ISIS) [2], are more advanced routing protocols that have addressed the deficiencies of distance vector protocols. Link state protocols work on the basis that routers exchange information elements, called link states, which carry information about links and nodes. This means that routers running link state protocols do not exchange routing tables. Each router inside a domain will have enough bits and pieces of the big puzzle that it can run a shortest path algorithm and build its own routing table.

Following are some of the benefits that link state protocols provide over distance vector protocols:

•  No hop count—No limits on the number of hops a route can take. Link state protocols work on the basis of metrics rather than hop counts.
As an example of a link state protocol's reliance on metrics rather than hop count, turn again to the RTA routing tables shown in figure 4-1. In the OSPF case, RTA has picked the optimal path to reach RTB by factoring in the cost of the links. Its routing table lists the next hop of 192.10.3.2 (RTC) to reach 192.10.5.0 (RTB). This is in contrast to the RIP scenario, which resulted in a suboptimal path.

•  Bandwidth representation—Link bandwidth and delays are factored in when calculating the shortest path to a certain destination. This leads to better load-balancing based on actual link cost rather than hop count.

•  Better convergence—Link and node changes are flooded into the domain via link state updates. All routers in the domain will immediately update their routing tables.

•  Support for VLSM and CIDR— Link state protocols exchange mask information as part of the information elements that are flooded in the domain. As a result, networks with variable length masks can be easily identified.

•  Better hierarchy—Whereas distance vector networks are flat networks, link state protocols divide the domain into different levels and areas. This hierarchical approach provides better control over network instabilities and a better mechanism to summarize routing updates across areas, specifically, by lumping multiple contiguous routing updates into supersets of routing updates called aggregates.

Even though link state algorithms have provided better routing scalability, which enables them to be used in bigger and more complex topologies, they still should be restricted to interior routing. Link state protocols, by themselves, cannot provide a global connectivity solution required for Internet interdomain routing. In very large networks and in case of route fluctuation caused by link instabilities, link state retransmission and recomputation will become too large for any router to handle.