< draft-ietf-lsvr-bgp-spf-05.txt   draft-ietf-lsvr-bgp-spf-06.txt >
Network Working Group K. Patel Network Working Group K. Patel
Internet-Draft Arrcus, Inc. Internet-Draft Arrcus, Inc.
Intended status: Standards Track A. Lindem Intended status: Standards Track A. Lindem
Expires: January 23, 2020 Cisco Systems Expires: April 2, 2020 Cisco Systems
S. Zandi S. Zandi
Linkedin Linkedin
W. Henderickx W. Henderickx
Nokia Nokia
July 22, 2019 September 30, 2019
Shortest Path Routing Extensions for BGP Protocol Shortest Path Routing Extensions for BGP Protocol
draft-ietf-lsvr-bgp-spf-05 draft-ietf-lsvr-bgp-spf-06
Abstract Abstract
Many Massively Scaled Data Centers (MSDCs) have converged on Many Massively Scaled Data Centers (MSDCs) have converged on
simplified layer 3 routing. Furthermore, requirements for simplified layer 3 routing. Furthermore, requirements for
operational simplicity have lead many of these MSDCs to converge on operational simplicity have lead many of these MSDCs to converge on
BGP as their single routing protocol for both their fabric routing BGP as their single routing protocol for both their fabric routing
and their Data Center Interconnect (DCI) routing. This document and their Data Center Interconnect (DCI) routing. This document
describes a solution which leverages BGP Link-State distribution and describes a solution which leverages BGP Link-State distribution and
the Shortest Path First (SPF) algorithm similar to Internal Gateway the Shortest Path First (SPF) algorithm similar to Internal Gateway
skipping to change at page 1, line 42 skipping to change at page 1, line 42
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 23, 2020. This Internet-Draft will expire on April 2, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 38 skipping to change at page 2, line 38
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. BGP Shortest Path First (SPF) Motivation . . . . . . . . 4 1.1. BGP Shortest Path First (SPF) Motivation . . . . . . . . 4
1.2. Requirements Language . . . . . . . . . . . . . . . . . . 5 1.2. Requirements Language . . . . . . . . . . . . . . . . . . 5
2. BGP Peering Models . . . . . . . . . . . . . . . . . . . . . 5 2. BGP Peering Models . . . . . . . . . . . . . . . . . . . . . 5
2.1. BGP Single-Hop Peering on Network Node Connections . . . 5 2.1. BGP Single-Hop Peering on Network Node Connections . . . 5
2.2. BGP Peering Between Directly Connected Network Nodes . . 6 2.2. BGP Peering Between Directly Connected Network Nodes . . 6
2.3. BGP Peering in Route-Reflector or Controller Topology . . 6 2.3. BGP Peering in Route-Reflector or Controller Topology . . 6
3. BGP-LS Shortest Path Routing (SPF) SAFI . . . . . . . . . . . 6 3. BGP-LS Shortest Path Routing (SPF) SAFI . . . . . . . . . . . 6
4. Extensions to BGP-LS . . . . . . . . . . . . . . . . . . . . 7 4. Extensions to BGP-LS . . . . . . . . . . . . . . . . . . . . 7
4.1. Node NLRI Usage and Modifications . . . . . . . . . . . . 7 4.1. Node NLRI Usage . . . . . . . . . . . . . . . . . . . . . 7
4.2. Link NLRI Usage . . . . . . . . . . . . . . . . . . . . . 8 4.1.1. Node NLRI Attribute SPF Capability TLV . . . . . . . 7
4.1.2. BGP-LS Node NLRI Attribute SPF Status TLV . . . . . . 8
4.2. Link NLRI Usage . . . . . . . . . . . . . . . . . . . . . 9
4.2.1. BGP-LS Link NLRI Attribute Prefix-Length TLVs . . . . 9 4.2.1. BGP-LS Link NLRI Attribute Prefix-Length TLVs . . . . 9
4.2.2. BGP-LS Link NLRI Attribute BGP SPF Status TLV . . . . 9 4.2.2. BGP-LS Link NLRI Attribute SPF Status TLV . . . . . . 10
4.2.3. BGP-LS Prefix NLRI Attribute SPF Status TLV . . . . . 10
4.3. Prefix NLRI Usage . . . . . . . . . . . . . . . . . . . . 10 4.3. Prefix NLRI Usage . . . . . . . . . . . . . . . . . . . . 10
4.4. BGP-LS Attribute Sequence-Number TLV . . . . . . . . . . 10 4.3.1. BGP-LS Prefix NLRI Attribute SPF Status TLV . . . . . 11
5. Decision Process with SPF Algorithm . . . . . . . . . . . . . 11 4.4. BGP-LS Attribute Sequence-Number TLV . . . . . . . . . . 11
5.1. Phase-1 BGP NLRI Selection . . . . . . . . . . . . . . . 12 5. Decision Process with SPF Algorithm . . . . . . . . . . . . . 12
5.2. Dual Stack Support . . . . . . . . . . . . . . . . . . . 13 5.1. Phase-1 BGP NLRI Selection . . . . . . . . . . . . . . . 13
5.3. SPF Calculation based on BGP-LS NLRI . . . . . . . . . . 13 5.2. Dual Stack Support . . . . . . . . . . . . . . . . . . . 14
5.4. NEXT_HOP Manipulation . . . . . . . . . . . . . . . . . . 16 5.3. SPF Calculation based on BGP-LS NLRI . . . . . . . . . . 14
5.5. IPv4/IPv6 Unicast Address Family Interaction . . . . . . 16 5.4. NEXT_HOP Manipulation . . . . . . . . . . . . . . . . . . 17
5.5. IPv4/IPv6 Unicast Address Family Interaction . . . . . . 17
5.6. NLRI Advertisement and Convergence . . . . . . . . . . . 17 5.6. NLRI Advertisement and Convergence . . . . . . . . . . . 17
5.6.1. Link/Prefix Failure Convergence . . . . . . . . . . . 17 5.6.1. Link/Prefix Failure Convergence . . . . . . . . . . . 17
5.6.2. Node Failure Convergence . . . . . . . . . . . . . . 17 5.6.2. Node Failure Convergence . . . . . . . . . . . . . . 18
5.7. Error Handling . . . . . . . . . . . . . . . . . . . . . 18 5.7. Error Handling . . . . . . . . . . . . . . . . . . . . . 18
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19
8. Management Considerations . . . . . . . . . . . . . . . . . . 18 8. Management Considerations . . . . . . . . . . . . . . . . . . 19
8.1. Configuration . . . . . . . . . . . . . . . . . . . . . . 18 8.1. Configuration . . . . . . . . . . . . . . . . . . . . . . 19
8.2. Operational Data . . . . . . . . . . . . . . . . . . . . 18 8.2. Operational Data . . . . . . . . . . . . . . . . . . . . 19
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 20
10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 19 10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 20
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.1. Normative References . . . . . . . . . . . . . . . . . . 19 11.1. Normative References . . . . . . . . . . . . . . . . . . 20
11.2. Information References . . . . . . . . . . . . . . . . . 20 11.2. Information References . . . . . . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23
1. Introduction 1. Introduction
Many Massively Scaled Data Centers (MSDCs) have converged on Many Massively Scaled Data Centers (MSDCs) have converged on
simplified layer 3 routing. Furthermore, requirements for simplified layer 3 routing. Furthermore, requirements for
operational simplicity have lead many of these MSDCs to converge on operational simplicity have lead many of these MSDCs to converge on
BGP [RFC4271] as their single routing protocol for both their fabric BGP [RFC4271] as their single routing protocol for both their fabric
routing and their Data Center Interconnect (DCI) routing. routing and their Data Center Interconnect (DCI) routing.
Requirements and procedures for using BGP are described in [RFC7938]. Requirements and procedures for using BGP are described in [RFC7938].
This document describes an alternative solution which leverages BGP- This document describes an alternative solution which leverages BGP-
skipping to change at page 4, line 7 skipping to change at page 4, line 9
Decision Process. Rather than reusing the BGP-LS SAFI, the BGP-LS- Decision Process. Rather than reusing the BGP-LS SAFI, the BGP-LS-
SPF SAFI is introduced to insure backward compatibility. The Phase 1 SPF SAFI is introduced to insure backward compatibility. The Phase 1
and 2 decision functions of the Decision Process are replaced with and 2 decision functions of the Decision Process are replaced with
the Shortest Path First (SPF) algorithm also known as the Dijkstra the Shortest Path First (SPF) algorithm also known as the Dijkstra
algorithm. The Phase 3 decision function is also simplified since it algorithm. The Phase 3 decision function is also simplified since it
is no longer dependent on the previous phases. This solution avails is no longer dependent on the previous phases. This solution avails
the benefits of both BGP and SPF-based IGPs. These include TCP based the benefits of both BGP and SPF-based IGPs. These include TCP based
flow-control, no periodic link-state refresh, and completely flow-control, no periodic link-state refresh, and completely
incremental NLRI advertisement. These advantages can reduce the incremental NLRI advertisement. These advantages can reduce the
overhead in MSDCs where there is a high degree of Equal Cost Multi- overhead in MSDCs where there is a high degree of Equal Cost Multi-
Path (ECMPs) and the topology is very stable. Additionally, using a Path (ECMPs) and the topology is very stable. Additionally, using an
SPF-based computation can support fast convergence and the SPF-based computation can support fast convergence and the
computation of Loop-Free Alternatives (LFAs) [RFC5286] in the event computation of Loop-Free Alternatives (LFAs) [RFC5286] in the event
of link failures. Furthermore, a BGP based solution lends itself to of link failures. Furthermore, a BGP based solution lends itself to
multiple peering models including those incorporating route- multiple peering models including those incorporating route-
reflectors [RFC4456] or controllers. reflectors [RFC4456] or controllers.
Support for Multiple Topology Routing (MTR) as described in [RFC4915] Support for Multiple Topology Routing (MTR) as described in [RFC4915]
is an area for further study dependent on deployment requirements. is an area for further study dependent on deployment requirements.
1.1. BGP Shortest Path First (SPF) Motivation 1.1. BGP Shortest Path First (SPF) Motivation
skipping to change at page 7, line 24 skipping to change at page 7, line 26
IDs of nodes, etc. IDs of nodes, etc.
The BGP protocol will be used in the Protocol-ID field specified in The BGP protocol will be used in the Protocol-ID field specified in
table 1 of [I-D.ietf-idr-bgpls-segment-routing-epe]. The local and table 1 of [I-D.ietf-idr-bgpls-segment-routing-epe]. The local and
remote node descriptors for all NLRI will be the BGP Router-ID (TLV remote node descriptors for all NLRI will be the BGP Router-ID (TLV
516) and either the AS Number (TLV 512) [RFC7752] or the BGP 516) and either the AS Number (TLV 512) [RFC7752] or the BGP
Confederation Member (TLV 517) [RFC8402]. However, if the BGP Confederation Member (TLV 517) [RFC8402]. However, if the BGP
Router-ID is known to be unique within the BGP Routing domain, it can Router-ID is known to be unique within the BGP Routing domain, it can
be used as the sole descriptor. be used as the sole descriptor.
4.1. Node NLRI Usage and Modifications 4.1. Node NLRI Usage
The BGP Node NLRI will be advertised unconditionally by all routers
in the BGP SPF routing domain.
4.1.1. Node NLRI Attribute SPF Capability TLV
The SPF capability is a new Node Attribute TLV that will be added to The SPF capability is a new Node Attribute TLV that will be added to
those defined in table 7 of [RFC7752]. The new attribute TLV will those defined in table 7 of [RFC7752]. The new attribute TLV will
only be applicable when BGP is specified in the Node NLRI Protocol ID only be applicable when BGP is specified in the Node NLRI Protocol ID
field. The TBD TLV type will be defined by IANA. The new Node field. The TBD TLV type will be defined by IANA. The new Node
Attribute TLV will contain a single-octet SPF algorithm as defined in Attribute TLV will contain a single-octet SPF algorithm as defined in
[RFC8402]. [RFC8402].
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
skipping to change at page 8, line 36 skipping to change at page 8, line 36
Note that usage of Strict Shortest Path First (SPF) algorithm is Note that usage of Strict Shortest Path First (SPF) algorithm is
defined in the IGP algorithm registry but usage is restricted to defined in the IGP algorithm registry but usage is restricted to
[I-D.ietf-idr-bgpls-segment-routing-epe]. Hence, its usage for BGP- [I-D.ietf-idr-bgpls-segment-routing-epe]. Hence, its usage for BGP-
LS SPF is out of scope. LS SPF is out of scope.
When computing the SPF for a given BGP routing domain, only BGP nodes When computing the SPF for a given BGP routing domain, only BGP nodes
advertising the SPF capability attribute will be included the advertising the SPF capability attribute will be included the
Shortest Path Tree (SPT). Shortest Path Tree (SPT).
4.1.2. BGP-LS Node NLRI Attribute SPF Status TLV
A BGP-LS Attribute TLV to BGP-LS Node NLRI is defined to indicate the
status of the node with respect to the BGP SPF calculation. This
will be used to rapidly take a node out of service or to indicate the
node is not to be used for transit (i.e., non-local) traffic. If the
SPF Status TLV is not included with the Node NLRI, the node is
considered to be up and is available for transit traffic.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TBD Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SPF Status |
+-+-+-+-+-+-+-+-+
BGP Status Values: 0 - Reserved
1 - Node Unreachable with respect to BGP SPF
2 - Node does not support transit with respect
to BGP SPF
3-254 - Undefined
255 - Reserved
4.2. Link NLRI Usage 4.2. Link NLRI Usage
The criteria for advertisement of Link NLRI are discussed in The criteria for advertisement of Link NLRI are discussed in
Section 2. Section 2.
Link NLRI is advertised with local and remote node descriptors as Link NLRI is advertised with local and remote node descriptors as
described above and unique link identifiers dependent on the described above and unique link identifiers dependent on the
addressing. For IPv4 links, the links local IPv4 (TLV 259) and addressing. For IPv4 links, the links local IPv4 (TLV 259) and
remote IPv4 (TLV 260) addresses will be used. For IPv6 links, the remote IPv4 (TLV 260) addresses will be used. For IPv6 links, the
local IPv6 (TLV 261) and remote IPv6 (TLV 262) addresses will be local IPv6 (TLV 261) and remote IPv6 (TLV 262) addresses will be
skipping to change at page 9, line 27 skipping to change at page 10, line 17
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TBD IPv4 or IPv6 Type | Length | | TBD IPv4 or IPv6 Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix-Length | | Prefix-Length |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Prefix-length - A one-octet length restricted to 1-32 for IPv4 Prefix-length - A one-octet length restricted to 1-32 for IPv4
Link NLIR endpoint prefixes and 1-128 for IPv6 Link NLIR endpoint prefixes and 1-128 for IPv6
Link NLRI endpoint prefixes. Link NLRI endpoint prefixes.
4.2.2. BGP-LS Link NLRI Attribute BGP SPF Status TLV 4.2.2. BGP-LS Link NLRI Attribute SPF Status TLV
A BGP-LS Attribute TLV to BGP-LS Link NLRI is defined to indicate the A BGP-LS Attribute TLV to BGP-LS Link NLRI is defined to indicate the
status of the link with respect to the BGP SPF calculation. This status of the link with respect to the BGP SPF calculation. This
will be used to expedite convergence for link failures as discussed will be used to expedite convergence for link failures as discussed
in Section 5.6.1. If the BGP SPF Status TLV is not included with the in Section 5.6.1. If the SPF Status TLV is not included with the
Link NLRI, the link is considered up and available. Link NLRI, the link is considered up and available.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TBD Type | Length | | TBD Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BGP SPF Status| | SPF Status |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
BGP Status Values: 0 - Reserved BGP Status Values: 0 - Reserved
1 - Link Unreachable with respect to BGP SPF 1 - Link Unreachable with respect to BGP SPF
2-254 - Undefined 2-254 - Undefined
255 - Reserved 255 - Reserved
4.2.3. BGP-LS Prefix NLRI Attribute SPF Status TLV 4.3. Prefix NLRI Usage
Prefix NLRI is advertised with a local node descriptor as described
above and the prefix and length used as the descriptors (TLV 265) as
described in [RFC7752]. The prefix metric attribute TLV (TLV 1155)
as well as any others required for non-SPF purposes SHOULD be
advertised. For loopback prefixes, the metric should be 0. For non-
loopback prefixes, the setting of the metric is a local matter and
beyond the scope of this document.
4.3.1. BGP-LS Prefix NLRI Attribute SPF Status TLV
A BGP-LS Attribute TLV to BGP-LS Prefix NLRI is defined to indicate A BGP-LS Attribute TLV to BGP-LS Prefix NLRI is defined to indicate
the status of the prefix with respect to the BGP SPF calculation. the status of the prefix with respect to the BGP SPF calculation.
This will be used to expedite convergence for prefix unreachability This will be used to expedite convergence for prefix unreachability
as discussed in Section 5.6.1. If the SPF Status TLV is not included as discussed in Section 5.6.1. If the SPF Status TLV is not included
with the Prefix NLRI, the prefix is considered reachable. with the Prefix NLRI, the prefix is considered reachable.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TBD Type | Length | | TBD Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BGP SPF Status| | SPF Status |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
BGP Status Values: 0 - Reserved BGP Status Values: 0 - Reserved
1 - Prefix down with respect to SPF 1 - Prefix down with respect to SPF
2-254 - Undefined 2-254 - Undefined
255 - Reserved 255 - Reserved
4.3. Prefix NLRI Usage
Prefix NLRI is advertised with a local node descriptor as described
above and the prefix and length used as the descriptors (TLV 265) as
described in [RFC7752]. The prefix metric attribute TLV (TLV 1155)
as well as any others required for non-SPF purposes SHOULD be
advertised. For loopback prefixes, the metric should be 0. For non-
loopback prefixes, the setting of the metric is a local matter and
beyond the scope of this document.
4.4. BGP-LS Attribute Sequence-Number TLV 4.4. BGP-LS Attribute Sequence-Number TLV
A new BGP-LS Attribute TLV to BGP-LS NLRI types is defined to assure A new BGP-LS Attribute TLV to BGP-LS NLRI types is defined to assure
the most recent version of a given NLRI is used in the SPF the most recent version of a given NLRI is used in the SPF
computation. The TBD TLV type will be defined by IANA. The new BGP- computation. The TBD TLV type will be defined by IANA. The new BGP-
LS Attribute TLV will contain an 8-octet sequence number. The usage LS Attribute TLV will contain an 8-octet sequence number. The usage
of the Sequence Number TLV is described in Section 5.1. of the Sequence Number TLV is described in Section 5.1.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
skipping to change at page 14, line 34 skipping to change at page 15, line 16
1. The current local RIB is invalidated. The local RIB is built 1. The current local RIB is invalidated. The local RIB is built
again from scratch. The existing routing entries are preserved again from scratch. The existing routing entries are preserved
for comparision to determine changes that need to be installed in for comparision to determine changes that need to be installed in
the global RIB. the global RIB.
2. The computing router's Node NLRI is installed in the local RIB 2. The computing router's Node NLRI is installed in the local RIB
with a cost of 0 and as as the sole entry in the candidate list. with a cost of 0 and as as the sole entry in the candidate list.
3. The Node NLRI with the lowest cost is removed from the candidate 3. The Node NLRI with the lowest cost is removed from the candidate
list for processing. The Node corresponding to this NLRI will be list for processing. If the BGP-LS Node attribute includes an
referred to as the Current Node. If the candidate list is empty, SPF Status TLV (Section 4.1.2) indicating the node is
the SPF calculation has completed and the algorithm proceeds to unreachable, the Node NLRI is ignored and the next lowest cost
step 6. Node NLRI is selected from candidate list. The Node
corresponding to this NLRI will be referred to as the Current
Node. If the candidate list is empty, the SPF calculation has
completed and the algorithm proceeds to step 6.
4. All the Prefix NLRI with the same Node Identifiers as the Current 4. All the Prefix NLRI with the same Node Identifiers as the Current
Node will be considered for installation. The cost for each Node will be considered for installation. The cost for each
prefix is the metric advertised in the Prefix NLRI added to the prefix is the metric advertised in the Prefix NLRI added to the
cost to reach the Current Node. cost to reach the Current Node.
* If the BGP-LS Prefix attribute includes an BGP-SPF Status TLV * If the BGP-LS Prefix attribute includes an SPF Status TLV
indicating the prefix is unreachable, the BGP-LS Prefix NLRI indicating the prefix is unreachable, the BGP-LS Prefix NLRI
is considered unreachable and the next BGP-LS Prefix NLRI is is considered unreachable and the next BGP-LS Prefix NLRI is
examined. examined.
* If the prefix is in the local RIB and the cost is greater than * If the prefix is in the local RIB and the cost is greater than
the Current route's metric, the Prefix NLRI does not the Current route's metric, the Prefix NLRI does not
contribute to the route and is ignored. contribute to the route and is ignored.
* If the prefix is in the local RIB and the cost is less than * If the prefix is in the local RIB and the cost is less than
the current route's metric, the Prefix is installed with the the current route's metric, the Prefix is installed with the
skipping to change at page 15, line 26 skipping to change at page 16, line 11
Node will be considered for installation. Each link will be Node will be considered for installation. Each link will be
examined and will be referred to in the following text as the examined and will be referred to in the following text as the
Current Link. The cost of the Current Link is the advertised Current Link. The cost of the Current Link is the advertised
metric in the Link NLRI added to the cost to reach the Current metric in the Link NLRI added to the cost to reach the Current
Node. Node.
* Optionally, the prefix(es) associated with the Current Link * Optionally, the prefix(es) associated with the Current Link
are installed into the local RIB using the same rules as were are installed into the local RIB using the same rules as were
used for Prefix NLRI in the previous steps. used for Prefix NLRI in the previous steps.
* If the current Node NLRI attributes includes the SPF status
TLV (Section 4.1.2) and the status indicates that the Node
doesn't support transit, the next link for the current node is
processed.
* The Current Link's endpoint Node NLRI is accessed (i.e., the * The Current Link's endpoint Node NLRI is accessed (i.e., the
Node NLRI with the same Node identifiers as the Link Node NLRI with the same Node identifiers as the Link
endpoint). If it exists, it will be referred to as the endpoint). If it exists, it will be referred to as the
Endpoint Node NLRI and the algorithm will proceed as follows: Endpoint Node NLRI and the algorithm will proceed as follows:
+ If the BGP-LS Link NLRI includes an BGP-SPF Status TLV + If the BGP-LS Link NLRI attribute includes an SPF Status
indicating the link is down, the BGP-LS Link NLRI is TLV indicating the link is down, the BGP-LS Link NLRI is
considered down and the next BGP-LS Link NLRI is examined. considered down and the next BGP-LS Link NLRI is examined.
+ All the Link NLRI corresponding the Endpoint Node NLRI will + All the Link NLRI corresponding the Endpoint Node NLRI will
be searched for a back-link NLRI pointing to the current be searched for a back-link NLRI pointing to the current
node. Both the Node identifiers and the Link endpoint node. Both the Node identifiers and the Link endpoint
identifiers in the Endpoint Node's Link NLRI must match for identifiers in the Endpoint Node's Link NLRI must match for
a match. If there is no corresponding Link NLRI a match. If there is no corresponding Link NLRI
corresponding to the Endpoint Node NLRI, the Endpoint Node corresponding to the Endpoint Node NLRI, the Endpoint Node
NLIR fails the bi-directional connectivity test and is not NLIR fails the bi-directional connectivity test and is not
processed further. processed further.
skipping to change at page 17, line 21 skipping to change at page 18, line 10
Consequently, local link failures should always be given priority Consequently, local link failures should always be given priority
over updates (e.g., withdrawing all routes learned on a session) in over updates (e.g., withdrawing all routes learned on a session) in
order to ensure the highest priority propagation and optimal order to ensure the highest priority propagation and optimal
convergence. convergence.
An IGP such as OSPF [RFC2328] will stop using the link as soon as the An IGP such as OSPF [RFC2328] will stop using the link as soon as the
Router-LSA for one side of the link is received. With normal BGP Router-LSA for one side of the link is received. With normal BGP
advertisement, the link would continue to be used until the last copy advertisement, the link would continue to be used until the last copy
of the BGP-LS Link NLRI is withdrawn. In order to avoid this delay, of the BGP-LS Link NLRI is withdrawn. In order to avoid this delay,
the originator of the Link NLRI will advertise a more recent version the originator of the Link NLRI will advertise a more recent version
of the BGP-LS Link NLRI including the BGP-SPF Status TLV of the BGP-LS Link NLRI including the SPF Status TLV Section 4.2.2
Section 4.2.2 indicating the link is down with respect to BGP-SPF. indicating the link is down with respect to BGP SPF. After some
After some configurable period of time, e.g., 2-3 seconds, the BGP-LS configurable period of time, e.g., 2-3 seconds, the BGP-LS Link NLRI
Link NLRI can be withdrawn with no consequence. If the link becomes can be withdrawn with no consequence. If the link becomes available
available in that period, the originator of the BGP-LS LINK NLRI will in that period, the originator of the BGP-LS LINK NLRI will simply
simply advertise a more recent version of the BGP-LS Link NLRI advertise a more recent version of the BGP-LS Link NLRI without the
without the BGP-SPF status TLV in the BGP-LS Link Attributes. SPF Status TLV in the BGP-LS Link Attributes.
Similarily, when a prefix becomes unreachable, a more recent version Similarily, when a prefix becomes unreachable, a more recent version
of the BGP-LS Prefix NLRI will be advertised with the BGP-SPF status of the BGP-LS Prefix NLRI will be advertised with the SPF Status TLV
TLV Section 4.2.3 indicating the prefix is unreachable in the BGP-LS Section 4.3.1 indicating the prefix is unreachable in the BGP-LS
Prefix Attributes and the prefix will be considered unreachable with Prefix Attributes and the prefix will be considered unreachable with
respect to BGP SPF. After some configurable period of time, e.g., respect to BGP SPF. After some configurable period of time, e.g.,
2-3 seconds, the BGP-LS Prefix NLRI can be withdrawn with no 2-3 seconds, the BGP-LS Prefix NLRI can be withdrawn with no
consequence. If the prefix becomes reachable in that period, the consequence. If the prefix becomes reachable in that period, the
originator of the BGP-LS Prefix NLRI will simply advertise a more originator of the BGP-LS Prefix NLRI will simply advertise a more
recent version of the BGP-LS Prefix NLRI without the BGP-SPF status recent version of the BGP-LS Prefix NLRI without the SPF Status TLV
TLV in the BGP-LS Prefix Attributes. in the BGP-LS Prefix Attributes.
5.6.2. Node Failure Convergence 5.6.2. Node Failure Convergence
With BGP without graceful restart [RFC4724], all the NLRI advertised With BGP without graceful restart [RFC4724], all the NLRI advertised
by node are implicitly withdrawn when a session failure is detected. by node are implicitly withdrawn when a session failure is detected.
If fast failure detection such as BFD is utilized and the node is on If fast failure detection such as BFD is utilized and the node is on
the fastest converging path, the most recent versions of BGP-LS NLRI the fastest converging path, the most recent versions of BGP-LS NLRI
may be withdrawn while these versions are in-flight on longer paths. may be withdrawn while these versions are in-flight on longer paths.
This will result the older version of the NLRI being used until the This will result the older version of the NLRI being used until the
new versions arrive and, potentially, unnecessary route flaps. new versions arrive and, potentially, unnecessary route flaps.
skipping to change at page 18, line 23 skipping to change at page 19, line 13
BGP peers as specified in [RFC7606]. When discarding a Node NLRI BGP peers as specified in [RFC7606]. When discarding a Node NLRI
with malformed TLV, a BGP speaker SHOULD log an error for further with malformed TLV, a BGP speaker SHOULD log an error for further
analysis. analysis.
6. IANA Considerations 6. IANA Considerations
This document defines an AFI/SAFI for BGP-LS SPF operation and This document defines an AFI/SAFI for BGP-LS SPF operation and
requests IANA to assign the BGP-LS/BGP-LS-SPF (AFI 16388 / SAFI TBD1) requests IANA to assign the BGP-LS/BGP-LS-SPF (AFI 16388 / SAFI TBD1)
as described in [RFC4750]. as described in [RFC4750].
This document also defines four attribute TLVs for BGP LS NLRI. We This document also defines five attribute TLVs for BGP-LS NLRI. We
request IANA to assign TLVs for the SPF capability, Sequence Number, request IANA to assign types for the SPF capability TLV, Sequence
IPv4 Link Prefix-Length, and IPv6 Link Prefix-Length from the "BGP-LS Number TLV, IPv4 Link Prefix-Length TLV, IPv6 Link Prefix-Length TLV,
Node Descriptor, Link Descriptor, Prefix Descriptor, and Attribute and SPF Status TLV from the "BGP-LS Node Descriptor, Link Descriptor,
TLVs" Registry. Prefix Descriptor, and Attribute TLVs" Registry.
7. Security Considerations 7. Security Considerations
This extension to BGP does not change the underlying security issues This extension to BGP does not change the underlying security issues
inherent in the existing [RFC4271], [RFC4724], and [RFC7752]. inherent in the existing [RFC4271], [RFC4724], and [RFC7752].
8. Management Considerations 8. Management Considerations
This section includes unique management considerations for the BGP-LS This section includes unique management considerations for the BGP-LS
SPF address family. SPF address family.
skipping to change at page 19, line 16 skipping to change at page 20, line 9
total number of SPF computations of each type and the total number of total number of SPF computations of each type and the total number of
SPF triggering events. Additionally, to troubleshoot SPF scheduling SPF triggering events. Additionally, to troubleshoot SPF scheduling
and backoff [RFC8405], the current SPF backoff state, remaining time- and backoff [RFC8405], the current SPF backoff state, remaining time-
to-learn, remaining holddown, last trigger event time, last SPF time, to-learn, remaining holddown, last trigger event time, last SPF time,
and next SPF time should be available. and next SPF time should be available.
9. Acknowledgements 9. Acknowledgements
The authors would like to thank Sue Hares, Jorge Rabadan, Boris The authors would like to thank Sue Hares, Jorge Rabadan, Boris
Hassanov, Dan Frost, and Fred Baker for their review and comments. Hassanov, Dan Frost, and Fred Baker for their review and comments.
Thanks to Chaitanya Yadlapalli and Pushpais Sarkar for discussions on
preventing a BGP SPF Router from being used for non-local traffic
(i.e., transit traffic).
The authors extend special thanks to Eric Rosen for fruitful The authors extend special thanks to Eric Rosen for fruitful
discussions on BGP-LS SPF convergence as compared to IGPs. discussions on BGP-LS SPF convergence as compared to IGPs.
10. Contributors 10. Contributors
In addition to the authors listed on the front page, the following In addition to the authors listed on the front page, the following
co-authors have contributed to the document. co-authors have contributed to the document.
Derek Yeung Derek Yeung
 End of changes. 27 change blocks. 
67 lines changed or deleted 109 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/