DUAL Algorithm

The Heart of EIGRP

The Diffusing Update Algorithm (DUAL) is the core of EIGRP that provides loop-free routing and fast convergence. Understanding DUAL is crucial for mastering EIGRP.

What is DUAL?

DUAL is a sophisticated algorithm that ensures loop-free routing by maintaining distance and vector information about routes. It guarantees that at any instant, no routing loops will form.

Key DUAL Concepts

Distance Information

  • Feasible Distance (FD): Best known distance to destination
  • Reported Distance (RD): Neighbor's distance to destination
  • Successor Distance: Distance via best path

Vector Information

  • Successor: Next-hop router for best path
  • Feasible Successor: Loop-free alternate path
  • Downstream Neighbor: Closer to destination

DUAL Operation States

Passive
→
Active
→
Passive
State Description Activities
Passive Route is stable and available Normal routing, feasible successor available
Active Route is being recomputed Querying neighbors, waiting for replies

Feasibility Condition

The Golden Rule

RD < FD

A route is considered feasible (loop-free) if the Reported Distance from a neighbor is less than the current Feasible Distance to that destination.

Why the Feasibility Condition Works

Loop Prevention Logic

Step 1

Router A has FD=100
to destination

Step 2

Router B reports
RD=80 to destination

Step 3

Since RD (80) < FD (100)
B is feasible successor

Result

No loop possible
B is closer to destination

DUAL Decision Process

Scenario Condition Action Result
Route learned First route to destination Install as successor Passive state
Better route found Lower metric received Update successor Passive state
Successor fails Feasible successor available Promote feasible successor Passive state
Successor fails No feasible successor Go active, send queries Active state

Query/Reply Process

When a router goes active, it queries its neighbors to find alternate paths:

Query Propagation Example

Router A (Active)
Lost successor to 10.0.0.0/8
Sends Query to all neighbors
Router B
Has route to 10.0.0.0/8
Sends Reply with metric
Router C
No route to 10.0.0.0/8
Sends Reply (unreachable)
Router D
Also goes active
Queries its neighbors

Query Rules

When to Send Queries

  • Route goes active (successor lost, no feasible successor)
  • Metric increase beyond feasible successor threshold
  • All neighbors except the one that caused the problem
  • Split horizon prevents queries back to the source

SIA (Stuck in Active)

SIA Problem

When a router doesn't receive all replies within the active timer (3 minutes), it becomes Stuck in Active:

  • Neighbor relationships are reset
  • Route computation starts over
  • Can cause network instability
  • Common in large networks with slow links

SIA Prevention

Technique Description Benefit
Route Summarization Aggregate routes at boundaries Reduces query scope
Stub Routing Mark stub routers Eliminates queries to stubs
Active Timer Tuning Adjust active timer value Faster SIA detection
Network Design Hierarchical topology Limits query propagation

DUAL Example Walkthrough

Initial Topology

Destination: 192.168.1.0/24
Router A:
  - via Router B: FD=100, RD=80 (Successor)
  - via Router C: FD=120, RD=90 (Feasible Successor)
  - via Router D: FD=150, RD=140 (Not feasible: RD > FD)

Topology Change Process

Event

Link to Router B fails

DUAL Action

Promote Router C
to successor

New State

FD=120 via Router C
No queries needed

Result

Sub-second
convergence

DUAL Advantages

Benefits of DUAL

  • Loop Freedom: Guaranteed loop-free routing
  • Fast Convergence: Immediate switching to feasible successors
  • Optimal Paths: Always selects best available path
  • Minimal Overhead: Queries only when necessary
  • Distributed Computation: No single point of failure

DUAL vs Other Algorithms

Algorithm Loop Prevention Convergence Complexity
DUAL Feasibility condition Very fast Medium
Dijkstra (OSPF) Complete topology Fast High
Bellman-Ford (RIP) Count-to-infinity Slow Low

Key Takeaways

  • Feasibility Condition: RD < FD ensures loop-free paths
  • Passive State: Normal operation with feasible successors
  • Active State: Route recomputation via query/reply
  • SIA: Avoided through proper network design

Metric Components

Understanding EIGRP Metrics

EIGRP uses a composite metric that can include bandwidth, delay, reliability, load, and MTU. Understanding these components is crucial for network optimization.

The Five Metric Components

Bandwidth

Primary Component

Slowest link bandwidth in the path

Measured in Kbps

Delay

Primary Component

Cumulative delay of all links

Measured in tens of microseconds

Reliability

Dynamic Component

Link reliability (0-255)

255 = 100% reliable

Load

Dynamic Component

Link utilization (0-255)

255 = 100% utilized

MTU

Path Component

Minimum MTU in path

Not used in calculation

Metric Calculation Formula

EIGRP Metric Formula

Metric = 256 × [(K1 × BW) + (K2 × BW)/(256 - Load) + (K3 × Delay)] × [K5/(Reliability + K4)]

