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
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-
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).
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
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