OSPF Equal-Cost Multi-Path (ECMP)

OSPF Equal-Cost Multi-Path (ECMP)

When several paths to the same destination have the same cost, OSPF does not pick just one. It installs every equal-cost path in the routing table and spreads traffic over them. This is ECMP (equal-cost multi-path).

This article looks at how RFC 2328 defines ECMP, how many paths are kept and what decides which packet takes which path, and confirms it on IOS XR. How a cost is derived is covered in OSPF Cost (Metric).

What RFC 2328 says

ECMP is not an extension added by implementations; it is part of the specification.

The above discussion has been simplified by considering only a single route to any destination. In reality, if multiple equal-cost routes to a destination exist, they are all discovered and used. This requires no conceptual changes to the algorithm. (RFC 2328 Section 2.4)

Section 16.8 gives the conditions for routes to be installed side by side.

Each one of the multiple routes will be of the same type (intra-area, inter-area, type 1 external or type 2 external), cost, and will have the same associated area. However, each route may specify a separate next hop and Advertising router. (RFC 2328 Section 16.8)

In other words, only the next hop and the advertising router may differ. Routes of a different type or cost are not installed together.

How many are kept is up to the implementation.

There is no requirement that a router running OSPF keep track of all possible equal-cost routes to a destination. An implementation may choose to keep only a fixed number of routes to any given destination. This does not affect any of the algorithms presented in this specification. (RFC 2328 Section 16.8)

The per-platform limits below follow from that sentence.

The forwarding plane decides the spread

Once several next hops are in the routing table, which packet takes which path is decided by the forwarding plane (CEF), not by OSPF. The default is a hash over the source and destination addresses, so packets with the same pair always take the same path (per-flow load sharing). Spreading packet by packet would reorder them.

Because of this, a ping or a traceroute to one destination only ever shows one path. To see that several paths are in use, change the destination or look at the counters of each path.

Lab verification

Lab setup

Six Cisco IOS XR routers (XRd 26.1.1). There are four paths of equal cost from R1 to R5, one through each of P1 to P4. Every link is point-to-point with cost 1 in area 0, so each path costs 3 from R1.

R5 holds eight loopbacks, 172.16.0.1/32 to 172.16.0.8/32, so that the spread can be observed as the destination changes.

Steps

The configurable range (before STEP 0)

This is the help output of maximum paths ? under router ospf.

RP/0/RP0/CPU0:R1(config)#router ospf 1

RP/0/RP0/CPU0:R1(config-ospf)#maximum ?

  interfaces              Limit number of interfaces
  paths                   Limit number of paths
  redistributed-prefixes  Limit number of redistributed prefixes
RP/0/RP0/CPU0:R1(config-ospf)#maximum 

% Incomplete command.
RP/0/RP0/CPU0:R1(config-ospf)#maximum paths ?

  <1-64>                   Maximum number of paths per route

On IOS XR the range is 1 to 64. The default is not shown in the help, so it is checked further down from the number of paths left after no maximum paths in STEP 3.

All four equal-cost paths are installed (STEP 0)

The routing table of R1:

RP/0/RP0/CPU0:R1#show route 172.16.0.1/32
Wed Sep 23 04:46:42.077 UTC

Routing entry for 172.16.0.1/32
  Known via "ospf 1", distance 110, metric 3, type intra area
  Installed Sep 23 04:40:24.867 for 00:06:17
  Routing Descriptor Blocks
    10.0.11.2, from 6.6.6.6, via GigabitEthernet0/0/0/0
      Route metric is 3
    10.0.12.2, from 6.6.6.6, via GigabitEthernet0/0/0/1
      Route metric is 3
    10.0.13.2, from 6.6.6.6, via GigabitEthernet0/0/0/2
      Route metric is 3
    10.0.14.2, from 6.6.6.6, via GigabitEthernet0/0/0/3
      Route metric is 3
  No advertising protos. 

All four next hops are there. The metric is 3 on every one of them, and the only difference is the next hop and the outgoing interface, exactly as Section 16.8 of RFC 2328 puts it.

The forwarding table (FIB) holds the same four paths.

