Unlike traditional DV protocols such as RIP and IGRP, EIGRP does not rely on periodic updates: routing updates are sent only when there is a change. Remember that RIP and IGRP reset the invalid and flush timers upon receiving a route update. When a route is lost, the updates stop; the invalid and flush timers grow and grow (the timers are not reset), and, ultimately, the route is flushed from the routing table. This process of convergence assumes periodic updates. EIGRP’s approach has the advantage that network resources are not consumed by periodic updates. However, if a router dies, taking away all its downstream routes, how would EIGRP detect the loss of these routes? EIGRP relies on small hello packets to establish neighbor relationships and to detect the loss of a neighbor. Neighbor relationships are discussed in detail in the next section.
RIP and IGRP suffer from a major flaw: routing loops . Routing loops happen when information about the loss of a route does not reach all routers in the network because an update packet gets dropped or corrupted. These routers (that have not received the information about the loss of the route) inject bad routing information back into the network by telling their neighbors about the route they know. EIGRP uses reliable transmission for all updates between neighbors. Neighbors acknowledge the receipt of updates, and if an acknowledgment is not received, EIGRP retransmits the update.
RIP and IGRP employ a battery of techniques to reduce the likelihood of routing loops: split horizon, hold-down timers, and poison reverse. These techniques do not guarantee that loops will not occur and, in any case, result in long convergence times. EIGRP uses the Diffusing Update Algorithm (DUAL) for all route computations. DUAL’s convergence times are an order of magnitude lower than those of traditional DV algorithms. DUAL is able to achieve such low convergence times by maintaining a table of loop-free paths to every destination, in addition to the least-cost path. DUAL is described in more detail later in this chapter.
DUAL can support IP, IPX, and AppleTalk. A protocol-dependent module encapsulates DUAL messages and handles interactions with the routing table. In summary, DUAL requires:
A method for the discovery of new neighbors and their loss (see the next section, Section 4.3.1).
Reliable transmission of update packets between neighbors (see the later section Section 4.3.2).
Protocol-dependent modules that can encapsulate DUAL traffic in IP, IPX, or AppleTalk. This text will deal only with EIGRP in IP networks (see the later section Section 4.3.4).
I’ll end this section with a discussion of EIGRP packet formats.
A router discovers a neighbor when it receives its first hello packet on a directly connected network. The router requests DUAL to send a full route update to the new neighbor. In response, the neighbor sends its full route update. Thus, a new neighbor relationship is established in the following steps:
The interval between hello packets from any EIGRP-speaking router on a network is five seconds (by default) on most media types. Each hello packet advertises hold-time -- the length of time the neighbor should consider the sender up. The default hold-time is 15 seconds. If no hellos are received for the duration of the hold-time, DUAL is informed that the neighbor is down. Thus, in addition to detecting a new neighbor, hello packets are also used to detect the loss of a neighbor.
The hello-interval can be changed with the following command in interface configuration mode:
ip hello-interval eigrp autonomous-system-number secondsLengthening the hello-interval will also lengthen the route convergence time. However, a longer hello-interval may be desirable on a congested network with many EIGRP routers.
If the hello-interval is changed, the hold-time should also be modified. A rule of thumb is to keep the hold-time at three times the hello-interval.
ip hold-time eigrp autonomous-system-number secondsNote that the hello-interval and hold-time need not be the same for all routers on a network. Each router advertises its own hold-time, which is recorded in the neighbor’s neighbor table.
The default hello-interval is 60 seconds (with a hold-time of 180 seconds) on multipoint interfaces (such as ATM, Frame Relay, and X.25) with link speeds of T-1 or less. Hello packets are multicast; no acknowledgments are expected.
The following output shows
NewYork’s neighbors. The first
column -- labeled H -- is the order in which the neighbors were
learned. The hold-time for 172.16.251.2
(Ames) is 10 seconds, from which we can deduce
that the last hello was received 5 seconds ago. The hold-time for
172.16.250.2 (Chicago) is 13
seconds, from which we can deduce that the last hello was received 2
seconds ago. The hold-time for a neighbor should not exceed 15
seconds or fall below 10 seconds (if the hold-time fell below 10 s,
that would indicate the loss of one or more hello packets).
NewYork#sh ip eigrp neighbor
IP-EIGRP neighbors for process 10
H Address Interface Hold Uptime SRTT RTO Q Seq
(sec) (ms) Cnt Num
1 172.16.251.2 Se0/1 10 00:17:08 28 2604 0 7
0 172.16.250.2 Se0/0 13 00:24:43 12 2604 0 14.After a neighbor relationship has been established between A and B the only EIGRP overhead is the exchange of hello packets, unless there is a topological change in the network.
The EIGRP transport mechanism uses a
mix of multicast and unicast packets, using reliable delivery when
necessary. All transmissions use IP with the protocol type field set
to 88. The IP multicast address used is
224.0.0.10.
DUAL requires guaranteed and sequenced delivery for some transmissions. This is achieved using acknowledgments and sequence numbers. So, for example, update packets (containing routing table data) are delivered reliably (with sequence numbers) to all neighbors using multicast. Acknowledgment packets -- with the correct sequence number -- are expected from every neighbor. If the correct acknowledgment number is not received from a neighbor, the update is retransmitted as a unicast.
The sequence number (seq num) in the last packet from the neighbor is recorded to ensure that packets are received in sequence. The number of packets in the queue that might need retransmission is shown as a queue count (QCnt), and the smoothed round trip time (SRTT) is used to estimate how long to wait before retransmitting to the neighbor. The retransmission timeout (RTO) is the time the router will wait for an acknowledgment before retransmitting the packet in the queue.
Some transmissions do not require reliable delivery. For example, hello packets are multicast to all neighbors on an Ethernet segment, whereas acknowledgments are unicast. Neither hellos nor acknowledgments are sent reliably.
EIGRP also uses queries and replies as part of DUAL. Queries are multicast or unicast using reliable delivery, whereas replies are always reliably unicast. Query and reply packets are discussed in more detail in the next section.
All route computations in EIGRP are handled by DUAL. One of DUAL’s tasks is maintaining a table of loop-free paths to every destination. This table is referred to as the topology table . Unlike traditional DV protocols that save only the best (least-cost) path for every destination, DUAL saves all paths in the topology table. The least-cost path(s) is copied from the topology table to the routing table. In the event of a failure, the topology table allows for very quick convergence if another loop-free path is available. If a loop-free path is not found in the topology table, a route recomputation must occur, during which DUAL queries its neighbors, who, in turn, may query their neighbors, and so on... hence the name “Diffusing” Update Algorithm.
These processes are described in detail in the following sections.
Just like RIP and IGRP, EIGRP calculates the lowest cost to reach a
destination based on updates[4] from neighbors. An update from a router
R contains the cost to reach the destination
network N from R. This cost
is referred to as the reported distance
(RD). NewYork
receives an update from Ames with a cost of
281,600, which is Ames’s cost
to reach 172.16.100.0. In other words, the RD for
Ames to reach 172.160.100.0
as reported to NewYork is 281,600. Just like
Ames, Chicago will report
its cost to reach 172.16.100.0.
Chicago’s RD is 2,195,456 (see
Figure 4-2).
NewYork will compute its cost to reach
172.16.100.0 via Ames and
Chicago. NewYork will then
compare the metrics for the two paths.
NewYork’s cost via
Ames is 46,251,776.
NewYork’s cost via
Chicago is 2,707,456. The lowest cost to reach a
destination is referred to as the feasible
distance
(FD) for that destination.
NewYork’s FD to
172.16.100.0 is 2,707,456
(BandW = 1,544 and Delay =
4,100). The next-hop router in the lowest-cost path to the
destination is referred to as the
successor
.
NewYork’s successor for
172.16.100.0 is 172.16.50.1
(Chicago).
If a reported distance for a destination is less than the feasible
distance for the same destination, the router that advertised the RD
is said to satisfy the feasibility
condition
(FC) and is referred to as a
feasible successor
(FS).
NewYork sees an RD of 281,600 via
Ames, which is lower than
NewYork’s FD of 2,707,456.
Ames satisfies the FC. Ames
is an FS for NewYork to reach
172.16.100.0.
The feasibility condition is a test for loop freedom : if the FC is met, the router advertising the RD must have a path to the destination not through the router checking the FC -- if it did, the RD would have been higher than the FD.
Let’s illustrate this concept with another example. Consider the network in Figure 4-3. The metric values used in this example have been simplified to small numbers to make it easier to follow the concept.
Router A’s best route to network N is via router B, and the cost of this path is 100 (A’s FD to N is 100). Router X also knows how to get to network N; X advertises N to A in an update packet (A copies this information into its topology table). In the event that A’s link to B fails, A can use the route to N via X if X does not use A to get to N (in other words, if the path is loop-free). Thus, the key question for A to answer is whether or not the path that X advertises is loop-free.
Here is how A answers this question. Let’s say that X advertises N with a metric of 90 (X’s RD for N). A compares 90 (RD) with 100 (FD). Is RD < FD? This comparison is the FC check. Since A’s FD is 100, X’s path to N must not be via A (and is loop-free). If X advertises N with a metric of 110, X’s path to N could be via A (the RD is not less than the FD, so the FC check fails) -- 110 could be A’s cost added to the metric of the link between A and X (and, hence, is not guaranteed to be free of a loop).
All destinations advertised by neighbors are copied into the
topology table. Each destination is
listed along with the neighbors that advertised the destination, the
RD, and the metric to reach the destination via that neighbor.
Let’s look at
NewYork’s topology table and
zoom in on destination 172.16.100.0. There are two
neighbors that sent updates with this destination:
Chicago (172.16.250.2) and
Ames (172.16.251.2), as shown
on lines 9 and 10, respectively:
NewYork#sh ip eigrp topology
IP-EIGRP Topology Table for process 10
Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status
...
P 172.16.100.0/24, 1 successors, FD is 2,707,456
9 via 172.16.250.2 (2,707,456/2,195,456), Serial0
10 via 172.16.251.2 (46,251,776/281,600), Serial1Chicago sent an update with an RD of 2,195,456, and Ames sent an update with an RD of 281,600. NewYork computes its own metric to 172.16.100.0: 2,707,456 and 46,251,776 via Chicago and Ames, respectively. NewYork uses the lower-cost path via Chicago. NewYork’s FD to 172.16.100.0 is thus 2,707,456, and Chicago is the successor. Next NewYork checks to see if Ames qualifies as a feasible successor. Ames’s RD is 281,600. This is checked against the FD. Since the RD < FD (281,600 < 2,707,456), Ames is a feasible successor (see Figure 4-2).
Note that not all loop-free paths satisfy the FC. Thus, NewYork’s topology table does not contain the alternate path to 172.16.50.0 (via Ames). The FC guarantees that the paths that satisfy the condition are loop-free; however, not all loop-free paths satisfy the FC.
Let’s take a closer look at 172.16.50.0 (Chicago) in NewYork’s topology table:
NewYork#sh ip eigrp topology
IP-EIGRP Topology Table for process 10
Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status
...
P 172.16.50.0/24, 1 successors, FD is 2195456
via 172.16.250.2 (2195456/281600), Serial0Notice that Ames
(172.16.251.2) did not become a feasible
successor, even though Ames offers a valid
loop-free path. The condition that Ames would
have to satisfy to become a feasible successor is for its RD to be
less than NewYork’s FD to
172.16.50.0.
Ames’s RD can be seen from
Ames’s routing table:
Ames#sh ip route
...
172.16.0.0/24 is subnetted, 6 subnets
C 172.16.252.0 is directly connected, Serial0
D 172.16.250.0 [90/2681856] via 172.16.252.1, 00:21:10, Serial0
C 172.16.251.0 is directly connected, Serial1
11 D 172.16.50.0 [90/2195456] via 172.16.252.1, 00:21:10, Serial0
D 172.16.1.0 [90/2707456] via 172.16.252.1, 00:15:36, Serial0
C 172.16.100.0 is directly connected, Ethernet0
Ames’s metric to
172.16.50.0 is 2,195,456 (line 11). This will be
the metric that Ames reports to
NewYork. The RD is thus 2,195,456.
NewYork’s FD to
172.16.50.0 is 2,195,456. The RD and the FD are
equal, which is not surprising given the topology: both
NewYork and Ames have
identical paths to 172.16.50.0 -- a T-1 link, a
router, and the destination Ethernet segment. Since the condition for
feasible successor is that RD < FD, Ames is
not an FS for 172.16.50.0 (see Figure 4-4).
The output of show ip eigrp topology shows only feasible successors. The output of show ip eigrp topology all-links shows all neighbors, whether feasible successors or not.
Note the “P” for “passive state” in the left margin of each route entry in NewYork’s topology table. Passive state indicates that the route is in quiescent mode, implying that the route is known to be good and that no activities are taking place with respect to the route.
Any of the following events can cause DUAL to reevaluate its feasible successors:
The transition in the state of a directly connected link
A change in the metric of a directly connected link
An update from a neighbor
If DUAL finds a feasible successor in its own topology table after one of these events, the route remains in passive state. If DUAL cannot find a feasible successor in its topology table, it will send a query to all its neighbors and the route will transition to active state .
The next section contains two examples of DUAL reevaluating its topology table. In the first example, the route remains passive; in the second example, the route becomes active before returning to the passive state.
Let’s say that the NewYork → Chicago link fails (Figure 4-5).
NewYork’s routing table shows
that 172.16.100.0 and
172.16.50.0 are learned via this link
(Serial0):
NewYork#sh ip route
...
172.16.0.0/24 is subnetted, 6 subnets
...
D 172.16.50.0 [90/2195456] via 172.16.250.2, 00:18:54, Serial0
D 172.16.100.0 [90/2707456] via 172.16.250.2, 00:18:54, Serial0
...These routes become invalid. DUAL attempts to find new successors for
both destinations -- 172.16.50.0 and
172.16.100.0.
Let’s start with 172.16.100.0.
DUAL checks the topology table for 172.16.100.0:
NewYork#sh ip eigrp topology
...
P 172.16.100.0/24, 1 successors, FD is 2707456
12 via 172.16.250.2 (2707456/2195456), Serial0
13 via 172.16.251.2 (46251776/281600), Serial1 Since Serial0 is down, the only feasible
successor is 172.16.251.2
(Ames). Let’s review how
Ames qualifies as an FS. The FS check is:
RD < FD.
RD=281,600 (line 13).
FD=2,707,456 (line 12).
Since 281,600 < 2,707,456, Ames qualifies as an FS.
In plain words, this implies that the path available to
NewYork via Ames (the FS)
is independent of the primary path that just failed. DUAL installs
Ames as the new successor for
172.16.100.0.
In our case study, only one FS was available. In general, multiple FSs may be available, all of which satisfy the condition that their RD < FD, where FD is the cost of the route to the destination via the successor that was just lost.
DUAL will compute its metric to reach the destination via each FS. Since DUAL is searching for the successor(s) for this destination, it will choose the minimum from this set of metrics via each FS. Let the lowest metric be Dmin. If only one FS yields this metric of Dmin, that FS becomes the new successor. If multiple FSs yield metrics equal to Dmin, they all become successors (subject to the limitation in the maximum number of parallel paths allowed -- four or six, depending on the IOS version number). Since the new successor(s) is found locally (without querying any other router), the route stays in passive state. After DUAL has installed the new successor, it sends an update to all its neighbors regarding this change.
How long does this computation take? We simulated the failure of the NewYork → Chicago link in our laboratory. To measure how long EIGRP would take to converge after the failure of the link, we started a long ping test just before failing the NewYork → Chicago link:
NewYork#ping Protocol [ip]: Target IP address: 172.16.100.1 Repeat count [5]: 1000 ... Sending 1000, 100-byte ICMP Echos to 172.16.100.1, timeout is 2 seconds: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Success rate is 99 percent (999/1000), round-trip min/avg/max = 1/3/92 ms
Note that only one ping packet was lost during this computation, implying that the convergence time (including the time to detect the failure of the link) was in the range of two to four seconds.
Let’s next follow
the steps that DUAL would take for 172.16.50.0.
Notice that this is a different case in that when
Serial0 is down, NewYork
has no feasible successors in its topology table (see line 14).
NewYork#sh ip eigrp topology
...
P 172.16.50.0/24, 1 successors, FD is 2195456
14 via 172.16.250.2 (2195456/281600), Serial0
...DUAL knows of no feasible successors, but NewYork has a neighbor that may know of a feasible successor. DUAL places the route in active state (see line 15) and sends a query to all its neighbors:
NewYork#sh ip eigrp topology
IP-EIGRP Topology Table for process 10
Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status
...
15 A 172.16.50.0/24, 0 successors, FD is 2195456, Q
1 replies, active 00:00:06, query-origin: Local origin
Remaining replies:
16 via 172.16.251.2, r, Serial1which in this case is only 172.16.251.2
(Ames, as in line 16).
NewYork sets the reply flag on (line 16), which
indicates that NewYork expects a reply to the
query. Ames receives the query and marks its
topology table entry for 172.16.50.0 via
NewYork as down. Next, Ames
checks its topology table for a feasible successor:
Ames#sh ip eigrp topology
IP-EIGRP Topology Table for process 10
Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status
...
17 P 172.16.50.0/24, 1 successors, FD is 2195456
via 172.16.252.1 (2195456/281600), Serial0
...and finds that it has a successor (172.16.252.1).
Ames sends a reply packet to
NewYork with an RD of 2,195,456 (line 17).
NewYork marks the route as passive and installs
a route for 172.16.50.0 via
172.16.251.2 (Ames).
In general, if DUAL does not find a feasible successor, it forwards the query to its neighbors. The query thus propagates (“diffuses”) until a reply is received. Routers that did not find a feasible successor would return an unreachable message. So, if Ames did not have a feasible successor in its topology table, it would mark the route as active and propagate the query to its neighbor, if it had another neighbor. If Ames had no other neighbor (and no feasible successor) it would return an unreachable message to NewYork and mark the route as unreachable in its own table.
When DUAL marks a route as active and sets the r flag on, it sets a timer for how long it will wait for a reply. The default value of the timer is three minutes. DUAL waits for a reply from all the neighbors it queries. If a neighbor does not respond to a query, the route is marked as stuck-in-active and DUAL deletes all routes in its topology table that point to the unresponsive neighbor as a feasible successor.
The successors in the DUAL topology table are eligible for installation in the routing table. Successors represent the best path to the destination known to DUAL. However, whether the successor is copied into the routing table is another matter. The router may be aware of a route to the same destination from another source (such as another routing protocol or via a static route) with a lower distance. The IP protocol-dependent module (PDM) handles this task. The PDM may also carry information in the reverse direction -- from the routing table to the topology table. This will occur if routes are being redistributed into EIGRP from another protocol.
The PDM is also responsible for encapsulating EIGRP messages in IP packets.
EIGRP
packets are encapsulated directly in IP with the protocol field set
to 88. The destination IP address in EIGRP depends on the packet
type -- some packets are sent as multicast (with an address of
224.0.0.10) and others are sent as unicast (see
the earlier section Section 4.3.2
for more details). The source IP address is the IP address of the
interface from which the packet is issued.
Following the IP header is an EIGRP header. Key fields in the EIGRP header are as follows, and are also shown in Figure 4-6:
The opcode field specifies the EIGRP packet type (update, query, reply, hello).
The checksum applies to the entire EIGRP packet, excluding the IP header.
The rightmost bit in the flags field is the initialization bit and is used in establishing a new neighbor relationship (see Section 4.3.1 earlier in this chapter).
The sequence and ack fields are used to send messages reliably (see Section 4.3.2 earlier in this chapter).
The AS number identifies the EIGRP process issuing the packet. The EIGRP process receiving the packet will process the packet only if the receiving EIGRP process has the same AS number; otherwise, the packet will be discarded.
The fields following the EIGRP header depend on the opcode field. Of particular interest to routing engineers is the information in updates. We will ignore the other types of EIGRP messages and focus on IP internal route updates and IP external route updates.
Internal routes contain destination network
numbers learned within this EIGRP AS. For example,
NewYork learns 172.16.50.0
from EIGRP 10 on Chicago as an internal route.
External routes contain destination network numbers that were not learned within this EIGRP AS but rather derived from another routing process and redistributed into this EIGRP AS.
Internal and external routes are represented differently in the EIGRP update.
Internal routes have a type field of 0x0102. The metric information contained with the route is much like IGRP’s (see Chapter 3). However, there are two new fields: next hop and prefix length. Figure 4-7 shows the value field for the IP internal route.
The next hop identifies the router to send packets destined for destination, the network number of the destination. In general, the next hop field for internal routes will be the IP address of the router on the interface on which it is issuing the update.
The prefix length field signifies the subnet mask to be associated with the network number specified in the destination field. Thus, if an EIGRP router is configured as follows:
ip address 172.16.1.1 255.255.255.0
it will advertise 172.16.1.0 with a prefix length
of 24.
Likewise, if the router is configured as follows:
ip address 172.16.250.1 255.255.255.252
it will advertise 172.16.250.0 with a prefix
length of 30.
Additional fields are required to represent the source from which external routes are derived, as shown in Figure 4-8.
The next hop field identifies the router to send packets destined for destination, the network number of the destination. This field was absent in the IGRP update. Let’s look at what this field signifies.
In IGRP, if router X sends an update to router A with a destination network number of N, router A’s next hop for packets to N will be X. In EIGRP, router X can send an update to router A with a destination network number of N and a next hop field of Y. This is useful, say, in a scenario where X and Y are running RIP and X is redistributing routes from RIP to IGRP. When X sends an update to its neighbors on a shared network, X can tell them to send traffic for network N directly to Y and not to X. This saves X from having to accept traffic on a shared network and then reroute it to Y.[5]
The originating router, originating AS, external protocol metric, and external protocol ID fields specify information about the router and the routing process from which this route was derived. The external protocol ID specifies the routing protocol from which this route was derived. Here is a partial list of external protocol IDs: IGRP -- 0x01; EIGRP -- 0x02; RIP -- 0x04; OSPF -- 0x06; BGP -- 0x09. Thus, if a route was learned from RIP with a hop count of 3 and redistributed into EIGRP, the originating router field would contain the address of the RIP router, the originating AS field would be empty, the external protocol metric would be 3, and the external protocol ID would be 0x04.
The arbitrary tag field is used to carry route maps.
Candidate default routes are marked by setting the flags field to 0x02. A flags field of 0x01 indicates an external route (but not a candidate default route).
The other parameters in the external route packet are similar to those in IGRP.
Get IP Routing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
