 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 HoldTime expires, DUAL is informed of the topology change.
The neighbor table entry also includes information required by the reliable transport mechanism. Sequence numbers are employed to match acknowledgments with data packets. The last sequence number received from the neighbor is recorded so out of order packets can be detected. A transmission list is used to queue packets for possible retransmission on a per neighbor basis. Round trip timers are kept in the neighbor data structure to estimate an optimal retransmission interval.
The Topology Table is populated by the protocol dependent modules and acted upon by the DUAL finite state machine. It contains all destinations advertised by neighboring routers. Associated with each entry is the destination address and a list of neighbors that have advertised the destination. For each neighbor, the advertised metric is recorded. This is the metric that the neighbor stores in its routing table. If the neighbor is advertising this destination, it must be using the route to forward packets. This is an important rule that distance vector protocols must follow.
Also associated with the destination is the metric that the router uses to reach the destination. This is the sum of the best advertised metric from all neighbors plus the link cost to the best neighbor. This is the metric that the router uses in the routing table and to advertise to other routers.
A destination entry is moved from the topology table to the routing table when there is a feasible successor. All minimum cost paths to the destination form a set. From this set, the neighbors that have an advertised metric less than the current routing table metric are considered feasible successors.
Feasible successors are viewed by a router as neighbors that are downstream with respect to the destination. These neighbors and the associated metrics are placed in the forwarding table.
When a neighbor changes the metric it has been advertising or a topology change occurs in the network, the set of feasible successors may have t