Cisco Knowledge Suite Cisco SystemsCisco Press
   

   
Home
MyCKS
Cutting Edge
Certification
Core Reference
Guided Learning
   
Networking Architecture
LAN
WAN
Switching
Internet Protocols (IP)
Network Protocols
Transport and Application Protocols
Desktop Protocols
Security and Troubleshooting
Network Resources and Management
Integrated Services
 

The Topology Table

   

< Back Contents Next >

Enhanced Interior Gateway Routing Protocol

  

 

EIGRP Background

  

 

New Features Found in EIGRP

  

 

EIGRP Data Structures

  

 

The Routing Table

  

 

The Topology Table

Save to MyCKS

 
IP Routing Fundamentals

From: IP Routing Fundamentals
Author: Mark Sportack
Publisher: Cisco Press (53)
More Information

The Topology Table

EIGRP uses its topology table to store all the information it needs to calculate a set of distances, and vectors, to all known and reachable destinations. This information includes the following fields:

  • Bandwidth—The bandwidth of the slowest interface in the path to a destination. This effectively limits the performance of the route and is used in calculation of the route's composite metric. This metric is calculated the same way in both IGRP and EIGRP.

  • Total DelayThis field contains the sum total of delay expected in that route. This sum is calculated the same way as IGRP.

  • ReliabilityThe reliability of the path is also recorded in the topology table. This metric is also identical to the IGRP Reliability metric.

  • LoadThe load level of the path is another of the IGRP metrics that has been retained by EIGRP.

  • MTUThis field contains the size of the smallest MTU supported by the router interfaces in the path. As the least-common MTU, datagrams exceeding this value will be fragmented en route to their destination. Therefore, EIGRP attempts to notify all routers, in advance, of the maximum MTU on each path to a given destination.

  • Reported DistanceThe reported distance of the path is the distance reported by an adjacent neighbor to a specific destination. This metric does not include the distance between this router and the adjacent neighbor.

  • Feasible DistanceThe feasible distance is the lowest calculated metric to each destination.

  • Route SourceThe source of the route is the identification number of the router that originally advertised that route. This field is populated only for routes learned externally from the EIGRP network. Route tagging can be particularly useful with policy-based routing. For more information on EIGRP's route tagging capabilities, refer to the sidebar titled “Route Tagging with EIGRP” later in this chapter.

Also recorded for each entry is the interface through which this destination is reachable. The topology table is sorted. Successors are at the top, followed immediately by feasible successors. EIGRP even stores routes that DUAL believes to be loops in the topology table. These routes are at the bottom of the sorted topology table. You can see the entire contents of the EIGRP topology table by executing the following command:

show ip eigrp topo all

A separate topology table is maintained for each protocol-dependent module being used by EIGRP. The information contained in a topology table is used as input to the DUAL finite-state machine.

Entries in a topology table can be in one of two states: active or passive. These states identify the status of the route indicated by the entry rather than the status of the entry itself. A passive route is one that is stable and available for use.

An active route is one currently being recomputed. Recomputation is the process of recalculating routes in search of new successors. This process isn't necessarily processor intensive, but it can be time intensive. Consequently, extensive recomputation can exacerbate convergence times in an EIGRP network. Recomputation is a rather resource-intensive measure. Therefore, in the event of a topology change, DUAL is designed to use any and all available feasible successors before recomputing. A recomputation will only occur if there are no successors or feasible successors to a route.

Route Tagging with EIGRP

EIGRP classifies routes as either internal or external. Internal routes are those that originated within an EIGRP network. External routes were either learned from a different routing protocol—those that lie outside of EIGRP's Autonomous System and were learned by a router on the border between the two autonomous systems—or are static routes that have been injected into EIGRP through redistribution. All external routes are tagged in the topology table and include the following information:

  • The identification number (router ID) of the EIGRP router that redistributed that route into the EIGRP network

  • The number of the Autonomous System where that route's destination resides

  • The protocol used in that external network

  • The cost or metric received from that external protocol

  • A tag that can be administratively set and used in route filtering

Route tagging gives the network administrator flexibility in establishing routing policies. This flexibility is most useful when the EIGRP network is internetworked with a policy-based routing protocol such as EGP or BGP.EIGRP routers will reject external routes tagged with a router ID identical to their own; this prevents routing loops from occurring with external routes.

