Route My World!

Enhanced Interior Gateway Protocol (EIGRP):

• Is a Cisco-proprietary protocol. It combines the best of link-state and distance vector routing protocols.
• Has its roots as a distance vector routing protocol but adds several link-state features such as dynamic neighbor discovery.
• Is easy to configure.
• Unlike IGRP, it has takes advantage of rapid convergence and guarantee a loop-free topology at all times.

Some of its features include:

• Fast Convergence
  • It uses the Diffusing Update Algorithm (DUAL) for rapid convergence
  • It stores a copy of its neighbors routing table and uses those information to act quickly in case the primary route fails
  • If there is no backup route in the routing table, EIGRP will send a query to its neighbors to find an alternate route. Queries will continue to be sent until a route is found, or it decides that there is no other routes that exists.
• Support Variable-length Subnet Masking
  • It advertises a subnet mask for each destination.
  • Supports discontiguous networks.
• Partial Updates
  • Instead of sending a complete update of the routes, partial updates are sent only when something changes. And it only sends information about the link that changes and not the whole routing table.
  • This allows EIGRP to consume less bandwidth and CPU.
  • Contrary to this behavior, link-state protocols send updates to all router within an area.
• Multiple Network Layer Support
  • EIGRP Supports IP, Appletalk, and IPX.
  • Each network layer uses its own protocol-dependent module to enable support for each.
• Works across all Data-link layer protocols and topologies
  • Unlike OSPF, it does not require special configuration to work across any Layer 2 protocols.
  • Works effectively on both LAN and WAN environments.
  • Supports all WAN topologies
    • dedicated links
    • point-to-point links
    • Non-broadcast multiaccess (NBMA) topoplogies
  • Reliable multicasting is used to form neighbor relationship in multiaccess topologies such as Ethernet
• Sophistacated Metric
  • Allows for unequal metric load balancing - an advantage over IGRP.
  • Unlike IGRP’s 24-bit format, EIGRP’s metric calculation uses 32-bit format (IGRP metric multiplied by 256)
• Use of Multicast and Unicast
  • Instead of broadcast, unicasts and multicast can avoid sending update and queries to user end stations.
  • EIGRP uses multicast address 224.0.0.10

• EIGRP routing information is delivered using IP packets with protocol number 88 in the IP header.
• EIGRP routing process is a transport layer function of the OSI reference model(?)
• Defaults to use automatic route summarization. Manual route summarization can be configured instead.
• Support creation of supernets and aggregated blocks of addresses.
• Supports both hierarchical and non-hierarchical IP addressing.

Underlying Process and Technologies

EIGRP uses four underlying technologies to define its operation:

1. Neighbor Discovery/Recovery Mechanism
   • Allows routers to discover other EIGRP enabled neighbor routers that are directly connected to each other.
   • With the use of low-overhead and periodic hello messages, each routers are able to discover when neighboring routers become unreachable or inoperative.
   • As long as hello messages are received, neighbors assume that each neighbor is functioning and they can exchange routing info.
2. Reliable Transport Protocol
   • RTP is responsible for making sure that EIGRP packets are guaranteed to be delivered. It also controls the correct order by which they are delivered.
   • Allows routers to transmit mixed multicast and unicast packets.
   • To allow for efficiency in transmission, only certain packets are transmitted reliably.
     • For example, a multicast transmission through Ethernet does not require a reliable transmission of packets to all neighbors individually. So EIGRP sends a multicast hello packet but indicating on the packet that the receiver need not acknowledge receipt.
     • Other types of packets, such as updates, do need acknowledge that they are receive, so EIGRP sends the packets containing an indicator letting the recipient know that it needs to be acknowledged.
   • RTP allows for sending packets quickly even when unacknowledged packets are pending. This helps with fast convergence time.
3. DUAL finite-state machine
   • DUAL is the mechanism that makes the decision for all route computations.
   • It tracks all the routes advertised by all the neighbors and uses distance information (metric or cost) to find the most efficient and loop-free route to a destination.
4. Protocol-dependent Modules
   • Responsible for supporting the use of IP, AppleTalk, IPX for specific Network Layer implementations of EIGRP.
   • Each of the above mentioned Network layer protocols has its own EIGRP module and operates independently of each other.
   • For example, IP EIGRP is responsible for handling EIGRP packets encapsulated in IP while at the same time IPX-EIGRP handles packets for IPX. IP-EIGRP parses EIGRP packets and informs DUAL of the new information that was received. DUAL makes routing decisions that is stored in the IP routing table. IP-EIGRP also redistributes routes learned by other IP routing protocols.

