EIGRP Algorithm and Operation
EIGRP supports IPv4 classless addressing and utilizes the DUAL algorithm in order to create the routing table. Both the algorithm and data structure (Neighbor Table & Topology Table) will be analyzed below:
EIGRP routers obtain information about the state of the adjacent neighbors and their IP addresses. Every time new neighbors are discovered their IP address and interface are recorded and stored in the neighbors’ table (data structure). While the neighbor sends Hello packets, it also advertises the Hold Time to determine whether the neighbor is operational and reachable. It must be noted that the ASN (Autonomous System Number), Subnet Number and K values must be identical in order for the neighbor adjacency to be formed. Hello packets are sent to the multicast address every 5 seconds on LAN interfaces & every 60 seconds on WAN interfaces to verify that the neighbor relationship is still active. If the Hold Time Interval passes (hold-down timer by default is 15 seconds) due to the fact that a Hello packet wasn’t heard within this, the DUAL algorithm is forced to run taking into account the topology changes. Furthermore, the neighbor table contains essential information for the RTP (Reliable Transport Protocol) mechanism in order to pair acknowledgements with their corresponding data packets. It must be stressed that round trip timers are stored in the neighbor table in order to evaluate an optimal retransmission interval (Graziani & Jonson, 2008).
Diffusion Update ALgorithm (DUAL)
EIGRP uses the DUAL (Diffusing Update ALgorithm) or else DUAL FSM (finish-state machine) which ensures that each route will be loop-free calculated in order for routing loops to be avoided. This algorithm responds promptly in changes that might occur in the routing topology and adjusts dynamically the routing tables. The factors that contribute in the loop-free routes mechanism are being analyzed below (Xu, Dai & Garcia-Luna-Aceves, 1997):
- Feasible Distance (FD) is the best EIGRP metric or else the lowest cost along a path to a destination network with the participation of the route metric that has been advertised by the neighbor, listed in the routing table.
- Reported Distance (RD) / Advertised Distance (AD) is the total cost of the route as advertised by the neighbor & needed along the path to the destination network.
- Successor also known as current Successor (or primary route) is the route with the lowest Feasible Distance guarantying a loop-free path to a destination. The successor routes are installed in the routing table in order to be used for forwarding packets.
- Feasible Successor (FS) is the backup route with reported distance less than the feasible distance. The FD of the Feasible Successor is greater than the FD of the Successor, however it’s Advertised Distance (AD) must be lower than the FD of the Successor. These routes are stored in the topology table and are promoted immediately when the Successor route fails.
- Feasibility Condition (FC) is the condition that provides loop-free routes to a destination with the contribution of the Successor and Feasible Successor routes. Feasibility Condition states that the Reported Distance must be lesser than the Feasible Distance [RD < FD] in order for a route to become a feasible Successor (Cisco, 2015).
EIGRP topology table includes all learned routes to a destination advertised by neighboring routers. Specifically, the topology table stores routes and their metrics, Successors and Feasible Successors as well as locally connected subnets. It must be noticed that routes in the topology table are usable by the router only when they are active and inserted into the routing table or have a higher AD than an equivalent path. For every reachable network, the topology table contains the total delay, reliability and path loading, the lowest bandwidth on the path (the weakest link), the feasible and reporting distance and finally the route source (Graziani & Jonson, 2008).
Convergence starts when two routers become neighbors. This dynamic learning happens through the exchange of hello packets (default hello timer is 5 seconds on high-bandwidth links and 60 seconds on slower links). The outcome of this neighbor discovery is the creation of the neighboring tables with all the additional features as described in previous sections.
At that point the neighboring routers exchange routing information and build their corresponding topology tables. In a next step they employ the DUAL algorithm to calculate the feasible and reported distances, and of course the successor and feasible successor routers. The latter routes may exist in the case the feasibility condition is met, thus providing loop-free alternatives to the successor route.
The feasible successor routes and their existence is utmost significant to the EIGRP convergence process. When a successor (primary route) fails, then the EIGRP process (Sankar & Lancaster, 2014):
- checks for a feasible successor and if one is found then it is immediately promoted to a successor and is inserted in the routing table
- If a feasible successor does not exist, then the EIGRP process marks the failed route as ACTIVE in the topology table and starts sending query packets to all neighbor routers to find an alternate route to the network that failed. If these neighbors do not have an alternate route then they mark this failed route as ACTIVE in their topology tables, and generate query packets which they forward to their neighboring routers and so on. In case a router knows an alternate path, he responds to the query packets and all routers converge through a recursive process. In the case no router responds, the routers keep this route as ACTIVE until the corresponding EIGRP timers expire, but until then they all are Stuck-In-Active (SIA).
The aforementioned convergence process poses a threat to the scaling of an EIGRP network in an arbitrary way. When the number of routers in an EIGRP network grows to the number of hundreds, then the stuck in active situation may bring the network to its knees. In that case, a strict design must be implemented both in organizational structure and in route summarization.
Summarizing all the above points, in order for a network designer to make EIGRP convergence quicker he must:
- Implement shorter timers. In this way, routers can form relationships faster and detect dead neighbors more efficiently.
- Provide Route Summarization through the hierarchical structure of the network. In this way, when a query arrives at an EIGRP router which features a summarized route, he immediately replies to this query, thus terminating quicker the stuck-in-active situation.
- Configure route filtering, so that a router will immediately respond to an EIGRP query with an inaccessible message reply, terminating again the SIA and helping in removing a non-existing route from all routing tables.
- Configure stub routers in remote locations so that central routers not require forward any queries to these.