The topology table also stores the identities of neighbors that are feasible successors. The concept of feasible succession was held over from IGRP. It is important to understand, however, that EIGRP's feasible succession is very different from IGRP's feasible succession. The concepts are similar, but their implementation and mechanics are very different. The IGRP version of feasible succession was examined in the preceding chapter.

In EIGRP, all neighboring routers that have an advertised composite metric (reported distance) that is less than a router's best current metric (feasible distance) for any given route are considered feasible successors to the current successor (path currently being used). If there are multiple routes with a cost equal to the best cost, they are all considered successors and are all installed in the routing table. A destination must have at least one successor before it can be moved from the topology table to the routing table!

An EIGRP router views its feasible successors as neighbors that are downstream, or closer, to the destination than it is. Whenever a change occurs in the network, which affects either its topology or even the composite metric of a single route, the set of successors and feasible successors to the affected route(s) may have to be reevaluated.

If a router loses its route through its successor, and there are no feasible successors, the route automatically goes into the active state and triggers recomputation. The router queries its neighbors, requesting new information about possible alternative paths to the impacted route. The neighboring routers must reply. Their reply can either contain information about their successors or notification that they can no longer reach the route either.

The route can only return to the passive state after the router has received a reply from each of its neighboring routers and can select a successor or determine that the destination is no longer reachable.

EIGRP Packet Types

EIGRP uses five specialized packets to maintain its various routing tables. Each packet type performs a specific function in support of routing table maintenance. The five EIGRP packet types are

  • Hello

  • Acknowledgment

  • Update

  • Query

  • Reply

Given that EIGRP is a proprietary Cisco Systems product, its detailed specifications—including the size and structure of its internal packet type—are not made public. Consequently, the following survey of the six EIGRP packet types is limited to their functional description and uses.

Hello Packets

Hello packets, as their name implies, are used to discover (or rediscover) and track other EIGRP routers in the network. Rediscovering neighbors can sometimes occur during convergence. In theory, a failure in the network changes its topology. If, during the process of convergence, neighboring routers lose contact for a moment, the hello process will eventually reestablish the relationship. Rediscovering a lost neighbor is known as recovery or rediscovery.

EIGRP nodes transmit hello packets at fixed intervals known as hello intervals. The default interval depends on the bandwidth available per interface. On relatively low-bandwidth (less than T1) multipoint circuits (such as multipoint Frame Relay, ATM, and X.25 circuits), EIGRP uses a 60-second hello interval. Higher-bandwidth interfaces include point-to-point serial links, multipoint circuits with bandwidth greater than or equal to T1, and LANs. EIGRP uses a 5-second hello interval on such interfaces. An EIGRP node uses its neighbor table to keep track of the other EIGRP routers in its network. Included in this table is the last time that each neighbor was heard from. Such contact may have been made via hello packets or any other EIGRP packet type. The point is that an EIGRP router considers a neighbor to be functional as long as it is capable of some form of communication.

There must be a finite period that an EIGRP router endures before concluding that a silent neighbor is actually out of service. This period is known as the hold time, which is tracked by the hold timer. If a router's hold timer counts down to zero, and a neighbor still hasn't been heard from, that router informs DUAL of the change. DUAL initiates convergence among the surviving routers in the network.

Hold time is usually defaulted to three times the hold time for an interface. Therefore, hold times are defaulted to 180 and 15 seconds respectively for low- and high-bandwidth interfaces. Both the hello interval and the hold time may be reset, per router interface, by a network administrator. Changing the hello interval does not automatically change the hold time, however. Each interval is manipulated individually. If you manually change the value of one, you should also manually change the value of the other.

NOTE

EIGRP enables a stable relationship between neighboring routers, even if they have different hold times or hello intervals! Hold time is one of the pieces of information exchanged via hello packets and stored in the neighbor table. Therefore, EIGRP routers won't prematurely assume that a neighbor is out of service just because it has a longer-than-normal hello interval or hold time. This capability is unique to EIGRP. OSPF, another protocol that uses hello intervals, requires both routers to have matching hold times and intervals.

Acknowledgment Packets

