EIGRP: Diffusing Update Algorithm

The Diffusing Update Algorithm (DUAL) is an algorithm that is used by EIGRP.  DUALs purpose is to prevent routing loops using the concept of diffusing computations to perform a distributed shortest path computation while maintaining the freedom of loops during the calculation.

When EIGRP detects a topology change and the router finds the new shortest path is provided by a neighbor who is  not a feasible successor, the router cannot use that neighbor right away because it might cause a routing loop.  It is at this point that the diffusing computation begins:

  1. the routing table entry still pointing to the unchanged successor is locked, it will not be removed or changed until the diffusing computation is completed and the route has been moved to the Passive state.
  2. The Feasible Distance is set to the current Computed distance through the unchanged successor.  If the router ever needs to advertise its distance to the network while in the Active state, it will also use the value of the current CD through the Successor
  3. the network is put into the Active state and the router sends a Query packet to all neighbors.  the Query packet contains the Active network’s prefix and  the routers current CD to it.

Each neighbor receiving the query will process it by updating its own topology table using the distance information advertised in the Query and reevaluating its own choice of successors.

At this point either the neighbor still has its own path that provides least cost loop free or the query causes the neighbor to stop considering the path through its current successor the shortest available and none of its own neighbors are feasible.

If the neighbor still has a Successor it will immediately send a Reply indicating the neighbors distance to the destination.  This neighbor did not engage in the diffusing computation since it did not need to put the network into the Active state itself.

If the neighbor does NOT have a successor it will join the diffusing computation, it will send out its own query packet and advertise its own current distance through its current successor.  This propagates through the part of the network that is affected by  the change.  Parts of the network not affected by the change are not affected.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s