Where:

  • BW = 10^7 / (minimum bandwidth in kbps)
  • Delay = sum of delays in tens of microseconds
  • K1, K2, K3, K4, K5 are K-values (weights)

Default K-Values

K-Value Component Default Impact
K1 Bandwidth 1 Enabled - primary factor
K2 Load 0 Disabled - too dynamic
K3 Delay 1 Enabled - secondary factor
K4 Reliability 0 Disabled - too dynamic
K5 MTU 0 Disabled - not used

Simplified Default Calculation

With default K-values (K1=1, K2=0, K3=1, K4=0, K5=0), the formula simplifies to:

Default Metric Calculation

Metric = 256 × [(10^7 / minimum_bandwidth_kbps) + (sum_of_delays)]

This makes bandwidth and delay the only factors in path selection.

Bandwidth Component

Interface Type Bandwidth BW Value Contribution
Serial 64K 64 Kbps 10^7 / 64 = 156,250 High impact
T1 1,544 Kbps 10^7 / 1544 = 6,476 Medium impact
Ethernet 10,000 Kbps 10^7 / 10000 = 1,000 Low impact
Fast Ethernet 100,000 Kbps 10^7 / 100000 = 100 Very low impact
Gigabit Ethernet 1,000,000 Kbps 10^7 / 1000000 = 10 Minimal impact

Delay Component

Interface Type Delay (microseconds) Delay Value Cumulative
Serial 20,000 2,000 Sum of all interfaces
Ethernet 1,000 100 Sum of all interfaces
Fast Ethernet 100 10 Sum of all interfaces
Gigabit Ethernet 10 1 Sum of all interfaces

Metric Calculation Examples

Example 1: Simple Path

Path: Router A → Fast Ethernet → Router B

  • Bandwidth: 100,000 Kbps
  • Delay: 100 microseconds
  • BW component: 10^7 / 100000 = 100
  • Delay component: 100 / 10 = 10
  • Metric = 256 × (100 + 10) = 28,160

Example 2: Multi-hop Path

Path: Router A → Serial T1 → Router B → Ethernet → Router C

  • Minimum bandwidth: 1,544 Kbps (T1)
  • Total delay: 20,000 + 1,000 = 21,000 microseconds
  • BW component: 10^7 / 1544 = 6,476
  • Delay component: 21,000 / 10 = 2,100
  • Metric = 256 × (6,476 + 2,100) = 2,195,456

Metric Tuning Strategies

Bandwidth Tuning

Cisco Interface Bandwidth

interface Serial0/0
 bandwidth 1544
 
interface FastEthernet0/0
 bandwidth 100000

Cisco Interface Delay

interface Serial0/0
 delay 20000
 
interface FastEthernet0/0
 delay 100

Advanced Metric Tuning

Custom K-Values

router eigrp 100
 metric weights 0 1 0 1 0 0
 ! K1=1, K2=0, K3=1, K4=0, K5=0 (default)
 
router eigrp 100
 metric weights 0 1 1 1 0 0
 ! Enable load-based routing (K2=1)

Common Metric Issues

Metric Pitfalls

  • Mismatched K-values: Prevents neighbor formation
  • Incorrect bandwidth: Leads to suboptimal path selection
  • Dynamic metrics: Using load/reliability causes instability
  • High-speed interfaces: May need bandwidth adjustment

Best Practices

Metric Optimization

  • Use default K-values: Bandwidth and delay only
  • Set correct bandwidth: Match actual interface speeds
  • Tune delay for path selection: Prefer paths with lower delay
  • Avoid dynamic metrics: Don't use load or reliability
  • Document changes: Keep track of metric modifications

Verification Commands

Cisco Metric Verification

# Check interface metrics
show interface
show ip eigrp interface detail

# Check K-values
show ip protocols
show ip eigrp topology

# Check calculated metrics
show ip eigrp topology all-links

Topology Table Analysis

# Detailed topology information
show ip eigrp topology 192.168.1.0

# Show metric components
show ip eigrp topology detail-links

# Debug metric calculation
debug eigrp packets

Key Takeaways

  • Composite Metric: Bandwidth and delay are primary factors
  • K-values: Must match between neighbors
  • Bandwidth: Minimum bandwidth in path
  • Delay: Cumulative delay of all links
  • Tuning: Use bandwidth and delay for path optimization

Neighbor Discovery

EIGRP Neighbor Discovery

EIGRP uses Hello packets to discover and maintain neighbor relationships. This process is fundamental to EIGRP's operation and ensures reliable route exchange between routers.

Hello Packet Process

Down
→
Init
→
Up

Neighbor States

State Description Condition Next Action
Down No communication Initial state or neighbor lost Send Hello packets
Init Hello received Unidirectional communication Wait for bidirectional Hello
Up Neighbor established Bidirectional communication Exchange topology information

Hello Packet Requirements

AS Number

Must match exactly

K-Values

Must be identical

Authentication

If configured, must match

Network Layer

Same subnet required

Hello Timers