Acknowledgment packets are used to acknowledge receipt of any EIGRP packet that requires reliable delivery. As explained in the section titled “Reliable Transport Protocol,” a packet's receipt must be acknowledged if it is to be delivered reliably. Otherwise, the source router would have no way of knowing whether the packet was actually delivered. EIGRP's standalone acknowledgment packet is actually a hello packet without any data. Acknowledgments (or Acks) can be differentiated from hello packets in another way, too. Hellos are always multicast, whereas acknowledgments are always sent to a single, specific IP address. This is known as unicasting. Hello and acknowledgment packets, incidentally, do not require acknowledgment. A router running EIGRP may also piggyback the acknowledgement information onto others' unicast packets, such as replies, being sent to the peer.

Update Packets

The update packet is used to convey routing information to known destinations. This packet type actually has two uses. The first use is to provide a complete dump of topological data to a newly discovered neighbor. Whenever a new neighbor is discovered (that is, a new router is added to an existing network), EIGRP nodes transmit update packets to this new neighbor for use in constructing its initial topology table. A series of update packets might be needed to send a complete set of topology information to the new router.

The second use of the update packet would be more typical of daily operation within an EIGRP network. Updates would be sent whenever a change in either topology or link cost occurred. These updates would be forwarded broadly to all known neighbors.

The way to differentiate between these two uses is to check the destination address of the update packets. Updates sent to a new neighbor will be directly addressed to that neighbor. Otherwise, update packets usually use an IP multicast address to forward to multiple neighbors simultaneously. The update packet is always transmitted reliably regardless of whether it is unicast or multicast.

One important improvement over virtually every other routing protocol is that EIGRP does not transmit updates of complete routing tables. Instead, EIGRP uses non-periodic, incremental routing updates. That is, EIGRP nodes convey only the information that has changed, when it has changed. By transmitting only the deltas, EIGRP converges more quickly and consumes much less bandwidth in the process.

Query and Reply Packets

Two of EIGRP's packet types, query and reply, are functionally interrelated. As a result, it doesn't make sense to examine them separately. Query packets are used whenever a router needs specific information from one or all of its neighbors. A reply packet is used to respond to a query.

One example showing the interaction of queries and replies is found in the process of finding an alternative route to a destination for which a router has lost its only routes. A router can send query packets to request information from neighbors about alternative paths that may be available. Neighboring routers would reply with their successor information.

Another example of the use of a query packet would be if a router receives a request for a destination that it previously didn't know about. In this case, the router receiving the query would immediately reply that it, also, doesn't know about this destination. This is one way in which queries are bounded in an EIGRP network. Unlike queries, which can be multicast, it doesn't make sense to multicast a reply. Instead, replies are unicast directly back to the originator of the query.

Queries are only sent when a destination becomes active. Otherwise, if the network is stable, and all routes are passive, there is no need to waste network bandwidth by requesting (and receiving) routing information. An additional bandwidth-conserving tactic is the capability to multicast queries. As demonstrated in the preceding two examples, queries can be both unicast and multicast. Regardless of which address type is used, queries are always transmitted reliably. Replies are also always transmitted reliably.

Convergence Using EIGRP

Convergence in an EIGRP network can be quite complicated. Part of this complexity is due to Cisco's standard of supporting up to six parallel routes to all destinations. Although this standard has helped make Cisco the market leader in internetworking products, it makes it more difficult to explain internetworking topics. For the sake of explaining the theory and mechanics of convergence, the examples in this section assume that a router remembers only a single primary route and one alternative (feasible successor) route.

The network illustrated in Figure11-1 is a relatively small EIGRP network with five separate regions and a modest degree of route redundancy. This network is used to illustrate how EIGRP converges using its DUAL algorithm and feasible succession.

Figure 11-1. A small EIGRP network.

In this illustration, there are five different networks within a single EIGRP Autonomous System. The routers are labeled A through E. Another simplifying assumption in this example is that all the links are T1s. Therefore, bandwidth and delay will be constant throughout the network, and route selection becomes an obfuscated hop-counting exercise. Therefore instead of complicating the example with composite metrics, hop counts are used.

Table11-1 contains the known distances between Router C and the other networks.

Table 11-1. Distances from Router C in the Network

Destination IP Address

Next Hop

Hop Count

193.9.1

A

1

193.9.2

B

1

193.9.4

B

2

193.9.5

A

2