EIGRP Terminology and Operation

• Neighbor Table
  • Stores information for new neighbors including the:
    • Neighbors address
    • The interface through which that neighbor can be reach.
  • Comparable to the neighbor database used by link-state routing protocols.
  • Similar to the link-state protocols, it ensures bi-directional communication between directly connected neighbors.
  • A separate neighbor table is created for different network protocols. Example:
    • IP neighbor table
    • IPX neighbor table
    • AppleTalk neighbor table
• Topology Table
  • Each neighbor routers sends to each other updates about routes each routers know about. These updates are stored in the topology table.
  • In other words, each router stores its neighbor’s routing tables in its EIGRP topology table.
  • The rule followed by all distance vector protocols is that if a neighbor is advertising a destination, use that route to forward packets.
  • Each network protocol has its own topology table (IP, IPX, AppleTalk)
• Routing Table
  • Holds the best routes to each destination and is used for forwarding packets.
  • The best route (known as successor) is presented to the routing table to be used for forwarding packets
  • If there are different routing sources involved and more than one route is found, the administrative distance is used to determine which route goes on the routing table.
  • by default, a total of 4 routes to the same destination with the same metric can be added to the routing table. The router can be configured to take up to 16 routes per destination.
  • Each network protocol has its own routing table as well.
• Feasible Distance
  • The lowest cost distance from this router to the destination.
  • This is the cost between this router (the local router) to the destination.
  • The sum of the cost between this router (the local router) and the next-hop router plus the cost between the next-hop router and the destination (advertised distance) is the feasible distance.
• Advertised Distance (aka Reported Distance)
  
  • Distance to a specific destination as advertised or reported by its neighbor
  • The cost between the next-hop router and the destination
• Successor
  • The route for a particular subnet with the best metric.
  • It is the neighboring router that has the lowest-cost path to a destination - which also means it has the lowest FD.
  • You can have multiple successors if they have the same FD.
• Feasible Successor
  • A next-hop router that serves as backup to the current successor.
  • The condition is that the said router’s AD (or RD) is less than the FD of the current successor route.
  • Once the feasible successor is selected, they are placed in the topology table. If a change in topology occurs which requires a new route, DUAL looks for the feasible successor and uses it as new route.
  • If no feasible successor exists, DUAL recomputes to find a new successor.

Populating EIGRP Tables

Neighbor Tables

• Contains lists of directly connected routers running EIGRP with which the router has an adjacency.
• The list includes the address of each neighbor and the outgoing interface of the local router to reach that neighbor.
• The neighbor-table entry also includes other information used by RTP:
  • In order to match acknowledgement with data packets for reliable transmission, sequence numbers are used. The last sequence number received from a neighbor is recorded to detect out-of-order packets.
  • A transmission list is used to queue packets for possible retransmission on a per-neighbor basis.
  • Round-trip timers are kept in the neighbor-table entry to estimate an optimal retransmission interval.

Topology Table

• Contains list of all routes learned from each EIGRP neighbor.
• Each neighbor sends a copy of its IP routing table to their connected neighbors. Once received, each router will story these tables on their respective EIGRP topology table.
• These topology tables maintain the metrics advertised by the neighbors (the AD/RD) as well as its own metric to reach the destination via these next-hop neighbors (their FD).
• To display all the IP entries in the topology table use the command:
  • sh ip eigrp topology all-links
• To display on the successor(s) and the feasible successor(s), use the command:
  • sh ip eigrp topology
• Updates occur when a directly connected route or interfaces changes, due to a failure or others, or when a neighboring router reports a change to a route.
• There are two states for a topology table entry:
  • Passive - a state when there is no computation being performed by the router. This considered a stable state.
  • Active - occurs when there is a change in the topology and the router needs to perform a recalculation (looking for a new successor, for instance.)
    • With the availability of a feasible successor, a destination never has to go into the active state.
    • Recomputation occurs in the event a successor goes down and there is no available feasible successor.
    • The recomputation starts by sending a query packet to each neighboring routers. The neighboring router sends a reply with a route to the destination. If a route does not exist another query packet is sent. At this instant the route in the neighboring router remains in active state. During this state the router cannot change the routing table information for the destination cannot change. Once all neighbors have sent back a reply packet, the topology table entry for the destination returns to the passive state.
    • Each router then examines its EIGRP topology table and determines the best route and feasible routes to every destination in the network.

IP Routing Table

