Enhanced Interior Gateway Routing Protocol
In early 1995 Cisco released version 10 of the Cisco Internetwork Operating System (IOS) software for their bridge/router product line. In this new version, Cisco implemented a new version of the Interior Gateway Routing Protocol (IGRP) called the Enhanced Interior Gateway Routing Protocol (EIGRP). Virtually all of the features implemented by IGRP can be found in EIGRP. Like IGRP, EIGRP is classified as a distance vector routing protocol. It uses a composite metric to calculate routes, and the routing information propagated from neighbor to neighbor is a routing vector that includes delay, load, and reliability information. This allows for an improved architecture while retaining existing investment in IGRP.
EIGRP differs from its predecessor in two major areas. First, EIGRP does not transmit routing updates on a 90 second clock. A new EIGRP router will receive full routing tables from its neighbors when first communicating with those neighbors.
Thereafter, only routing table changes are transmitted when a change in the network causes a router to alter the information stored in its routing table. This can eliminate a significant amount of traffic in a stable internetwork. However, EIGRP does not completely eliminate periodic messages. EIGRP requires a router to transmit hello messages to its neighbors on a periodic basis. Although these messages are periodic, they are also very small and consume relatively little bandwidth. Their purpose is to allow routers to monitor the health of their neighbors (i.e., other routers with which they share the same subnetwork). These two procedures, sending Hello messages and event-driven partial updates, operate similarly to link-state protocols.
The second major distinction between EIGRP and IGRP is the range of Network Layer protocols it can route. EIGRP has been extended so as to support multiple Network Layer protocols, thereby allowing DUAL to support other protocol suites, namely Internet Protocol (IP), Internetwork Packet Exchange (IPX), and Datagram Delivery Protocol (DDP). IGRP can only be used to route IP traffic. EIGRP can route IP as well, but can also be used to route IPX and DDP traffic. This makes EIGRP one of the most flexible routing protocols in the market.
EIGRP has four basic components. First, neighbor discovery/recovery is the process that routers use to dynamically learn of other routers on their directly attached networks. Routers must also discover when their neighbors become unreachable or inoperative. This process is achieved with low overhead by periodically sending small Hello packets. As long as Hello packets are received, a router can determine that a neighbor is alive and functioning; the neighboring routers can then exchange routing information.
Second, the reliable transport is responsible for guaranteed, sequential delivery of EIGRP packets to all neighbors. It supports an intermixed transmission of multicast or unicast packets. Some EIGRP packets must be transmitted reliably and others need not. For efficiency, reliability is provided only when necessary. For example, on a multiaccess network that has multicast capabilities, such as Ethernet, it is not necessary to send Hellos reliably to each individual neighbor. Instead, EIGRP sends a single multicast Hello with an indication that the packet need not be acknowledged. Updates, on the other hand, do require acknowledgment and is thus indicated in the packet. The reliable transport has a provision to send multicast packets quickly when there are unacknowledged packets pending. This helps ensure that convergence time remains low in the presence of varying speed links.
Third, the diffusing update algorithm (DUAL) finite state machine embodies the decision process for all route computations. It tracks all routes advertised by all neighbors. The distance information, known as a metric, is used by DUAL to select efficient, loop-free paths. DUAL selects routes to be inserted into a routing table based on feasible successors. A successor is a neighboring router used for packet forwarding that has a least cost path to a destination that is guaranteed not to be part of a routing loop. When there are no feasible successors but there are neighbors advertising the destination, a recomputation of a new successor must occur. The amount of time it takes to recompute the successor affects the convergence time. Even though the recomputation is not processor-intensive, it is advantageous to avoid recomputation if it is not necessary. When a topology change occurs, DUAL tests for feasible successors. If a feasible successor exists, recomputation is avoided.
The convergence properties and the operating efficiency of EIGRP has improved significantly over IGRP. The DUAL is the algorithm used to obtain loop freedom at every instant throughout a route computation. This enables all routers involved in a topology change to synchronize at the same time. Routers that are not affected by topology changes are not involved in the recomputation. The convergence time with DUAL rivals that of any other existing routing protocol.
Protocol-dependent modules are responsible for Network Layer, protocol-specific requirements. For example, the IP-EIGRP module is responsible for sending and receiving EIGRP packets that are encapsulated in IP. IP-EIGRP is responsible for parsing EIGRP packets and informing DUAL of the new information received. IP-EIGRP asks DUAL to make routing decisions, the results of which are stored in the IP routing table. IP-EIGRP is also responsible for redistributing routes learned by other IP routing protocols.
Lastly, EIGRP supports variable length subnet masks (VLSM) by carrying network mask information in routing updates. This is most useful when creating networks to support a varying number of hosts.
Each router keeps information about adjacent neighbors. When newly discovered neighbors are learned, the address and interface of the neighbor are recorded in the neighbor data structure. The “neighbor table” holds these entries—and there is one neighbor table for each protocol-dependent module. When a neighbor sends a Hello message, it advertises a Hold Time. The Hold Time is the amount of time a router treats a neighbor as reachable and operational. In other words, if a Hello packet isn’t heard within the Hold Time, the neighbor is considered unreachable, and DUAL is informed of the change.
The neighbor table entry also includes information required by the reliable transport mechanism. Sequence numbers are employed to match acknowledgments with data packets. The last sequence number received from the neighbor is recorded so out-of-order packets can be detected. A transmission list is used to queue packets for possible retransmission on a per neighbor basis. Round-trip timers are kept in the neighbor data structure to estimate an optimal retransmission interval.
The “topology table” is populated by the protocol-dependent modules and acted upon by the DUAL finite state machine. It contains all destinations advertised by neighboring routers. Associated with each entry is the destination address and a list of neighbors that have advertised the destination. For each neighbor, the advertised metric is recorded. This is the metric that the neighbor stores in its routing table. Also associated with the destination is the metric that the router uses to reach the destination. This is the sum of the best advertised metric from all neighbors plus the link cost to the best neighbor.
A destination entry is moved from the topology table to the routing table when it is considered a successor. A successor is a neighboring router that has the least cost to route to a destination. The successor is what is currently being used to reach a destination. Feasible successors are neighbors that provide the next loop-free, least cost path to a destination. All minimum cost paths to the destination form a set. From this set, the neighbors that have an advertised metric less than the current routing table metric are considered feasible successors. Feasible successors are viewed by a router as neighbors that are downstream with respect to the destination. These neighbors and the associated metrics are placed in the routing table.
When there are no feasible successors, a route goes into active state and a route recomputation occurs. A route recomputation commences with a router sending a Query packet to all neighbors. Neighboring routers can either reply, if they have feasible successors for the destination, or return a Query indicating that they are performing a route recomputation. While in active state, a router cannot change the next-hop neighbor it is using to forward packets. After all replies are received for a given Query, the destination can transition to passive state and a new successor can be selected. When a link to a neighbor that is the only feasible successor goes down, all routes through that neighbor commence a route recomputation and enter the active state.
EIGRP Packet Types
EIGRP uses five packet types.
- Hello/ ACKs
Hellos are multicast for neighbor discovery/recovery. They do not require acknowledgment. A Hello with no data is also used as an acknowledgment (ACK). ACKs are always sent using a unicast address and contain a nonzero acknowledgment number. Updates are used to convey reachability of destinations. When a new neighbor is discovered, Update packets are sent so the neighbor can build up its topology table. In this case, Update packets are unicast. In other cases, such as a link cost change, Updates are multicast. Updates are always transmitted reliably.
Queries and Replies are sent when destinations go into active state. Queries are always multicast unless they are sent in response to a received Query. In this case, it is unicast back to the successor that originated the Query. Replies are always sent in response to Queries to indicate to the originator that it does not need to go into active state because it has feasible successors. Replies are unicast to the originator of the Query. Both Queries and Replies are transmitted reliably. Request packets are used to get specific information from one or more neighbors. Request packets are used in route server applications. They can be multicast or unicast. Requests are transmitted unreliably.
These packets are duplicated for each Network Layer protocol EIGRP is providing routing services for. So EIGRP does not create efficiencies by having only one set of updates and hellos, it has one set per protocol.
The benefit of EIGRP is that it replaces the existing legacy Distance vector routing protocols used by IP, IPX, and DDP and improves the convergence time and efficiencies of supporting that protocol in the network.
|<mp3>http://podcast.hill-vt.com/podsnacks/2007q2/eigrp.mp3%7Cdownload</mp3> | Enhanced Interior Gateway Routing Protocol (EIGRP)|