Router C's DUAL algorithm has selected the least-cost paths from the multiple available paths to networks 193.9.4 and 193.9.5. Table11-2 summarizes Router C's view of the network. Note that none of these routers have any feasible successors for any of these destinations. This is because the distance reported by the neighbor must be less than—not less than or equal to—the best metric available to reach that destination.

Table 11-2. A Summary of Router C's Network Topology

Destination IP Address

Route, from C

Hop Count

Successor or Feasible Successor?

193.9.1

A

1

Successor

193.9.2

B

1

Successor

193.9.4

B to D

2

Successor

193.9.5

A to E

2

Successor

There are other paths through the network, but their hop counts exceed both the primary route and the feasible successor. It is possible, for example, for Router C to forward datagrams to network 193.9.1 by using the route through Router B to D to E and, finally, to Router A and network 193.9.1. However, the hop count of this network (where both bandwidth and delay are equal across all links) is four. Therefore, it is unattractive as both a primary route and a feasible successor to the primary route. Such a route may become either a primary route or a feasible successor, but only if multiple network failures occurred and it were the least-cost route. However, the entire EIGRP network would have to recompute routes to known destinations for this to occur. To understand how the process of finding an alternative path works, consider Figure11-2. In this illustration, the link between Routers B and C fails.

Figure 11-2. The link between Routers C and B fails.

The consequences of this failure are that all routes that used B as a next hop go active in the EIGRP topology table. The effects of this failure, as documented in the topology table, are summarized in Table11-3.

Table 11-3. A Summary of Router C's Network Topology, after a Link Failure

Destination IP Address

Route, from C

Route State

Successor or Feasible Successor?

193.9.1

A

Passive

Successor

193.9.2

B

Active

Successor

193.9.4

B to D

Active

Successor

193.9.5

A to E

Passive

Successor

In this example, all that used the link between Routers C and B become active in the topology table. Other routes, including those that pass through Router B via Router A, remain passive and unaffected by the topology change.

Router C responds to this topology change by sending a query to its neighbors, notifying them that it has lost two primaries. It has only two neighbors, B and A, and one of them is now unreachable.

Router A is obligated by the protocol specifications to respond to Router C's query for alternative path information. Its own topology table has not been affected by the link failure because it has a different set of neighbors. Therefore, there is hope that other routes can be discovered.

Router A's topology table, in the middle of convergence, is summarized in Table11-4.

Table 11-4. A Summary of Router A's Network Tepology, in the Midst of Convergence

Destination IP Address

Route, from A

Status

Successor or Feasible Successor?

193.9.2

B

Passive

Successor

193.9.3

C

Passive

Successor

193.9.4

B to D

Passive

Successor

193.9.5

E

Passive

Successor

The link failure between Routers B and C has not affected any of Router A's primary routes. They remain passive and in use. Because this is the case, Router A will respond with information on an alternative route through Router E to these destination networks.

When Router C receives the reply from Router A, it knows that all the neighbors in the network have processed the link failure and modified their tables accordingly.

Table11-5 summarizes the results of Router C's new understanding of the network's topology.

Table 11-5. A Summary of Router C's Network Topology, Post Convergence

Destination IP Address

Route, from C

State

Successor or Feasible Successor?

193.9.1

A

Passive

Successor

193.9.2

A to B

Passive

Successor

193.9.4

A to B to D

Passive

Successor

193.9.5

A to E

Passive

Successor

Router C was able to identify an alternative path—that is, successor—to all the routes it had been able to reach through Router B. These alternatives are far from ideal, however: They all begin with the hop to Router A, which is also the primary route to 193.9.1. If a failure were to beset this link, Router A, or any of the router interfaces that connect this link to Routers A and C, Router C would be completely isolated from the remainder of the network.

 

   

< Back Contents Next >

Save to MyCKS

 

Breaking News

One of the primary architects of OpenCable, Michael Adams, explains the key concepts of this initiative in his book OpenCable Architecture.

Expert Advice

Ralph Droms, Ph.D., author of The DHCP Handbook and chair of the IETF Dynamic Host Configuration Working Group, guides you to his top picks for reliable DHCP-related information.

Just Published

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

             
     

From the Brains at InformIT

|

Contact Us

|

Copyright, Terms & Conditions

|

Privacy Policy

 

© Copyright 2000 InformIT. All rights reserved.