RP/0/RP0/CPU0:R1#show cef 172.16.0.1/32 detail
Wed Sep 23 04:46:43.069 UTC
172.16.0.1/32, version 51, internal 0x1000001 0x10 (ptr 0x882972c0) [1], 0x400 (0x894f1f98), 0x0 (0x0)
 Updated Sep 23 04:40:24.911 
 local adjacency to GigabitEthernet0/0/0/0

 Prefix Len 32, traffic index 0, precedence n/a, priority 1
  gateway array (0x8938b848) reference count 9, flags 0x0, source rib (7), 0 backups
                [10 type 3 flags 0x8401 (0x8942e220) ext 0x0 (0x0)]
  LW-LDI[type=3, refc=1, ptr=0x894f1f98, sh-ldi=0x8942e220]
  gateway array update type-time 1 Sep 23 04:40:24.874
 LDI Update time Sep 23 04:40:24.911
 LW-LDI-TS Sep 23 04:40:24.911
   via 10.0.11.2/32, GigabitEthernet0/0/0/0, 7 dependencies, weight 0, class 0 [flags 0x0]
    path-idx 0 NHID 0x2 [0x8a75b500 0x0]
    next hop 10.0.11.2/32
    local adjacency
   via 10.0.12.2/32, GigabitEthernet0/0/0/1, 7 dependencies, weight 0, class 0 [flags 0x0]
    path-idx 1 NHID 0x3 [0x8a75b640 0x0]
    next hop 10.0.12.2/32
    local adjacency
   via 10.0.13.2/32, GigabitEthernet0/0/0/2, 7 dependencies, weight 0, class 0 [flags 0x0]
    path-idx 2 NHID 0x4 [0x8a75b780 0x0]
    next hop 10.0.13.2/32
    local adjacency
   via 10.0.14.2/32, GigabitEthernet0/0/0/3, 7 dependencies, weight 0, class 0 [flags 0x0]
    path-idx 3 NHID 0x5 [0x8a75b8c0 0x0]
    next hop 10.0.14.2/32
    local adjacency

    Load distribution: 0 1 2 3 (refcount 10)

    Hash  OK  Interface                 Address
    0     Y   GigabitEthernet0/0/0/0    10.0.11.2      
    1     Y   GigabitEthernet0/0/0/1    10.0.12.2      
    2     Y   GigabitEthernet0/0/0/2    10.0.13.2      
    3     Y   GigabitEthernet0/0/0/3    10.0.14.2      

path-idx 0 to 3 are the four buckets the hash result is mapped onto.

The path changes with the destination (STEP 0)

Running traceroute to the eight destinations gives a different first hop depending on the destination.

RP/0/RP0/CPU0:R1#traceroute 172.16.0.1 source 1.1.1.1 timeout 1 probe 3 maxttl 4
Wed Sep 23 04:46:06.381 UTC

Type escape sequence to abort.
Tracing the route to 172.16.0.1

 1  10.0.14.2 80 msec  5 msec  5 msec 
 2  10.0.24.5 74 msec  *  9 msec 

RP/0/RP0/CPU0:R1#traceroute 172.16.0.5 source 1.1.1.1 timeout 1 probe 3 maxttl 4
Wed Sep 23 04:46:14.858 UTC

Type escape sequence to abort.
Tracing the route to 172.16.0.5

 1  10.0.11.2 19 msec  4 msec  4 msec 
 2  10.0.21.5 8 msec  *  10 msec 

RP/0/RP0/CPU0:R1#traceroute 172.16.0.8 source 1.1.1.1 timeout 1 probe 3 maxttl 4
Wed Sep 23 04:46:20.723 UTC

Type escape sequence to abort.
Tracing the route to 172.16.0.8

 1  10.0.12.2 8 msec  6 msec  4 msec 
 2  10.0.22.5 37 msec  *  10 msec 

The first hop of all eight destinations came out as follows (from the ..._ping.txt files).

All three probes to one destination take the same path, and the path changes when the destination changes, which is the per-flow hashing described above. The spread is not even: eight destinations fall into four buckets, and this time four landed on P4, two on P3 and one each on P1 and P2.

The input counters of the relays show the same skew. In STEP 0 the counters were cleared before sending 50 packets to each of the eight destinations (400 in total) plus the traceroutes.

