BFD down but traffic still blackholed downstream

Introduction to Failure Boundary Mapping

Understanding Failure Boundaries

A failure boundary is the point in the control‑plane where a local routing change stops propagating correctly, allowing stale forwarding state to persist downstream. When the head‑end (the router that originates a prefix or initiates a withdrawal) acts quickly, downstream routers may still be processing recursion, ECMP load‑balancing tables, or FIB updates. The resulting mismatch creates a forwarding black hole or micro‑loop that outlives the detection event. Mapping this boundary requires tracing:

1. The control‑plane event (withdrawal, path‑selection change).
2. Propagation of that event through routing protocols (BGP, OSPF/IS‑IS, LDP, etc.).
3. The point at which each downstream router installs the new RIB entry and programs the FIB.
4. Any lag introduced by ECMP hash‑table recomputation, next‑hop recursion resolution, or hardware‑pipeline update cycles.

Key Concepts: ECMP, FIB, and Downstream Recursion

• ECMP (Equal‑Cost Multi‑Path) – When multiple next‑hops share the same best‑path metric, the router installs a set of ECMP members and forwards packets using a hash function. A change in the ECMP set triggers a hash‑table rebuild; until the rebuild completes, packets may be sent to a withdrawn next‑hop or experience packet reordering.
• FIB (Forwarding Information Base) – The hardware‑accelerated copy of the RIB used for packet lookup. FIB programming is not instantaneous; it depends on the ASIC’s update pipeline, TCAM write latency, and any batching mechanisms. A lag between RIB change and FIB update means the dataplane continues to use stale forwarding entries.
• Downstream Recursion – Many prefixes are resolved via a recursive next‑hop (e.g., a BGP prefix pointing to an IGP‑learned address). If the IGP next‑hop withdraws or its metric changes, the BGP prefix must be re‑resolved. Recursion adds an extra hop of state exchange; any delay in IGP convergence or in the BGP next‑hop tracking process prolongs the forwarding inconsistency.

Network Architecture and Failure Scenarios

Overview of Network Topology

Consider a typical spine‑leaf or POPs‑core design:

• Head‑end routers (PEs or route‑reflector clients) originate prefixes via BGP or static routes.
• Transit routers (route reflectors, core routers) propagate the prefixes using IBGP or OSPF/IS‑IS.
• Leaf/access routers receive the prefixes, perform ECMP load‑balancing across multiple uplinks, and install FIB entries for forwarding to hosts or servers.

Failure Scenario

1. Head‑end withdraws a prefix (BGP UPDATE with withdraw, or IGP LSA delete).
2. The withdraw is processed locally within a few hundred milliseconds.
3. Downstream routers still have the prefix in their RIB because:
   • The IBGP update has not yet been received (propagation delay).
   • The IGP next‑hop used for recursion is still reachable (stale IGP LSA).
   • The ECMP set has not been recomputed or the FIB has not been flushed.
4. Packets continue to be forwarded toward the withdrawn prefix, either being dropped at the point of loss or looping until the stale state times out.

Impact of Head‑End Withdrawal on Downstream Routing

• BGP – The UPDATE is sent to all IBGP peers. If route reflection is used, the RR may delay re‑advertisement until its own best‑path selection changes (e.g., after checking alternative paths).
• IGP – If the withdrawn prefix is an IGP‑originated route (static or OSPF) address used as a BGP next‑hop, the IGP must first withdraw the corresponding LSA. IGP convergence timers (hello/dead, SPF delay) dictate when downstream routers learn the loss.
• ECMP – Upon learning that one of the ECMP next‑hops is no longer reachable, the router must:
  1. Remove the dead next‑hop from the ECMP list.
  2. Re‑hash the remaining members (if any) or fall back to a single path.
  3. Update the FIB to reflect the new hash buckets.
     Any of these steps can lag, causing packets to be hashed to the withdrawn next‑hop.

Role of ECMP in Failure Boundary Mapping

ECMP amplifies the failure boundary because the forwarding decision is distributed across multiple next‑hops. A single stale next‑hop can attract a fraction of traffic proportional to the hash bucket size. The boundary therefore extends beyond the router that first learns the withdraw; it includes every router that:

