Enhanced Interior Gateway Routing Protocol (EIGRP)
CCIE Professional Development: Routing TCP/IP Volume I
Author: Jeff Doyle
Publisher: Cisco Press (53)
First released in IOS 9.21, Enhanced Interior Gateway Routing protocol
(EIGRP) is, as the name says, an enhancement of IGRP. The name is apt because
unlike RIPv2, EIGRP is
far more than the same protocol with some added extensions. EIGRP remains
a distance vector protocol and uses the same composite metrics as IGRP uses.
Beyond that, there are few similarities.
EIGRP is occasionally described as a distance
vector protocol that acts like a link state protocol. To recap the extensive
discussion in Chapter 4, a distance vector protocol
shares everything it knows but only with directly connected neighbors. Link
state protocols announce information only about their directly connected links,
but they share the information with all routers in their routing domain or
All the distance vector protocols discussed so far run some variant
of the Bellman- Ford (or Ford-Fulkerson) algorithm. These protocols are prone
to routing loops and counting to infinity. As a result, they must implement
loop-avoidance measures such as split horizon, route poisoning, and hold-down
timers. Because each router must run the routing algorithm on received routes
before passing those routes along to its neighbors, larger internetworks may
be slow to converge. More important, distance vector protocols advertise routes;
the change of a critical link may mean the advertisement of many changed routes.
Compared to distance vector protocols, link state protocols are far
less susceptible to routing loops and bad routing information. The forwarding
of link state packets is not dependent on performing the route calculations
first, so large internetworks may converge faster. And only links and their
states are advertised, not routes, which means the change of a link will not cause
the advertisement of all routes using that link. However, compared to distance
vector algorithms, the complex Dijkstra algorithms and the associated databases
place a higher demand on CPU and memory.
Regardless of whether other routing protocols perform route calculations
before sending distance vector updates to neighbors or after building a topological
database, their common denominator is that they perform the calculations individually.
In contrast, EIGRP uses a system of diffusing computationsroute
calculations that are performed in a coordinated fashion among multiple routersto
attain fast convergence while remaining loop free at every instant.
Although EIGRP updates are still vectors
of distances transmitted to directly connected neighbors, they are nonperiodic,
partial, and bounded. Nonperiodic means that updates
are not sent at regular intervals; rather, updates are sent only when a metric
or topology change occurs. Partial means that the updates
will include only routes that have changed, not every entry in the route table. Bounded
means that the updates are sent only to affected routers. These characteristics
mean that EIGRP uses much less bandwidth than typical distance vector protocols
use. This feature can be especially important on low-bandwidth, high-cost
Another concern when routing
over low-bandwidth WAN links is the maximum amount of bandwidth used during
periods of convergence, when routing traffic is high. By default, EIGRP
uses no more than 50% of the bandwidth of a link. Later IOS releases allow
this percentage to be changed with the command ip
EIGRP is a classless protocol (that is, each route entry in an update
includes a subnet mask). Variable-length subnet masks may be used with EIGRP
not only for sub-subnetting as described in Chapter 7,“Routing
Information Protocol Version 2,” but also for address aggregationthe
summarization of a group of major network addresses.
Beginning with IOS 11.3, EIGRP packets can be authenticated using an MD5 cryptographic checksum. The basics of authentication and MD5
are covered in Chapter 7; an example of configuring
EIGRP authentication is included in this chapter.
Finally, a major feature of EIGRP is that it can route
not only IP but also IPX and AppleTalk.
EIGRP uses the same formula as IGRP uses to calculate its
composite metric. However, EIGRP scales the metric components by 256 to achieve
a finer metric granularity. So if the minimum configured bandwidth on the
path to a destination is 512K and the total configured delay is 46000 microseconds,
IGRP would calculate a composite metric of 24131. (See Chapter
6, “Interior Gateway Routing Protocol (IGRP),” for a detailed
discussion of IGRP metric calculations.) EIGRP, however, will multiply the
bandwidth and delay components by 256 for a metric of 256 × 24131 =
EIGRP has four components (Figure
Reliable Transport Protocol (RTP)
Neighbor Discovery/ Recovery
Diffusing Update Algorithm (DUAL)
Figure 8.1. The four major components of EIGRP. RTP and neighbor discovery are
lower-level protocols that enable the correct operation of DUAL. DUAL can
perform route computations for multiple routed protocols.
This section examines each EIGRP component, with
particular emphasis on DUAL, and ends with a discussion of address aggregation.
EIGRP implements modules for
IP, IPX, and AppleTalk, which are responsible for the protocol-specific routing
tasks. For example, the IPX EIGRP module is responsible for exchanging route
information about IPX networks with other IPX EIGRP processes and for passing
the information to the DUAL. Additionally, the IPX module will send and receive
As Figure 8.1 shows, the traffic for
the individual modules is encapsulated withisn their respective network layer
protocols. EIGRP for IPX, for example, is carried in IPX packets.
EIGRP will automatically redistribute with other protocols in many cases:
IPX EIGRP will automatically redistribute with IPX RIP and
AppleTalk EIGRP will automatically redistribute with AppleTalk
IP EIGRP will automatically redistribute routes with IGRP
if the IGRP process is in
the same autonomous system.
The configuration section includes an example of redistributing between
IGRP and EIGRP. (Redistribution with other IP routing protocols is the subject
of Chapter 11, “Route Redistribution.”)
Configuration of EIGRP for IPX and AppleTalk is outside the scope of
this book. Refer to
the Cisco Configuration Guide for more information.
Transport Protocol (RTP) manages the delivery and reception of EIGRP packets. Reliable delivery means
that delivery is guaranteed and that packets will be delivered in order.
Guaranteed delivery is accomplished by means of a Cisco-proprietary
algorithm known as reliable multicast, using the reserved
class D address 184.108.40.206. Each neighbor receiving a reliably multicast packet
will unicast an acknowledgment.
Ordered delivery is ensured by including two sequence numbers in the
packet. Each packet includes a sequence number assigned by the sending router.
This sequence number is incremented by one each time the router sends a new
packet. In addition, the sending router places in the packet the sequence
number of the last packet received from the destination router.
In some cases, RTP may use unreliable delivery. No acknowledgment is
required, and no sequence number will be included for unreliably delivered
EIGRP uses multiple packet types, all of which are identified by protocol number 88
in the IP header.
Hellos are used by the neighbor discovery
and recovery process. Hello packets
are multicast and use unreliable delivery.
Acknowledgments (ACKs) are Hello
packets with no data
in them. ACKs are always unicast and use unreliable delivery.
Updates convey route information. Unlike
RIP and IGRP updates, these packets are transmitted only when necessary, contain
only necessary information, and are sent only to routers that require the
information. When updates are required by a specific router, they are unicast.
When updates are required by multiple routers, such as upon a metric or topology
change, they are multicast. Updates always use reliable delivery.
Queries and Replies
are used by the DUAL finite state machine to manage its diffusing computations.
Queries can be multicast or unicast, and replies are always unicast. Both
queries and replies use reliable delivery.
Requestswere a type of packet originally
intended for use in route servers. This application was never implemented,
and request packets are noted here only because they are mentioned in some
older EIGRP documentation.
If any packet is reliably multicast and an ACK is not
received from a neighbor, the packet will be retransmitted as a unicast to
that unresponding neighbor. If an ACK is not received after 16 of these unicast
retransmissions, the neighbor will be declared dead.
The time to wait for an ACK before switching from multicast to unicast
is specified by the multicast
flow timer. The time between the subsequent unicasts is specified
by the retransmission timeout (RTO). Both the multicast
flow timer and the RTO are calculated for each neighbor from the smooth
round-trip time (SRTT). The SRTT is the average elapsed time, measured
in milliseconds, between the transmission of a packet to the neighbor and
the receipt of an acknowledgment. The formulas for calculating the exact values of the
SRTT, the RTO, and the multicast flow timer are proprietary.
The following two subsections discuss the EIGRP components that use
the various packet types.
Because EIGRP updates are
nonperiodic, it is especially important to have a process whereby neighborsEIGRP-speaking
routers on directly connected networksare discovered and tracked. On most
networks, Hellos are multicast every
5 seconds, minus a small random time to prevent synchronization. On multipoint
X.25, Frame Relay, and ATM interfaces, with access link speeds of T1 or
slower, Hellos are unicast every 60 seconds.2 This longer Hello
interval is also the default for ATM SVCs and for ISDN PRI interfaces. In
all cases, the Hellos are unacknowledged. The default Hello interval can
be changed on a per interface basis with the command
ip hello-interval eigrp.
When a router receives a Hello packet from a neighbor, the packet will
include a hold time. The hold
time tells the router the maximum time it should wait to receive subsequent
Hellos. If the hold timer expires before a Hello is received, the neighbor
is declared unreachable and DUAL is informed of the loss of a neighbor.
By default, the hold time is three times the Hello interval180 seconds
for low-speed non-broadcast
multi-access (NBMA) networks and 15 seconds for all other networks. The
default can be changed on a per interface basis with the command
ip hold-time eigrp. The capability to detect a lost neighbor within
15 seconds, as opposed to 180 seconds for RIP and 270 seconds for IGRP,
is one factor contributing to EIGRP's fast reconvergence.
Information about each neighbor is recorded in a neighbor table. As Figure 8.2 shows, the neighbor table
records the IP address of the neighbor and the interface on which the neighbor's
Hellos are received. The hold time advertised by the neighbor is recorded, as
is the SRTT and the uptimethe time since
the neighbor was added to the table. The RTO is the time, in milliseconds,
that the router will wait for an acknowledgment of a unicast packet sent after
a multicast has failed. If an EIGRP update, query, or reply is sent, a copy
of the packet will be queued. If the RTO expires before an ACK is received,
another copy of the queued packet is sent. The Q Count indicates the number
of enqueued packets. The sequence number of the last update, query, or reply
packet received from the neighbor is also recorded in the neighbor table.
The RTP tracks these sequence numbers to ensure that packets from the neighbor
are not received out of order. Finally, the H column records the order in
which the neighbors were learned.
Figure 8.2. The command show ip eigrp neighbors is used to observe the IP EIGRP
The design philosophy behind DUAL is that even temporary routing loops are detrimental to the
performance of an internetwork. DUAL uses diffusing computations, first proposed
by E. W. Dijkstra and C. S. Scholten,3 to perform
distributed shortest-path routing while maintaining freedom from loops at
every instant. Although many researchers have contributed to the development
of DUAL, the most prominent work is that of J. J. Garcia-Luna-Aceves. 4
For DUAL to operate correctly, a lower-level protocol must
assure that the following conditions are met5:
A node detects within a finite time the existence of a new
neighbor or the loss of connectivity with a neighbor.
All messages transmitted over an operational link are received
correctly and in the proper sequence within a finite time.
All messages, changes in the cost of a link, link failures,
and new-neighbor notifications are processed one at a time within a finite
time and in the order in which they are detected.
Cisco's EIGRP uses Neighbor Discovery/Recovery and RTP to establish
Before the operation of DUAL can be examined, a few terms and concepts
must be described.
Upon startup, a router uses Hellos to discover neighbors and to identify
itself to neighbors. When a neighbor is discovered, EIGRP will attempt to
form an adjacency with that neighbor. An adjacency
is a virtual link between two neighbors over which route information is exchanged.
When adjacencies have been established, the router will receive updates from
its neighbors. The updates will contain all routes known by the sending routers
and the metrics of those routes. For each route, the router will calculate
a distance based on the distance advertised by the neighbor and the cost of
the link to that neighbor.
The lowest calculated metric to each destination will become the feasible distance (FD) of that
destination. For example, a router may be informed of three different routes
to subnet 172.16.5.0 and may calculate metrics of 380672, 12381440, and 660868
for the three routes. 380672 will become the FD because
it is the lowest calculated distance.
condition(FC) is a condition that
is met if a neighbor's advertised distance to a destination is lower than
the router's FD to that same destination.
If a neighbor's advertised distance to a destination meets the FC, the
neighbor becomes a feasible successor6 for that destination. For example, if the
FD to subnet 172.16.5.0 is 380672 and a neighbor advertises a route to that
subnet with a distance of 355072, the neighbor will become a feasible successor;
if the neighbor advertises a distance of 380928, it will not satisfy the FC
and will not become a feasible successor.
The concepts of feasible successors and the FC are central to loop avoidance.
Because feasible successors are always “downstream” (that is,
a shorter metric distance to the destination than the FD), a router will never
choose a path that will lead back through itself. Such a path would have a
distance larger than the FD.
Every destination for which one or more feasible successors exist will
be recorded in a topological table, along with the following
The destination's FD
All feasible successors
Each feasible successor's advertised distance to the destination
The locally calculated distance to the destination via each
feasible successor, based on the feasible successor's advertised distance
and the cost of the link to
The interface connected to the network
on which each feasible successor is found7
For every destination listed in the topological table, the route with the
lowest metric is chosen and placed into the route table. The neighbor advertising
that route becomes
the successor, or the next-hop router to which packets
for that destination are sent.
An example will help clarify these terms, but first a brief discussion
of the internetwork used in the examples in this section is necessary.
Figure 8.3 shows the EIGRP-based internetwork
that is used throughout this and the next three subsections.8
The command metric
weights 0 00 1 0 0 has been added to the EIGRP process so that only
delay is used in the metric calculations. The delay
command has been used with the numbers shown at each link; for example,
the interfaces of routers Wright and Langley, connected
to subnet 10.1.3.0, have been configured with a delay of 2. These steps
have been taken to simplify the examples that follow.
It should be pointed out that although the delay parameters used here
sacrifice realism for simplicity, the way the metrics are manipulated
is realistic. Many parameters are calculated from an interface's bandwidth
specification; some, such as the ip
bandwidth-percent eigrp, apply directly to EIGRP. Others, such as
OSPF cost, do not. As a result, changes of the configured bandwidth should
be avoided except to set serial links to their actual bandwidth. If interface
metrics need to be manipulated to influence EIGRP (or IGRP) routing, use
delay. Many unexpected headaches can be avoided.
Figure 8.3. The examples and illustrations of this and the next two subsections
are based on this EIGRP network.
In Figure 8.4, the command
show ip eigrp topology is used to observe the topology
table of router Langley. Each of the seven subnets shown in Figure
8.3 is listed, along with the feasible
successors for the subnets. For example, the feasible successors for subnet
10.1.6.0 are 10.1.3.1 (Wright) and 10.1.5.2 (Chanute), via interfaces
S0 and S1, respectively.
Two metrics in parentheses are also associated with each feasible successor.
The first number is the locally calculated metric from Langley to the destination.
The second number is the metric advertised by the neighbor. For example, in Figure 8.3 the metric from Langley to subnet 10.1.6.0
via Wright is 256 x (2 + 1 + 1) = 1024, and the metric advertised by Wright
for that destination is 256 x (1 + 1) = 512. The two metrics for the same
destination via Chanute are 256 x (4 + 1 + 1 + 1) = 1792 and 256 x (1 + 1
+ 1) = 768.
The lowest metric from Langley to subnet
10.1.6.0 is 1024, so that is the feasible distance (FD). Figure
8.5 shows Langley's route table, with the chosen successors.
Figure 8.5. Langley's route table shows that a single successor has been chosen
for each known destination, based on the lowest metric distance.
Langley has only one successor for every route. The topology table of
Cayley (Figure 8.6) shows that there are two
successors for 10.1.4.0 because the locally calculated metric for both
routes matches the FD. Both routes are entered into the route table (Figure 8.7), and
Cayley will perform equal-cost load balancing.
Figure 8.6. The topology table of Cayley, showing two successors to subnet 10.1.4.0.
Figure 8.7. Equal-cost load sharing will be performed between the two successors
The topology table of Chanute (Figure 8.8)
routes for which there is only one feasible successor. For example, the route
to 10.1.6.0 has an FD of 768, and Wright (10.1.2.1) is the only feasible successor.
Langley has a route to 10.1.6.0, but its metric is 256 x (2 + 1 + 1) = 1024,
which is greater than the FD. Therefore, Langley's route to 10.1.6.0 does
not satisfy the FC, and Langley does not qualify as a feasible successor.
Figure 8.8. Several of the subnets reachable from Chanute have only one feasible
If a feasible successor advertises a route for which the locally calculated
metric is lower than the metric via the present successor, the feasible successor
will become the successor. The following conditions can cause this situation
For example, Figure 8.9 shows that Lilienthal's successor
to subnet 10.1.3.0 is Cayley (10.1.6.2). Suppose the cost of the link between
Lilienthal and Wright is decreased to one. Wright (10.1.4.1) is advertising
a distance of 512 to subnet 10.1.3.0; with the new cost of the link to Wright,
Lilienthal's locally calculated metric to the subnet via that router is now
768. Wright will replace Cayley as the successor to subnet 10.1.3.0.
Next, suppose Lilienthal discovers a new neighbor that is advertising
a distance of 256 to subnet 10.1.3.0. This distance is lower than the FD,
so the new neighbor will become a feasible successor. Suppose further
that the cost of the link to the new neighbor is 256. Lilienthal's locally
calculated metric to 10.1.3.0 via the new neighbor will be 512. This metric
is lower than the distance via Wright, so
o the new
neighbor will become the successor to 10.1.3.0.
Feasible successors are important because they reduce the number of
diffusing computations and therefore increase performance. Feasible successors
also contribute to lower reconvergence times. If a link to a successor fails
or if the cost of the link increases beyond the FD, the router will first
look into its topology table for a feasible successor. If one is found, it
will become the successor. The router will only begin a diffusing computation
if a feasible successor cannot be found.
The following section gives a more formal set of rules for when and
how a router will search for feasible successors. This set of rules is called
the DUAL finite state machine.
When an EIGRP router is performing no diffusing
computations, each route is in the passive
state. Referring to any of the topology tables in the previous
section, a key to the left of each route indicates a passive state.
A router will reassess its list of feasible successors for a route,
as described in the last section, any time an input event
occurs. An input event can be:
A change in the cost of a directly connected link
A change in the state (up or down) of a directly connected
The reception of an update packet
The reception of a query packet
The reception of a reply packet
The first step in its reassessment
is a local
computation in which the distance to the destination is recalculated
for all feasible successors. The possible results are:
If the feasible successor with the lowest distance is different
from the existing successor, the feasible successor will become the successor.
If the new distance is lower than the FD, the FD will be updated.
If the new distance is different from the existing distance,
updates will be sent to all neighbors.
While the router is performing a local computation, the route remains
in the passive state. If a feasible successor
is found, an update is sent to all neighbors and no state change occurs.
If a feasible successor cannot
be found in the topology table, the router will begin a diffusing computation
and the route will change to the active
state.Until the diffusing computation is completed and the route transitions back
to the passive state, the router cannot:
Change the route's successor
Change the distance it is advertising for the route
Change the route's FD
Begin another diffusing computation for the route
A router begins a diffusing computation by sending queries to all of
its neighbors (Figure 8.10). The query will
contain the new locally calculated distance to the destination. Each neighbor,
upon receipt of the query, will perform its own local computation:
If the neighbor has one or more feasible successors for the
destination, it will send a reply
to the originating router. The reply will contain that neighbor's minimum
locally calculated distance to the destination.
If the neighbor does not have a feasible successor, it too
will change the route to the active state and will begin a diffusing computation.
For each neighbor to which a query is sent, the router will set a reply
status flag (r) to keep track of all outstanding queries. The diffusing
computation is complete when the router has received a reply to every
query sent to every neighbor.
In some cases, a router does not receive a reply to every query sent.
For example, this may happen in large networks with many low-bandwidth or
low-quality links. At the beginning of the diffusing computation, an Active
timer is set for 3 minutes.9 If all expected replies
are not received before the Active time expires, the route is declared stuck-in-active(SIA).
The neighbor or neighbors that did
not reply will be removed from the neighbor table, and the diffusing computation will consider the neighbor
to have responded with an infinite metric.
Figure 8.10. A diffusing computation grows as queries are sent and shrinks as replies
The default 3-minute Active time can be changed or disabled with the
active-time. The deletion of a neighbor because of a lost query obviously
can have disruptive results, and SIAs should never occur in a stable,
well-designed internetwork. The troubleshooting section of this chapter
discusses SIAs in more detail.
At the completion of the diffusing computation, the originating router
will set FD to infinity to ensure that any neighbor replying with a finite
distance to the destination will meet the FC and become a feasible successor.
For each of these replies, a metric is calculated based on the distance advertised
in the reply plus the cost of the link to the neighbor who sent the reply.
A successor is selected based on the lowest metric, and FD is set to this
metric. Any feasible successors that do not satisfy the FC for this new FD
will be removed from the topology table. Note that a successor is not chosen
until all replies have been received.
Since there are multiple types of input events that can cause a route
to change state, some of which may occur while a route is active, DUAL defines
multiple active states. A query origin flag (O) is used to indicate
the current state. Figure 8.11 and Table 8.1 show the complete DUAL finite state machine.
Table 8.1. Input events for the DUAL finite state machine.
input event for which FC is satisfied or the destination is unreachable
Query received from
the successor; FC not satisfied
Input event other than a query from the successor; FC not satisfied
Input event other
than last reply or a query from the successor
Input event other than last reply, a query from the successor,
or an increase in distance to destination
Input event other than last reply
Input event other than last
reply or increase in distance to destination
Increase in distance to destination
Last reply received; FC not
met with current FD
Query received from the successor
Last reply received; FC met
with current FD
Last reply received; set FD to infinity
8.11. The DUALfinite state machine. The query origin flag(o) marks
the current state of the diffusing calculation. See Table
8.1 for a description of each input event(IE).
Two examples will help clarify the DUAL process. Figure
8.12 shows the example network, focusing only on each router's path
to subnet 10.1.7.0; refer to Figure 8.3 for
specific addresses. On the data links, an arrow indicates the successor each
router is using to reach 10.1.7.0. In parentheses are each router's locally
calculated distance to the subnet, the router's FD, the reply status flag
(r), and the query origin flag (O), respectively. Active routers are indicated with a circle.
This example focuses only on Cayley and its route
to subnet 10.1.7.0. In Figure 8.13, the link
between Cayley and Wright (10.1.1.1) has failed. EIGRP interprets the failure
as a link with an infinite distance10. Cayley checks its topology table for
a feasible successor to 10.1.7.0 and finds none (refer to Figure
Figure 8.12. All routes to subnet 10.1.7.0 are in the passive state, indicated by
r = 0 and O = 1.
Figure 8.13. The link between Wright and Cayley has failed, and Cayley does not
have a feasible successor to subnet 10.1.7.0.
Cayley's route becomes active (Figure 8.14).
The distance and the FD of the route are changed to unreachable, and a query
containing the new distance is sent to Cayley's neighbor, Lilienthal. Cayley's
reply status flag for Lilienthal is set to one, indicating that a reply is
expected. Because the input event was not the reception of a query (IE3),
Figure 8.14. Cayley's route to 10.1.7.0 transitions to active, and Lilienthal is
queried for a feasible successor.
Upon receipt of the query, Lilienthal performs a local computation (Figure 8.15). Because Lilienthal has a
feasible successor for 10.1.7.0 (see Figure 8.9),
the route does not become active. Wright becomes the new successor, and a
reply is sent with Lilienthal's distance to 10.1.7.0 via Wright. Because the
distance to 10.1.7.0 has increased and the route
did not become active, the FD is unchanged at Lilienthal.
Upon receipt of the reply from Lilienthal, Cayley sets r=0 and the route
becomes passive (Figure 8.16). Lilienthal
becomes the new successor, and the FD is set to the new distance. Finally,
an update is sent to Lilienthal with Cayley's locally calculated
metric. Lilienthal will also send an update advertising its new metric.
EIGRP packet activity can be observed with the debug
eigrp packets. By default, all EIGRP packets are displayed. Because
Hellos and ACKs can make the debug output hard to follow, the command
allows the use of optional keywords so that only specified packet types
are displayed. In Figure
eigrp packets queryreply update is used to observe the packet activity
at Cayley for the events described in this example.
Figure 8.15. Lilienthal has a feasible successor to 10.1.7.0. A local computation
is performed, a reply is sent to Cayley with the distance via Wright, and
an update is sent to Wright.
Figure 8.16. Cayley's route to 10.1.7.0 becomes passive, and an update is sent to
Figure 8.17. The EIGRP packet events described in this example can be observed in
these debug messages.
Flags, in the debug messages, indicate the state
of the flags in the EIGRP packet header (see the
section “The EIGRP Packet Header” later in this chapter). 0x0
indicates that no flags are set. 0x1 indicates that the initialization
bit is set. This flag is set when the enclosed route entries are the first
in a new neighbor relationship. 0x2 indicates that the conditional
receive bit is set. This flag is used in the proprietary Reliable
is the Packet Sequence Number/Acknowledged Sequence Number.
indicates packets in the input queue/packets in the output queue of the interface.
indicates unreliable multicast packets awaiting transmission/reliable multicast
packets awaiting transmission on the interface.
peerQ indicates unreliable unicast packets
awaiting transmission/ reliable unicast packets awaiting transmission on the
serno is a pointer to a doubly linked serial number
for the route. This is used by an internal (and proprietary) mechanism for
tracking the correct route information in a rapidly changing
This example focuses on Wright
and its route to subnet 10.1.7.0. Although the combination of input events
portrayed here (the delay of a link changing twice during a diffusing computation)
is unlikely to occur in real life, the example shows how DUAL handles multiple
In Figure 8.18, the cost of the link
between Wright and Langley changes from 2 to 10. The distance to 10.1.7.0
via Langley now exceeds Wright's FD, causing that router to begin a local
computation. The metric is updated, and Wright sends updates to all its neighbors
except the neighbor on the link whose cost changed (Figure
Note that Langley was the only feasible
successor to subnet 10.1.7.0 because Chanute's locally calculated metric is
higher than Wright's FD (1024 > 768). The metric
increase on the Wright-Langley link causes Wright to look in its topology
table for a new successor. Because the only feasible successor that Wright
can find in its topology table is Langley, the route becomes active. Queries
are sent to the neighbors (Figure 8.20).
At the same time, the updates sent by Wright in Figure
8.19 cause Cayley, Lilienthal, and Chanute to perform a local calculation.
At Cayley, the route via Wright now exceeds Cayley's FD (2816 > 1024).
The route goes active and queries are sent to the neighbors.
Figure 8.18. Cayley's route to 10.1.7.0 becomes passive, and an update is sent to
Figure 8.19. Wright sends updates containing the new metric to all neighbors except
Figure 8.20. Wright's route to 10.1.7.0 becomes active, and it queries its neighbors
for a feasible successor. In response to the earlier update from Wright, Cayley
makes its route active and queries its neighbors; also, Chanute changes its
metric and sends updates.
Lilienthal is using Cayley as a successor and in Figure
8.20 has not yet received the query from Cayley. Therefore, Lilienthal
merely recalculates the metric of the path via Wright, finds that it no longer
meets the FC, and drops the path from the topology table.
At Chanute, Wright is the successor. Because Wright's advertised distance
no longer meets the FC at Chanute (2816 > 1024) and because Chanute does have
a feasible successor
(refer to Figure 8.8), Wright is deleted from
Chanute's topology table. Langley becomes the successor at Chanute; the metric
is updated, and Chanute sends updates to its neighbors (refer to Figure
8.20). The route at Chanute never becomes active.
Cayley, Lilienthal, and Chanute each respond differently to the queries
from Wright (Figure 8.21).
Figure 8.21. Cayley (a) replies to Wright's query. Lilienthal (b) replies to Wright's
query and (c) goes active for the route, sending queries in response to Cayley's
query. Chanute (d) replies to Wright's query. Wright (e) replies to Cayley's
Cayley is already active. Because the input event is a query from the
successor, the query origin flag will be 2 (O=2) (refer to Figure
8.11 and Table 8.1).
Lilienthal, upon the receipt of Wright's query, sends a response with
its distance via Cayley. However, just after the reply is sent, Lilienthal
receives the query from Cayley. The FD is exceeded, the metric is updated,
and the route goes active. Lilienthal queries its neighbors.
Chanute, which has already switched to Langley as its successor, merely
sends a reply.
While all this is going on, Figure 8.21
shows that the cost of the link between Wright and Langley again increases,
from 10 to 20. Wright will recalculate the metric
to 10.1.7.0 based on this new cost, but because the route is active, neither
the FD nor the distance it advertises will change until the route becomes
According to Figure 8.11 and Table 8.1, an increase in the distance to the
destination while the route is active will cause O=0 (Figure
8.22). Wright responds to the query from Lilienthal. The distance it
reports is the distance it had when the route first became active (remember,
the advertised distance cannot change while the route is active). Cayley also
sends a reply to Lilienthal's query.
Figure 8.22. Wright cannot change the metric it advertises until the route becomes
Lilienthal, having received replies to all its queries, will transition
the route to passive (Figure 8.23). A new
FD is set for the route. Cayley remains the successor because its advertised
route is lower than the FD at Lilienthal. Lilienthal also sends a reply to
Figure 8.23 also shows that the distance
has changed again, from 20 to 15. Wright recalculates its local distance for
the route again, to 4096 (Figure 8.24). If
it were to receive a query before going passive, the route would still be
advertised with a distance of 2816the distance when the route went
Figure 8.23. Having received the last expected reply, Lilienthal changes its route
to the passive state (r=0, O=1).
When Cayley receives the reply to its query, its route to 10.1.7.0 also
becomes passive (Figure 8.24) and a new FD
is set. Although Wright's locally calculated metric is 4096, the last metric
it advertised was 2816. Therefore, Wright meets the FC at Cayley and becomes
the successor to 10.1.7.0. A reply is sent to Wright.
In Figure 8.25, Wright has received
a reply to every query it sent, and its route becomes passive. It chooses
Chanute as its new successor and changes the FD to the sum of Chanute's advertised
distance and the cost of the link to that neighbor. Wright sends an update
to all its neighbors, advertising the new locally calculated metric.
Cayley is already using Wright as the successor. When it receives the
update from Wright with a lower cost, it changes its locally calculated metric
and FD accordingly and updates its neighbors (Figure
The update from Cayley has no effect at Wright because it does not satisfy
the FC there. At Lilienthal the update causes a local computation.
Figure 8.24. Having received its last expected reply, Cayley changes its route to
the passive state.
Figure 8.25. Wright transitions to passive, chooses Chanute as the successor, changes
the FD, and updates all neighbors.
Figure 8.26. Cayley recalculates its metric, changes the FD based on the lower cost
advertised by Wright, and updates its neighbors.
Lilienthal lowers the metric, lowers the
FD, and updates its neighbors (Figure 8.27).
Figure 8.27. Lilienthal recalculates its metric, changes the FD based on the update
from Cayley, and updates its neighbors.
Although they are rather elaborate and may take several readings to
fully understand, this and the previous example contain the important core
behavior of diffusing computations:
Any time an input event occurs, perform a local calculation.
If one or more feasible successors are found in the topology
table, make the one(s) with the lowest metric cost the successor(s).
If no feasible successor can be found, make the route active
and query the neighbors for a feasible successor.
Keep the route active until all queries are answered by a
reply or by the expiration of the active timer.
If the diffusing calculation does not result in the discovery
of a feasible successor, declare the destination
The IP header of an EIGRP packet specifies protocol number 88, and the maximum length of
the packet will be the IP maximum transmission unit (MTU)usually 1500
octets. Following the IP header is an EIGRP header followed by various Type/Length/Value
(TLV) triplets. These TLVs will not only carry the route entries but also
may provide fields for the management of the DUAL process, multicast sequencing,
and IOS software versions.
Figure 8.28 shows the EIGRP header, which begins every EIGRP packet.
Version specifies the particular version of the
originating EIGRP process. Although two software releases of EIGRP are currently
available,11 the version of the EIGRP process itself
has not changed since its release.
Opcode specifies the EIGRP packet type, as shown
in Table 8.2. Although the IPX SAP packet
type is included in the table, a discussion of IPX EIGRP is outside the scope
of this book.
Checksum is a standard IP
checksum. It is calculated for the entire EIGRP
packet, excluding the IP header.
Flags currently include just two flags. The right-most
bit is Init, which when set (0x00000001) indicates that
the enclosed route entries are the first in a new neighbor relationship. The
second bit (0x00000002) is the Conditional Receive bit, used in the proprietary
Reliable Multicasting algorithm.
Sequenceis the 32-bit sequence number used by the
ACK is the 32-bit sequence number last heard from
the neighbor to which the packet is being sent. A Hello packet with a nonzero
ACK field will be treated as an ACK packet rather than as a Hello. Note that
an ACK field will only be nonzero if the packet itself is unicast because
acknowledgments are never multicast.
Autonomous System Number is the identification number of the EIGRP domain.
Following the header are the TLVs, whose various types are listed in Table 8.3. IPX and AppleTalk types are included,
although they are not discussed in this book. Each TLV includes one of the
two-octet type numbers listed in Table 8.3,
a two-octet field specifying the length of the TLV, and a variable field whose
format is determined
by the type.
Table 8.3. Type/length/value (TLV) types.
General TLV Types
Next Multicast Sequence
IP-Specific TLV Types
IP Internal Routes
IP External Routes
AppleTalk-Specific TLV Types
AppleTalk Internal Routes
AppleTalk External Routes
AppleTalk Cable Configuration
IPX-Specific TLV Types
IPX Internal Routes
IPX External Routes
These TLVs carry EIGRP management
information and are not specific to any one routed protocol. The Parameters
TLV, which is used to convey metric weights and the hold time, is shown in Figure 8.29. The Sequence, Software Version, and
Next Multicast Sequence TLVs are used by Cisco's proprietary Reliable Multicast
algorithm and are beyond the scope of this book.
Each Internal and External Routes TLV contains one route entry. Every Update, Query, and Reply packet
contains at least one Routes TLV.
The Internal and External Routes TLVs include metric information for
the route. As noted earlier, the metrics used by EIGRP are the same metrics
used by IGRP, although scaled by 256, and are discussed in more detailalong
with the calculation of the composite metricin Chapter
IP Internal Routes TLV
An internal route is a path to a destination within the EIGRP autonomous
system. The format of the Internal Routes TLV is shown in Figure
Next Hop is the next-hop
IP address. This address may or may not be the address of the originating
router. Delay is the sum of the configured delays
expressed in units of 10 microseconds. Notice that unlike the 24-bit delay
field of the IGRP packet, this field is 32 bits. This larger field accommodates
the 256 multiplier used by EIGRP. A delay of 0xFFFFFFFF indicates an unreachable
Bandwidth is 256 * BWIGRP(min),
or 2,560,000,000 divided by the lowest configured bandwidth of any interface
along the route. Like Delay, this field is also eight bits larger than the IGRP field.
MTU is the smallest
Transmission Unit of any link along the route to the destination. Although
an included parameter, it has never been used in the calculation of metrics.
Hop Count is a number between 0x01 and 0xFF indicating
the number of hops to the destination. A router will advertise a directly
connected network with a hop count of 0; subsequent routers will record and
advertise the route relative to the next-hop router.
Reliability is a number between 0x01 and 0xFF that
reflects the total outgoing error rates of the interfaces along the route,
calculated on a 5-minute exponentially weighted average. 0xFF indicates a
100% reliable link.
Load is also a number between 0x01 and 0xFF, reflecting
the total outgoing load of the interfaces along the route, calculated on a
5-minute exponentially weighted average. 0x01 indicates
a minimally loaded link.
Reserved is an unused field and is always 0x0000.
Prefix Length specifies the number of network bits of the address mask. Destinationis
the destination address of the route. Although the field is shown as a three-octet
field in Figures 8.30 and 8.31,
the field varies with the specific address. For example, if the route is to
10.1.0.0/16, the prefix length will be 16 and the destination will be a two-octet
field containing 10.1. If the route is to 192.168.17.64/27, the prefix length
will be 27 and the destination will be a four-octet field containing 192.168.16.64.
If this field is not exactly three octets, the TLV will be padded with zeros
to make it end on a
IP External Routes TLV
An external route is a path that leads to a destination outside of the EIGRP autonomous system
and that has been redistributed into the EIGRP domain. Figure
8.31 shows the format of the External Routes TLV.
Next Hop is the next-hop IP address. On a multiaccess network,
the router advertising the route may not be the best next-hop router to the
destination. For example, an EIGRP-speaking router on an Ethernet link may
also be speaking BGP and may be advertising a BGP-learned route into the EIGRP
autonomous system. Because other routers on the link do not speak BGP, they
may have no way of knowing that the interface to the BGP speaker is the best
next-hop address. The Next Hop field allows the “bilingual” router
to tell its EIGRP neighbors, “Use address A.B.C.D as the next hop instead
of using my interface address.” Originating Router
is the IP address or router ID of the router that redistributed the external
route into the EIGRP
Originating Autonomous System Number is the autonomous
system number of the router originating the route.
Arbitrary Tagmay be used to carry a tag set by
route maps. See Chapter 14, “Route Maps,”
for information on the use of route maps.
External Protocol metric
is, as the name implies, the metric of the external protocol. This field is
used, when redistributing with IGRP, to track the IGRP metric.
Reserved is an unused field
and is always 0x0000.
External Protocol ID
specifies the protocol from which the external route was learned. Table
8.4 lists the possible
values of this field.
Flags currently constitute just two flags.
If the right-most bit of the eight-bit field is set (0×01), the route
is an external route. If the second bit is set (0×02), the route is
a candidate default route. Default routes are discussed in Chapter
12, “Default Routes and On-Demand Routing.”
The remaining fields describe the metrics and the destination address. The descriptions of these fields are
the same as those given in the discussion of the
Internal Routes TLV.
Chapter 2, “TCP/IP Review,” introduced
the practice of subnetting, in which the address mask is extended into the
host space in order to address multiple data links under one major network
address. Chapter 7 introduced the practice of variable-length
subnet masking, in which the address mask is extended even
more to create subnets within subnets.
From an opposite perspective, a subnet address may be thought of as
a summarization of a group of sub-subnets. And a major network
address may be thought of as a summarization of a group of subnet addresses.
In each case, the summarization is achieved by reducing the length of the
Address aggregation takes summarization a step further by breaking the
class limits of major network addresses. An aggregate address represents a
numerically contiguous group of network addresses, known as a supernet. 13 Figure 8.32 shows an example of an aggregate address.
Figure 8.32. This group of network addresses can be represented with a single aggregate
address, or subnet.
Figure 8.33 shows how the aggregate
address of Figure 8.32 is derived. For a
group of network addresses, find the bits that are common to all of the addresses
and mask these bits. The masked portion is the aggregate address.
When designing a supernet, it is important that the member addresses
should form a complete, contiguous set of the formerly masked bits. In Figure 8.33, for example, the 20-bit mask of the
aggregate address is four bits less than the mask of the member addresses.
Of the four “difference” bits, notice that they include every
possible bit combination from 0000 to 1111. Failure to follow this design
rule will make the addressing
scheme confusing, can reduce the efficiency of aggregate routes, and may lead to routing loops
and black holes.
The obvious advantage of summary addressing is the conservation of network
resources. Bandwidth is conserved by advertising fewer routes, and CPU cycles
are conserved by processing fewer routes. Most important, memory is conserved
by reducing the size of the route tables.
Figure 8.33. The aggregate address is derived by masking all the common bits of
a group of numerically contiguous network addresses.
Classless routing, VLSM, and aggregate
addressing together provide the means to maximize resource conservation by
building address hierarchies. Unlike IGRP, EIGRP supports all of these addressing
strategies. In Figure 8.34, the engineering
division of Treetop Aviation has been assigned 16 class C addresses. These
addresses have been assigned to the various departments according to need.
The aggregate addresses of the engines, electrical, and hydraulics departments
are themselves aggregated into a single address, 192.168.16.0/21. That address
and the aggregate address of the airframe department are aggregated into the
single address 192.168.16.0/20, which represents the entire engineering division.
Other divisions may be similarly represented.
For example, if Treetop Aviation has a total of eight divisions and if those divisions are all addressed similarly
to the engineering division, the backbone router at the top of the hierarchy
may have as few as eight routes (Figure 8.35).
Figure 8.34. At Treetop Aviation, several departments within a larger division are
aggregating addresses. In turn, the entire division can be advertised with
a single aggregate address (192.168.16.0/20).
The hierarchical design is continued within each department of each
division by subnetting the individual network addresses. VLSM may be used
to further divide the subnets. The routing protocols will automatically summarize
the subnets at network boundaries, as discussed in previous chapters.
Address aggregation also allows both address conservation and address
hierarchies in the Internet. With the exponential growth of the Internet,
two increasing concerns have been
the depletion of available IP addresses (particularly class B addresses) and the huge databases needed
to store the Internet routing information.
Figure 8.35. Although there are 128 major network addresses and possibly over 32,000
hosts in this internetwork, the backbone router has only eight aggregate addresses
in its route table.
A solution to this problem is an initiative known as Classless
Interdo main Routing (CIDR). 14
Under CIDR, aggregates of class C addresses are allocated by the InterNIC
to the various worldwide address assignment authorities such as Network Solutions
in the United States and R\x8f seaux IP Europ\x8f ens (RIPE) in Europe. The
aggregates are organized geographically, as shown in Table
Table 8.5. CIDR address allocations
by geographic region.
The address assignment authorities
in turn divide their portions among the regional Internet Service Providers
(ISPs). When an organization applies for an IP address and requires addressing
for less than 32 subnets and 4096 hosts, it will be given a contiguous group
of class C addresses called a CIDR block.
In this way, the Internet routers of individual organizations might
advertise a single summary address to their ISP. The ISP, in turn, aggregates
all of its addresses, and all ISPs in a region of the world may be summarized
by the addresses of Table 8.5.
This chapter's case studies include some examples of address aggregation;
further examples are included in Chapter 9, “Open Shortest Path First.”
1 A major software revision of EIGRP was
released in IOS 10.3(11), 11.0(8), and 11.1(3). The performance and stability
improvements of the later version make it highly preferable over the older
2 Point-to-point subinterfaces send Hellos
every 5 seconds.
3 Edsger W. Dijkstra and C. S.
Scholten. “Termination Detection for Diffusing Computations.”
Information Processing Letters, Vol. 11, No. 1, pp. 1-4: 29 August 1980.
4 J. J. Garcia-Luna-Aceves. “A
Unified Approach for Loop-Free Routing Using Link States or Distance Vectors,”
ACM SIGCOMM Computer Communications Review, Vol. 19, No. 4, pp.
212-223: September 1989.
J. J. Garcia-Luna-Aceves. “Loop-Free Routing Using Diffusing
Computations,” IEEE/ACM Transactions on Networking, Vol.
1, No. 1, February 1993.
5 J.J. Garcia-Luna-Aceves. “Area-Based,
Loop-Free Internet Routing.” Proceedings of IEEE INFOCOMM 94. Toronto,
Ontario, Canada, June 1994.
6 Successor simply means a router
that is one hop closer to a destinationin other words, a next-hop router.
7 Actually, the interface is not
explicitly recorded in the route table. Rather, it is an attribute of the
neighbor itself. This convention implies that the same router, seen across
multiple parallel links, will be viewed by EIGRP as multiple neighbors.
8 Several of the illustrations
in this and the following section, and in the network example used throughout,
are adapted from Dr. Garcia-Luna's “Loop-Free Routing Using Diffusing
Computations,” with his permission.
9 The default Active timer is 1
minute in some earlier IOS versions.
10 An infinite
distance is indicated by a delay of 0xFFFFFFFF, or 4294967295.
11 Because of the improvements
to its stability beginning with IOS 10.3(11), 11.0(8), and 11.1(3) use of
the later version of EIGRP is highly recommended.
12 This packet indicates whether
the older software release is running (software version 0) or thenewer
release, as of IOS 10.3(11), 11.0(8), and 11.1(3), is running (version 1).
13 An aggregate is, more correctly,
any summarized group of addresses. For clarity, in this book the term aggregate
refers to a summarization of a group of major network addresses.
14 V. Fuller, T. Li, J. I. Yu,
and K. Varadhan. “Classless Inter-Domain Routing (CIDR): An Address
Assignment and Aggregation Strategy.” RFC 1519, September 1993.
One of the primary architects of OpenCable, Michael
Adams, explains the key concepts of this initiative in his book
Broadband, Second Edition
by George Abe
Introduces the topics surrounding high-speed networks
to the home. It is written for anyone seeking a broad-based familiarity
with the issues of residential broadband (RBB) including product
developers, engineers, network designers, business people, professionals
in legal and regulatory positions, and industry analysts.