GigabitEthernet0/0/0/0 is up, line protocol is up 
  Interface state transitions: 1
  Hardware is GigabitEthernet, address is 5254.00d4.4e7c (bia 5254.00d4.4e7c)
  Description: to R1
  Internet address is 10.0.11.2/24
  MTU 1514 bytes, BW 1000000 Kbit (Max: 1000000 Kbit)
     reliability 255/255, txload 0/255, rxload 0/255
  Encapsulation ARPA,
  Full-duplex, 1000Mb/s, unknown, link type is force-up
  output flow control is off, input flow control is off
  Carrier delay (up) is 10 msec
  loopback not set,
  Last link flapped 00:07:26
  ARP type ARPA, ARP timeout 04:00:00
  Last input 00:00:00, output 00:00:00
  Last clearing of "show interface" counters 00:01:42
  5 minute input rate 0 bits/sec, 0 packets/sec
  5 minute output rate 0 bits/sec, 1 packets/sec
     68 packets input, 7276 bytes, 0 total input drops
     0 drops for unrecognized upper-level protocol
     Received 0 broadcast packets, 12 multicast packets
              0 runts, 0 giants, 0 throttles, 0 parity
     0 input errors, 0 CRC, 0 frame, 0 overrun, 0 ignored, 0 abort
     169 packets output, 19030 bytes, 0 total output drops
     Output 0 broadcast packets, 11 multicast packets
     0 output errors, 0 underruns, 0 applique, 0 resets
     0 output buffer failures, 0 output buffers swapped out
     0 carrier transitions

GigabitEthernet0/0/0/0 is up, line protocol is up 
  Interface state transitions: 1
  Hardware is GigabitEthernet, address is 5254.00e5.b90a (bia 5254.00e5.b90a)
  Description: to R1
  Internet address is 10.0.12.2/24
  MTU 1514 bytes, BW 1000000 Kbit (Max: 1000000 Kbit)
     reliability 255/255, txload 0/255, rxload 0/255
  Encapsulation ARPA,
  Full-duplex, 1000Mb/s, unknown, link type is force-up
  output flow control is off, input flow control is off
  Carrier delay (up) is 10 msec
  loopback not set,
  Last link flapped 00:07:45
  ARP type ARPA, ARP timeout 04:00:00
  Last input 00:00:01, output 00:00:01
  Last clearing of "show interface" counters 00:02:09
  5 minute input rate 0 bits/sec, 0 packets/sec
  5 minute output rate 0 bits/sec, 1 packets/sec
     121 packets input, 13274 bytes, 0 total input drops
     0 drops for unrecognized upper-level protocol
     Received 0 broadcast packets, 15 multicast packets
              0 runts, 0 giants, 0 throttles, 0 parity
     0 input errors, 0 CRC, 0 frame, 0 overrun, 0 ignored, 0 abort
     228 packets output, 25932 bytes, 0 total output drops
     Output 0 broadcast packets, 13 multicast packets
     0 output errors, 0 underruns, 0 applique, 0 resets
     0 output buffer failures, 0 output buffers swapped out
     0 carrier transitions

GigabitEthernet0/0/0/0 is up, line protocol is up 
  Interface state transitions: 1
  Hardware is GigabitEthernet, address is 5254.00c4.9ab7 (bia 5254.00c4.9ab7)
  Description: to R1
  Internet address is 10.0.13.2/24
  MTU 1514 bytes, BW 1000000 Kbit (Max: 1000000 Kbit)
     reliability 255/255, txload 0/255, rxload 0/255
  Encapsulation ARPA,
  Full-duplex, 1000Mb/s, unknown, link type is force-up
  output flow control is off, input flow control is off
  Carrier delay (up) is 10 msec
  loopback not set,
  Last link flapped 00:08:15
  ARP type ARPA, ARP timeout 04:00:00
  Last input 00:00:00, output 00:00:00
  Last clearing of "show interface" counters 00:02:36
  5 minute input rate 0 bits/sec, 0 packets/sec
  5 minute output rate 0 bits/sec, 0 packets/sec
     130 packets input, 13912 bytes, 0 total input drops
     0 drops for unrecognized upper-level protocol
     Received 0 broadcast packets, 18 multicast packets
              0 runts, 0 giants, 0 throttles, 0 parity
     0 input errors, 0 CRC, 0 frame, 0 overrun, 0 ignored, 0 abort
     25 packets output, 2818 bytes, 0 total output drops
     Output 0 broadcast packets, 17 multicast packets
     0 output errors, 0 underruns, 0 applique, 0 resets
     0 output buffer failures, 0 output buffers swapped out
     0 carrier transitions

