EIGRP algorithm

EIGRP algorithm
3.1.6

This page will describe the DUAL algorithm, which results in the exceptionally fast convergence of EIGRP.
The sophisticated DUAL algorithm results in the exceptionally fast convergence of EIGRP. To better understand convergence with DUAL, consider the example in Figure . Each router has constructed a topology table that contains information about how to route to destination Network A.
Each topology table identifies the following information:

• The routing protocol or EIGRP
• The lowest cost of the route, which is called feasible distance (FD)
• The cost of the route as advertised by the neighboring router, which is called reported distance (RD)

The Topology column identifies the primary route called the successor route (successor), and, where identified, the backup route called the feasible successor (FS). Note that it is not necessary to have an identified feasible successor.
The EIGRP network follows a sequence of actions to allow convergence between the routers, which currently have the following topology information:

• Router C has one successor route by way of Router B.
• Router C has one feasible successor route by way of Router D.
• Router D has one successor route by way of Router B.
• Router D has no feasible successor route.
• Router E has one successor route by way of Router D.
• Router E has no feasible successor.

The feasible successor route selection rules are specified in Figure .
The following example demonstrates how each router in the topology will carry out the feasible successor selection rules when the route from Router D to Router B goes down:
In Router D: 

• Route by way of Router B is removed from the topology table.
• This is the successor route. Router D has no feasible successor identified.
• Router D must complete a new route computation.

In Router C:

• Route to Network A by way of Router D is down.
• Route by way of Router D is removed from the table.
• This is the feasible successor route for Router C.

In Router D:  

• Router D has no feasible successor. It cannot switch to an identified alternative backup route.
• Router D must recompute the topology of the network. The path to destination Network A is set to Active.
• Router D sends a query packet to all connected neighbors to request topology information.
• Router C does have a previous entry for Router D.
• Router D does not have a previous entry for Router E.

In Router E:

• Route to Network A through Router D is down.
• The route by way of Router D is removed from the table.
• This is the successor route for Router E.
• Router E does not have a feasible route identified.
• Note that the RD cost of routing by way of Router C is 3. That is the same cost as the successor route by way of Router D.

In Router C: 

• Router E sends a query packet to Router C.
• Router C removes Router E from the table.
• Router C replies to Router D with a new route to Network A.

In Router D:

• Route status to destination Network A is still marked as Active. The computation has not been completed yet.
• Router C has replied to Router D to confirm that a route to destination Network A is available with a cost of 5.
• Router D still waits for a reply from Router E.

In Router E:

• Router E has no feasible successor to reach destination Network A.
• Router E, therefore, tags the status of the route to destination network as Active.
• Router E has to recompute the network topology.
• Router E removes the route by way of Router D from the table.
• Router E sends a query to Router C, to request topology information.
• Router E already has an entry by way of Router C. It is at a cost of 3, the same as the successor route.

In Router E: 

• Router C replies with an RD of 3.
• Router E can now set the route by way of Router C as the new successor with an FD of 4 and an RD of 3.
• Router E replaces the Active status of the route to destination Network A with a Passive status. Note that a route will have a Passive status by default as long as hello packets are received. In this example, only Active status routes are flagged.

In Router E: 

• Router E sends a reply to Router D to inform it of the Router E topology information.

In Router D:

• Router D receives the reply packed from Router E.
• Router D enters this data for the route to destination Network A by way of Router E.
• This route becomes an additional successor route as the cost is the same as routing by way of Router C and the RD is less than the FD cost of 5.

Convergence occurs among all EIGRP routers that use the DUAL algorithm.
This page concludes this lesson. The next lesson will discuss the configuration of EIGRP. The first page will explain how EIGRP is configured.

EIGRP data structure

EIGRP data structure
3.1.5

Like OSPF, EIGRP relies on different types of packets to maintain its tables and establish relationships with neighbor routers. This page will describe these packet types.
The following are the five types of EIGRP packets:

• Hello
• Acknowledgment
• Update
• Query
• Reply

EIGRP relies on hello packets to discover, verify, and rediscover neighbor routers. Rediscovery occurs if EIGRP routers do not receive hellos from each other for a hold time interval but then re-establish communication.
EIGRP routers send hellos at a fixed, but configurable interval called the hello interval. The default hello interval depends on the bandwidth of the interface. On IP networks, EIGRP routers send hellos to the multicast IP address 224.0.0.10.
EIGRP routers store information about neighbors in the neighbor table. The neighbor table includes the Sequence Number (Seq No) field to record the number of the last received EIGRP packet that each neighbor sent. The neighbor table also includes a Hold Time field which records the time the last packet was received. Packets should be received within the Hold Time interval period to maintain a Passive state. The Passive state is a reachable and operational status.
If EIGRP does not receive a packet from a neighbor within the hold time, EIGRP considers that neighbor down. DUAL then steps in to re-evaluate the routing table. By default, the hold time is three times the hello interval, but an administrator can configure both timers as desired.
OSPF requires neighbor routers to have the same hello and dead intervals to communicate. EIGRP has no such restriction. Neighbor routers learn about each of the other respective timers through the exchange of hello packets. They then use that information to forge a stable relationship regardless of unlike timers.
Hello packets are always sent unreliably. This means that no acknowledgment is transmitted.
EIGRP routers use acknowledgment packets to indicate receipt of any EIGRP packet during a reliable exchange. RTP provides reliable communication between EIGRP hosts. A message that is received must be acknowledged by the recipient to be reliable. Acknowledgment packets, which are hello packets without data, are used for this purpose. Unlike multicast hellos, acknowledgment packets are unicast. Acknowledgments can be attached to other kinds of EIGRP packets, such as reply packets.
Update packets are used when a router discovers a new neighbor. EIGRP routers send unicast update packets to that new neighbor so that it can add to its topology table. More than one update packet may be needed to convey all the topology information to the newly discovered neighbor.
Update packets are also used when a router detects a topology change. In this case, the EIGRP router sends a multicast update packet to all neighbors, which alerts them to the change. All update packets are sent reliably.
An EIGRP router uses query packets whenever it needs specific information from one or all of its neighbors. A reply packet is used to respond to a query.
If an EIGRP router loses its successor and cannot find a feasible successor for a route, DUAL places the route in the Active state. A query is then multicasted to all neighbors in an attempt to locate a successor to the destination network. Neighbors must send replies that either provide information on successors or indicate that no information is available. Queries can be multicast or unicast, while replies are always unicast. Both packet types are sent reliably.
The next page will describe the EIGRP algorithm