• Still believes the withdrawn next‑hop is viable (stale IGP or BGP state).
• Has not yet updated its ECMP hash table.
• Has not yet programmed the revised FIB entry.

Mapping the boundary requires measuring the time delta between the head‑end’s withdraw and the point at which all downstream routers have:

1. Updated their RIB (no stale route).
2. Updated their ECMP next‑hop set.
3. Refreshed their FIB.

Only after the slowest of these three conditions is satisfied does the forwarding path align with intent.

Troubleshooting Failure Boundaries

Identifying Broken Forwarding Paths

1. Confirm the withdraw at the source – show ip bgp <prefix> or show ip route <prefix> on the head‑end should indicate the prefix is absent or marked withdrawn.
2. Trace the path downstream – Use traceroute or ping with record‑route option from a host beyond the suspected black hole to see where packets stop.
3. Check RIB vs. FIB – On each suspect router, compare the RIB entry (show ip route <prefix>) with the FIB entry (show ip cef <prefix> or show fib <prefix>). A RIB entry that is absent but a FIB entry that persists indicates a FIB lag.
4. Validate ECMP membership – show ip cef <prefix> detail (Cisco) or show route receive-protocol bgp <neighbor> (Juniper) lists the current next‑hops; compare with the expected set from the routing protocol.
5. Monitor protocol timers – show ip bgp neighbors (BGP hold time), show ip ospf neighbor (OSPF dead interval), or show isis neighbors (IS‑IS hold time) to see if a neighbor is still considered up while the prefix is withdrawn.

Analyzing FIB Lag and Its Effects

FIB lag manifests as:

• Micro‑loops – Packets forwarded to a next‑hop that itself forwards back toward the source due to inconsistent ECMP sets.
• Black holes – Packets sent to a withdrawn next‑hop that drops them (e.g., ACL deny or null0).
• Out‑of‑order delivery – Hash changes cause packets to take different paths mid‑flow.

To quantify lag, measure:

• RIB‑to‑FIB delta – Timestamp of RIB update (from syslog or show logging) vs. timestamp of FIB update (from hardware counters).
• ECMP hash‑table rebuild time – Some platforms expose a counter for “ECMP rehash events”; compare before/after values.

Using CLI Commands for Troubleshooting

Example: Debugging ECMP Routing Issues

# Verify BGP withdraw propagation
show ip bgp neighbors 10.0.0.1 received-routes | include 192.168.100.0/24

# Check current ECMP set for the prefix
show ip cef 192.168.100.0/24 detail
# Output shows: 2 paths, next-hop 10.1.1.1, 10.1.2.2

# Simulate loss of one next-hop and observe hash table
monitor session 1 type erspan-source
   destination ip 10.0.0.10
   source ip 10.0.0.1
   no shut

The monitor session captures packets; a sudden drop in packets destined to 10.1.1.1 after the withdraw indicates the ECMP set has not been updated.

Example: Monitoring FIB Updates

# Enable FIB change logging (platform‑dependent)
logging buffered 1000000
logging trap debugging
# On Cisco Nexus:
system internal fib event-history size 10000

# After the withdraw, check the log for FIB update timestamps
show logging | include FIB_UPDATE|192.168.100.0/24

# Alternatively, poll the FIB entry timestamp
show ip cef 192.168.100.0/24 | include epoch

The epoch value increments each time the FIB entry is rewritten; comparing epochs before and after the withdraw reveals the update latency.

Code Examples for Failure Boundary Detection

Scripting for Automated Failure Detection

Automated detection hinges on polling the RIB/FIB state at a frequency higher than the expected convergence time (e.g., every 100 ms) and flagging any mismatch that persists beyond a threshold.

Example Code: Python Script for ECMP Route Monitoring

#!/usr/bin/env python3
import time
import subprocess
import re

PREFIX = "192.168.100.0/24"
HEADEND = "10.0.0.1"
CHECK_INTERVAL = 0.1   # seconds
MAX_STALE = 2.0        # seconds before we alarm

def get_rib_state():
    """Return True if prefix present in RIB on local router."""
    out = subprocess.check_output(["show", "ip", "route", PREFIX], text=True)
    return bool(re.search(rf"{PREFIX}\s+