GigabitEthernet0/0/0/0 is up, line protocol is up 
  Interface state transitions: 1
  Hardware is GigabitEthernet, address is 5254.00ad.0eed (bia 5254.00ad.0eed)
  Description: to R1
  Internet address is 10.0.14.2/24
  MTU 1514 bytes, BW 1000000 Kbit (Max: 1000000 Kbit)
     reliability 255/255, txload 0/255, rxload 0/255
  Encapsulation ARPA,
  Full-duplex, 1000Mb/s, unknown, link type is force-up
  output flow control is off, input flow control is off
  Carrier delay (up) is 10 msec
  loopback not set,
  Last link flapped 00:08:37
  ARP type ARPA, ARP timeout 04:00:00
  Last input 00:00:01, output 00:00:01
  Last clearing of "show interface" counters 00:03:03
  5 minute input rate 0 bits/sec, 1 packets/sec
  5 minute output rate 0 bits/sec, 0 packets/sec
     247 packets input, 26334 bytes, 0 total input drops
     0 drops for unrecognized upper-level protocol
     Received 0 broadcast packets, 21 multicast packets
              0 runts, 0 giants, 0 throttles, 0 parity
     0 input errors, 0 CRC, 0 frame, 0 overrun, 0 ignored, 0 abort
     131 packets output, 14886 bytes, 0 total output drops
     Output 0 broadcast packets, 19 multicast packets
     0 output errors, 0 underruns, 0 applique, 0 resets
     0 output buffer failures, 0 output buffers swapped out
     0 carrier transitions

P1 received 68 packets, P2 121, P3 130 and P4 247 (OSPF Hellos and LSAs included). The order matches the traceroute results.

Changing how many paths are kept (STEPs 1 to 3)

maximum paths was set to 2 on R1.

RP/0/RP0/CPU0:R1#show configuration commit changes last 1
Wed Sep 23 04:49:44.445 UTC
!! Building configuration...
!! IOS XR Configuration 26.1.1
router ospf 1
 maximum paths 2
!
end

RP/0/RP0/CPU0:R1#show route 172.16.0.1/32
Wed Sep 23 04:52:09.210 UTC

Routing entry for 172.16.0.1/32
  Known via "ospf 1", distance 110, metric 3, type intra area
  Installed Sep 23 04:49:43.669 for 00:02:25
  Routing Descriptor Blocks
    10.0.11.2, from 6.6.6.6, via GigabitEthernet0/0/0/0
      Route metric is 3
    10.0.14.2, from 6.6.6.6, via GigabitEthernet0/0/0/3
      Route metric is 3
  No advertising protos. 

RP/0/RP0/CPU0:R1#show route 172.16.0.1/32
Wed Sep 23 04:57:39.656 UTC

Routing entry for 172.16.0.1/32
  Known via "ospf 1", distance 110, metric 3, type intra area
  Installed Sep 23 04:55:12.909 for 00:02:26
  Routing Descriptor Blocks
    10.0.14.2, from 6.6.6.6, via GigabitEthernet0/0/0/3
      Route metric is 3
  No advertising protos. 

RP/0/RP0/CPU0:R1#show route 172.16.0.1/32
Wed Sep 23 05:03:08.953 UTC

Routing entry for 172.16.0.1/32
  Known via "ospf 1", distance 110, metric 3, type intra area
  Installed Sep 23 05:00:42.608 for 00:02:26
  Routing Descriptor Blocks
    10.0.11.2, from 6.6.6.6, via GigabitEthernet0/0/0/0
      Route metric is 3
    10.0.12.2, from 6.6.6.6, via GigabitEthernet0/0/0/1
      Route metric is 3
    10.0.13.2, from 6.6.6.6, via GigabitEthernet0/0/0/2
      Route metric is 3
    10.0.14.2, from 6.6.6.6, via GigabitEthernet0/0/0/3
      Route metric is 3
  No advertising protos. 

