in the recomputation. The convergence time with DUAL rivals that of any other existing routing protocol.
EIGRP has been extended to be network-layer-protocol independent, thereby allowing DUAL to support other protocol suites.
EIGRP has four basic components:
Reliable Transport Protocol
DUAL Finite State Machine
Protocol Dependent Modules
Neighbor Discovery/Recovery is the process that routers use to dynamically learn of other routers on their directly attached networks. Routers must also discover when their neighbors become unreachable or inoperative. This process is achieved with low overhead by periodically sending small hello packets. As long as hello packets are received, a router can determine that a neighbor is alive and functioning. Once this is determined, the neighboring routers can exchange routing information.
The reliable transport is responsible for guaranteed, ordered delivery of EIGRP packets to all neighbors. It supports intermixed transmission of multicast or unicast packets. Some EIGRP packets must be transmitted reliably and others need not. For efficiency, reliability is provided only when necessary. For example, on a multi-access network that has multicast capabilities, such as Ethernet, it is not necessary to send hellos reliably to all neighbors individually. So EIGRP, sends a single multicast hello with an indication in the packet informing the receivers that the packet need not be acknowledged. Other types of packets, such as updates, require acknowledgment and this is indicated in the packet. The reliable transport has a provision to send multicast packets quickly when there are unacknowledged packets pending. This helps insure that convergence time remains low in the presence of varying speed links.
The DUAL finite state machine embodies the decision process for all route computations. It tracks all routes advertised by all neighbors. The distance information, known as a metric, is used by DUAL to select efficient loop free paths. DUAL selects routes to be inserted into a routing table based on feasible successors. A successor is a neighboring router used for packet forwarding that has a least cost path to a destination that is guaranteed not to be part of a routing loop. When there are no feasible successors but there are neighbors advertising the destination, a recomputation must occur. This is the process where a new successor is determined. The amount of time it takes to recompute the route affects the convergence time. Even though the recomputation is not processor-intensive, it is advantageous to avoid recomputation if it is not necessary. When a topology change occurs, DUAL will test for feasible successors. If there are feasible successors, it will use any it finds in order to avoid any unnecessary recomputation. Feasible successors are defined in more detail later in this document.
The protocol-dependent modules are responsible for network layer, protocol-specific requirements. For example, the IP-EIGRP module is responsible for sending and receiving EIGRP packets that are encapsulated in IP. IP-EIGRP is responsible for parsing EIGRP packets and informing DUAL of the new information received. IP-EIGRP asks DUAL to make routing decisions and the results of which are stored in the IP routing table. IP-EIGRP is responsible for redistributing routes learned by other IP routing protocols.
This section describes some details about Cisco's EIGRP implementation. Both data structures and the DUAL concepts are discussed.
Each router keeps state information about adjacent neighbors. When newly discovered neighbors are learned, the address and interface of the neighbor is recorded. This information is stored in the neighbor data structure. The neighbor table holds these entries. There is one neighbor table for each protocol dependent module. When a neighbor sends a hello, it advertises a HoldTime. The HoldTime is the amount of time a router treats a neighbor as reachable and operational. In other words, if a hello packet isn't heard within the HoldTime, then the HoldTime expires. When the HoldTim