Quick Notes: EIGRP DUAL

on
** From: Routing TCP/IP, Volume I, 2nd Edition **


Diffusing Update Algorithm (DUAL)

  • DUAL is a convergence algorithm that replaces the Bellman-Ford or Ford-Fulkerson algorithms used by other distance vector protocols.
  • DUAL uses diffusing computations to perform distributed shortest-path routing while maintaining freedom from loops at every instant.
  • For DUAL to operate correctly, a lower-level protocol must ensure that the following conditions are met:
    • A node detects within a finite time the existence of a few neighbor or the loss of connectivity with a neighbor.
    • All messages transmitted over an operational link are received correctly and in the proper sequence within a finite time.
    • All messages, changes in the cost of a link, link failures, and new-neighbor notifications are processed one at a time within a finite time and in the order in which they are detected.
  • The Cisco EIGRP uses Neighbor Discovery/Recovery and RTP to establish these preconditions.
  • When a neighbor is discovered, EIGRP will attempt to form an adjacency with that neighbor.
  • An adjacency is a logical association between two neighbors over which route information is exchanged.
  • The updates will contain all routes known by the sending routers and the metrics of those routes.
  • For each route, the router will calculate a distance based on the distance advertised by the neighbor and the cost of the link to that neighbor.
  • The lowest calculated metric to each destination will become the feasible distance (FD) of that destination.
  • For example, a router may be informed of three different routes to subnet 172.16.5.0 and may calculate metrics of 380672, 12381440, and 660868 for the three routes. 380672 will become the FD because it is the lowest calculated distance.
  • The feasibility condition (FC) is a condition that is met if a neighbor’s advertised distance to a destination is lower than the router’s FD to that same destination.
  • If a neighbor’s advertised distance to a destination meets the FC, the neighbor becomes a feasible successor for that destination. For example, if the FD to subnet 172.16.5.0 is 380672 and a neighbor advertises a route to that subnet with a distance of 355072, the neighbor will become a feasible successor; if the neighbor advertises a distance of 380928, it will not satisfy the FC and will not become a feasible successor.
  • The concepts of feasible successors and the FC are central to loop avoidance. Because feasible successors are always “downstream,” (that is, a shorter metric distance to the destination than the FD) a router will never choose a path that will lead back through itself, creating a loop. Such a path would have a distance larger than the FD.
  • For every destination listed in the topological table, the route with the lowest metric is chosen and placed into the route table. The neighbor advertising that route becomes the successor, or the next-hop router to which packets for that destination are sent.
  • The command metric weights 0 0 0 1 0 0 has been added to the EIGRP process so that only delay is used in the metric calculations.
  • It should be pointed out that although the delay parameters used here sacrifice realism for simplicity, the way the metrics are manipulated is realistic.
  • If interface metrics need to be manipulated to influence EIGRP (or IGRP) routing, use delay.
  • The show ip eigrp topology command is used to observe the topology table of router Langley.

Langley#show ip eigrp topology
IP-EIGRP Topology Table for process 1

 Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
       r - Reply status

 P 10.1.3.0/24, 1 successors, FD is 512
         via Connected, Serial0
P 10.1.2.0/24, 1 successors, FD is 768
         via 10.1.3.1 (768/256), Serial0
         via 10.1.5.2 (1280/256), Serial1
P 10.1.1.0/24, 1 successors, FD is 768
         via 10.1.3.1 (768/256), Serial0
         via 10.1.5.2 (1536/512), Serial1
P 10.1.7.0/24, 1 successors, FD is 256
         via Connected, Ethernet0
P 10.1.6.0/24, 1 successors, FD is 1024
         via 10.1.3.1 (1024/512), Serial0
         via 10.1.5.2 (1792/768), Serial1
P 10.1.5.0/24, 1 successors, FD is 1024
         via Connected, Serial1
P 10.1.4.0/24, 1 successors, FD is 5632
         via 10.1.3.1 (5632/5120), Serial0
         via 10.1.5.2 (6400/5376), Serial1
Langley#

  • Two metrics in parentheses are also associated with each feasible successor. The first number is the locally calculated metric from Langley to the destination. The second number is the metric advertised by the neighbor.
  • Langley’s route table shows that a single successor has been chosen for each known destination, based on the lowest metric distance.

Langley#show ip route
Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP
       i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default
       U - per-user static route
Gateway of last resort is not set
     10.0.0.0/8 is subnetted, 7 subnets
C       10.1.3.0 is directly connected, Serial0
D       10.1.2.0 [90/768] via 10.1.3.1, 00:32:06, Serial0
D       10.1.1.0 [90/768] via 10.1.3.1, 00:32:07, Serial0
C       10.1.7.0 is directly connected, Ethernet0
D       10.1.6.0 [90/1024] via 10.1.3.1, 00:32:07, Serial0
C       10.1.5.0 is directly connected, Serial1
D       10.1.4.0 [90/5632] via 10.1.3.1, 00:32:07, Serial0
Langley#

  • Feasible successors are important because they reduce the number of diffusing computations and therefore increase performance.
  • If a link to a successor fails, or if the cost of the link increases beyond the FD, the router will first look into its topology table for a feasible successor. If one is found, it will become the successor; this selection normally occurs in the sub-second range.
  • The router will begin a diffusing computation only if a feasible successor cannot be found.