• List of all best routes from EIGRP topology table and other routing processes.
• When a router examines the topology table, the router compares all the FDs to reach each destinations and selects the lowest FD for those destination and places the route in the IP routing table.

EIGRP Packets

• Hello
  • Used for neighbor discovery.
  • Sent as multicast using address 224.0.0.10
  • Do not require acknowledgment. They carry an acknowledgment number of 0.
• Update
  • Contain route change information.
  • Sent to communicate the routes that a particular router has used to converge.
  • Only sent to affected routers.
  • Updates are sent as multicast by routers after they have discovered a new route and have converged (when the route becomes passive).
  • During the EIGRP startup sequence, updates are sent to the neighbors as unicasts to synchronize their topology tables.
  • Updates are sent reliably.
• Query
  • A query packet is sent to neighbors when a router performs route computation and it does not find a feasible successor.
  • Normally sent as multicast but can be retransmitted as unicast packets in certain cases.
  • Query packets are sent reliably
• Reply
  • Sent in response to a query packet.
  • Sent as unicast back to the router that sent the query.
  • Sent reliably
• ACK
  • Used to acknowledge updates, queries, and replies.
  • They are unicast hello packets.
  • Contain a nonzero acknowledgment number.
  • Does not require acknowldgement.

EIGRP Hello Packets

• EIGRP routers discover other EIGRP routers connected to it through the hello protocol. EIGRP is configured on interfaces on routers and hello packets are sent out through these interfaces addressed to multicast destination of 224.0.0.10. If a router receives a hello packet coming from another router in the same autonomous system (AS), they establish a neighbor relationship (adjacency)
• By default, hello packets are sent out every 5 seconds on:
  • LAN links such as:
    • Ethernet
    • Token Ring
    • FDDI
  • WAN links such as:
    • point-to-point links such as PPP
    • HDLC
    • Frame Relay
    • ATM
  • Multipoint circuits with bandwidth greater than T1
    • ISDN
    • PRI
    • ATM
    • Frame Relay
• On slower interfaces (T1 or less), hello packets are sent out every 60 seconds:
  • ISDN BRI
  • Frame Relay
  • ATM
  • X.25
• The hello interval can be adjusted on a per-interface basis, to change the rate at which hello packets are sent. To change, use the interface subcommand:
  • ip hello-interval eigrp as-number seconds
• Hold-Time interval is the amount of time a router considers a neighbor up or alive without receiving a hello or some other EIGRP packet from that neighbor.
  • The hold time interval is set to 3 times the hello interval.
    • 15 seconds for LAN and fast WAN
    • 180 seconds on slower WAN
  • To adjust the hold time, use the interface subcommand:
    • ip hold-time eigrp as-number seconds
• If the hold time expires without receiving a packet from the neighbor, the adjacency is deleted and all topology entries learned from that router are removed.

EIGRP Neighbors

• The hello and hold-timers don’t have to match for two routers to establish adjacency. Therefore, hello interval and hold-time values can be set independently on different routers.
• In order to solve some addressing issues, secondary addressing can be applied on interfaces. However, because EIGRP traffic uses the interface’s primary address, EIGRP will not build adjacency over secondary addresses. EIGRP packets use the primary IP address of all neighbor routers as their source IP address.
  • In order to form adjacency, the routers’ primary IP addresses must be in the same subnet
  • Additionaly, they must reside in the same autonomous system.
  • Also, their K values (metric-calculation mechanism constants) must match.

Neighbor Table

• Information on the routing tables are built using the information gathered from the hello packets received from neighbors
• The command sh ip eigrp neighbor displays the content of the IP neighbor table.
• The elements on the neighbor table includes:

Router# show ip eigrp neighbors
P-EIGRP Neighbors for process 77

Address          Interface    Holdtime Uptime   Q      Seq  SRTT  RTO

                              (secs)   (h:m:s)  Count  Num  (ms)  (ms)
172.16.80.31     Ethernet0     12       0:02:02  0      4    5     20

172.16.81.28     Ethernet1     13       0:00:41  0      11   4     20

172.16.80.28     Ethernet0     14       0:02:01  0      10   12    24

EIGRP Reliability

• RTP ensures and guarantees an ordered delivery of EIGRP packets to all neighbors. It supports transmission of multicast and unicast packets. To maximize efficiency, only certain packets are transmitted reliably
• Reliable Packets
  • Update packets
  • Query packets
  • Reply packets
  • These packets contain routing information and are are sent reliably - because they don’t go out on a periodic basis.
  • A sequence number is assigned to each packet and an acknowledgment is required for that sequence number.
