Monday, November 28, 2011

EIGRP DUAL - Diffusing Update Algorithm

EIGRP uses the DUAL finite-state machine to tracks all routes advertised by all neighbors with the topology table, performs route computation on all routes to select an efficient and loop-free path to all destinations, and inserts the lowest metric route into the routing table.

EIGRP uses the advertised distance and feasible distance to determine the successor (best route) and feasible successor (backup route) to a destination network.

Advertised Distance The EIGRP metric for a next-hop EIGRP neighboring router to reach a destination network. Also known as Reported Distance.
Feasible Distance The EIGRP metric for the local router to reach a destination network. Theoretically it is the sum of the advertise distance of an EIGRP neighbor and the metric to reach the neighbor, but actually the local router would recalculate the EIGRP metric to the destination network.
The xxx and yyy in the via A.B.C.D (xxx/yyy), interface entry in the show ip eigrp topology EXEC command represent feasible distance and advertised distance respectively.

An EIGRP router compares all feasible distances to reach a destination network in its topology table. The lowest-metric route(s) will be placed in its IP routing table as the successor route(s).

EIGRP Neighbor Table, Topology Table, and Routing Table

RT1’s topology table has 2 paths to reach The EIGRP metric for RT1 to reach RT2 and RT3 is 1000. The metric (1000) will be added to the respective AD from each router, which represents the FD for RT1 to reach network via a particular neighbor. RT1 chooses the least-cost FD (2000) as the best route and inserts it into its IP routing table. An EIGRP route in the routing table is the best FD selected from the EIGRP topology table.
Note: Advertised distance is used only to calculate the feasible distance (the least-cost path); it does not affect the selection of the best route. Because there could be cases where the advertised distance from a neighbor is promising, but the metric to the neighbor is disappointing. Hence the path via the neighbor would not be selected as the feasible distance.

Successor is a neighboring router that has the least-cost or lowest-metric (best) path of all possible paths to reach a destination network. After the best path to reach a network is selected, EIGRP inserts the destination network, metric to reach the network, outbound interface to reach the next-hop router, and the IP address of the next-hop router into the IP routing table. If the EIGRP topology table has multiple equal-cost FD entries to a destination network, all successors (4 by default) for the destination network will be inserted into the routing table.

Feasible Successor is a neighboring router that does not does not provide the least-cost path but provides a backup route. The route through the feasible successor must be loop-free. Successors and feasible successors are selected at the same time during the metric computation process. Feasible successor routes are maintained in the topology table, as well as in the routing table when unequal-cost load balancing is enabled with the variance router subcommand.

To be qualified as a feasible successor, the AD from a neighboring router must be less than (and not equal to) the FD of the successor route to a destination network. This ensures an FS is loop-free and will never route packets to the destination network through the local router, or else this would result in a routing loop. The AD of the local router (RT1) would often be greater than the FD of the neighboring feasible successor router (RT2) and will eventually notify the neighboring feasible successor router (RT2) that the local router is not a feasible successor for the destination network and never route packets to the destination network via the local router (RT1). When the AD from a neighboring router is greater than or same as the FD of the local router to the destination network, it means that the neighboring router could route packets to the destination network via the local router. Considering the path via the neighboring router as a feasible successor (backup route) and immediately uses the path to forward packets upon the failure of the successor route would result in routing loop.

Every neighbor that satisfies the relation of AD < FD for a particular destination network is a loop-free route to that destination. This feasibility condition is proven in Loop-free Routing using Diffusing Computations by Dr. J. J. Garcia-Lunes-Aceves published by IEEE on Feb 1993. Below shows an excerpt from the output of the show ip eigrp topology EXEC command. The FD (successor) to the network is via Fa0/0. The route via S1/0 is considered a FS as the AD from (30720) is less than the FD (284160) to the network.
P, 1 successors, FD is 284160
         via (284160/281600), FastEthernet0/0
         via (2174976/30720), Serial1/0

RT3 is an FS to, as the AD through RT3 (1500) is less than the FD of the current successor, RT2 (2000).

All routing protocols can insert only the next-hop router information in the routing table, information about the subsequent routers along the path can never appear in the routing table. Each router counts on the next-hop router to reach a destination network. Each router makes a path selection to reach a network and installs the best next-hop address to reach the network. A router trusts a successor (the best next-hop router) to forward traffic to the destination network.

The routing table is a subset of the topology table. The topology table contains more detailed information about each route, backup routers, and information used exclusively by DUAL.

When a router loses a route, it first looks at the topology table for an FS. If there is an FS, the route does not go into active state, and the best FS is promoted as the successor and inserted into the routing table – an FS is used immediately without any route computation. If there is no FS, a route goes into active state. A new successor will be determined through the route computation process, in which an EIGRP router will begin the process by sending queries to all its neighbors. The queried neighbors may also go through the same process, which creates a cascading of queries through the network to search the network for a path to the destination. The amount of route computation time affects the convergence time.