The table went down to two, then one, and no maximum paths brought it back to four. All four are installed with the default in place, so the IOS XR default is at least 4 (this lab only has four equal-cost paths, so the exact limit cannot be determined here).

maximum paths 1 turns ECMP off and keeps a single path. The one left this time was 10.0.14.2 (P4). When the costs are equal, which one survives is not something the configuration decides; to pin traffic to a particular path, give it a different cost.

The per-prefix-distribution keyword in the help assigns the paths per prefix; it is not used in this lab.

A path that is no longer equal-cost drops out (STEP 4)

The cost of the R1 - P4 link was set to 5 on both ends.

RP/0/RP0/CPU0:R1#show configuration commit changes last 1
Wed Sep 23 05:06:12.638 UTC
!! Building configuration...
!! IOS XR Configuration 26.1.1
router ospf 1
 area 0
  interface GigabitEthernet0/0/0/3
   cost 5
  !
 !
!
end

RP/0/RP0/CPU0:R1#show route 172.16.0.1/32
Wed Sep 23 05:09:13.079 UTC

Routing entry for 172.16.0.1/32
  Known via "ospf 1", distance 110, metric 3, type intra area
  Installed Sep 23 05:06:12.108 for 00:03:01
  Routing Descriptor Blocks
    10.0.11.2, from 6.6.6.6, via GigabitEthernet0/0/0/0
      Route metric is 3
    10.0.12.2, from 6.6.6.6, via GigabitEthernet0/0/0/1
      Route metric is 3
    10.0.13.2, from 6.6.6.6, via GigabitEthernet0/0/0/2
      Route metric is 3
  No advertising protos. 

Only the path through P4 dropped out, leaving three. Its cost became 7 and no longer matched the other three (3). ECMP requires the costs to be equal, so even a small difference removes a path.

Design notes

• Decide deliberately whether paths should be equal-cost. Making links of different bandwidth equal-cost sends the same share of traffic down the thin one; adjust it with the reference bandwidth described in OSPF Cost (Metric)
• The spread is per flow, so the load on each path depends on how the destinations hash. Do not size capacity assuming an even split across the paths
• maximum paths 1 does not let you choose which path survives. Give a path a different cost if traffic has to use it

Configurations and show outputs

In each STEP the following files were collected from all six routers, one file per router. The configuration used in the lab is the ..._run.txt file (the final state is the one of the last STEP).

There is no commit.cfg for STEPs and routers whose configuration did not change. The help output for maximum paths is in precheck. Since the subject is the result of route calculation and forwarding, no packet captures were taken.

STEP 0: Initial state (four equal-cost paths)

STEP 1: maximum paths 2 on R1

STEP 2: maximum paths 1 on R1

STEP 3: no maximum paths on R1 (back to the default)

STEP 4: The cost of R1 - P4 raised to 5 on both ends

STEP 5: The cost set back to 1 (final state)

References

Related articles

• What is OSPF
• OSPF Router ID
• OSPF Packet Types and Header Format
• OSPF Authentication
• OSPF Neighbor States
• OSPF Options Field
• OSPF DR and BDR
• OSPF Network Types
• OSPF Cost (Metric)
• OSPF Equal-Cost Multi-Path (ECMP)
• OSPF External Routes (Redistributing Static Routes)
• OSPF RFC1583 Compatibility (External Route Selection Rules)
• OSPF Forwarding Address of AS External Routes
• OSPF Multiple Areas and the ABR
• OSPF Virtual Links
• OSPF Stub and Totally Stubby Areas
• OSPF NSSA and Totally NSSA
• OSPF Default Route
• OSPF Route Summarization
• OSPF LSAs and the LSA Header
• OSPF Hello and Dead Intervals
• OSPF Convergence Timers (SPF / LSA Throttling)
• OSPF LSA Refresh and Pacing
• OSPF router-LSA (type 1)
• OSPF network-LSA (type 2)
• OSPF summary-LSA (type 3)
• OSPF ASBR summary-LSA (type 4)
• OSPF AS external-LSA (type 5)
• OSPF NSSA External-LSA (Type 7)