EIGRP DUAL The Diffusion Update Algorithm
Article will provide the complete concepts about EIGRP DUAL (The Diffusion Update Algorithm) and the EIGRP topology table are fully explained. You will also learn how the DUAL finite state machine (FSM) works and its use is exemplified.EIGRP uses the DUAL convergence algorithm which helps the networks to avoid routing loops. Routing loops, even temporary ones, can be detrimental to network performance. Distance vector routing protocols, such as RIP, avoid routing loops with waiting timers and split horizon. Although EIGRP uses both techniques, it uses them somewhat differently; The main way in which EIGRP avoids routing loops is with the DUAL algorithm.
What is EIGRP DUAL Algorithm ?
EIGRP uses the diffusion update algorithm (DUAL) to provide the best route without loops and the best backup routes without loops. The DUAL algorithm is used to ensure that there are no loops in each instance through the computation of a route. In the context of DUAL several terms are used, which are analyzed in more detail in this section:
- Successor
- Feasible distance (FD)
- Feasible Successor (FS)
- Published Distance (AD) or Notified Distance (RD):
- Feasible condition or Feasibility condition (FC)
These terms and concepts are essential in the DUAL loop prevention mechanism. EIGRP DUAL provides:
- Routes without loops
- Backup routes without loops that can be used immediately
- Fast convergence
- Minimal bandwidth usage with limited updates
EIGRP Successors and Feasible Distance?
In Image, the topology for this topic is shown. A successor is a neighboring router that is used for packet forwarding and is the least expensive route to the destination network. The successor's IP address is shown in a routing table entry just after the word via.
FD is the lowest metric calculated to reach the destination network. FD is the metric listed in the routing table entry as the second number within the square brackets. As in other routing protocols, this is also known as the “ route metric” .
Analyze the routing table for R2 in Image 2 and note that the best EIGRP route for the 192.168.1.0/24 network is through router R3 and that the feasible distance is 3 012 096. This is the metric that was calculated in the previous topic.
FEASIBLE SUCCESSORS, FEASIBILITY CONDITION AND DISTANCE REPORTED
DUAL can converge quickly after a change in the topology, because it can use backup routes to other networks without recalculating DUAL. These backup routes are known as " feasible successors " (FS).An FS is a neighbor that has a backup route without loops to the same network as the successor and satisfies the feasibility condition (FC). The successor of R2 for the 192.168.1.0/24 network is R3, which provides the best route or the lowest metric to the destination network. Note in Figure 1 that R1 provides an alternative route, but is it an FS? Before R1 can be an FS for R2, it must meet the FC.
The FC is met when the notified distance (RD) from a neighbor to a network is less than the feasible distance from the local router to the same destination network. If the reported distance is shorter, it represents a route without loops. The reported distance is simply a feasible distance from the EIGRP neighbor to the same destination network. The reported distance is the metric that a router informs a neighbor about its own cost to that network.
EXAMPLES: Feasible Successor
In following figure, the feasible distance from R1 to 192.168.1.0/24 is 2 170 112.
- R1 informs R2 that its FD at 192.168.1.0/24 is 2 170 112.
- From the perspective of R2, 2 170 112 is the RD of R1.
R2 uses this information to determine if R1 meets the FC and therefore can be an FS.
As shown in following image, because the RD of R1 (2 170 112) is lower than the FD of R2 (3 012 096), R1 meets the FC.
R1 is now an FS for R2 to the 192.168.1.0/24 network.
If there is an error in the route from R2 to 192.168.1.0/24 through R3 (successor), R2 immediately installs the route through R1 (FS) in its routing table. R1 becomes the new successor for the route of R2 to this network, as shown in Image below.
EIGRP TOPOLOGY TABLE
The EIGRP topology table contains all known routes to each EIGRP neighbor. As an EIGRP router discovers routes from its neighbors, those routes are installed in its EIGRP topology table. If you want to learn about EIGRP Commands you can visit here.
SHOW IP EIGRP TOPOLOGY COMMAND
As shown in Image, the first line in the topology table shows the following:
- P : route in passive state. When DUAL does not perform its broadcast counts to determine the route for a network, the route is in stable mode, known as " passive state ".
If DUAL recalculates or searches for a new route, the route is active, and an “A” is displayed. All routes in the topology table should be in the passive state for a stable routing domain.
192.168.1.0/24 : destination network, which is also found in the routing table.
- 1 successors : shows the number of successors for this network. If there are several routes of the same cost to this network, there are several successors.
- FD is 3012096 : FD is the metric of EIGRP to reach the destination network. This is the metric shown in the IP routing table.
UNDERSTANDING THE RESULT
As shown in Image, the first sub-entry in the result shows the successor:
- via 192.168.10.10 : address of the next hop of the successor, R3. This address is shown in the routing table.
- 3012096 : FD at 192.168.1.0/24. It is the metric shown in the IP routing table.
- 2816 : RD of the successor; It is the cost of R3 to reach this network.
- Serial 0/0/1 : output interface used to reach this network, which is also shown in the routing table.
ABSENCE OF FEASIBLE SUCCESSOR
To see how DUAL uses successors and FSs, examine the routing table of R1 based on the assumption that the network is convergent, as shown in the figure.
In the following result, a partial result of the show ip route command is shown on R1. The route to 192.168.1.0/24 shows that the successor is R3 through 192.168.10.6, with an FD of 2 170 112.
R1 # show ip route
<result omitted>
D 192.168.1.0/24 [ 90/2170112 ] via 192.168.10.6 ,
01:23:13, Serial0 / 0/1
The IP routing table only includes the best route, that is, the successor. To see if there is any FS, we must analyze the EIGRP topology table.
In the following topology table, only the successor 192.168.10.6 is shown, which is R3.
R1 # show ip eigrp topology
<result omitted>
P 192.168.1.0/24, 1 successors, FD is 2170112
via 192.168.10.6 (2170112/2816), Serial0 / 0/1
There is no FS. When looking at the actual physical topology or the network diagram, it is obvious that there is a backup route for 192.168.1.0/24 through R2. R2 is not an FS, because it does not meet the FC. However, when observing the topology, it is obvious that R2 is a backup route, since EIGRP does not have a map of the network topology. EIGRP is a distance vector routing protocol and only knows the information of the remote network through its neighbors.
THE SHOW IP EIGRP TOPOLOGY ALL-LINKS COMMAND
DUAL does not store the route through R2 in the topology table. All links can be displayed using the show ip eigrp topology all-links command . This command shows the links, regardless of whether they meet the FC or not.As shown in Image, the show ip eigrp topology all-links command shows all possible routes to a network, including successors, FSs and even non-FS routes. The FD of R1 at 192.168.1.0/24 is 2 170 112, through the successor R3. For R2 to be considered an FS, it must meet the FC. The RD from R2 to R1 to reach 192.168.1.0/24 must be lower than the current FD of R1. According to the illustration, the RD of R2 is 3 012 096, which is higher than the current FD of R1, of 2 170 112.
Although R2 looks like a possible backup route for 192.168.1.0/24, R1 does not know that the route is not a potential loop back through itself. EIGRP is a distance vector routing protocol, without the ability to view a topology map without complete network loops.
The DUAL method to ensure that a neighbor has a loopless route is that the neighbor's metric meets the FC. By ensuring that the neighbor's RD is lower than its own FD, the router can assume that that neighboring router is not part of its own announced route and, therefore, always avoid a potential loop.
R2 can be used as a successor if R3 fails, however, there is a longer delay before adding it to the routing table. Before R2 can be used as a successor, DUAL must carry out more processes.
DUAL FINITE STATE MACHINE (FSM)
The core of EIGRP are DUAL and its EIGRP route calculation engine. The real name of this technology is DUAL Finite State Machine (FSM). This FSM contains all the logic used to calculate and compare routes in an EIGRP network. The figure shows a simplified version of DUAL FSM.An FSM is an abstract machine, not a mechanical device with moving parts. FSM defines a set of possible states that can be passed through, what events cause these states and what events are the result of these states. Designers use the WSF to describe the way in which a device, a computer program or a routing algorithm reacts to a set of input events.
The WFTUs exceed the scope of this course. However, the concept is used to examine some of the results of the EIGRP FSMs by using the debug eigrp fsm command . Use this command to analyze what DUAL does when a route is deleted from the routing table.
DUAL: FEASIBLE SUCCESSOR
Currently, R2 uses R3 as the successor to 192.168.1.0/24. In addition, R2 currently includes R1 as an FS, as shown in Image.
The result of show ip eigrp topology for R2 verifies that R3 is the successor and R1 is the FS for network 192.168.1.0/24.
R2 # show ip eigrp topology
P 192.168.1.0/24, 1 successors, FD is 3012096
via 192.168.10.10 (3012096/2816), Serial0 /
0/1 via 172.16.3.1 (41024256/2170112), Serial0 / 0/0
To understand how DUAL can use an FS when the route used by the successor is not available, a link failure between R2 and R3 is simulated.
LINK FAILURE SIMULATION
Before simulating the failure, DUAL debugging must be enabled using the debug eigrp fsm command on R2, as shown in Image 14. The link failure is simulated by the shutdown command on the Serial 0/0/1 interface of the R2.
The debug result shows the activity generated by DUAL when a link is out of order. The R2 must inform all EIGRP neighbors of the lost link and also update their own routing and topology tables. In this example, only selected debug results are shown. Note in particular that the DUAL FSM searches for and finds an FS for the route in the EIGRP topology table.
The FS R1 now becomes the successor and is installed in the routing table as the new best route to 192.168.1.0/24. With an FS, this change in the routing table happens almost immediately.
R2 # show ip route
D 192.168.1.0/24 [90/41024256] via 172.16.3.1, 00:15:51,
Serial0 / 0/0
As shown below, the topology table for R2 now shows R1 as the successor, and there are no new FS. If the link between R2 and R3 is activated again, R3 becomes the successor again and R1 becomes the FS once again.
R2 # show ip eigrp topology
P 192.168.1.0/24, 1 successors, FD is 41024256
via 172.16.3.1 (41024256/2170112), Serial0 / 0/0
No comments:
Post a Comment