Diffusing Update Algorithm – An Introduction
Diffusing Update Algorithm (DUAL) is the convergence algorithm used by EIGRP instead of the Bellman-Ford or Ford Fulkerson algorithms used by other distance vector routing protocols, like RIP. DUAL is based on research conducted at SRI International, using calculations that were first proposed by E.W. Dijkstra and C.S. Scholten. The most prominent work with DUAL has been done by J.J. Garcia-Luna-Aceves.
Routing loops, even temporary ones, can be extremely detrimental to network performance. Distance vector routing protocols such as RIP prevent routing loops with hold-down timers and split horizon. Although EIGRP uses both of these techniques, it uses them somewhat differently; the primary way that EIGRP prevents routing loops is with the DUAL algorithm.
The DUAL algorithm is used to obtain loop-freedom at every instant throughout a route computation. This allows all routers involved in a topology change to synchronize at the same time. Routers that are not affected by the topology changes are not involved in the recomputation. This method provides EIGRP with faster convergence times than other distance vector routing protocols.
The decision process for all route computations is done by the DUAL Finite State Machine. In general terms, a finite state machine (FSM) is a model of behavior composed of a finite number of states, transitions between those states, and events or actions that create the transitions.
The DUAL FSM tracks all routes, uses its metric to select efficient, loop-free paths, and selects the routes with the least cost path to insert into the routing table.
Because recomputation of the DUAL algorithm can be processor-intensive, it is advantageous to avoid recomputation whenever possible. Therefore, DUAL maintains a list of backup routes it has already determined to be loop-free. If the primary route in the routing table fails, the best backup route is immediately added to the routing table.
Administrative distance (AD) is the trustworthiness (or preference) of the route source. EIGRP has a default administrative distance of 90 for internal routes and 170 for routes imported from an external source, such as default routes. When compared to other interior gateway protocols (IGPs), EIGRP is the most preferred by the Cisco IOS because it has the lowest administrative distance.
Notice in the figure that EIGRP has a third AD value, of 5, for summary routes. Later in this chapter, you will learn how to configure EIGRP summary routes.
Basic EIGRP configuration
AutonomousSystem
An autonomous system (AS) is a collection of networks under the administrative control of a single entity that presents a common routing policy to the Internet. In the figure, companies A, B, C, and D are all under the administrative control of ISP1. ISP1 "presents a common routing policy" for all of these companies when advertising routes to ISP2.
The guidelines for the creation, selection, and registration of an autonomous system are described in RFC 1930. AS numbers are assigned by the Internet Assigned Numbers Authority (IANA), the same authority that assigns IP address space. You learned about IANA and its Regional Internet Registries (RIRs) in a previous course. The local RIR is responsible for assigning an AS number to an entity from its block of assigned AS numbers. Prior to 2007, AS numbers were 16-bit numbers, ranging from 0 to 65535. Now 32-bit AS numbers are assigned, increasing the number of available AS numbers to over 4 billion.
Who needs an autonomous system number? Usually ISPs (Internet Service Providers), Internet backbone providers, and large institutions connecting to other entities that also have an AS number. These ISPs and large institutions use the exterior gateway routing protocol Border Gateway Protocol, or BGP, to propagate routing information. BGP is the only routing protocol that uses an actual autonomous system number in its configuration.
The vast majority of companies and institutions with IP networks do not need an AS number because they come under the control of a larger entity such as an ISP. These companies use interior gateway protocols such as RIP, EIGRP, OSPF, and IS-IS to route packets
within their own networks. They are one of many independent and separate networks within the autonomous system of the ISP. The ISP is responsible for the routing of packets within its autonomous system and between other autonomous systems.
Process ID
Both EIGRP and OSPF use a process ID to represent an instance of their respective routing protocol running on the router.
Router(config)#router eigrp autonomous-system
Although EIGRP refers to the parameter as an "autonomous-system" number, it actually functions as a process ID. This number is not associated with an autonomous system number discussed previously and can be assigned any 16-bit value.
Router(config)#router eigrp 1
In this example, the number 1 identifies this particular EIGRP process running on this router. In order to establish neighbor adjacencies, EIGRP requires all routers in the same routing domain to be configured with the same process ID. Typically, only a single process ID of any routing protocol would be configured on a router.
The network Command with a Wildcard Mask
By default, when using the network command and a classful network address such as 172.16.0.0, all interfaces on the router that belong to that classful network address will be enabled for EIGRP. However, there may be times when the network administrator does not want to include all interfaces within a network when enabling EIGRP. To configure EIGRP to advertise specific subnets only, use the wildcard-mask option with the network command:
Router(config-router)#network network-address [wildcard-mask]
Think of a wildcard mask as the inverse of a subnet mask. The inverse of subnet mask 255.255.255.252 is 0.0.0.3. To calculate the inverse of the subnet mask, subtract the subnet mask from 255.255.255.255:
255.255.255.255
-255.255.255.252
Subtract the subnet mask
---------------
0. 0. 0. 3 Wildcard mask
In the figure, R2 is configured with the subnet 192.168.10.8 and the wildcard mask 0.0.0.3.
R2(config-router)#network 192.168.10.8 0.0.0.3
Some IOS versions will also let you simply enter the subnet mask. For example, you might enter the following:
R2(config-router)#network 192.168.10.8 255.255.255.252
However, the IOS will then convert the command to the wildcard mask format, as can be verified with the show run command:
R2#show run
The figure also shows the configuration for R3. As soon as the classful network 192.168.10.0 is configured, R3 establishes adjacencies with both R1 and R2.
Verifying EIGRP Operation
Before any updates can be sent or received by EIGRP, routers must establish adjacencies with their neighbors. EIGRP routers establish adjacencies with neighbor routers by exchanging EIGRP Hello packets.
Use the show ip eigrp neighbors command to view the neighbor table and verify that EIGRP has established an adjacency with its neighbors. For each router, you should be able to see the IP address of the adjacent router and the interface that this router uses to reach that EIGRP neighbor. In the figure, we can verify that all routers have established the necessary adjacencies. Each router has two neighbors listed in the neighbor table.
The output from the show ip eigrp neighbor command includes:
H column -Lists the neighbors in the order they were learned. Address -The IP address of the neighbor. Interface -The local interface on which this Hello packet was received. Hold -The current hold time. Whenever a Hello packet is received, this value is reset to the maximum hold time for that interface and then counts down to zero. If zero is reached, the neighbor is considered "down". Uptime - Amount of time since this neighbor was added to the neighbor table. SRTT (Smooth Round Trip Timer) and RTO (Retransmit Interval) - Used by RTP to manage reliable EIGRP packets. Queue Count - Should always be zero. If more than zero, then EIGRP packets are waiting to be sent. Sequence Number - Used to track updates, queries, and reply packets.
The show ip eigrp neighbors command is very useful for verifying and troubleshooting EIGRP.
Another way to verify that EIGRP and other functions of the router are configured properly is to examine the routing tables with the show ip route command.
By default, EIGRP automatically summarizes routes at the major network boundary. We can disable the automatic summarization with the no auto-summary command, just as we did in RIPv2. We will examine this in more detail in a later section.
Notice that EIGRP routes are denoted in the routing table with a D, which stands for DUAL.
Remember, because EIGRP is a classless routing protocol (includes the subnet mask in the routing update), it supports VLSM and CIDR. We can see in the routing table for R1 that the 172.16.0.0/16 parent network is variably subnetted with three child routes using either a /24 or /30 mask.
EIGRP Composite Metric and the K value
EIGRP uses the following values in its composite metric to calculate the preferred path to a network:
Bandwidth Delay Reliability Load
The figure 9 shows the composite metric formula used by EIGRP. The formula consists of values K1 through K5, known as EIGRP metric weights. By default, K1 and K3 are set to 1, and K2, K4, and K5 are set to 0. The result is that only the bandwidth and delay values are used in the computation of the default composite metric.
The figure shows the composite metric formula used by EIGRP. The formula consists of values K1 through K5, known as EIGRP metric weights. By default, K1 and K3 are set to 1, and K2, K4, and K5 are set to 0. The result is that only the bandwidth and delay values are used in the computation ofthe default composite metric.
The default K values can be changedwith the EIGRP router command:
Router(config-router)#metric weights tos k1 k2 k3 k4 k5
The show ip protocols command is used to verify the K values. The command output for R1 is shown in the figure. Notice that the K values on R1 are set to the default. Again, changing these values to other than the default is not recommended unless the network administrator has a very good reason to do so.
You now know the defaults for the K values. By using the show interface command we can examine the actual values used for bandwidth, delay, reliability, and load in the computation of the routing metric.
The output in the figure 11 shows the values used in the composite metric for the Serial 0/0/0 interface on R1.
MTU 1500 bytes, BW 1544 Kbit, DLY 20000 usec,
reliability 255/255, txload 1/255, rxload 1/255
The bandwidth metric (1544 Kbit) is a static value used by some routing protocols such as EIGRP and OSPF to calculate their routing metric. The bandwidth is displayed in Kbit (kilobits). Most serial interfaces use the default bandwidth value of 1544 Kbit or 1,544,000 bps (1.544 Mbps). This is the bandwidth of a T1 connection. However, some serial interfaces use a different default bandwidth value. Always verify bandwidth with the show interface command.
The value of the bandwidth may or may not reflect the actual physical bandwidth of the interface. Modifying the bandwidth value does not change the actual bandwidth of the link. If actual bandwidth of the link differs from the default bandwidth value, then you should modify the bandwidth value, as we will see in a later section.
Delay is a measure of the time it takes for a packet to traverse a route. The delay (DLY) metric is a static value based on the type of link to which the interface is connected and is expressed in microseconds. Delay is not measured dynamically. In other words, the router does not actually track how long packets are taking to reach the destination. The delay value, much like the bandwidth value, is a default value that can be changed by the network administrator.
MTU 1500 bytes, BW 1544 Kbit, DLY 20000 usec,
reliability 255/255, txload 1/255, rxload 1/255
The table in the figure 12 shows the default delay values for various interfaces. Notice that the default value is 20,000 microseconds for Serial interfaces and 100 microseconds for FastEthernet interfaces.
Reliability (reliability) is a measure of the probability that the link will fail or how often the link has experienced errors. Unlike delay, Reliability is measured dynamically with a value between 0 and 255, with 1 being a minimally reliable link and 255 one hundred percent reliable. Reliability is calculated on a 5-minute weighted average to avoid the sudden impact of high (or low) error rates.
Reliability is expressed as a fraction of 255 -the higher the value, the more reliable the link. So, 255/255 would be 100 percent reliable, whereas a link of 234/255 would be 91.8 percent reliable.
Load (load) reflects the amount of traffic utilizing the link. Like reliability, load is measured dynamically with a value between 0 and 255. Similar to reliability, load is expressed as a fraction of 255. However, in this case a lower load value is more desirable because it indicates less load on the link. So, 1/255 would be a minimally loaded link. 40/255 is a link at 16 percent capacity, and 255/255 would be a link that is 100 percent saturated.
Load is displayed as both an outbound, or transmit, load value (txload) and an inbound, or receive, load value (rxload). This value is calculated on a 5-minute weighted average to avoid the sudden impact of high (or low) channel usage.
Calculating the EIGRP Metric
The figure 14 shows the composite metric used by EIGRP. Using the default values for K1 and K3, we can simplify this calculation to: the slowest bandwidth (or minimum bandwidth) plus the cumulative sum of all of the delays.
In other words, by examining the bandwidth and delay values for all of the outgoing interfaces of the route, we can determine the EIGRP metric. First, determine the link with the slowest bandwidth. That bandwidth is used for the (10,000,000/bandwidth) * 256 portion of the formula. Next, determine the delay value for each outgoing interface on the way to the destination. Sum the delay values and divide by 10 (sum of delay/10) and then multiply by 256 (* 256). Add the bandwidth and sum of delay values to obtain the EIGRP metric.
The routing table output for R2 shows that the route to 192.168.1.0/24 has an EIGRP metric of 3,014,400. Let's see exactly how EIGRP calculated this value.
Because EIGRP uses the slowest bandwidth in its metric calculation, we can find the slowest bandwidth by examining each interface between R2 and the destination network 192.168.1.0. The Serial 0/0/1 interface on R2 has a bandwidth of 1,024 Kbps or 1,024,000 bps. The FastEthernet 0/0 interface on R3 has a bandwidth of 100,000 Kbps or 100 Mbps. Therefore, the slowest bandwidth is 1024 Kbps and is used in the calculation of the metric.
EIGRP takes the reference bandwidth value of 10,000,000 and divides it by the bandwidth value in kbps. This will result in higher bandwidth values receiving a lower metric and lower bandwidth values receiving a higher metric.
10,000,000 is divided by 1024. If the result is not a whole number, then the value is rounded down. In this case, 10,000,000 divided by 1024 equals 9765.625. The .625 is dropped before multiplying by 256. The bandwidth portion of the composite metric is 2,499,840.
Dual Concepts
As stated in a previous section, DUAL (Diffusing Update Algorithm) is the algorithm used by EIGRP. This section will discuss how DUAL determines the best loop-free path and loop-free backup paths.
DUAL uses several terms which will be discussed in more detail throughout this section:
Successor Feasible Distance (FD) Feasible Successor (FS) Reported Distance (RD) or Advertised Distance (AD)
A successor is a neighboring router that is used for packet forwarding and is the least-cost route to the destination network. The IP address of a successor is shown in a routing table entry right after the word via.
Feasible distance (FD) is the lowest calculated metric to reach the destination network. FD is the metric listed in the routing table entry as the second number inside the brackets. As with other routing protocols this is also known as the metric for the route.
The successor, feasible distance, and any feasible successors with their reported distances are kept by a router in its EIGRP topology table or topology database. As shown in the figure, the topology table can be viewed using the show ip eigrp topology command. The topology table lists all successors and feasible successors that DUAL has calculated to destination networks.
DUAL Finite State Machine (FSM)
The centerpiece of EIGRP is DUAL and its EIGRP route-calculation engine. The actual name of this technology is DUAL Finite State Machine (FSM). This finite state machine contains all of the logic used to calculate and compare routes in an EIGRP network. The figure shows a simplified version of the DUAL FSM.
A finite state machine is an abstract machine, not a mechanical device with moving parts. FSMs define a set of possible states that something can go through, what events cause those states, and what events result from those states. Designers use FSMs to describe how a device, computer program, or routing algorithm will react to a set of input events. Finite state machines are beyond the scope of this course; however, we introduce the concept in order to examine some of the output from EIGRP's finite state machine using debug eigrp fsm. Let's use the command to watch what DUAL does when a route is removed from the routing table.
i learn so many things from this blog.keep updating.thank you so much.
RispondiElimina