IGP Reverse SPF Algorithm
draft-ietf-lsr-igp-reverse-spf-algo-01

LSR Working Group                                              P. Psenak
Internet-Draft                                                   J. Horn
Intended status: Standards Track                             L. Ginsberg
Expires: 20 March 2026                                     Cisco Systems
                                                       16 September 2025

                       IGP Reverse SPF Algorithm
                 draft-ietf-lsr-igp-reverse-spf-algo-01

Abstract

   IANA has set up a subregistry called "IGP Algorithm Type" under the
   "Interior Gateway Protocol (IGP) Parameters" registry.  This draft
   introduces a new algorithm type which utilizes the cost in the
   reverse direction on each link.

   This document also discusses using this new algorithm type in
   combination with IGP Flexible Algorithm to compute constraint-based
   paths.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 20 March 2026.

Copyright Notice

   Copyright (c) 2025 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components

Psenak, et al.            Expires 20 March 2026                 [Page 1]
Internet-Draft          IGP Reverse SPF Algorithm         September 2025

   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Requirements Language . . . . . . . . . . . . . . . . . . . .   3
   3.  Use Case Example  . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Flexible Algorithm Usage of Reverse Shortest Path First
           Algorithm . . . . . . . . . . . . . . . . . . . . . . . .   3
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   4
     5.1.  IGP Algorithm Types Registry  . . . . . . . . . . . . . .   4
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   4
   7.  Normative References  . . . . . . . . . . . . . . . . . . . .   4
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   5

1.  Introduction

   Existing IGP Algorithm types as defined in the IANA IGP Algorithm
   Types registry created by [RFC8665] utilize metrics in the forward
   direction on each link.  But there are use cases (discussed later in
   this document) where utilizing the metric in the reverse direction on
   each link is desirable.

   This document defines a new IGP Algorithm type which uses link
   metrics in the reverse direction.

   An IGP Flexible Algorithm as specified in [RFC9350] computes a
   constraint-based path.  It supports various metric types, including
   native Interior Gateway Protocol (IGP) metric, Min Unidirectional
   Link Delay, Traffic Engineering Default Metric, all defined in
   [RFC9350].  In addition, Bandwidth Metric and User defined metrics
   are defined in [I-D.ietf-lsr-flex-algo-bw-con].

   Existing IGP Flexible Algorithm use cases specify an IGP Algorithm
   Type where all these link metric types are used by Flexible Algorithm
   in the forward direction, e.g., the direction in which the link is
   added to the topology during the computation.

   This document extends IGP Flexible Algorithm to be able to use the
   IGP Algorithm Type which specifies using the link metric in a reverse
   direction.

   Usage of the Reverse Shortest Path First (RSPF) algorithm outside of
   the IGP Flexible Algorithm is outside of the scope of this draft.

Psenak, et al.            Expires 20 March 2026                 [Page 2]
Internet-Draft          IGP Reverse SPF Algorithm         September 2025

2.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in BCP
   14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

3.  Use Case Example

   A multicast tree is typically established from the receivers (R)
   towards the multicast source (S).  When determining the path for
   traffic originating from S towards R, a shortest path from R to S is
   often used.  When the metric on all links is symmetric, e.g. equal in
   both directions, this provides the correct outcome.

   With the introduction of IGP Flexible Algorithms, additional metrics
   become available for calculating the shortest path.  One commonly
   employed metric is latency, which often exhibits asymmetry.
   Multicast traffic is frequently required to take the path with the
   minimal latency.  In the presence of the asymmetric link latency, the
   usage of the reverse link latency is required for multicast tree
   calculation.  Failure to use the reverse link latency can result in
   multicast traffic not taking the least latency path across the
   network.

4.  Flexible Algorithm Usage of Reverse Shortest Path First Algorithm

   Flexible Algorithm Definition Sub-TLV [RFC9350] defines the Calc-Type
   field, that carries the calculation-type used by the Flexible
   Algorithm.  Values are defined in IANA "IGP Algorithm Types" registry
   defined under the "Interior Gateway Protocol (IGP) Parameters"
   registry.

   We define a new IGP Algorithm Type - Reverse Shortest Path First
   (SPF) algorithm based on link metric.  It is equivalent to the IGP
   Algorithm Type 0, but the link metric is taken from the reverse
   direction of the link.

   If the winning Flexible Algorithm Definition signals the Reverse SPF
   algorithm calculation-type, defines the metric-type other than IGP
   metric and such metric is not advertised for the link in the reverse
   direction in a topology for which the computation is done, such link
   MUST be pruned from the computation.  A metric of value 0 MUST NOT be
   assumed in such a case.  This is the application of the rule (5), as
   specified in section 13 of [RFC9350], in a reverse direction.

Psenak, et al.            Expires 20 March 2026                 [Page 3]
Internet-Draft          IGP Reverse SPF Algorithm         September 2025

5.  IANA Considerations

5.1.  IGP Algorithm Types Registry

   This document defines a new algorithm type in the IANA "IGP Algorithm
   Types" registry defined under the "Interior Gateway Protocol (IGP)
   Parameters" registry.  The "value" is suggested - to be assigned by
   IANA.

        Value   Description
        -----   ------------------------------
        2       Shortest Path First (SPF) algorithm based on reverse link metric. It's
                equivalent to standard (SPF) algorithm (IGP Algorithm Type 0), but uses
                the metric from the reverse direction of the link.

6.  Security Considerations

   This document inherits security considerations from the [RFC9350]

7.  Normative References

   [I-D.ietf-lsr-flex-algo-bw-con]
              Hegde, S., Britto, W., Shetty, R., Decraene, B., Psenak,
              P., and T. Li, "IGP Flexible Algorithms: Bandwidth, Delay,
              Metrics and Constraints", Work in Progress, Internet-
              Draft, draft-ietf-lsr-flex-algo-bw-con-22, 13 February
              2025, <https://datatracker.ietf.org/doc/html/draft-ietf-
              lsr-flex-algo-bw-con-22>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

   [RFC8665]  Psenak, P., Ed., Previdi, S., Ed., Filsfils, C., Gredler,
              H., Shakir, R., Henderickx, W., and J. Tantsura, "OSPF
              Extensions for Segment Routing", RFC 8665,
              DOI 10.17487/RFC8665, December 2019,
              <https://www.rfc-editor.org/info/rfc8665>.

Psenak, et al.            Expires 20 March 2026                 [Page 4]
Internet-Draft          IGP Reverse SPF Algorithm         September 2025

   [RFC9350]  Psenak, P., Ed., Hegde, S., Filsfils, C., Talaulikar, K.,
              and A. Gulko, "IGP Flexible Algorithm", RFC 9350,
              DOI 10.17487/RFC9350, February 2023,
              <https://www.rfc-editor.org/info/rfc9350>.

Authors' Addresses

   Peter Psenak
   Cisco Systems
   Apollo Business Center
   Mlynske nivy 43
   82109 Bratislava
   Slovakia
   Email: ppsenak@cisco.com

   Jakub Horn
   Cisco Systems
   Milpitas, CA 95035
   United States of America
   Email: jakuhorn@cisco.com

   Les Ginsberg
   Cisco Systems
   Milpitas, CA 95035
   United States of America
   Email: ginsberg@cisco.com

Psenak, et al.            Expires 20 March 2026                 [Page 5]