Before you start reading this article, we advise you to familiarize yourself with the material about the calculation of the path according to the Bellman - Ford algorithm.
The diffusion update algorithm (Diffusing Update Algorithm -Dual) is one of the two algorithms discussed here originally intended for implementation in a distributed network. It is unique in that it also removes information about achievability and topology contained in the final automata of the algorithm. Other algorithms discussed here leave the removal of information at the discretion of the implementation of the protocol, and do not consider this aspect of the work of the algorithm within the algorithm itself.
By 1993, Bellman-Ford and Dijkstra were implemented as distributed algorithms in several routing protocols. The experience gained as a result of these early implementations and deployments led to the "second wave" of research and reflection on the problem of routing in network switching networks, which led to the appearance of the path vector and DUAL.
Since Dual is designed as a distributed algorithm, it is best to describe his work on the network. For this purpose, Figures 8 and 9 are used. To explain Dual, this example will be traced in a stream of three destinations, and then changes are processed in the availability state for the same destination items. In the first example, the case will be considered when there is an alternative path, but there is no downstream neighbor, the second will consider the case when there is an alternative path and downstream neighbor.
In Figure 8, study D from the point of view A:
- A learns two ways to D:
- A will not recognize the path through B, because B uses A as its successor:
- A compares the available paths and selects the shortest path without loops:
- A Checks the remaining paths to determine if there are any of them downstream neighbors:
A knows this because C announces the route to D with its local metric equal to 3.
A maintains a local metric C in its topology table.
Consequently, A knows the local value in C and the local value in A.
- 3 (Cost in C) = 3 (Cost in a), so this route may be loop, therefore, C does not satisfy the condition of feasibility. C is not labeled as Downstream Neighbors.
DOWNSTREAM NEIGHBORS in DUAL is called possible successors. Suppose that the channel [A, H] does not work. Dual does not rely on periodic updates, so A can not just wait for another update with reliable information. Rather, A must actively follow an alternative path. Thus, this is a diffuse detection process of an alternative path. If the channel [A, H] does not work, considering only D:
- A Checks your local table for possible successors (Downstream Neighbors).
- There are no possible successors, so A must find an alternative path without loops to D (if it exists).
- A sends a request to each neighbor to determine if there is any alternative path without loops to D.
- In C:
- In B:
- A gets these answers:
In Figure 9, the destination (D) item was moved with H to E. This will be used in the second example.
In this example, there is a possible successor (Downstream Neighbor).
Study D from the point of view A:
- A learns two ways to D:
- A will not recognize any way through B:
- A compares the available paths and selects the shortest path without loops:
- A Checks the remaining paths to determine if there are any of them downstream neighbors:
If the channel [A, C] does not work, simply considering a:
- A checks its table of local topology for a possible successor.
- Possible successor exists through H.
- A switches its local table on H as the best way.
- A sends an update to its neighbors, noting that its cost of achievement D has changed from 3 to 4.
As you can see, processing when there is a possible successor, much faster and easier than without it. In networks where the routing protocol was deployed using Dual (in particular, EIGRP), one of the main design objectives will limit the volume of any requests generated in the absence of a possible successor. The request area is the main determining factor how the double algorithm is quickly completed and, therefore, how quickly the network converges.
Figure 10 shows the basic finished DUAL machine.
Things included in the Route Gets Worse (degradation of the route) may be:
- Failure of the connected channel or neighbor
- Obtaining an update for a route with a higher metric
- Getting a query from the current successor
- Getting a new route from a neighbor
- A new neighbor was found, as well as routes by which it can get
- Getting all requests sent to neighbors when the route worsens