Interface Type Hello Interval Hold Time Configuration
High-speed (>T1) 5 seconds 15 seconds Default
Low-speed (≤T1) 60 seconds 180 seconds Default
Custom Configurable Typically 3x Hello Manual setting

Timer Configuration

Adjusting Hello Timers

# Configure Hello interval (interface mode)
interface serial0/0/0
 ip hello-interval eigrp 100 30
 ip hold-time eigrp 100 90

# Verification
show ip eigrp neighbors detail
show ip eigrp interfaces detail

Timer Considerations

  • Match Requirements: Hello and hold timers don't need to match between neighbors
  • Convergence Impact: Shorter timers = faster detection but more overhead
  • WAN Links: Consider adjusting timers for slow or unreliable links
  • Best Practice: Keep default timers unless specific requirements exist

Route Types

EIGRP Route Classification

EIGRP classifies routes into different types based on their origin and characteristics. Understanding these types is crucial for proper routing table analysis and troubleshooting.

Route Type Categories

Internal Routes (AD: 90)
External Routes (AD: 170)
Summary Routes (AD: 5)

Route Type Details

Route Type Code Administrative Distance Source Description
Internal D 90 EIGRP domain Routes learned from EIGRP neighbors within the AS
External D EX 170 Route redistribution Routes redistributed from other routing protocols
Summary D 5 Route summarization Manually configured summary routes

Route Table Examples

EIGRP Route Table Output

Router# show ip route eigrp
Codes: L - local, C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area

Gateway of last resort is not set

D    192.168.1.0/24 [90/2816000] via 10.1.1.2, 00:05:23, Serial0/0/0
D EX 172.16.0.0/16 [170/2816000] via 10.1.1.2, 00:02:15, Serial0/0/0  
D    192.168.0.0/22 [5/128256] via Null0, 00:10:30

Route Information Fields

Field Example Description
Network 192.168.1.0/24 Destination network and subnet mask
Administrative Distance [90/2816000] Route preference (lower is better)
Metric [90/2816000] EIGRP composite metric
Next Hop via 10.1.1.2 Next-hop router IP address
Age 00:05:23 Time since last update
Interface Serial0/0/0 Outgoing interface

Administrative Distance Priority

Route Selection Order

Lower Administrative Distance = Higher Priority

  1. Summary Routes (AD: 5) - Highest priority
  2. Internal Routes (AD: 90) - Standard EIGRP routes
  3. External Routes (AD: 170) - Lowest priority

Route Type Benefits

  • Internal Routes: Trusted within EIGRP domain, preferred over external
  • External Routes: Lower preference prevents routing loops during redistribution
  • Summary Routes: Highest preference ensures proper aggregation behavior

Autonomous Systems

EIGRP Autonomous Systems

An Autonomous System (AS) in EIGRP defines a routing domain where all routers share the same EIGRP process and routing information. The AS number is crucial for neighbor formation and route exchange.

AS Number Fundamentals

Aspect Description Range Significance
AS Number Routing domain identifier 1-65535 Must match for neighbor formation
Scope Local significance only Per organization Different from BGP AS numbers
Multiple AS Multiple EIGRP processes Limited by router resources Requires redistribution for communication

AS Number Configuration

Single AS Configuration

# Basic EIGRP configuration with AS 100
router eigrp 100
 network 192.168.1.0 0.0.0.255
 network 10.0.0.0 0.255.255.255
 no auto-summary

# All routers in the domain must use AS 100

Multiple AS Configuration

Multiple EIGRP Processes

# Router with multiple EIGRP processes
router eigrp 100
 network 192.168.1.0 0.0.0.255
 no auto-summary

router eigrp 200  
 network 172.16.0.0 0.0.255.255
 no auto-summary

# These processes are independent and require redistribution
# to exchange routes between AS 100 and AS 200

AS Design Considerations

Single AS

Simple design
Automatic route sharing

Multiple AS

Segmented domains
Controlled route exchange

Redistribution

Inter-AS communication
Route filtering possible

Administrative

Organizational boundaries
Security segmentation

AS Redistribution

Inter-AS Route Exchange

# Redistribute between EIGRP AS numbers
router eigrp 100
 redistribute eigrp 200 metric 1544 20000 255 1 1500

router eigrp 200
 redistribute eigrp 100 metric 1544 20000 255 1 1500

# Metric values: bandwidth delay reliability load mtu
# Required when redistributing into EIGRP

AS Verification

AS Verification Commands

# Check EIGRP processes
show ip protocols
show ip eigrp neighbors
show ip eigrp topology

# Verify AS numbers
show running-config | section eigrp

# Check for multiple processes
show ip route eigrp

AS Design Best Practices

  • Keep It Simple: Use single AS when possible
  • Document AS Usage: Maintain clear AS number assignments
  • Plan Redistribution: Design route exchange carefully
  • Consider Security: Use multiple AS for network segmentation
  • Avoid Conflicts: Ensure AS numbers don't conflict with BGP
Previous: Chapter 1 - Introduction Next: Chapter 3 - Packet Types