Diffusing update algorithm

from Wikipedia, the free encyclopedia

The Diffusing Update Algorithm ( DUAL for short ) is a component of the originally proprietary routing protocol EIGRP from Cisco. He is responsible for the route calculation. The full name of the algorithm supplied by Cisco is "DUAL finite-state machine" (DUAL FSM).

Using DUAL, when using EIGRP, loop-free routing is created within an autonomous system . DUAL reacts dynamically to changes in the routing topology and automatically adapts the routing tables of the router to changed circumstances.

functionality

For route calculation, DUAL uses three tables created separately by EIGRP in each router. These tables are created on the basis of EIGRP information exchanged between the routers. This is similar to the exchange of information using a link-state routing protocol. In contrast to link state transmissions, in which each router sends the "link states" - ie the status (active / inactive) and the bandwidth of its interfaces to all routers of an autonomous system, so-called "neighborhood relationships" are established with EIGRP. Only the information required by the remote station is transmitted from router to router via these neighborhoods.

The three tables and their function in detail:

  • Neighbor table = contains information about all other directly connected routers. There is a separate neighbor table for each protocol (IP, IPX etc.) that EIGRP supports. An entry with a description of the network interface and address is created for each neighbor . In addition, a timer is initialized that checks at certain intervals whether the connection with the neighbor is still active. This is done using so-called Hello packets. If a Hello packet is not answered within a certain period of time, it is assumed that the route is no longer available and is marked as "passive". (See below)
  • Topology table = contains the information about the cost of each possible connection to each destination within the autonomous system. This information is used to define the primary and secondary route to a destination within the topology table. Among other things, the topology table contains the following entries per destination:
FD (Feasible Distance) : The best calculated distance to a target within the autonomous system.
RD (Reported Distance) : The distance to a destination that was transmitted as information from a router neighbor. For each neighbor there is a separate RD from the neighbor to the desired destination.
Route status : a route is marked either as "active" or "passive". Routes marked as "passive" are stable and can be used for data transmission. Routes marked as "active" are recalculated or are currently being requested from a neighbor.
  • Routing table = contains the best (metric-related, in this case the "cheapest") connection to a destination

DUAL evaluates the data received from other routers within the topology table and calculates the primary and redundant network path. The primary path is usually the lowest cost path to reach the destination, and the redundant path is the second lowest cost path. All paths are kept, but only one of these paths is actually used. Loops are thus automatically avoided.

In order to process requests to a specific destination via the primary path, DUAL enters the neighbor on the primary path as the gateway for all requests to the destination in the routing table. Cisco calls this router a Successor . In the topology table of EIGRP, DUAL also shows the neighbors of the second best connection to a destination as a so-called feasible successor . If the route to the as Successor provided router, this is Feasible Successor instead of the Successors registered in the routing table. For this, the RD needs of Feasible Successor less than the FD of the Successors be. If this is not the case, a possible successor is searched for with the help of a query process. This behavior and these conditions serve to avoid loops.

example

Legend:

+ = Router
- or | = Connection
(X) = cost of the connection
     A    (2)    B    (1)    C
     + - - - - - + - - - - - +
                 |           |
              (2)|           | (3)
                 |           |
                 + - - - - - +
                 D    (1)    E

If a client in a network on router E now wants to start communication with a client in a network connected to router A, this means that router E must provide a route to router A.

This route was calculated as follows:

The direct neighbors of E are D and C.

DUAL asks for the Reported Distance (RD) from C and D to A. This produces the following results:

Destination: Router A
via D: RD (4)
via C: RD (3)

The route via C is therefore the cheapest route if DUAL only included the distance between the neighbors in the routing decisions. In the next step, the distance between the neighbor and the router itself is also included in the calculation . The sum of the reported distance plus the distance to the neighbor is defined as the feasible distance (FD) and used as the basis for prioritizing the routes:

Destination: Router A
via D: RD (4), FD (5)
via C: RD (3), FD (6)

Thus, DUAL determines that the route via D is the most cost-effective route overall. The route via D is therefore marked as a successor , given a passive status and entered in the routing table for use. The route via C is held as a feasible successor .

Destination: Router A
via D: RD (4), FD (5) Successor
via C: RD (3), FD (6) Feasible Successor

literature