DUAL Finite State Machine

  • When an EIGRP router is performing no diffusing computations, each route is in the passive state. (Good thing!)
  • The first step in its reassessment is a local computation in which the distance to the destination is recalculated for all feasible successors. The possible results are:
    • If the feasible successor with the lowest distance is different from the existing successor, the feasible successor will become the successor.
    • If the new distance is lower than the FD, the FD will be updated.
    • If the new distance is different from the existing distance, updates will be sent to all neighbors.
  • While the router is performing a local computation, the route remains in the passive state.
  • If a feasible successor cannot be found in the topology table, the router will begin a diffusing computation and the route will change to the active state. Until the diffusing computation is completed and the route transitions back to the passive state, the router cannot:
    • Change the route’s successor
    • Change the distance it is advertising for the route
    • Change the route’s FD
    • Begin another diffusing computation for the route
  • A router begins a diffusing computation by sending queries to all of its neighbors. The query will contain the new locally calculated distance to the destination. Each neighbor, upon receipt of the query, will perform its own local computation:
  • If the neighbor has one or more feasible successors for the destination, it will send a reply to the originating router. The reply will contain that neighbor’s minimum locally calculated distance to the destination.
  • If the neighbor does not have a feasible successor, it too will change the route to the active state and will begin a diffusing computation.
  • For each neighbor to which a query is sent, the router will set a reply status flag (r) to keep track of all outstanding queries. The diffusing computation is complete when the router has received a reply to every query sent to every neighbor.
  • In some cases, a router does not receive a reply to every query sent.
  • At the beginning of the diffusing computation, an Active timer is set for three minutes. If all expected replies are not received before the Active time expires, the route is declared stuck-in-active (SIA). The neighbor or neighbors that did not reply will be removed from the neighbor table, and the diffusing computation will consider the neighbor to have responded with an infinite metric.
  • The default three-minute Active time can be changed or disabled with the command timers active-time. The deletion of a neighbor because of a lost query obviously can have disruptive results, and SIAs should never occur in a stable, well-designed network.
  • At the completion of the diffusing computation, the originating router will set FD to infinity to ensure that any neighbor replying with a finite distance to the destination will meet the FC and become a feasible successor. For each of these replies, a metric is calculated based on the distance advertised in the reply plus the cost of the link to the neighbor who sent the reply. A successor is selected based on the lowest metric, and FD is set to this metric. Any feasible successors that do not satisfy the FC for this new FD will be removed from the topology table. Note that a successor is not chosen until all replies have been received.
  • EIGRP packet activity can be observed with the debug command debug eigrp packets. By default, all EIGRP packets are displayed. Because Hellos and ACKs can make the debug output hard to follow, the command allows the use of optional keywords so that only specified packet types are displayed.

Cayley#debug eigrp packet update query reply
EIGRP Packets debugging is on
    (UPDATE, QUERY, REPLY)
B#
%LINEPROTO-5-UPDOWN: Line protocol on Interface Ethernet0, changed state to down
EIGRP: Enqueueing QUERY on Serial0 iidbQ un/rely 0/1 serno 45-49
EIGRP: Enqueueing QUERY on Serial0 nbr 10.1.6.1 iidbQ un/rely 0/0 peerQ un/rely
0/0 serno 45-49
EIGRP: Sending QUERY on Serial0 nbr 10.1.6.1
  AS 1, Flags 0x0, Seq 45/64 idbQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/1 serno
45-49
EIGRP: Received REPLY on Serial0 nbr 10.1.6.1
  AS 1, Flags 0x0, Seq 65/45 idbQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/0
EIGRP: Enqueueing UPDATE on Serial0 iidbQ un/rely 0/1 serno 50-54
EIGRP: Enqueueing UPDATE on Serial0 nbr 10.1.6.1 iidbQ un/rely 0/0 peerQ un/rely
 0/0 serno 50-54
EIGRP: Sending UPDATE on Serial0 nbr 10.1.6.1
  AS 1, Flags 0x0, Seq 46/66 idbQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/1 serno
50-54
EIGRP: Received UPDATE on Serial0 nbr 10.1.6.1
  AS 1, Flags 0x0, Seq 67/46 idbQ 0/0 iidbQ un/rely 0/0 peerQ un/rely 0/1
#Cayley

  • Seq is the Packet Sequence Number/Acknowledged Sequence Number.
  • idbq indicates packets in the input queue/packets in the output queue of the interface.
  • iidbq indicates unreliable multicast packets awaiting transmission/reliable multicast packets awaiting transmission on the interface.
  • peerQ indicates unreliable unicast packets awaiting transmission/reliable unicast packets awaiting transmission on the interface.
  • serno is a pointer to a doubly linked serial number for the route. This is used by an internal (and proprietary) mechanism for tracking the correct route information in a rapidly changing topology.

Core behavior of diffusing computations:
  • Any time an input event occurs, perform a local calculation.
  • If one or more feasible successors are found in the topology table, take the ones with the lowest metric cost as the successors.
  • If no feasible successor can be found, make the route active and query the neighbors for a feasible successor.
  • Keep the route active until all queries are answered by reply or by the expiration of the active timer.
  • If the diffusing calculation does not result in the discovery of a feasible successor, declare the destination unreachable.

Comments

Post a Comment