An EIGRP router would perform the following tasks upon the receipt of a query for a route:
i) If the EIGRP topology table of the router does not contain an exact entry for the queried route, it immediately replies with a network is unreachable message to state that there is no path for the queried route through this neighboring router.
ii) If the EIGRP topology table of the router lists the querying router as the successor for the queried route and contains one or more FSs, the FS with the lowest metric will be installed into the routing table and the router immediately replies the information of the FS to the querying router.
iii) If the EIGRP topology table of the router lists the querying router as the successor for the queried route and does not contain a FS, the router propagates the query to all its neighboring routers except the querying router to seek for another alternative successor. The router will not reply to the querying router until it has received a reply for each query it propagated to its neighboring routers.
iv) If the querying router is not the successor for the queried route, the router immediately replies the information of its successor to the neighboring router.

For each neighbor to which a query is sent, an EIGRP router will set a reply status flag (r) to keep track of all outstanding queries that are waiting for replies. The DUAL computation is completed when the router has received a reply for every query sent out earlier.
Router>sh ip eigrp topology
IP-EIGRP Topology Table for AS(100)/ID(

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
       r - reply Status, s - sia Status

Passive (P) Indicates an available and stable network which can be installed into the routing table.
Active (A) Indicates an unavailable network which has outstanding queries and cannot be installed into the routing table.
Update (U) Indicates that a network is being updated and the router is waiting for an acknowledgment for the update packet.
Query (Q) Indicates that a network has an outstanding query packet or the router is waiting for an acknowledgment for a query packet.
Reply (R) Indicates that the router is generating a reply for the network or is waiting for an acknowledgment for the reply packet.
Reply Status (r) Indicates that the router is waiting for the reply to a query packet from a neighboring router.

At the beginning of the DUAL computation, an Active timer will be set for 3 minutes. If the expected reply for each outstanding query is not received before the Active timer expires, the route will enter into the Stuck-in-Active (SIA) state. The router will reset the neighbor relationships for a neighbor that failed to reply, and cause the router to go active on all routes known through the neighbor and re-exchange routing information with the neighbor.

SIA should not occur in well-designed and stable networks. If a neighboring router or a link fails, it should be detected by the expiry of the hold timer instead of the expiry of the active timer. Such problems are often not the root cause of SIA.

SIA may occur due to looping of queries, heavily congested and/or low bandwidth links, and/or overloaded routers in a large network. SIA may lead to flushing of valid neighbors and routes which would affect the stability of a network.

The EIGRP SIA Rewrite or Active Process Enhancement feature was introduced to provide improved network reliability by preventing unintended resets of neighbor relationships between querying and queried routers due to the SIA conditions.


The figure above shows the differences of the SIA conditions with and without the SIA Rewrite feature. When RT1 loss the route to, it would send a query for the network to RT2. RT2 would propagate the query to RT3 as it has no feasible successor for the network. As RT3 has no other neighbors to query, it would reply RT2 that it has no feasible successor. If RT2 never receives the reply from RT3 due to an errored link between RT2 and RT3, RT1 would reset the neighbor relationship between RT1 and RT2 after its Active timer expired. The question is why interrupts RT1 and RT2 when RT2 and RT3 are experiencing problems?

With the SIA Rewrite feature, RT1 would query RT2 about the status of the route with a SIA-Query when the SIA-retransmit timer expires (90 seconds). RT2 would respond to the SIA-Query from RT1 with a SIA-Reply indicates that it is still searching for a new successor. Upon the receipt of SIA-Reply from RT2, RT1 would acknowledge the status of RT2 and reset the Active and SIA-retransmit timers. RT2 would also send a SIA-Query to RT3. If no SIA-Reply or reply to the original query for the active route is received from RT3 within the SIA-retransmit timer due to network link problem, RT2 would terminate the neighbor relationship with RT3 and inform RT1 that is unreachable. RT1 and RT2 would remove the active route from their topology and routing tables and the neighbor relationship between them remains intact.
Note: When a router starts querying for an active route, it would activate the Active timer (3 minutes) and SIA-retransmit timer, which is half of the value of the Active timer (90 seconds).

Assuming that no reply to the original query is received, an EIGRP router will send up to 3 SIA-Query messages as long as SIA-Reply messages are received before resetting a neighbor. Hence as long as a neighbor router responds to every SIA-Query within the SIA-transmit timer, it won't be declared SIA and reset for 6 minutes, assuming a default Active timer of 180 seconds. This gives more time for large networks to respond to the query-reply processes for active routes.

3 SIA Query-Reply Cycles Maintain Neighbor Relationship up to 6 Minutes

No comments:

Post a Comment