Diffusing update algorithm
Encyclopedia
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. It was developed by J.J. Garcia-Luna-Aceves at SRI International
. 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.
DUAL evaluates the data received from other routers in the topology table and calculates the primary (successor) and secondary (feasible successor) routes. The primary path is usually the path with the lowest metric to reach the destination, and the redundant path is the path with the second lowest cost (if it meets the feasibility condition). There may be multiple successors and multiple feasible successors. Both successors and feasible successors are maintained in the topology table, but only the successors are added to the routing table and used to route packets.
For a route to become a feasible successor, its RD must be smaller than the FD of the successor. If this feasibility condition is met, there is no way that adding this route to the routing table could cause a loop.
If all the successor routes to a destination fail, the feasible successor becomes the successor and is immediately added to the routing table. If there is no feasible successor in the topology table, a query process is initiated to look for a new route.
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:
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):
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", because its RD is less than the FD of the successor:
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used by Cisco
Cisco
Cisco may refer to:Companies:*Cisco Systems, a computer networking company* Certis CISCO, corporatised entity of the former Commercial and Industrial Security Corporation in Singapore...
's EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. It was developed by J.J. Garcia-Luna-Aceves at SRI International
SRI International
SRI International , founded as Stanford Research Institute, is one of the world's largest contract research institutes. Based in Menlo Park, California, the trustees of Stanford University established it in 1946 as a center of innovation to support economic development in the region. It was later...
. 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
Feasibility condition
The feasibility condition, along with the tangency condition, is used in microeconomics to solve the consumer choice problem and obtain the demand function. It is formed by taking the equality of the budget line...
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 tables for the route calculation. These tables are created using information exchanged between the EIGRP routers. The information is different than that exchanged by link-state routing protocols. In EIGRP, the information exchanged includes the routes, the "metric" or cost of each route, and the information required to form a neighbor relationship (such as AS number, timers, and K values). 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 received from a neighbor for a specified time period, the router is assumed down and removed from the neighbor table.
- Topology table contains the metric (cost information) of all routes to any destination within the autonomous system. This information is received from neighboring routers contained in the Neighbor table. The primary (successor) and secondary (feasible successor) 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 calculated metric of a route to a destination within the autonomous system.
- "RD (Reported Distance)": The metric to a destination as advertised by a neighboring router. RD is used to calculate the FD, and to determine if the route meets the "feasibility condition".
- Route Status: A route is marked either "active" or "passive". "Passive" routes are stable and can be used for data transmission. "Active" routes are being recalculated, and/or not available.
- Routing table contains the best route(s) to a destination (in terms of the lowest "metric"). These routes are the successors from the topology table.
DUAL evaluates the data received from other routers in the topology table and calculates the primary (successor) and secondary (feasible successor) routes. The primary path is usually the path with the lowest metric to reach the destination, and the redundant path is the path with the second lowest cost (if it meets the feasibility condition). There may be multiple successors and multiple feasible successors. Both successors and feasible successors are maintained in the topology table, but only the successors are added to the routing table and used to route packets.
For a route to become a feasible successor, its RD must be smaller than the FD of the successor. If this feasibility condition is met, there is no way that adding this route to the routing table could cause a loop.
If all the successor routes to a destination fail, the feasible successor becomes the successor and is immediately added to the routing table. If there is no feasible successor in the topology table, a query process is initiated to look for a new route.
Example
Legend:- + = Router
- - or | = Link = Metric 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):
- Destination: 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", because its RD is less than the FD of the successor:
- Destination: Router A
- via D: RD(4), FD(5) successor
- via C: RD(3), FD(6) feasible successor