BGP Link State (BGP-LS) Shortest Path First (SPF) Routing
Extracted elements (30)
A new BGP-LS-SPF SAFI (80) is introduced rather than reusing the BGP-LS SAFI to ensure backward compatibility. The BGP-LS SAFI uses the standard BGP Decision Process, whereas BGP-LS-SPF replaces it with SPF computation; sharing a SAFI would create conflicts.
BGP SPF significantly reduces NLRI advertisement volume compared to standard path-vector BGP: a single link failure requires only the originating BGP speaker to withdraw its Link NLRI, rather than triggering readvertisement of potentially hundreds of prefix NLRIs across the domain.
The 64-bit sequence number uses the high-order 32 bits as a boot/wrap count stored in non-volatile storage, so that after a cold restart or sequence number wrap the strictly-increasing property is preserved. If state is completely lost, the NLRI selection rules (adjacent peers prefer self-originated NLRIs) still ensure convergence.
AS_PATH and AS4_PATH attributes are preserved and used for loop detection even though BGP-LS-SPF replaces the standard Decision Process. Attributes such as ORIGIN, MULTI_EXIT_DISC, LOCAL_PREF, and the MP_REACH_NLRI Next-Hop are ignored during SPF computation.
The 'BGP-LS NLRI and Attribute TLVs' registry is shared between BGP-LS SAFI and BGP-LS-SPF SAFI, but TLVs defined in this document (1181, 1184, 1185) may not apply to the BGP-LS SAFI. Unknown or unexpected TLVs must not cause an NLRI to be treated as malformed, per RFC 9552.
All malformed BGP-LS-SPF TLVs (SPF Status TLV with reserved value, missing IGP Metric, malformed Address Family Link Descriptor, malformed Sequence Number TLV) cause the corresponding NLRI to be treated as treat-as-withdraw per RFC 7606. Implementations SHOULD log errors subject to rate limiting.
BGP-LS-SPF NLRI MUST be readvertised to all BGP-LS-SPF peers immediately upon receipt, prior to or independent of SPF computation. The BGP MinASOriginationIntervalTimer is not applicable; MinRouteAdvertisementIntervalTimer applies with a suggested default of 5 seconds.
For Node NLRI and Link NLRI, the Protocol-ID field MUST be set to the direct protocol (4); an NLRI with any other Protocol-ID is considered malformed. For Prefix NLRI, the Protocol-ID MUST reflect the origin of the prefix.
It is RECOMMENDED that BGP-LS-SPF IPv4/IPv6 route computation and installation be given scheduling priority over other BGP address families by default, since BGP-LS-SPF serves as an underlay SAFI. BGP-LS-SPF and BGP unicast address families operate in ships-in-the-night mode with no implicit route redistribution.
It is RECOMMENDED that RFC 8654 Extended Message Support be implemented to accommodate large BGP-LS Attributes. A BGP speaker MUST NOT advertise a single BGP-LS-SPF NLRI that would cause an UPDATE message to exceed the maximum BGP message size.
NLRI selection for Phase 1 follows four rules in priority order: (1) self-originated NLRIs from directly connected peers are preferred; (2) a peer's NLRI always replaces the same peer's prior NLRI; (3) higher Sequence Number is preferred; (4) numerically larger BGP Identifier is preferred.
On link or prefix failure, the originating BGP speaker SHOULD advertise a more recent NLRI with the SPF Status TLV set to unreachable before withdrawing, using the configurable LinkStatusDownAdvertise or PrefixStatusDownAdvertise timer (suggested default 2 seconds). If the link/prefix recovers during that interval, the speaker MUST readvertise without the SPF Status TLV.
The IGP Metric (TLV 1095) MUST be advertised with every Link NLRI; a Link NLRI received without an IGP Metric TLV MUST be treated as malformed (treat-as-withdraw). The metric length is 4 octets and applies to the output side of the interface.
The Node NLRI MUST be advertised unconditionally by all routers in the BGP SPF routing domain. The Local and Remote Node Descriptors for all NLRIs MUST include the BGP Router-ID (TLV 516) and the Autonomous System number (TLV 512).
The Sequence Number TLV MUST be present in every BGP-LS-SPF NLRI; its absence renders the NLRI malformed and it MUST be handled as treat-as-withdraw. The sequence number MUST be strictly increasing and implementations MUST preserve it across cold restarts.
The SPF-based Decision Process MUST NOT be used with AFI/SAFI combinations other than BGP-LS AFI (16388) / SAFI 80. Two BGP speakers MUST exchange the Multiprotocol Extensions Capability (RFC 4760) with AFI 16388 / SAFI 80 before exchanging BGP-LS-SPF NLRIs.
The SPF computation requires bidirectional connectivity: for a link to be used, the remote node's Link NLRI must exist with matching address descriptors pointing back to the current node. A link is excluded if either direction's SPF Status TLV indicates unreachable.
To avoid errors in other AFI/SAFIs from impacting BGP-LS-SPF (or vice versa), isolation mechanisms such as separate BGP instances or sessions SHOULD be used for BGP-LS-SPF information distribution.
When a BGP speaker receives a self-originated NLRI with a more recent sequence number, it MUST immediately advance its own sequence number past the received value and readvertise the NLRI to all peers. Subsequent stale self-originated NLRIs trigger a delay of BGP_LS_SPF_SELF_READVERTISEMENT_DELAY (default 5 seconds) before readvertisement.
When LSDB synchronization is lost between two BGP-LS-SPF peers, the BGP session MUST be reset with a NOTIFICATION message using BGP error code 'Loss of LSDB Synchronization' (value 9).
The BGP-LS-SPF SAFI is assigned value 80 and uses AFI 16388. It carries Node, Link, and Prefix NLRIs for SPF-based route computation and is distinct from the BGP-LS SAFI to ensure backward compatibility.
IANA assigned SAFI value 80 for BGP-LS-SPF in the 'SAFI Values' registry (First Come First Served). Three TLVs were assigned in the 'BGP-LS NLRI and Attribute TLVs' registry: 1181 (Sequence Number), 1184 (SPF Status), 1185 (Address Family Link Descriptor). TLVs 1180, 1182, and 1183 are deprecated.
IANA assigned value 9 ('Loss of LSDB Synchronization') in the 'BGP Error (Notification) Codes' registry within the 'Border Gateway Protocol (BGP) Parameters' registry group.
Three new registries were created under the 'BGP Shortest Path First (BGP SPF)' registry group: 'BGP-LS-SPF Node NLRI Attribute SPF Status TLV Values' (Expert Review), 'BGP-LS-SPF Link NLRI Attribute SPF Status TLV Values' (IETF Review), and 'BGP-LS-SPF Prefix NLRI Attribute SPF Status TLV Values' (IETF Review), each with initial values 0 (Reserved), 1 (unreachable), 255 (Reserved).
Multiple BGP speakers originating the same BGP-LS-SPF NLRI (identified by Node Descriptors) indicate either a configuration error or a masquerading attack; an error SHOULD be logged so operators can take corrective action. The BGP-LS-SPF SAFI is also vulnerable to DoS via malformed BGP attributes that trigger treat-as-withdraw processing.
To mitigate peering with masquerading BGP speakers, TCP-AO (RFC 5925) is RECOMMENDED for authenticating all BGP-LS-SPF sessions. A compromised authorized peer could advertise modified NLRIs causing misrouting or excessive SPF calculations.
The Dijkstra SPF algorithm proceeds in six steps: (1) invalidate Local-RIB and clear CAN-LIST; (2) seed computing router at cost 0; (3) pop lowest-cost node, skip if SPF Status = unreachable; (4) install prefix routes for current node; (5) evaluate links with bidirectional connectivity check, update CAN-LIST; (6) apply Local-RIB changes to GLOBAL-RIB.
The Address Family Link Descriptor TLV (type 1185) is a 1-octet field used with unnumbered links to indicate the address family (1 = IPv4, 2 = IPv6) for which the link should be included in SPF. Values 0 and 255 are reserved; 3–254 are undefined.
The BGP-LS Attribute Sequence Number TLV (type 1181) encodes a mandatory 8-octet (64-bit) strictly increasing sequence number, with the high-order 32 bits serving as a boot/wrap count and the low-order 32 bits as the per-NLRI counter.
The SPF Status TLV (type 1184) is a 1-octet field shared across Node, Link, and Prefix NLRIs. For Node NLRIs: 1 = unreachable, 2 = no transit; for Link NLRIs: 1 = unreachable; for Prefix NLRIs: 1 = unreachable. Values 0 and 255 are reserved.