Enhanced Interior Gateway Routing Protocol

From Wikipedia, the free encyclopedia

You have new messages (last change).

Enhanced Interior Gateway Routing Protocol (EIGRP) is a Cisco proprietary routing protocol loosely based on their original IGRP. EIGRP is an advanced distance-vector routing protocol, with optimizations to minimize both the routing instability incurred after topology changes, as well as the use of bandwidth and processing power in the router.

Most of the routing optimizations are based on the Diffusing Update Algorithm (DUAL) work from SRI, which guarantees loop-free operation. In particular, DUAL avoids the "count to infinity" behaviour common in distance-vector routing protocols when a destination becomes completely unreachable. The maximum hop count of EIGRP-advertised routes (i.e. destination networks) is 220. EIGRP has a lower maximum hop count than IGRP, 220 for EIGRP and 255 for IGRP.

Contents

[edit] Basic operation

The data EIGRP collects is stored in three tables:

  • Neighbor Table: Stores data about the neighbouring routers, i.e. those directly accessible through directly connected interfaces.
  • Topology Table: Confusingly named, this table does not store an overview of the complete network topology; rather, it effectively contains the aggregation of the routing tables gathered from all the neighbours. This table contains a list of destination networks in the EIGRP-routed network together with their respective metrics. Also for every destination, a successor and a feasible successor are identified and stored in the table if they exist. Every destination in the topology table can be marked either as "Passive", which is the state when the routing has stabilized and the router knows the route to the destination, or "Active" when the topology has changed and the router is in the process of (actively) updating its route to that destination.
  • Routing table: Stores the actual routes to all destinations; the routing table is populated from the topology table with every destination network that has its successor and optionally feasible successor identified (if unequal-cost load-balancing is enabled using the variance command). The successors and feasible successors serve as the next hop routers for these destinations

[edit] Multiple metrics

EIGRP associates five different metrics with each route:

  • Total Delay (in microseconds)
  • Minimum Bandwidth (in kilobits per second)
  • Reliability (number in range <1, 255>, 255 being most reliable)
  • Load (number in range <1, 255>, 255 being saturated)
  • Minimum MTU (though not actually used in the calculation)

For the purposes of comparing routes, these are combined together in a weighted formula to produce a single overall metric:

\bigg [ \bigg ( K_1 \cdot \text{Bandwidth} + \frac{K_2 \cdot \text{Bandwidth}}{256-\text{Load}} + K_3 \cdot \text{Delay} \bigg ) \cdot \frac {K_5}{K_4 + \text{Reliability}} \bigg ] \cdot 256

where the various constants (K1 through K5) can be set by the user to produce varying behaviours. An important and totally non-obvious fact is that if K5 is set to zero, the term \tfrac {K_5}{K_4 + \text{Reliability}} is not used (i.e. taken as 1).

The default is for K1 and K3 to be set to 1, and the rest to zero, effectively reducing the above formula to (Bandwidth + Delay) * 256.

Obviously, these constants must be set to the same value on all routers in an EIGRP system, or permanent routing loops will probably result. Cisco routers running EIGRP will not form an EIGRP adjacency and will complain about K-values mismatch until these values are identical on these routers.

EIGRP scales Bandwidth and Delay metrics with following calculations:

Bandwidth for EIGRP = 107 / Interface Bandwidth
Delay for EIGRP = Interface Delay / 10

On Cisco routers, the interface bandwidth is a configurable static parameter expressed in kilobits per second. Dividing a value of 107 Kbps (i.e. 10 Gbps) by the interface bandwidth yields a value that is used in the weighted formula. Analogously, the interface delay is a configurable static parameter expressed in units of tens of microseconds. Dividing this interface delay value by 10 yields a delay in units of microseconds that is used in the weighted formula.

IGRP uses the same basic formula for computing the overall metric, the only difference is that in IGRP, the formula does not contain the scaling factor of 256. In fact, this scaling factor was introduced as a simple means to facilitate backward compatility between EIGRP and IGRP: In IGRP, the overall metric is a 24-bit value while EIGRP uses a 32-bit value to express this metric. By multiplying a 24-bit value with the factor of 256 (effectively bit-shifting it 8 bits to the left), the value is extended into 32 bits, and vice versa. This way, redistributing information between EIGRP and IGRP involves simply dividing or multiplying the metric value by a factor of 256 which is done automatically.

EIGRP also maintains a hop count for every route, however, the hop count is not used in metric calculation. It is only verified against a predefined maximum on an EIGRP router (by default it is set to 100 and can be changed to any value between 1 and 220). Routes having a hop count higher than the maximum will be advertised as unreachable by an EIGRP router.

[edit] Successor

A successor for a particular destination is a next hop router that satisfies these two conditions:

  • it provides the least distance to that destination
  • it is guaranteed not to be a part of some routing loop

