Diffusing update algorithm

DUAL, the Diffusing Update ALgorithm, is the algorithm used by Cisco's EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. According to Cisco, the full name of the algorithm is DUAL finite-state machine (DUAL FSM). EIGRP is responsible for the routing within an autonomous system and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.

EIGRP uses a feasibility condition to ensure that only loop-free routes are ever selected. The feasibility condition is conservative: when the condition is true, no loops can occur, but the condition might under some circumstances reject all routes to a destination although some are loop-free.

When no feasible route to a destination is available, the DUAL algorithm invokes a Diffusing Computation to ensure that all traces of the problematic route are eliminated from the network. At which point the normal Bellman-Ford algorithm is used to recover a new route.

Operation

DUAL uses three separate routing tables for the route calculation. These tables are created using information exchanged between the EIGRP routers. The information is similar to that exchanged by link-state routing protocols. In EIGRP, the information exchanged includes the "link states", i.e. sent status (active/inactive), and the neighbourhood relations. The three tables and their functions in detail are as follows:

• Neighbor table contains information on all other directly connected routers. A separate table exists for each supported protocol (IP, IPX, etc). Each entry corresponds to a neighbour with the description of network interface and address. In addition, a timer is initialized to trigger the periodic detection of whether the connection is alive. This is achieved through "Hello" packets. If a "Hello" packet is not answered for a specified time period, the route is assumed down and marked "inactive". (See below)
• Topology table contains the cost information of all possible connections to any destination within the autonomous system. The primary and secondary routes to a destination will be determined with the information in the topology table. Among other things, each entry in the topology table contains the following:

"FD (Feasible Distance)": The best calculated distance to a destination within the autonomous system.

"RD (Reported Distance)": The distance to a destination from a neighbouring router as reported through the routing protocol. RD to the desired destination exists for each of its own neighbour.

Route Status: A route is marked either "active" or "passive". "Passive" routes are stable and can be used for data transmission. "Active" routes are recalculated, and/or not available.

• Routing table contains the current best (in terms of "cost") route to a destination

DUAL evaluates the data received from other routers in the topology table and calculates the primary and secondary (redundant) network path. The primary path is usually the path with the lowest costs to reach the destination, the redundant path is the path with the second lowest cost. All paths are maintained, but only one of them is also used, so that loops can be avoided automatically.

To route a packet to a destination, the a primary path is used. The primary path is composed of a designated "successor" router of the previous one, until the destination. In the EIGRP topology table, besides the "successor", there is also an entry of the second best neighbor to the destination, known as "feasible successor". If routing to "successor" fails, the "feasible successor" is used instead. When this happens, the RD of "feasible successor" must be smaller than the FD, which is the distance through the "successor". Otherwise, a query process is initiated to look for a "feasible successor". This is a loop avoidance measure.

Example

Legend:

+ = Router

- or | = Link

(X) = Cost of link

     A    (2)    B    (1)    C
     + - - - - - + - - - - - +           
                 |           |
              (2)|           | (3)         
                 |           |
                 + - - - - - +
                 D    (1)    E

Now a client on router E wants to talk to a client on router A. That means a route between router A and router E must be available. This route is calculated as follows:

The immediate neighbours of router E are router C and router D. DUAL in router E asks for the reported distance from routers C and D respectively to router A. The following are the results:

Destination: Router A

via D: RD(4)

via C: RD(3)

The route via C is therefore in the lowest cost. In the next step, the distance from router E to the neighbours are added to the reported distance to get the feasible distance (FD):

Dstination: Router A

via D: RD(4), FD(5)

via C: RD(3), FD(6)

DUAL therefore finds that the route via D has the least total cost. Then the route via D will be marked as "successor", equipped with passive status and registered in the routing table. The route via C is kept as a "feasible successor:

Destination: Router A

via D: RD(4), FD(5) successor

via C: RD(3), FD(6) feasible successor