Routers develop a hop-by-hop mechanism by keeping track of “next
hop” information that enables a data packet to find its destination
through the network. A router that does not have a direct physical connection
to the destination checks its routing table and forwards the packet to another
next hop router that is closer to that destination. The process repeats until
the traffic finds its way through the network to its final destination.
EGPs, such as BGP, were introduced because IGPs do not scale in networks
that go beyond the enterprise level. IGPs were never designed for the purpose
of global internetworking because they do not have the necessary hooks to
segregate enterprises into different administrations that are technically
and politically independent from one another. This chapter touches upon basic
IGP functionality and then explains the specifics of BGP.
Figure 4-1 describes three routers,
RTA, RTB, and RTC, connecting three local area networks, 126.96.36.199, 188.8.131.52,
and 184.108.40.206, via serial links. Each serial link is repesented by its own
network number, which results in three additional networks, 220.127.116.11, 18.104.22.168,
and 22.214.171.124. Each network has a metric associated with it indicating the
level of overhead (cost) of transmitting traffic on that particular link.
The link between RTA and RTB, for example, has a cost of 2,000, much higher
than the cost of 60 of the link between RTA and RTC. In practice, the link
between RTA and RTB is a 56 Kbps link with much bigger delays than the T1
link between RTA and RTC and the T1 link between RTC and RTB combined.
Routers RTA, RTB, and RTC would exchange network information via some
interior gateway protocol and build their respective IP routing tables. Figure 4-1 shows examples of RTA's IP routing
table for two different scenarios; the routers are exchanging routing information
via RIP in one scenario and OSPF in another.
As an example of how traffic is passed between end stations, if host
126.96.36.199 is trying to reach host 188.8.131.52, it will first send the traffic
to RTA. RTA will look in its IP routing table for any network that matches
this destination and would find that network 184.108.40.206 is reachable via next
hop 220.127.116.11 (RTC) out on Serial line 2 (S2). RTC would receive the traffic
and would try to look for the destination in its IP routing table (not shown).
RTC would discover that the host is directly connected to its Ethernet 0 interface
(E0) and would send the traffic to 18.104.22.168.
In the preceding example, the routing is the same whether RTA is using
the RIP or OSPF scenario. RIP and OSPF, however, fall into different categories
of IGP protocols, namely distance vector protocols and link state protocols,
respectively. For a different routing example in figure
4-1, the results might be different depending on whether you
are looking at the RIP or OSPF scenario. It is useful at this point to consider
characteristics of both IGP protocol categories, to see how protocols generally
have evolved to meet increasingly sophisticated routing demands.
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 22.214.171.124. 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, such as the Open Shortest Path First (OSPF) 
and Intermediate System-to-Intermediate System (ISIS) , 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 countNo limits on the number of hops a route can
take. Link state protocols work on the basis of metrics rather than
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 126.96.36.199 (RTC) to reach 188.8.131.52 (RTB). This is in contrast to
the RIP scenario, which resulted in a suboptimal path.
Bandwidth representationLink 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 convergenceLink 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 CIDRLink 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 hierarchyWhereas 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.