OSPF Extensions for Precomputed Fast Reroute

Abstract

This document proposes an enhancement to OSPF (Open Shortest Path First) that enables routers to precompute backup loop-free alternate (LFA) paths for fast reroute (FRR) in case of primary path failures. This mechanism improves convergence time and network stability by eliminating the delay associated with on-demand SPF recalculation during failure events.¶

1. Terminology

SPT - Shortest Path Tree¶

FRR - Fast Reroute¶

LFA - Loop-Free Alternate¶

iSPF - Incremental SPF¶

2. Design Overview

Each OSPF router computes its primary SPT as per standard operation. In addition, the router precomputes alternate paths to selected destinations, simulating failure scenarios (e.g., primary next-hop failure). These alternate paths are validated for loop-freeness using LFA criteria and stored in a local cache for immediate use.¶

3. Detailed Use Case and Diagram

Consider a simple OSPF topology where R1 is connected to R2, R3, and R4. The destination prefix 10.0.0.0/24 is reachable via R2 under normal conditions. The enhancement involves precomputing a backup path via R3.¶

        +-----+        +-----+
        | R2  |--------| R5  |
        +-----+        +-----+
         /                \
        /                  \
  +-----+                    +-----+
  | R1  |--------------------| R3  |
  +-----+                    +-----+
        \                  /
         \                /
        +-----+        +-----+
        | R4  |--------| R6  |
        +-----+        +-----+

Steps:¶

1. R1 computes shortest path to 10.0.0.0/24 via R2.¶

2. R1 simulates failure of R1–R2 link and recomputes SPF excluding that link.¶

3. R3 is validated as an LFA-capable neighbor and cached as a backup next-hop.¶

4. On failure detection (e.g., via BFD), R1 switches to the cached path via R3.¶

4. Precomputation Process

For each destination:¶

a. Identify alternate neighbors not used in the primary path.¶

b. Simulate primary link failure.¶

c. Run SPF on the altered topology.¶

d. Validate for loop-freeness.¶

e. Store valid backup path in a local cache.¶

5. Protocol Extensions

No OSPF LSA format changes are required. Optionally, a new Router Information LSA TLV may advertise precomputed FRR capability.¶

6. Proposed Opaque LSA Format: Precomputed Backup Path Advertisement

In implementations where it is desirable to advertise backup paths to neighbors or controllers, an Opaque LSA format may be introduced.¶

TLV Type: TBD2¶

Value: List of destinations and corresponding backup next-hops¶

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Type=TBD2 |             Length                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                Destination Prefix (IPv4/IPv6)                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 Backup Next-Hop Router ID                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

7. Router Information Opaque LSA

A TLV may indicate support for precomputed backup paths.¶

TLV Type: TBD1¶

Length: 1 byte¶

Value: 0x01 indicates support¶

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Type=TBD1 |    Length=1   |      Value=0x01               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

8. Comparison with Existing Mechanisms

- OSPF LFA (RFC 5286): on-the-fly LFA, not proactive¶

- NotVia (RFC 6981): complex, encapsulation required¶

- TI-LFA (RFC 8665): segment-routing-based, not applicable to classic OSPF¶

- Proposed: simple, proactive, no encapsulation or SR dependencies¶

9. Interaction with BFD

Bidirectional Forwarding Detection (BFD) can be used in conjunction with this proposal to detect failures quickly. Upon BFD session failure, the router can immediately switch to the precomputed alternate path.¶

10. Scalability Considerations

The number of precomputed backup entries should be limited to avoid overwhelming memory. Incremental SPF (iSPF) techniques SHOULD be used. Alternate paths SHOULD be computed selectively, and aging mechanisms MAY be applied.¶

11. Security Considerations

This mechanism does not introduce new protocol messages and inherits OSPF's security properties. However, LSAs used in precomputation MUST be validated to prevent path manipulation by attackers. Authentication and origin validation are RECOMMENDED.¶

12. IANA Considerations

This document makes no requests of IANA at this time.¶

13. Acknowledgements

The authors thank members of the IETF OSPF Working Group for their feedback and suggestions on earlier versions of this draft.¶

14. Contributors

Srinivasa Mohan Kumar Varigonda <sri.mohan@samsung.com>¶

Veerendranatha Reddy Vallem <vallemr@tejasnetworks.com>¶

15. Appendix A: Example CLI Behavior

<CODE BEGINS>¶

router ospf 1
  fast-reroute precompute
  backup-paths enable
  timers lfa reevaluation 300

<CODE ENDS>¶

16. Appendix B: Future Work

- Support for SR-MPLS and SRv6 backup path precomputation.¶

- Incorporation of topology constraints in alternate path selection.¶

17. Appendix C: Change Log

draft-kumarvarigonda-ospf-precomputed-frr-00¶

- Initial version including use case, diagram, and precomputation process.¶

- Added example Opaque LSA encoding and scalability discussion.¶

- Included proposed backup path advertisement format.¶

- Added comparison with existing mechanisms section.¶