# The Diffusing Update Algorithm

 ‚  < ‚  Free Open Study ‚  > ‚

### The Diffusing Update Algorithm

The Diffusing Update Algorithm (DUAL) is the brain behind the operation of EIGRP. It is an algorithm that tracks all the routes advertised from a neighbor and then selects a loop-free path to the destination. Before discussing the details of DUAL, you must understand several terms and concepts:

• Feasible distance (FD) ‚ Feasible distance is the minimum metric along the path to a destination. Figure 6-1 shows the feasible distance calculation to reach Network 7 for each of Router A's neighbors, from Router A's perspective.

##### Figure 6-1. Feasible Distance Calculation

• Reported distance (RD) ‚ Reported distance, sometimes also known as advertised distance, is the metric toward the destination, as advertised by the upstream neighbor. In other words, the reported distance is the neighbor's metric going to the destination. Figure 6-2 shows the reported distance calculation to reach Network 7 for each of Router A's neighbors.

##### Figure 6-2. Reported Distance Calculation

• Feasibility condition (FC) ‚ The feasibility condition (FC) is a condition in which the reported distance (RD) is less than the feasible distance (FD). In other words, the feasibility condition is met when the neighbor's metric to a destination is less than the local router's metric. This condition is important to ensure a loop-free path.

• EIGRP successor ‚ A successor is a neighbor that met the feasibility condition (FC) and has the lowest metric toward the destination. A successor is used as the next hop to forward the packet going to the destination network.

• Feasible successor ‚ A feasible successor is a neighbor that satisfies the feasibility condition (FC) but is not selected as the successor. The feasible successor can be thought of as a potential backup route when the primary route goes away.

Figure 6-3 illustrates the concepts of successor and feasible successor.

##### Figure 6-3. Explanation of Successor and Feasible Successor

Router B is chosen as the successor because Router B has the lowest feasible distance (metric = 121) to Network 7 among all of Router A's neighbors. To select a feasible successor, Router A sees which neighbor has a reported distance (RD) that is less than the feasible distance of its successor. In this case, Router H has a reported distance of 30, which is less than the feasible distance of its successor, which is 121. Therefore, Router H is chosen as the feasible successor. Router D is neither a successor nor a feasible successor because its reported distance is 140, which is larger than 121 and thus does not satisfies the feasibility condition.

• Passive route ‚ A passive route in EIGRP indicates that the router has a valid successor to a destination and EIGRP has no complaints.

• Active route ‚ An active route in EIGRP indicates that the router has lost its successor, it doesn't have any feasible successor available, and the router is currently actively searching for alternate routes to converge.

 ‚  < ‚  Free Open Study ‚  > ‚
 ‚  < ‚  Free Open Study ‚  > ‚

### DUAL Finite-State Machine

When EIGRP loses its successor or primary route, EIGRP immediately tries to reconverge by looking at its topology table to see if any feasible successors are available. If a feasible successor is available, EIGRP immediately promotes the feasible successor to a successor and informs its neighbors about the change. The feasible successor then becomes the next hop for EIGRP to forward the packets to the destination. The process by which EIGRP converges locally and does not involve other routers in the convergence process is called local computation. This also saves CPU power because all the feasible successors are already chosen before the primary route failures. (Refer to Figure 6-3.) If the primary route (Router D) is not available for some reason, the preselected feasible successor Router H immediately takes over as the primary route.

Now, if the primary route goes away and no feasible successors are available, the router goes into diffused computation. In diffused computation, the router sends query packets to all its neighbors asking for the lost route, and the router goes into Active state. If neighboring routers have information about the lost route, they reply to the querying router. If neighboring routers do not have information about the lost route, they send queries to all their neighbors. If the neighboring router does not have an alternate route and doesn't have any other neighbors, it sends a reply packet back to the router with a metric set to infinity, indicating that it, too, doesn't have an alternate route available. The querying router waits for all the replies from all its neighbors and then chooses the neighbor with the best metric in its replies as the next hop to forward packets.

Referring to Figure 6-3, if the primary successor Router B is not available and its feasible successor Router H is also not available, Router A sends a query to Router D asking for Network 7. In this case, Router D simply replies to the query with a valid metric to Network 7. Router A then converges using Router D as its next hop to Network 7.

To sum up the operation of DUAL, DUAL selects a successor as the primary path and also selects a feasible successor as its backup path based on the feasibility condition. If the successor becomes unavailable, the feasible successor is used as the primary route. If the feasible successor is not present, the router queries all its neighbors and computes a new successor based on the replies to the queries. Therefore, in an EIGRP network, the query mechanism is the only means to achieve fast convergence.

Chapter 8 of the Cisco Press book Routing TCP/IP, Volume 1, by Jeff Doyle, provides an excellent , detailed description of the operation of the EIGRP DUAL algorithm.

 ‚  < ‚  Free Open Study ‚  > ‚