Throughput Calculation Latency Calculation Composite Calculation Protocol Number Protocol Assignment Encoding Destination Assignment Encoding Type Field Encoding Length Field Encoding Value Field Encoding Classic Flag Field Encoding Classic Metric Encoding Classic Exterior Encoding Classic Destination Encoding TLV Header Encoding Wide Metric Encoding Extended Metrics Exterior Encoding Destination Encoding Route Information Security Considerations IANA Considerations Normative References Informative References DUAL, the algorithm used to converge the control plane to a single set of loop-free paths is based on research conducted at SRI International [ 3 ].
The Diffusing Update Algorithm DUAL is the algorithm used to obtain loop freedom at every instant throughout a route computation [ 2 ]. This allows all routers involved in a topology change to synchronize at the same time; the routers not affected by topology changes are not involved in the recalculation. This document describes the protocol that implements these functions.
Conventions 2. Terminology The following is a list of abbreviations and terms used throughout this document: ACTIVE State: The local state of a route on a router triggered by any event that causes all neighbors providing the current least-cost path to fail the Feasibility Condition check. A route in Active state is considered unusable. During Active state, the router is actively attempting to compute the least-cost loop-free path by explicit coordination with its neighbors using Query and Reply messages.
Address Family Identifier AFI : Identity of the network-layer protocol reachability information being advertised [ 12 ]. Autonomous System AS : A collection of routers exchanging routes under the control of one or more network administrators on behalf of a single administrative entity.
Destinations exchanged within the Base Topology are identified with a Topology Identifier value of zero 0. Computed Distance CD : Total distance metric along a path from the current router to a destination network through a particular neighbor computed using that neighbor's Reported Distance RD and the cost of the link between the two routers.
CR-Mode Conditionally Received Mode Diffusing Computation: A distributed computation in which a single starting node commences the computation by delegating subtasks of the computation to its neighbors that may, in turn, recursively delegate sub-subtasks further, including a signaling scheme allowing the starting node to detect that the computation has finished while avoiding false terminations.
In DUAL, the task of coordinated updates of routing tables and resulting best path computation is performed as a diffusing computation. Diffusing Update Algorithm DUAL : A loop-free routing algorithm used with distance vectors or link states that provides a diffused computation of a routing table.
It works very well in the presence of multiple topology changes with low overhead. The technology was researched and developed at SRI International [ 3 ]. Downstream Router: A router that is one or more hops away from the router in question in the direction of the destination. Feasibility Condition: The Feasibility Condition is a sufficient condition used by a router to verify whether a neighboring router provides a loop-free path to a destination.
Being effectively a record of the smallest known metric since the last time the network entered the PASSIVE state, the FD is not necessarily a metric of the current best path.
Exactly one FD is computed per destination network. Feasible Successor: A neighboring router that meets the Feasibility Condition for a particular destination, hence, providing a guaranteed loop-free path. The ability of two routers to become neighbors depends on their mutual connectivity and compatibility of selected EIGRP configuration parameters.
Two neighbors with interfaces connected to a common subnet are known as adjacent neighbors. Two neighbors that are multiple hops apart are known as remote neighbors. Network Layer Reachability Information NLRI : Information a router uses to calculate the global routing table to make routing and forwarding decisions. Reported Distance RD : For a particular destination, the value representing the router's distance to the destination as advertised in all messages carrying routing information.
RD is not equivalent to the current distance of the router to the destination and may be different from it during the process of path re-computation. Exactly one RD is computed and maintained per destination network. Sub-Topology: For a given Base Topology, a sub-topology is characterized by an independent set of routers and links in a network for which EIGRP performs an independent path calculation.
This allows each sub- topology to implement class-specific topologies to carry class- specific traffic. Successor-Directed Acyclic Graph SDAG : For a particular destination, a graph defined by routing table contents of individual routers in the topology, such that nodes of this graph are the routers themselves and a directed edge from router X to router Y exists if and only if router Y is router X's successor.
After the network has converged, in the absence of topological changes, SDAG is a tree. Topology Identifier TID : A number that is used to mark prefixes as belonging to a specific sub-topology. Each TLV-formatted information element consists of three generic fields: Type identifying the nature of information carried in this element, Length describing the length of the entire TLV triplet, and Value carrying the actual information.
The Value field may, itself, be internally structured; this depends on the actual type of the information element. This format allows for extensibility and backward compatibility.
Upstream Router: A router that is one or more hops away from the router in question, in the direction of the source of the information. DUAL guarantees that each constructed path is loop free at every instant including periods of topology changes and network reconvergence.
This is accomplished by all routers, which are affected by a topology change, computing the new best path in a coordinated diffusing way and using the Feasibility Condition to verify prospective paths for loop freedom.
Routers that are not affected by topology changes are not involved in the recalculation. The convergence time with DUAL rivals that of any other existing routing protocol. Only nodes that are affected by a topology change need to propagate and act on information about the topology change, allowing EIGRP to have good scaling properties, reduced overhead, and lower complexity than many other interior gateway protocols.
Distributed routing algorithms are required to propagate information as well as coordinate information among all nodes in the network. Unlike basic Bellman-Ford distance vector protocols that rely on uncoordinated updates when a topology change occurs, DUAL uses a coordinated procedure to involve the affected part of the network into computing a new least-cost path, known as a "diffusing computation". A diffusing computation grows by querying additional routers for their current RD to the affected destination, and it shrinks by receiving replies from them.
Unaffected routers send replies immediately, terminating the growth of the diffusing computation over them. These intrinsic properties cause the diffusing computation to self-adjust in scope and terminate as soon as possible. One attribute of DUAL is its ability to control the point at which the diffusion of a route calculation terminates by managing the distribution of reachability information through the network.
This provides the ability to create effective failure domains within a single AS, and allows the network administrator to manage the convergence and processing characteristics of the network. Consequently, in PASSIVE state, the router does not perform any route recalculation in coordination with its neighbors because no such recalculation is needed. In ACTIVE state, the router is actively involved in re-computing the least-cost loop-free path in coordination with its neighbors. The state is reevaluated and possibly changed every time a topology change is detected.
A topology change is any event that causes the CD to the destination over any neighbor to be added, changed, or removed from EIGRP's topology table. More exactly, the two states are defined as follows: o Passive A route is considered to be in the Passive state when at least one neighbor that provides the current least-total-cost path passes the Feasibility Condition check that guarantees loop freedom.
A route in the ACTIVE state is considered unusable and this router must coordinate with its neighbors in the search for the new loop- free least-total-cost path. Feasible Successors providing the least-total-cost path are also called "successors". While these neighbors are guaranteed to provide a loop-free path, that path is potentially not the shortest available. The fact that the least-total-cost path can be provided by a neighbor that fails the Feasibility Condition check may not be intuitive.
However, such a situation can occur during topology changes when the current least-total-cost path fails and the next-least-total-cost path traverses a neighbor that is not a Feasible Successor. Feasibility Condition The Feasibility Condition is a criterion used to verify loop freedom of a particular path. The Feasibility Condition is a sufficient but not a necessary condition, meaning that every path meeting the Feasibility Condition is guaranteed to be loop free; however, not all loop-free paths meet the Feasibility Condition.
Based on the result of the Feasibility Condition check after a topology change is detected, the route may either remain PASSIVE if, after the topology change, the neighbor providing the least cost path meets the Feasibility Condition or it needs to enter the ACTIVE state if the topology change resulted in none of the neighbors providing the least cost path to meet the Feasibility Condition. Nodes that are not affected by the topology change are not required to perform a DUAL computation and may not be aware a topology change occurred.
This can occur in two cases: Savage, et al. A route that meets the Feasibility Condition is determined to be loop free and downstream along the path between the router and the destination. Second, if informed about a topology change for which it does not currently have reachability information, a router is not required to enter into the ACTIVE state, nor is it required to participate in the DUAL process.
In order to facilitate describing the Feasibility Condition, a few definitions are in order. Typically, the successor is chosen based on the least-cost path to reach the destination.
A Feasible Successor is regarded as a downstream neighbor towards the destination, but it may not be the least-cost path but could still be used for forwarding data packets in the event equal or unequal cost load sharing was active. A Feasible Successor can become a successor when the current successor becomes unreachable. It should be noted it is not necessarily the current best distance; rather, it is a historical record of the best distance known since the last diffusing computation for the destination has finished.
Thus, the value of the FD can either be the same as the current best distance, or it can be lower. A neighbor that advertises a route with a cost that does not meet the Feasibility Condition may be upstream and thus cannot be guaranteed to be the next hop for a loop-free path.
Routes advertised by upstream neighbors are not recorded in the routing table but saved in the topology table. 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. 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 recalculation must occur to determine a new successor. Even though the recalculation is not processor intensive, it is advantageous to avoid recalculation if it is not necessary. If there are Feasible Successors, it will use any it finds in order to avoid any unnecessary recalculation.
The FSM, which applies per destination in the topology table, operates independently for each destination. However, a separate SDAG is computed for each destination, so loop- free topologies can be maintained for each reachable destination.
Split horizon takes effect for a query or update from the successor it is using for the destination in the query. The route stays in ACTIVE state if there are more replies pending because the router has not heard from all neighbors. Each node is labeled with its costs to destination N. The arrows indicate the successor next hop used to reach destination N.
If a router is redistributing routes between two EIGRP autonomous systems, it replies to the query within the normal processing rules and launches a new query into the other autonomous system. For example, if the link to the network attached to Router Three goes down, Router Three marks the route unreachable and queries Router Two for a new path:.
Router Two replies that this network is unreachable and launches a query into autonomous system toward Router One. Once Router Three receives the reply to its original query, it removes the route from its table.
Router Three is now passive for this network:. While the original query did not propagate throughout the network it was bound by the autonomous system border , the original query leaks into the second autonomous system in the form of a new query.
This technique may help to prevent stuck in active SIA problems in a network by limiting the number of routers a query must pass through before being answered, but it does not solve the overall problem that each router must process the query.
In fact, this method of bounding a query may worsen the problem by preventing the auto-summarization of routes that would otherwise be summarized external routes are not summarized unless there is an external component in that major network.
Rather than block the propagation of a query, distribution lists in EIGRP mark any query reply as unreachable. Let us use Figure 19 as an example. Router Three has a distribute-list applied against its serial interfaces that only permits it to advertise Network B. When Router One loses its connection to Network A, it marks the route as unreachable and sends a query to Router Three.
Router Three does not advertise a path to Network A because of the distribution list on its serial ports. Router Two examines its topology table and finds that it has a valid connection to Network A. Note the query was not affected by the distribution list in Router Three:. Router Three builds the reply to the query from Router One, but the distribution list causes Router Three to send a reply that Network A is unreachable, even though Router Three has a valid route to Network A:.
Some routing protocols consume all of the available bandwidth on a low bandwidth link while they are converging adapting to a change in the network. EIGRP avoids this congestion by pacing the speed at which packets are transmitted on a network, thereby using only a portion of the available bandwidth.
The default configuration for EIGRP is to use up to 50 percent of the available bandwidth, but this can be changed with the following command:. Essentially, each time EIGRP queues a packet to be transmitted on an interface, it uses the following formula to determine how long to wait before sending the packet:. This allows a packet or groups of packets of at least bytes to be transmitted on this link before EIGRP sends its packet. The pacing timer determines when the packet is sent, and is typically expressed in milliseconds.
The pacing time for the packet in the above example is 0. There is a field in show ip eigrp interface that displays the pacing timer, as shown below:. The time displayed is the pacing interval for the maximum transmission unit MTU , the largest packet that can be sent over the interface. There are two ways to inject a default route into EIGRP: redistribute a static route or summarize to 0. Use the first method when you want to draw all traffic to unknown destinations to a default route at the core of the network.
This method is effective for advertising connections to the Internet. For example:. If you use another network, you must use the ip default-network command to mark the network as a default network. Summarizing to a default route is effective only when you want to provide remote sites with a default route.
Since summaries are configured per interface, you do not need to worry about using distribute-lists or other mechanisms to prevent the default route from being propagated toward the core of your network. Note that a summary to 0. The only way to configure a default route on a router using this method is to configure a static route to 0. EIGRP puts up to four routes of equal cost in the routing table, which the router then load-balances.
The type of load balancing per packet or per destination depends on the type of switching being done in the router. EIGRP, however, can also load-balance over unequal cost links. The router, by default, places traffic on both path 1 and 2.
Using EIGRP, you can use the variance command to instruct the router to also place traffic on paths 3 and 4. The variance is a multiplier: traffic will be placed on any link that has a metric less than the best path multiplied by the variance. Similarly, to also add path 4, issue variance 4 under the router eigrp command. How does the router divide the traffic between these paths? It divides the metric through each path into the largest metric, rounds down to the nearest integer, and uses this number as the traffic share count.
The router sends the first three packets over path 1, the next three packets over path 2, the next two packets over path 3, and the next packet over path 4. The router then restarts by sending the next three packets over path 1, and so on. Note: Even with variance configured, EIGRP will not send traffic over an unequal cost path if the reported distance is greater than the feasible distance for that particular route. The bandwidth should always be set to the real bandwidth of the interface; multipoint serial links and other mismatched media speed situations are the exceptions to this rule.
Because EIGRP uses the interface bandwidth to determine the rate at which to send packets, it is important that these be set correctly.
At lower bandwidths, the bandwidth has more influence over the total metric; at higher bandwidths, the delay has more influence over the total metric. External administrative tags are useful for breaking redistribution routing loops between EIGRP and other protocols. It is not possible to modify the administrative distance for a default gateway that was learned from an external route because, in EIGRP, the modification of the administrative distance only applies for internal routes.
In order to raise the metric, use a route-map with prefix-list; do not change the administrative distance. A basic example of configuring these tags follows, but this example does not show the entire configuration used for breaking redistribution loops. The output of this command shows the information that has been exchanged between the neighboring EIGRP router. An explanation of each output field follows the table. This command only displays feasible successors.
To display all entries in the topology table, use the show ip eigrp topology all-links command. FD is shows the feasible distance, which is the best metric to reach this destination or the best metric known when the route went active.
Q means a query is pending. This field can also be: U, for update pending; or R, for reply pending. This field can also be: Multiple origins, meaning that multiple neighbors have sent queries on this destination, but not the successor; or Successor origin, meaning the successor originated the query. This field can also be: Connected, if the network is directly connected to this router; Redistributed, if this route is being redistributed into EIGRP on this router; or Summary, if this is a summary route generated on this router.
Q is the send flag for this route, meaning there is a query pending. This field can also be: U, meaning there is an update pending; or R, meaning there is a reply pending. Via This command displays all entries in the topology table for this destination, not just feasible successors. State is Passive means the network is in passive state, or, in other words, we are not looking for a path to this network.
Routes are almost always in a passive state in stable networks. Query origin flag is 1 If this route is active, this field provides information on who originated the query. This router has received more than one query for this route from more than one source. Similar to 2, but it also means there is a query origin string which describes the queries outstanding for this path. FD is shows the best current metric to this network. If the route is active, this indicates the metric of the path we were previously using to route packets to this network.
Routing Descriptor Blocks Each of the following entries describes one path to the network. The first number in the parentheses is the total cost to the network through this path, including the cost to the next hop.
The second number in the parentheses is the reported distance, or, in other words, the cost the next hop router uses. EIGRP does not propagate total cost information throughout the network; the vector metrics are propagated, and each router computes the cost and reported distance individually. Minimum bandwidth is Kbit shows the lowest bandwidth on the path to this network.
Total delay is microseconds shows the sum of the delays on the path to this network. This number is calculated dynamically, but is not used by default in metric calculations. This number is calculated dynamically, and is not used by default when EIGRP calculates the cost to use this path. The maximum number of hops that EIGRP will accept is by default, although the maximum can be configured to with metric maximum hops. If the route is external, the following information is included.
Same output format as show ip eigrp topology , but it also shows some portion of the topology table. Same output format as show ip eigrp topology , but it also shows all links in the topology table, rather than just feasible successors.
Skip to content Skip to search Skip to footer. Available Languages. Download Options. Updated: September 9, 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 must occur.
This is the process where a new successor is determined. The amount of time it takes to recompute the route 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 will test for feasible successors.
If there are feasible successors, it will use any it finds in order to avoid any unnecessary recomputation. Feasible successors are defined in more detail later in this document. The protocol-dependent modules are responsible for network layer, protocol-specific requirements. Both data structures and the DUAL concepts are discussed. Each router keeps state information about adjacent neighbors.
When newly discovered neighbors are learned, the address and interface of the neighbor is recorded. This information is stored in the neighbor data structure. The neighbor table holds these entries. There is one neighbor table for each protocol dependent module. When a neighbor sends a hello, it advertises a HoldTime.
The HoldTime 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 HoldTime, then the HoldTime expires. 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. 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. If the neighbor is advertising this destination, it must be using the route to forward packets. This is an important rule that distance vector protocols must follow. 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. This is the metric that the router uses in the routing table and to advertise to other routers.
A destination entry is moved from the topology table to the routing table when there is a feasible successor. 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.
Reliability is measured dynamically and is expressed as an eight-bit number, where is a percent reliable link and 1 is a minimally reliable link. Load is represented as a fraction of , 1 is a minimally loaded link, and is a percent loaded link. If reliability or load is to be used as a metric or as part of a composite metric, the algorithm for calculating the metric must not allow sudden changes in the error rate or channel occupancy to destabilize the network.
If an instantaneous, measure of load is used, a burst of heavy traffic could cause a route to go into holddown and an abrupt drop in traffic could trigger an update. To prevent frequent metric changes, reliability and load are calculated based on an exponentially weighted average with a five-minute time constant, which is updated every five seconds. Router config-router metric weights? Unlike the traditional Distance Vector routing protocols which will send their neighbors period routing updates that contain all routing information, EIGRP sends non-periodic incremental routing updates to distribute routing information throughout the routing domain.
EIGRP has a default hop-count limitation of ; however, this value can be manually adjusted by the administrator using the following command;. Both TLVs include an 8-bit Prefix Length field which specifies the number of bits used for the subnet mask of the destination network. These can be changed under the routing protocol with the following command;. EIGRP can also query neighboring routers for information to an alternate path if it is not located in the local routers Topology Table. DUAL is used to track all routes advertised by neighbors and then select the best, loop-free path to the destination network.
0コメント