The first condition can be satisfied by comparing metrics from all neighboring routers that advertise that particular destination, increasing the metrics by the cost of the link to that respective neighbor, and selecting the neighbor that yields the least total distance. The second condition can be satisfied by testing a so-called Feasibility Condition for every neighbor advertising that destination. There can be multiple successors for a destination, depending on the actual topology.

The successors for a destination are recorded in the topology table and afterwards they are used to populate the routing table as next-hops for that destination.

[edit] Feasible Successor

A feasible successor for a particular destination is a next hop router that satisfies this condition:

This condition is also verified by testing the Feasibility Condition.

Thus, every successor is also a feasible successor. However, in most references about EIGRP the term "feasible successor" is used to denote only those routers which provide a loop-free path but which are not successors (i.e. they do not provide the least distance). From this point of view, for a reachable destination there is always at least one successor, however, there might not be any feasible successors.

A feasible successor provides a working route to the same destination, although with a higher distance. At any time, a router can send a packet to a destination marked "Passive" through any of its successors or feasible successors without alerting them in the first place, and this packet will be delivered properly. Feasible successors are also recorded in the topology table.

The feasible successor effectively provides a backup route in the case that existing successors die. Also, when performing unequal-load balancing (balancing the network traffic in inverse proportion to the cost of the routes), the feasible successors are used as next hops in the routing table for the load-balanced destination.

By default, the total count of successors and feasible successors for a destination stored in the routing table is limited to four. This limit can be changed in the range from 1 to 6.

[edit] Active and Passive State

A destination in the topology table can be marked either as Passive or Active. A Passive state is a state when the router has identified the successor(s) for the destination. The destination changes to Active state when current successor no longer satisfies the Feasibility Condition and there are no feasible successors identified for that destination (i.e. no backup routes are available). The destination changes back from Active to Passive when the router received replies to all queries it has sent to its neighbors. Notice that if a successor stops satisfying the Feasibility Condition but there is at least one feasible successor available, the router will promote a feasible successor with the lowest total distance (the distance as reported by the feasible successor plus the cost of the link to this neighbor) to a new successor and the destination remains in the Passive state.

[edit] Advertised Distance and Feasible Distance

Advertised Distance (AD) is the distance to a particular destination as reported by a router to its neighbors. This distance is sometimes also called a Reported Distance and is equal to the current lowest total distance through a successor.

A Feasible Distance (FD) is the lowest known distance from a router to a particular destination since the last time the route went from Active to Passive state. While a route remains in Passive state, then the FD is updated only if the destination decreases, otherwise it stays at its present value.

For example, if the route to a newly discovered destination X went from Active to Passive state with a total distance of 10, the router sets the AD and FD to 10. Later this distance decreases from 10 to 8. The distance remains in the Passive state (because distance decrease never violates the Feasibility Condition) and the router updates the AD and FD to 8. Even later, the distance increases to 12 but in such a way that there is still a valid successor or feasible successor available. In this case, the AD gets updated to 12, however, the FD will remain at the value of 8. Therefore, the values of AD and FD can be different.

[edit] Feasibility Condition

The feasibility condition is a sufficient condition for loop freedom in EIGRP-routed network. It is used to select the successors and feasible successors that are guaranteed to be on a loop-free route to a destination. Its simplified formulation is strikingly simple:

If, for a destination, a neighbor router advertises a distance that is strictly lower than our feasible distance, then this neighbor lies on a loop-free route to this destination.

In other words, every neighbor that satisfies the relation AD < FD for a particular destination is on a loop-free route to that destination.

This condition is also called the Source Node Condition and is one of more equivalent conditions that were proposed and proven by Dr. J. J. Garcia-Luna-Aceves at SRI. The paper proposing the Source Node Condition and the Diffusing Update Algorithm algorithm itself can be found here.

It is important to realize that this condition is a sufficient, not a neccesary condition. That means that neighbors which satisfy this condition are guaranteed to be on a loop-free path, however, there may be also other neighbors on a loop-free path which do not satisfy this condition. For EIGRP purposes, this is not a problem, though.

[edit] Other details

EIGRP is able to deal with Classless Inter-Domain Routing (CIDR), allowing the use of variable-length subnet masks - one of the protocol's main advantages over its predecessor. Its main disadvantage is that it runs only on Cisco equipment, which may lead to an organization being locked in to this vendor. Also, the EIGRP is not usable in applications where routers need to know the exact network topology (for example, traffic engineering in MPLS).

EIGRP can run separate routing processes for IP, IPv6, IPX and AppleTalk. However, this does not facilitate translation between protocols.

[edit] Further reading

[edit] External links

Retrieved from "http://en.wikipedia.org../../../e/n/h/Enhanced_Interior_Gateway_Routing_Protocol_664b.html"