• RTO Timer
  • Each neighbor maintains a retransmission list that indicates packets not yet acknowledged by a neighbor within the RTO.
  • If RTO expires before receiving an ACK packet, EIGRP retransmit another copy of the packet, up to a maximum of 16 times or until the hold time expires.
• On multi access media where multiple neighbors reside, there could be potential problems if one of the peers does not respond with an ack immediately. The next multicast packets are not sent until every peer have acknowledged the multicast packet the was sent earlier which causes delay on sending packets to those peers that have already sent acknowledgments. To remedy this, RTP resends the unacknowledged packets as unicasts. This allows the transmission of reliable multicast to operate without slowing downs the other neighbors.
• Multicast flow timer
  • Maximum amount of time to wait for an ACK packet before EIGRP starts sending unicast instead of multicast.
  • The RTO determines the amount of time to wait between subsequent unicasts
  • Multicast flow timer and RTO are calculated based on the SRTT.
• Sometimes, the average hold time of 15 seconds (on high speed links) or 180 seconds (on slow speed links) wait time is too slow to wait before determining a neighbor adjacency to be down. Other conditions can override the hold time can be overridden and allows the network to converge much quicker.
  • For example, a slow WAN link to a remote site whose router is flapping and timing out constantly, the hold timers begin counting down from 180 seconds. When the main site sends an update to the remote site and the remote site does not send an acknowledgment, the main router tries to retransmit the update 16 times - sending one update every time the RTO expires up to 16 times. After the 16th attempt, the router resets the neighbor adjancency. This allows faster convergence of the network instead of waiting for the hold time to expire - 16 RTO times could be a matter of milliseconds compared to 180 seconds hold time.

Initial Router Discovery

Consider two routers (Router A & Router B). Router A just comes up on the link with EIGRP configured:

1. Router A sends a Hello packet out all interfaces configured for EIGRP
2. Router B receives the Hello packet from its interface connected to A. B responds by sending an Update packet back to A, containing the routes B has in its routing table. The one exception is that B does not send routing information that it learned through its interface with Router A. Router B also send a Hello back to Router A, at which point a neighborhood adjacency is formed.
3. Router A sends an acknowledgment (ACK packet) back to Router B to let it know that it received all updates.
4. Router A adds the information to its topology table where all other destinations learned from other routers are stored. Each destination lists all neighbors that can get to that destination along with their respective metrics.
5. Router A then sends an update packet to Router B.
6. Router B sends back an ACK.
7. At this point Router A and Router B calculates their successor and feasible successor routes in the topology table and offers the successor to the routing table. The feasible successor stays in the topology table where it waits until it is needed.

Split Horizon

• In its basic premise, split horizon prevents a router from advertising a route out of the interface through which that route was learned.
• Consider the following scenario:
  

• R1 is the hub router and R2 & R3 are the spokes connected to a single multipoint interface on R1 (frame relay)
• In this scenario, EIGRP is used to advertise the networks on each routers.
• However, split horizon is enabled by default on EIGRP therefore R1 will not be able to advertise the network 2.2.2.2 it learned from R2 to router R3. Likewise, R1 cannot advertise to R2 the network 3.3.3.3 that it learned from R3.
• Because R1 learned each of the networks through its interface connecting to R2 and R3, it cannot re-advertise those learned networks back the same single interface.

Route Selection

• A distinguish factor in the EIGRP route selection that is different from other routing protocols is its selection of a primary (successor) and backup (feasible successor) routes. EIGRP calculates a successor and feasible successor and puts them into the topology table. It then takes the success route information and offers it up to the IP routing table.
• EIGRP route types:
  • Internal - routes that originate withing the EIGRP autonomous system
  • External - routes learned from another routing protocol or another EIGRP AS.
  • Summary - routes that encompass multiple subnets.
• DUAL calculates the best route to a destination. To select the best route, it adds up the FD and AD of the neighbor route and the least-cost route is the route that is injected into the routing table. DUAL also makes sure that the path is loop-free. DUAL also calculates the feasible successor route and makes sure it too is loop-free.

Metric Calculation

There are 5 variables that can be used to calculate the EIGRP metric, but it only uses the first two by default:

• Bandwidth - the slowest bandwidth between the source and destination
• Delay - cumulative delay (add all delay values of each routers) along the path.
  

The next 3 are rarely used for calculation because they either result in more calculation or the default values results in them not being used:

