Distance Vector Versus Link-State Protocols

This section takes a look at routing protocol from a different perspective. In the previous sections, we considered general classification such as classful versus classless and also IGP versus EGP. This section discusses classification based on design and operation. The second row in Table 1-4 places the protocols discussed so far into four different categories, two of which stand out—distance vector and link-state. These two broad categories actually apply to IGP as shown in the table.

EIGRP is essentially a distance vector protocol just like IGRP, except that it is rightfully considered in its own class as an advanced distance vector protocol because it has more modern characteristics, such as support of classless routing and fast convergence. BGP is also in its own category, path vector protocol because, as an interdomain routing protocol, it uses the AS path attribute, which is made up of the list of autonomous systems that a route has traversed as a key measure for route comparison and selection.

Versions 1 and 2 of RIP (RIP-1 and RIP-2) and IGRP are classified as distance vector protocols because they use route-computation algorithms based on the Bellman-Ford algorithm. The Bellman- Ford algorithm is used in graph theory for calculating the shortest distance between two vertices in a directed graph. A directed graph is a collection of points, interconnected with directional links, such as the nodes and links in an internetwork. Routers running distance vector routing protocols use the Bellman-Ford algorithm for determining the shortest paths to all known locations in the network.

OSPF and Integrated IS-IS are both link-state protocols and use the shortest path first algorithm (Dijkstra) for route computation. Just like the Bellman-Ford algorithm, the Dijkstra algorithm provides an alternate method for computing the shortest distance between two points in a directed graph.

EIGRP uses a Cisco Systems–patented algorithm known as the Diffusing Update Algorithm (DUAL) to optimize route calculation, breaking away from its predecessor, IGRP, which is based on the Bellman- Ford algorithm.

The type of algorithm used by a protocol for route computation goes a long way toward affecting the efficiency of the protocol and how fast it converges. The following sections examine the concepts and operational principles behind distance vector protocols and link-state protocols.

Distance Vector Routing Concepts

This section reviews key concepts that underlie the operation of distance vector routing protocols, such as metrics, count to infinity, split horizon, holddowns, and triggered updates. These concepts are evaluated in terms of general routing functionality, such as stability and speed of convergence and loop avoidance.

Distance Vector Metrics

In the Bellman-Ford algorithm, each router advertises the best paths to all known des-tinations, from its perspective, to all neighbors. The links between routers are assigned a measure known as cost or metric. The metric can be determined from characteristics of the links, such as hop count, bandwidth, delay, reliability, monetary value, and so on. The hop count associated with a link between two directly connected nodes is usually 1, even though arbitrary values can be administratively assigned. The metric associated with a specific path to a known destination from any router is the sum of all the metrics of links along that path. Usually, the path with the lowest metric is the best. A router might have many neighbors and, therefore, might receive multiple paths for the same destination. It then computes the metric associated with each of these paths and selects the best path by a criterion such as the lowest metric.

RIP uses hop count for metric, with the maximum possible number of hops to any reachable destinations being 15. A metric of 16 hops or more is considered to be infinity. Hence, a hop count of 15 defines the maximum width of reachability in a RIP network. This imposes a limit on the size of RIP-based networks, which also implies that RIP is suitable for only small, flat networks. Hop count actually pertains to the node count from a specific source to a destination and has no consideration for actual network characteristics, such as bandwidth, delay, or monetary costs.

IGRP, which is also a distance vector protocol, uses a metric system that takes into consider-ation relevant characteristics of the network, such as bandwidth, associated maximum trans-mission unit, reliability of links, and also path delay. The metric assigned to each link in the outgoing direction is calculated from a formula that takes into consideration all these char-acteristics. This sort of multifaceted metric is called a composite metric.

The Bellman-Ford algorithm uses a vector (distance vector), consisting of cost (metric) and next-hop information for each known route to determine best paths in the network from any standpoint. An iterative procedure calculates the cost of all paths for any received route and selects the vector with the best cost for each route. Hence, routing protocols that are based on the Bellman-Ford algorithm commonly are referred to as distance vector protocols (see Table 1-4).

Routing Convergence

When there is a topology change, a router might invalidate some of the previously known best paths. The router then uses new or existing information to determine an alternate best path for each affected destination. Recalculating routes to rediscover alternate routes as a result of network topology changes is referred to as routing convergence. Routing convergence may be triggered by events such as router failures, link failures, or even administrative metric adjustments.

Distance vector protocols such as RIP and IGRP are relatively simple compared to their link-state counterparts. However, this simplicity comes with a price. Because each router bases its best-path determination on the best paths advertised by neighbors, such protocols are very prone to routing loops. A routing loop occurs when two nodes point to each other as the next hop along the path to the same destination. The most obvious effect of routing loops is that they prolong the time it takes for a router to determine a route is no longer available or to select an alternate path. Routing loops adversely impact convergence times. Therefore, it is desirable that unusable routes be removed from the network as soon as possible. The following sections discuss various methods employed by distance vector protocols to prevent or limit the effect of routing loops and improve convergence. The following is discussed:

• Counting to infinity

• Using holddown

• Using split horizon and poison reverse

• Using triggered updates

Loop Avoidance

Routers running distance vector protocols determine best paths for routes relative to neigh-bors that have advertised those routes to them. The mechanics of operation of distance vector protocols, specifically the way routes are advertised by distance vector protocols, makes such environments very susceptible to routing loops—for example, when a router running a distance vector protocol broadcasts routing updates over all interfaces activated for the protocol. When a router broadcasts all known routes in this manner, it may advertise a route back to the source it was heard from. Consequently, when there is a failure, it is possible for two neighboring nodes to think that the other is the next hop along the best path to a specific destination. This situation, which results in a routing loop, is elaborated in Figure 1-10.

Figure 1-10. Routing Loops in Distance Vector Environments