Network Bulls
www.networkbulls.com
Best Institute for CCNA CCNP CCSP CCIP CCIE Training in India
M-44, Old Dlf, Sector-14 Gurgaon, Haryana, India
Call: +91-9654672192
Distance vector–based routing algorithms (also known as Bellman-Ford-Moore algorithms) pass
periodic copies of a routing table from router to router and accumulate distance vectors. (Distance
means how far, and vector means in which direction.) Regular updates between routers
communicate topology changes.
Each router receives a routing table from its direct neighbor. For example, in Figure 3-5, Router
B receives information from Router A. Router B adds a distance vector metric (such as the number
of hops), increasing the distance vector. It then passes the routing table to its other neighbor,
Router C. This same step-by-step process occurs in all directions between direct-neighbor routers.
(This is also known as routing by rumor.)
Figure 3-5 Distance Vector Protocols
Table 3-1 Default Administrative Distance Values
Route Source Default Distance
Connected network 0
Static route 1
EIGRP 90
OSPF 110
RIPv2 120
External EIGRP 170
Unknown or unbelievable 255 (will not be added to the routing table to pass traffic)
D C B A
B
D
C A
Routing
Table
Distance = How far?
Vector = In which direction.
Routing
Table
Routing
Table
Routing
Table
104 Chapter 3: Medium-Sized Routed Network Construction
In this way, the algorithm accumulates network distances so that it can maintain a database of
internetwork topology information. Distance vector algorithms do not allow a router to know the
exact topology of an internetwork.
Route Discovery, Selection, and Maintenance
In Figure 3-6, the interface to each directly connected network is shown as having a distance of 0.
Figure 3-6 Routing Information Sources
As the distance vector network discovery process proceeds, routers discover the best path to
nondirectly connected destination networks based on accumulated metrics from each neighbor.
For example, Router A learns about other networks based on information it receives from Router
B. Each of these other network entries in the routing table has an accumulated distance vector to
show how far away that network is in the given direction.
When the topology in a distance vector protocol internetwork changes, routing table updates must
occur. As with the network discovery process, topology change updates proceed step by step from
router to router.
Distance vector algorithms call for each router to send its entire routing table to each of its adjacent
or directly connected neighbors. Distance vector routing tables include information about the total
path cost (defined by its metric) and the logical address of the first router on the path to each
network it knows about.
When a router receives an update from a neighboring router, it compares the update to its own
routing table. The router adds the cost of reaching the neighboring router to the path cost reported
by the neighbor to establish the new metric. If the router learns about a better route (smaller total
metric) to a network from its neighbor, the router updates its own routing table.
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
E0
S0
S0
0
0
1
2
Reviewing Dynamic Routing 105
For example, if Router B in Figure 3-7 is one unit of cost from Router A, Router B would add 1
to all costs reported by Router A when Router B runs the distance vector processes to update its
routing table. This would be maintained by the routers exchanging routing information in a timely
manner through some update mechanism.
Figure 3-7 Maintaining Routes
Routing Loops
When you are maintaining the routing information, routing loops can occur if the slow
convergence of the internetwork after a topology change causes inconsistent routing entries. The
example presented in the next few pages uses a simple network design to convey the concepts.
Later in this chapter, you look at how routing loops occur and are corrected in more complex
network designs. Figure 3-8 illustrates how each node maintains the distance from itself to each
possible destination network.
Figure 3-8 Maintaining Distance
Just before the failure of network 10.4.0.0, shown in Figure 3-9, all routers had consistent
knowledge and correct routing tables. The network is said to have converged. For this example,
A
Process to
Update This
Routing
Table
B
Process to
Update This
Routing
Table
Topology
Change
Causes
Routing
Table
Update
Router A Sends
Out This Updated
Routing Table
After the
Next Period
Expires
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
E0
S0
S0
0
0
1
2
106 Chapter 3: Medium-Sized Routed Network Construction
the cost function is hop count, so the cost of each link is 1. Router C is directly connected to
network 10.4.0.0, with a distance of 0. The path of Router A to network 10.4.0.0 is through Router
B, with a hop count of 2.
Figure 3-9 Slow Convergence Produces Inconsistent Routing
When network 10.4.0.0 fails, Router C detects the failure and stops routing packets out its E0
interface. However, Routers A and B have not yet received notification of the failure. Router A still
believes it can access 10.4.0.0 through Router B. The routing table of Router A still reflects a path
to network 10.4.0.0 with a distance of 2.
Because the routing table of Router B indicates a path to network 10.4.0.0, Router C believes it
has a viable path to network 10.4.0.0 through Router B. Router C updates its routing table to reflect
a path to network 10.4.0.0 with a hop count of 2, as illustrated in Figure 3-10.
Figure 3-10 Inconsistent Path Information Between Routers
Router B receives a new update from Router C (3 hops). Router A receives the new routing table
from Router B, detects the modified distance vector to network 10.4.0.0, and recalculates its own
distance vector to 10.4.0.0 as 4, as shown in Figure 3-11.
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
E0
S0
S0
0
Down
1
2
X
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
2
1
2
X
Reviewing Dynamic Routing 107
Figure 3-11 Inconsistent Data Continues to Propagate
Because Routers A, B, and C conclude that the best path to network 10.4.0.0 is through each other,
packets from Router A destined to network 10.4.0.0 continue to bounce between Routers B and C,
as illustrated in Figure 3-12.
Figure 3-12 Routing Loop Exists Because of Erroneous Hop Count
Continuing the example in Figure 3-12, the invalid updates about network 10.4.0.0 continue to
loop. Until some other process can stop the looping, the routers update each other inappropriately,
considering that network 10.4.0.0 is down.
This condition, called count-to-infinity, causes the routing protocol to continually increase its
metric and route packets back and forth between the devices, despite the fundamental fact that the
destination network, 10.4.0.0, is down. While the routing protocol counts to infinity, the invalid
information enables a routing loop to exist, as illustrated in Figure 3-13.
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
4
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
3
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
2
1
2
X
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
4
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
3
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
2
1
2
X
Packet for
Network 10.4.0.0
108 Chapter 3: Medium-Sized Routed Network Construction
Figure 3-13 Count-to-Infinity Condition
Without countermeasures to stop this process, the distance vector of hop count increments each
time the routing update is broadcast to another router. This causes data packets to be sent through
the network because of incorrect information in the routing tables. The following sections cover
the countermeasures that distance vector routing protocols use to prevent routing loops from
running indefinitely.
Troubleshooting Routing Loops with Maximum Metric Settings
IP packets have inherent limits via the Time-To-Live (TTL) value in the IP header. In other words,
a router must reduce the TTL field by at least 1 each time it gets the packet. If the TTL value
becomes 0, the router discards that packet. However, this does not stop the router from continuing
to attempt to send the packet to a network that is down.
To avoid this prolonged problem, distance vector protocols define infinity as some maximum
number. This number refers to a routing metric, such as a hop count.
With this approach, the routing protocol permits the routing loop until the metric exceeds its
maximum allowed value. Figure 3-14 shows this unreachable value as 16 hops. After the metric
value exceeds the maximum, network 10.4.0.0 is considered unreachable.
Figure 3-14 Maximum Metric
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
6
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
5
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
4
1
2
X
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
16
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
16
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
16
1
2
X
Reviewing Dynamic Routing 109
Preventing Routing Loops with Split Horizon
One way to eliminate routing loops and speed up convergence is through the technique called split
horizon. The split horizon rule is that sending information about a route back in the direction from
which the original update came is never useful. For example, Figure 3-15 illustrates the following:
■ Router B has access to network 10.4.0.0 through Router C. It makes no sense for Router B to
announce to Router C that Router B has access to network 10.4.0.0 through Router C.
■ Given that Router B passed the announcement of its route to network 10.4.0.0 to Router A, it
makes no sense for Router A to announce its distance from network 10.4.0.0 to Router B.
■ Having no alternative path to network 10.4.0.0, Router B concludes that network 10.4.0.0 is
inaccessible.
Figure 3-15 Split Horizon
Preventing Routing Loops with Route Poisoning
Another operation complementary to split horizon is a technique called route poisoning. Route
poisoning attempts to improve convergence time and eliminate routing loops caused by
inconsistent updates. With this technique, when a router loses a link, the router advertises the loss
of a route to its neighbor device. Route poisoning enables the receiving router to advertise a route
back toward the source with a metric higher than the maximum. The advertisement back seems to
violate split horizon, but it lets the router know that the update about the down network was
received. The router that received the update also sets a table entry that keeps the network state
consistent while other routers gradually converge correctly on the topology change. This
mechanism allows the router to learn quickly of the down route and to ignore other updates that
might be wrong for the hold-down period. This prevents routing loops.
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
E0
S0
S0
0
0
1
2
X X
110 Chapter 3: Medium-Sized Routed Network Construction
Figure 3-16 illustrates the following example. When network 10.4.0.0 goes down, Router C
poisons its link to network 10.4.0.0 by entering a table entry for that link as having infinite cost
(that is, being unreachable). By poisoning its route to network 10.4.0.0, Router C is not susceptible
to incorrect updates from neighboring routers, which may still have an outdated entry for network
10.4.0.0.
Figure 3-16 Route Poisoning
When Router B sees the metric to 10.4.0.0 jump to infinity, it sends an update called a poison
reverse to Router C, stating that network 10.4.0.0 is inaccessible, as illustrated in Figure 3-17. This
is a specific circumstance overriding split horizon, which occurs to make sure that all routers on
that segment have received information about the poisoned route.
Figure 3-17 Poison Reverse
Route Maintenance Using Hold-Down Timers
Hold-down timers prevent regular update messages from inappropriately reinstating a route that
might have gone bad. Hold-downs tell routers to hold any changes that might affect routes for
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
E0
S0
S0
0
Down
1
2
X
Metric = Infinity
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0
Routing Table
10.1.0.0
10.2.0.0
10.3.0.0
10.4.0.0
E0
S0
S0
S0
0
0
1
2
Routing Table
10.2.0.0
10.3.0.0
10.4.0.0
10.1.0.0
S0
S1
S1
S0
0
0
1
Routing Table
10.3.0.0
10.4.0.0
10.2.0.0
10.1.0.0
S0
S0
S0
S0
0
Infinity
1
2
X
Poison
Reverse
Possibly
Down
Reviewing Dynamic Routing 111
some period of time. The hold-down period is usually calculated to be just greater than the time
necessary to update the entire network with a routing change.
Hold-down timers perform route maintenance as follows:
1. When a router receives an update from a neighbor indicating that a previously accessible
network is now inaccessible, the router marks the route as inaccessible and starts a hold-down
timer.
2. If an update arrives from a neighboring router with a better metric than originally recorded
for the network, the router marks the network as accessible and removes the hold-down timer.
3. If at any time before the hold-down timer expires, an update is received from a different
neighboring router with a poorer metric, the update is ignored. Ignoring an update with a
higher metric when a holddown is in effect enables more time for the knowledge of the change
to propagate through the entire network.
4. During the hold-down period, routes appear in the routing table as “possibly down.”
Figure 3-18 illustrates the hold-down timer process.
Figure 3-18 Hold-Down Timers
Route Maintenance Using Triggered Updates
In the previous examples, routing loops were caused by erroneous information calculated as a
result of inconsistent updates, slow convergence, and timing. If routers wait for their regularly
scheduled updates before notifying neighboring routers of network catastrophes, serious problems
can occur, such as loops or traffic being dropped.
Normally, new routing tables are sent to neighboring routers on a regular basis. A triggered update
is a new routing table that is sent immediately, in response to a change. The detecting router
immediately sends an update message to adjacent routers, which, in turn, generate triggered
updates notifying their adjacent neighbors of the change. This wave propagates throughout the
portion of the network that was using the affected link. Figure 3-19 illustrates what takes place
when using triggered updates.
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0 X
Update After
Hold-Down Time
Update After
Hold-Down Time
Network 10.4.0.0
is unreachable.
Network 10.4.0.0 is down,
then back up, and
then back down.
112 Chapter 3: Medium-Sized Routed Network Construction
Figure 3-19 Triggered Updates
Triggered updates would be sufficient with a guarantee that the wave of updates reached every
appropriate router immediately. However, two problems exist:
■ Packets containing the update message can be dropped or corrupted by some link in the
network.
■ The triggered updates do not happen instantaneously. A router that has not yet received the
triggered update can issue a regular update at just the wrong time, causing the bad route to be
reinserted in a neighbor that had already received the triggered update.
Coupling triggered updates with holddowns is designed to get around these problems.
Route Maintenance Using Hold-Down Timers with Triggered Updates
Because the hold-down rule says that when a route is invalid, no new route with the same or a
higher metric will be accepted for the same destination for some period, the triggered update has
time to propagate throughout the network.
The troubleshooting solutions presented in the previous sections work together to prevent routing
loops in a more complex network design. As depicted in Figure 3-20, the routers have multiple
routes to each other. As soon as Router B detects the failure of network 10.4.0.0, Router B removes
its route to that network. Router B sends a trigger update to Routers A and D, poisoning the route
to network 10.4.0.0 by indicating an infinite metric to that network.
Figure 3-20 Implementing Multiple Solutions
Routers D and A receive the triggered update and set their own hold-down timers, noting that the
10.4.0.0 network is “possibly down.” Routers D and A, in turn, send a triggered update to Router
E, indicating the possible inaccessibility of network 10.4.0.0. Router E also sets the route to
E0 A B C
S0
S0
10.1.0.0 10.2.0.0 10.4.0.0
S0
S1 E0
10.3.0.0 X
Network 10.4.0.0
is unreachable.
Network 10.4.0.0
is unreachable.
Network 10.4.0.0
is unreachable.
E B C
A
D
10.4.0.0
X
Reviewing Dynamic Routing 113
10.4.0.0 in holddown. Figure 3-21 depicts the way Routers A, D, and E implement hold-down
timers.
Figure 3-21 Route Fails
Router A and Router D send a poison reverse to Router B, stating that network 10.4.0.0 is
inaccessible. Because Router E received a triggered update from Routers A and D, it sends a
poison reverse to Routers A and D. Figure 3-22 illustrates the sending of poison reverse updates.
Figure 3-22 Route Holddown
Routers A, D, and E will remain in holddown until one of the following events occurs:
■ The hold-down timer expires.
■ Another update is received, indicating a new route with a better metric.
■ A flush timer, which is the time a route will be held before being removed, removes the route
from the routing table.
10.4.0.0
E B C
D
A
X
Holddown
Holddown
Holddown
E B C
A
D
10.4.0.0
X
Holddown
Holddown
Holddown
Poison Reverse
Poison Reverse
Poison Reverse
Poison Reverse
114 Chapter 3: Medium-Sized Routed Network Construction
During the hold-down period, Routers A, D, and E assume that the network status is unchanged
from its original state and attempt to route packets to network 10.4.0.0. Figure 3-23 illustrates
Router E attempting to forward a packet to network 10.4.0.0. This packet will reach Router B.
However, because Router B has no route to network 10.4.0.0, Router B will drop the packet and
return an Internet Control Message Protocol (ICMP) network unreachable message.
Figure 3-23 Packets During Holddown
When the 10.4.0.0 network comes back up, Router B sends a trigger update to Routers A and D,
notifying them that the link is active. After the hold-down timer expires, Routers A and D add route
10.4.0.0 back to the routing table as accessible, as illustrated in Figure 3-24.
Figure 3-24 Network Up
10.4.0.0
E B C
D
A
X
Holddown
Holddown
Packet for
Network 10.4.0.0
Packet for
Network 10.4.0.0
Holddown
10.4.0.0
E B Link Up! C
D
A
Reviewing Dynamic Routing 115
Routers A and D send Router E a routing update stating that network 10.4.0.0 is up, and Router E
updates its routing table after the hold-down timer expires, as illustrated in Figure 3-25.
Figure 3-25 Network Converges
Link-State and Advanced Distance Vector Protocols
In addition to distance vector–based routing, the second basic algorithm used for routing is the
link-state algorithm. Link-state protocols build routing tables based on a topology database. This
database is built from link-state packets that are passed between all the routers to describe the state
of a network. The shortest path first algorithm uses the database to build the routing table. Figure
3-26 shows the components of a link-state protocol.
Figure 3-26 Link-State Protocols
Understanding the operation of link-state routing protocols is critical to being able to enable,
verify, and troubleshoot their operation.
E B C
A
D
10.4.0.0
Link Up!
Link-State Packets
SPF
Algorithm
SPF Tree
Topological
Database
C A
B
D
Routing
Table
116 Chapter 3: Medium-Sized Routed Network Construction
Link-state-based routing algorithms—also known as shortest path first (SPF) algorithms—
maintain a complex database of topology information. Whereas the distance vector algorithm has
nonspecific information about distant networks and no knowledge of distant routers, a link-state
routing algorithm maintains full knowledge of distant routers and how they interconnect.
Link-state routing uses link-state advertisements (LSA), a topological database, the SPF
algorithm, the resulting SPF tree, and, finally, a routing table of paths and ports to each network.
Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are
classified as link-state routing protocols. RFC 2328 describes OSPF link-state concepts and
operations. Link-state routing protocols collect routing information from all other routers in the
network or within a defined area of the internetwork. After all the information is collected, each
router, independently of the other routers, calculates its best paths to all destinations in the
network. Because each router maintains its own view of the network, it is less likely to propagate
incorrect information provided by any one particular neighboring router.
Link-state routing protocols were designed to overcome the limitations of distance vector routing
protocols. Link-state routing protocols respond quickly to network changes, send triggered
updates only when a network change has occurred, and send periodic updates (known as link-state
refreshes) at long intervals, such as every 30 minutes. A hello mechanism determines the
reachability of neighbors.
When a failure occurs in the network, such as a neighbor becomes unreachable, link-state
protocols flood LSAs using a special multicast address throughout an area. Each link-state router
takes a copy of the LSA, updates its link-state (topological) database, and forwards the LSA to all
neighboring devices. LSAs cause every router within the area to recalculate routes. Because LSAs
need to be flooded throughout an area and all routers within that area need to recalculate their
routing tables, you should limit the number of link-state routers that can be in an area.
A link is similar to an interface on a router. The state of the link is a description of that interface
and of its relationship to its neighboring routers. A description of the interface would include, for
example, the IP address of the interface, the mask, the type of network to which it is connected,
the routers connected to that network, and so on. The collection of link states forms a link-state,
or topological, database. The link-state database is used to calculate the best paths through the
network. Link-state routers find the best paths to a destination by applying Dr. Edsger Dijkstra’s
SPF algorithm against the link-state database to build the SPF tree. The best paths are then selected
from the SPF tree and placed in the routing table.
Reviewing Dynamic Routing 117
As networks become larger in scale, link-state routing protocols become more attractive for the
following reasons:
■ Link-state protocols always send updates when a topology changes.
■ Periodic refresh updates are more infrequent than for distance vector protocols.
■ Networks running link-state routing protocols can be segmented into area hierarchies,
limiting the scope of route changes.
■ Networks running link-state routing protocols support classless addressing.
■ Networks running link-state routing protocols support route summarization.
Link-state protocols use a two-layer network hierarchy, as shown in Figure 3-27.
Figure 3-27 Link-State Network Hierarchy
The two-layer network hierarchy contains two primary elements:
■ Area: An area is a grouping of networks. Areas are logical subdivisions of the autonomous
system (AS).
■ Autonomous system: An AS consists of a collection of networks under a common
administration that share a common routing strategy. An AS, sometimes called a domain, can
be logically subdivided into multiple areas.
Area 0
Autonomous System
Area 1 Area 2
Router A
Router B Router C
Router D Router E
118 Chapter 3: Medium-Sized Routed Network Construction
Within each AS, a contiguous backbone area must be defined. All other nonbackbone areas are
connected off the backbone area. The backbone area is the transition area because all other areas
communicate through it. For OSPF, the nonbackbone areas can be additionally configured as a
stub area, a totally stubby area, a not-so-stubby area (NSSA), or a totally not-so-stubby area to
help reduce the link-state database and routing table size.
Routers operating within the two-layer network hierarchy have different routing entities. The
terms used to refer to these entities are different for OSPF than IS-IS. Refer to the following
examples from Figure 3-27:
■ Router A is called the backbone router in OSPF and the L2 router in IS-IS. The backbone, or
L2, router provides connectivity between different areas.
■ Routers B and C are called area border routers (ABR) in OSPF, and L1/L2 routers in IS-IS.
ABR, or L1/L2, routers attach to multiple areas, maintain separate link-state databases for
each area to which they are connected, and route traffic destined for or arriving from other
areas.
■ Routers D and E are called nonbackbone internal routers in OSPF, or L1 routers in IS-IS.
Nonbackbone internal, or L1, routers are aware of the topology within their respective areas
and maintain identical link-state databases about the areas.
■ The ABR, or L1/L2, router will advertise a default route to the nonbackbone internal, or L1,
router. The L1 router will use the default route to forward all interarea or interdomain traffic
to the ABR, or L1/L2, router. This behavior can be different for OSPF, depending on how the
OSPF nonbackbone area is configured (stub area, totally stubby area, or not-so-stubby area).
Link-State Routing Protocol Algorithms
Link-state routing algorithms, known collectively as SPF protocols, maintain a complex database
of the network topology. Unlike distance vector protocols, link-state protocols develop and
maintain full knowledge of the network routers and how they interconnect. This is achieved
through the exchange of link-state packets (LSP) with other routers in a network.
Each router that has exchanged LSPs constructs a topological database using all received LSPs.
An SPF algorithm is then used to compute reachability to networked destinations. This
information is employed to update the routing table. The process can discover changes in the
network topology caused by component failure or network growth.
In fact, the LSP exchange is triggered by an event in the network, instead of running periodically.
This can greatly speed up the convergence process because it is unnecessary to wait for a series of
timers to expire before the networked routers can begin to converge.
Reviewing Dynamic Routing 119
If the network shown in Figure 3-28 uses a link-state routing protocol, connectivity between New
York City and San Francisco is not a concern. Depending on the actual protocol employed and the
metrics selected, it is highly likely that the routing protocol could discriminate between the two
paths to the same destination and try to use the best one.
Figure 3-28 Link-State Algorithms
Table 3-2 summarizes the contents of the routing database of each router in the figure.
Table 3-2 Link-State Routing Database
Router Destination Next Hop Cost
A 185.134.0.0 B 1
192.168.33.0 C 1
192.168.157.0 B 2
192.168.157.0 C 2
B 10.0.0.0 A 1
192.168.33.0 C 1
192.168.157.0 D 1
Network
10.0.0.0
Network
185.134.0.0
A
B
New York
San Francisco
Cost = 1
Network
192.168.33.0
Network
192.168.157.0
C
D
Boston
Los Angeles
Cost = 1
Cost = 1
Cost = 1
Cost = 1
continues
120 Chapter 3: Medium-Sized Routed Network Construction
As shown in the table link-state database entries for the New York (Router A) to Los Angeles
(Router D) routes, a link-state protocol would remember both routes. Some link-state protocols
can even provide a way to assess the performance capabilities of these two routes and bias toward
the better-performing one. If the better-performing path, such as the route through Boston (Router
C), experienced operational difficulties of any kind, including congestion or component failure,
the link-state routing protocol would detect this change and begin forwarding packets through San
Francisco (Router B).
Link-state routing might flood the network with LSPs during initial topology discovery and can
be both memory- and processor-intensive. This section describes the benefits of link-state routing,
the caveats to consider when using it, and the potential problems.
The following list highlights some of the many benefits that link-state routing protocols have over
the traditional distance vector algorithms, such as RIP-1 or the now obsolete Interior Gateway
Routing Protocol (IGRP):
■ Link-state protocols use cost metrics to choose paths through the network. For Cisco IOS
devices, the cost metric reflects the capacity of the links on those paths.
■ By using triggered, flooded updates, link-state protocols can immediately report changes in
the network topology to all routers in the network. This immediate reporting generally leads
to fast convergence times.
■ Because each router has a complete and synchronized picture of the network, it is difficult for
routing loops to occur.
■ Because LSPs are sequenced and aged, routers always base their routing decisions on the
latest set of information.
■ With careful network design, the link-state database sizes can be minimized, leading to
smaller SPF calculations and faster convergence.
Router Destination Next Hop Cost
C 10.0.0.0 A 1
185.134.0.0 B 1
192.168.157.0 D 1
D 10.0.0.0 B 2
10.0.0.0 C 2
185.134.0.0 B 1
192.168.33.0 C 1
Table 3-2 Link-State Routing Database (Continued)
Reviewing Dynamic Routing 121
The link-state approach to dynamic routing can be useful in networks of any size. In a welldesigned
network, a link-state routing protocol enables your network to gracefully adapt to
unexpected topology changes. Using events, such as changes, to drive updates, rather than fixedinterval
timers, enables convergence to begin that much more quickly after a topological change.
The overhead of the frequent, time-driven updates of a distance vector routing protocol is also
avoided. This makes more bandwidth available for routing traffic rather than for network
maintenance, provided you design your network properly.
A side benefit of the bandwidth efficiency of link-state routing protocols is that they facilitate
network scalability better than either static routes or distance vector protocols. When compared to
the limitations of static routes or distance vector protocols, you can easily see that link-state
routing is best in larger, more complex networks, or in networks that must be highly scalable.
Initially configuring a link-state protocol in a large network can be challenging, but it is well worth
the effort in the long run.
Link-state protocols do, however, have the following limitations:
■ They require a topology database, an adjacency database, and a forwarding database, in
addition to the routing table. This can require a significant amount of memory in large or
complex networks.
■ Dijkstra’s algorithm requires CPU cycles to calculate the best paths through the network. If
the network is large or complex (that is, the SPF calculation is complex), or if the network is
unstable (that is, the SPF calculation is running on a regular basis), link-state protocols can
use significant CPU power.
■ To avoid excessive memory or CPU power, a strict hierarchical network design is required,
dividing the network into smaller areas to reduce the size of the topology tables and the length
of the SPF calculation. However, this dividing can cause problems because areas must remain
contiguous at all times. The routers in an area must always be capable of contacting and
receiving LSPs from all other routers in their area. In a multiarea design, an area router must
always have a path to the backbone, or it will have no connectivity to the rest of the network.
In addition, the backbone area must remain connected at all times to avoid some areas
becoming isolated (partitioned).
■ The configuration of link-state networks is usually simple, provided that the underlying
network architecture has been soundly designed. If the network design is complex, the
operation of the link-state protocol might have to be tuned to accommodate it.
■ During the initial discovery process, link-state routing protocols can flood the network with
LSPs and significantly decrease the capability of the network to transport data because no
traffic is passed until after the initial network convergence. This performance compromise is
122 Chapter 3: Medium-Sized Routed Network Construction
temporary but can be noticeable. Whether this flooding process will noticeably degrade
network performance depends on two things: the amount of available bandwidth and the
number of routers that must exchange routing information. Flooding in large networks with
relatively small links, such as low-bandwidth links, is much more noticeable than a similar
exercise on a small network with large links, such as T3s and Ethernet.
■ Link-state routing is both memory- and processor-intensive. Consequently, more fully
configured routers are required to support link-state routing than distance vector routing. This
increases the cost of the routers that are configured for link-state routing.
The following are some of the benefits of a link-state routing protocol:
■ Troubleshooting is usually easier in link-state networks because every router has a complete
copy of the network topology, or at least of its own area of the network. However, interpreting
the information stored in the topology, neighbor databases, and routing table requires an
understanding of the concepts of link-state routing.
■ Link-state protocols usually scale to larger networks than distance vector protocols,
particularly the traditional distance vector protocols such as RIPv1 and IGRP.
You can address and resolve the potential performance impacts of both drawbacks through
foresight, planning, and engineering.
Advanced Distance Vector Protocol Algorithm
The advanced distance vector protocol, or hybrid routing protocol, uses distance vectors with more
accurate metrics to determine the best paths to destination networks. However, it differs from most
distance vector protocols by using topology changes to trigger routing database updates, as
opposed to periodic updates.
This routing protocol converges more rapidly, like the link-state protocols. However, it differs
from link-state protocols by emphasizing economy in the use of required resources, such as
bandwidth, memory, and processor overhead.
An example of an advanced distance vector protocol is the Cisco Enhanced Interior Gateway
Routing Protocol (EIGRP).
Summary of Reviewing Routing Operations
The following list summarizes the key points discussed in this section:
■ Dynamic routing requires administrators to configure either a distance vector or a link-state
routing protocol.
Implementing Variable-Length Subnet Masks 123
■ Distance vector routing protocols incorporate solutions such as split horizon, route poisoning,
and hold-down timers to prevent routing loops.
■ Link-state routing protocols scale to large network infrastructures better than distance vector
routing protocols, but they require more planning to implement.
No comments:
Post a Comment