• Reliability - the worst reliability between the source and destination, based on keepalives.
• Loading - the worst load on a link between the source and destination based on the packet rate and the interface’s configured bandwidth.
• Maximum transmission unit (MTU) - the smallest MTU in the path.

In addition the the variables mentioned above, the metric calculations for EIGRP factor in some constant weight values. They are:

• K1 = 1
• K2 = 0
• K3 = 1
• K4 = 0
• K5 = 0

The formula is:

Because of the default values of of the K values, the metric above ends up being:

metric = [(1 x bandwidth) + [(0 x bandwidth) / (256-load)] + 1 x delay] x [0/ 0+reliability] x 256
metric = bandwidth + [0] + delay x [0] x 256
metric = bandwidth + delay

• K values are included in the hello packets.
• In order for routers to form neighbor relationship, the K values must match
• Modifying these values is generally not recommended.

Delay and Bandwidth Values

• Delay values are calculated in units of tens of microseconds and is the sum of all delays in the path multiplied by 256.
  • show interfaces command displays delay values in microseconds (vs. tens of microseconds)
• The bandwidth value is calculated using the minimum bandwidth link in the unit of kbps. The formula is (10⁷ / least-bandwidth) x 256
• EIGRP and IGRP
  • EIGRP uses a 32-bit format while IGRP uses 24-bit in representing its metrics.
  • Basically, they both have the same formula, but when integrating IGRP routes into an EIGRP domain using redistribution, the router multiplies IGRP metric by 256 to get the EIGRP-equivalent metric. Inversely, when redistributing EIGRP routes to IGRP routing domain, the router divides each EIGRP metric by 256 to get the proper 24-bit metric.

Routing Table and EIGRP DUAL

• Diffusing Update Algorithm DUAL
  • is the mechanism that decides what information goes in the topology and routing table.
  • process behind route computation
  • tracks all routes advertised by all neighbors
  • uses the metric to select an efficient, loop-free path to each destination, and inserts the choice in the routing table.
• Advertised Distance and Feasible Distance
  • The Advertised Distance (aka Reported Distance) is the neighbor router’s metric to reach a particular destination network. This metric is advertised/reported to their neighbor routers letting them know how far the destination from their perspective. This is the metric between the next-hop router and the destination network
  • The Feasible Distance FD is the metric of the this router to reach a particular network. To get the FD, add the AD/RD of the next-hop router and the EIGRP metric to reach that next-hop router (the cost between this router and the next-hop router)
  • It is important to remember that the FD, not the AD, affects the selection of the best route. The AD is merely a component that is part of the calculation of the FD.
• The Successor Route is the route to the destination network that cost the least. The router inspects all the FDs in its topology table. The least-cost FD to reach a destination network is selected by the router to be placed in the routing table to be used as the successor route to the destination network. The FD of the chosen route also becomes the EIGRP routing metric in the routing table.
• Successor
  • This is the next-hop router that has the least-cost path (the best path) to the destination.
  • It has the lowest FD of all possible paths to the destination.
  • When the router chooses the best path to a destination, it adds the following details to the IP routing table:
  • • The destination network
    • The metric to reach that network
    • The outbound interface to reach the next-hop router
    • The IP of the next-hop router
  • By default, up to four successors can be added to the IP routing table. This can occur if as many entries that have equal-cost FD exist in the topology table.
• The routing table is basically a subset of the topology table. There is more information in the topology table, which includes:
  • Detailed information about each route.
  • Any backup routes.
  • Information used exclusively by DUAL
• Feasible Successor (FS)
  • The router that act as the backup route.
  • They are selected at the same time the successors are identified.
  • They are kept in the topology table.
  • There can be multiple FS routes in a topology table.
  • Requirements to be a feasible successor:
    • Must be mathematically proven
    • The next-hop router must have an AD less than the FD of the current successor route for that network.
  • If a router loses a route, the router looks for an FS in the topology table. If the FS exists, that router is promoted to a successor and added to the routing table. The router never goes into an active state because there is no calculation necessary and the change is immediate.
  • If there is no available FS, the router has to recalculate to find the best route. This is when the router goes into active state.

Resources:

1. Internetworking Technology Handbook - EIGRP
2. EIGRP Technology White Paper
3. Cisco IOS IP Routing Protocols Command Reference - EIGRP commands
4. The EIGRP Neighbor Discovery Process
5. EIGRP and Split Horizon - Chris Bryant
6. EIGRP FAQ - Split horizon
7. EIGRP - Wikipedia
8. EIGRP DUAL Queries, SIA and Stub Routers - Chris Bryant