Archive
Juniper Employee , Juniper Employee Juniper Employee
Archive
Per-prefix LFA
Apr 9, 2020

Introduction

 

In previous articles at #TheRoutingChurn, such as LFA analysis with WANDL - Part I or LFA analysis with WANDL - Part II (topology refinement), we have reviewed academic aspects and analyzed the Loop Free Alternates (LFA) or IP Fast Reroute (FRR) applicability for a given network with diverse simulation options.

 

I am covering now some concrete Junos OS tidbits in our usual Junosphere topology in the coming posts to understand the particular influence of certain LFA features.

 

Herewith I am using first the per-prefix-calculation extension for LFA to illustrate where it makes more sense to apply it and for which use cases.

 

Where is per-prefix LFA really applicable with Junos OS? Where does it really make sense? Have a look at this post and please let us know what you think about it!

 

About the Junos OS LFA implementation

 

The Junos OS started to offer initial Loop Free Alternates (LFA) mechanisms based on [RFC5286] back in 9.5 for the IS-IS protocol first, extending it to OSPF later and implementing other enhancements over latest releases

 

The basic configuration options are very well summarized under http://www.juniper.net/techpubs/en_US/junos14.2/topics/topic-map/isis-link-protection.html with a simple example that gathers configuration steps and command outputs.

 

I also highly recommend and strongly encourage reading the Understanding and Deploying Loop-Free Alternate Feature implementation guide from my colleague Christian Graf (http://kb.juniper.net/InfoCenter/index?page=content&id=TN54), that provides an accurate theoretical overview with some operational examples based on Junos OS.

 

Scaling through a tracklist

 

[RFC5286] Section 3 defines the basic backup path calculation methodology and mentions some scaling concerns when implementing the algorithm with the known route inequalities for all neighbors. 

 

In a large network or IGP domain, state consumption for backup path calculations on behalf of all neighbors and considering Shared-Risk Link Group (SRLG) intersections for all these cases could become a concern regarding control-plane CPU utilization, especially in largely meshed topologies with a high number of neighbor adjacencies.

 

The Junos OS implements a tracklist concept to optimize the LFA implementation and avoid state explosion. With this tracklist concept, each system tracks each node towards a given destination D when using a certain neighbor N as primary path next hop. 

 

Instead of performing a full Routing Information Base (RIB) walk upon topological changes, Junos OS implements a splay tree approach for all LFA candidate prefixes from a route with specific SPF version numbers. A separate tree is created per route and changes are tracked on all these candidate prefixes by traversing the splay tree and updating the state upon topology changes.

 

This mechanism allows the enforcement of same [RFC5286] route inequality results and Section 3 calculation requirements but leverages the calculation by just needing to perform linear walks of N entries, instead of N*log(N) operations. By keeping record of (and updating) all these candidate prefixes, it ensures that the backup path for each rerouting neighbor N yields a positive result for loop-free forwarding and a closer distance in the end.

 

Also, by using this tracklist concept, if a system detects some duplicated identities in a certain LFA route calculation for a backup path, it can rule out that path because of loop detection.

 

In a nutshell, this implementation provides same loop-free backup path calculation results from the main [RFC5286] route inequalities and allows more efficient resource consumption for largely scaled networks.

 

Per-prefix LFA

 

[RFC5286] Section 6.1 covers a specific LFA use case for multi-homed prefixes:

 

   An SPF-like computation is run for each topology, which corresponds
   to a particular OSPF area or IS-IS level.  The IGP needs to determine
   loop-free alternates to multi-homed routes.  Multi-homed routes occur
   for routes obtained from outside the routing domain by multiple
   routers, for subnets on links where the subnet is announced from
   multiple ends of the link, and for routes advertised by multiple
   routers to provide resiliency.

   Figure 6 demonstrates such a topology.  In this example, the shortest
   path to reach the prefix p is via E.  The prefix p will have the link
   to E as its primary next-hop.  If the alternate next-hop for the
   prefix p is simply inherited from the router advertising it on the
   shortest path to p, then the prefix p's alternate next-hop would be
   the link to C.  This would provide link protection, but not the node
   protection that is possible via A.


                      5   +---+  8   +---+  5  +---+
                    ------| S |------| A |-----| B |
                    |     +---+      +---+     +---+
                    |       |                    |
                    |     5 |                  5 |
                    |       |                    |
                  +---+ 5 +---+   5       7    +---+
                  | C |---| E |------ p -------| F |
                  +---+   +---+                +---+

                       Figure 6: Multi-Homed Prefix

   To determine the best protection possible, the prefix p can be
   treated in the SPF computations as a node with unidirectional links
   to it from those routers that have advertised the prefix.  Such a
   node need never have its links explored, as it has no out-going
   links.

   [...]

   A router SHOULD compute the alternate next-hop for an IGP multi-homed
   prefix by considering alternate paths via all routers that have
   announced that prefix.

 

The original specification is therefore expanded to cover not only node representations, but also multi-homed prefixes.  And it is recommended to cover this type of computation as well.

 

In this case, the scaling concerns described above make even more sense, as per-prefix granularity, instead of per-node granularity is required! Depending on the network topology, and especially IGP layers and leaking policies across these boundaries, this requirement may become a real major performance difference.

 

How does this feature get activated in Junos OS?

 

Per-prefix LFA activation in Junos OS is a global non-intrusive per-prefix-calculation extension command for the IGP. Considering IS-IS in this case:

[edit protocols isis]
backup-spf options {
per-prefix-calculation;}

Just by globally enforcing this command, per-prefix granularity is activated as per [RFC5286] Section 6.1. Let's have a look now at where it actually makes more sense to configure it...

 

Examples with Junosphere: per-prefix LFA


Rather than picking up an LFA appealing topology with specific metric values for best coverage, let's come back to our original worst-case scenario in our usual Junosphere setup with multiple parallel metric values and Equal Cost MultiPath (ECMP) next-hop structures:

LFA-topology-stage1.jpg

 And in terms of metrics for IS-IS L1 Areas and L2 backbone:

 

WANDL-initial-ISIS-L1.png

 

WANDL-initial-ISIS-L2.png

 

 

 

 

 

Let's focus on a representative use case from [RFC5286] Section 6.1 for a multi-homed prefix, namely the IS-IS L1 Area including R1, R2, R3 and R4.

 

In this case, R3 and R4 act as IS-IS L1L2 systems and leak other router loobacks from the L2 backbone to the L1 Area as per best-practice policy for optimal routing purposes. We can evaluate the [RFC5286] route inequality cases, but let's focus on R24's reachability across these both systems by looking at R3 and R4 IS-IS L1 LSPs:

 

juniper@R1> show isis database R3 detail    
IS-IS level 1 link-state database:

R3.00-00 Sequence: 0x2f, Checksum: 0xfdd, Lifetime: 59808 secs
   IS neighbor: R1.00                         Metric:       50
   IP prefix: 192.168.1.0/30                  Metric:       50 Internal Up
   IP prefix: 192.168.255.3/32                Metric:        0 Internal Up
   IP prefix: 192.168.255.6/32                Metric:       60 Internal Down
   IP prefix: 192.168.255.7/32                Metric:       10 Internal Down
   IP prefix: 192.168.255.10/32               Metric:       20 Internal Down
   IP prefix: 192.168.255.11/32               Metric:       30 Internal Down
  [...]
   IP prefix: 192.168.255.21/32               Metric:       60 Internal Down
   IP prefix: 192.168.255.22/32               Metric:      110 Internal Down
   IP prefix: 192.168.255.23/32               Metric:      100 Internal Down
   IP prefix: 192.168.255.24/32               Metric:      110 Internal Down
   IP prefix: 192.168.255.25/32               Metric:      110 Internal Down
                                        
IS-IS level 2 link-state database:

juniper@R1> show isis database R4 detail    
IS-IS level 1 link-state database:

R4.00-00 Sequence: 0x35, Checksum: 0x4323, Lifetime: 59885 secs
   IS neighbor: R2.00                         Metric:       50
   IS neighbor: R5.00                         Metric:       50
   IP prefix: 192.168.2.0/30                  Metric:       50 Internal Up
   IP prefix: 192.168.7.0/30                  Metric:       50 Internal Up
   IP prefix: 192.168.255.4/32                Metric:        0 Internal Up
   IP prefix: 192.168.255.6/32                Metric:       70 Internal Down
   IP prefix: 192.168.255.7/32                Metric:       20 Internal Down
   IP prefix: 192.168.255.10/32               Metric:       30 Internal Down
   IP prefix: 192.168.255.11/32               Metric:       20 Internal Down
  [...]
   IP prefix: 192.168.255.21/32               Metric:       50 Internal Down
   IP prefix: 192.168.255.22/32               Metric:      100 Internal Down
   IP prefix: 192.168.255.23/32               Metric:      110 Internal Down
   IP prefix: 192.168.255.24/32               Metric:      110 Internal Down
   IP prefix: 192.168.255.25/32               Metric:      100 Internal Down

IS-IS level 2 link-state database:


This network topology is highly symmetrical and mostly divided in 2 planes, without specific LFA-attractive V-shapes... with the exception of R24! R24 is the only exception that keeps the same IGP metric to both planes inside its area:

LFA-topology-stage1.jpg

Because R24 is advertised from R3 and R4 with the same metric, its loopback effectively becomes the most eligible muti-homed prefix to benefit from the per-prefix-calculation extension, as backup SPF path calculations from R1 or R2 surely traverse the other plane and do not share fate or loop back.

 

Having a look at initial IS-IS backup coverage and specific R24 path installation in R1:

 

juniper@R1> show isis backup coverage
Backup Coverage:
Topology        Level   Node    IPv4    IPv6    CLNS
IPV4 Unicast        1   0.00%  23.33%   0.00%   0.00%
IPV4 Unicast        2   0.00%   0.00%   0.00%   0.00%

 

juniper@R1> show route 192.168.255.24/32 extensive

inet.0: 39 destinations, 41 routes (39 active, 0 holddown, 0 hidden)
192.168.255.24/32 (1 entry, 1 announced)
        State: <FlashAll>
TSI:
KRT in-kernel 192.168.255.24/32 -> {192.168.1.2}
        *IS-IS  Preference: 18
                Level: 1
                Downbit: 1
                Next hop type: Router, Next hop index: 596
                Address: 0x9859024
                Next-hop reference count: 36
                Next hop: 192.168.1.2 via ge-0/0/1.0 weight 0x1, selected
                Session Id: 0x2
                State: <Active Int>
                Local AS: 65000
                Age: 1:24       Metric: 160
[...]

inet.3: 24 destinations, 24 routes (24 active, 0 holddown, 0 hidden)
                                        
192.168.255.24/32 (1 entry, 1 announced)
        State: <FlashAll>
        *LDP    Preference: 9
                Next hop type: Router
                Address: 0x9858400
                Next-hop reference count: 6
                Next hop: 192.168.1.2 via ge-0/0/1.0 weight 0x1, selected
                Label operation: Push 300144
                Label TTL action: prop-ttl
                Load balance label: Label 300144: None;
                Session Id: 0x0
                State: <Active Int>
                Local AS: 65000
                Age: 1:24       Metric: 160
[...]

juniper@R1> show route forwarding-table able destination 192.168.255.24/32 extensive                  
Routing table: default.inet [Index 0]
Internet:
    
Destination:  192.168.255.24/32
  Route type: user                  
  Route reference: 0                   Route interface-index: 0   
  Multicast RPF nh index: 0             
  Flags: sent to PFE, rt nh decoupled  
  Nexthop: 192.168.1.2
  Next-hop type: unicast               Index: 596      Reference: 40   
  Next-hop interface: ge-0/0/1.0   

[...]

 

Activating per-prefix LFA

 

Let's activate now per-prefix-calculation at R1 and have a look at the same commands:

 

[edit]
juniper@R1# set protocols isis backup-spf-options per-prefix-calculation

[edit]
juniper@R1# commit and-quit
[...]
juniper@R1> show isis backup coverage
Backup Coverage:
Topology        Level   Node    IPv4    IPv6    CLNS
IPV4 Unicast        1   0.00%  26.67%   0.00%   0.00%
IPV4 Unicast        2   0.00%   0.00%   0.00%   0.00%

Note that due to per-prefix LFA activation, the IPv4 prefix coverage has increased. And this happens inside an L1 IS-IS Area that, due to purely symmetric costs and squared form, the node coverage is actually 0% due to Path loops.

 

Having a look at R24's loopback address, we can see how a new 0xf000 weight has been programmed for the route:

 

juniper@R1> show route 192.168.255.24/32 extensive                          

inet.0: 39 destinations, 41 routes (39 active, 0 holddown, 0 hidden)
192.168.255.24/32 (1 entry, 1 announced)
        State: <FlashAll>
TSI:
KRT in-kernel 192.168.255.24/32 -> {192.168.1.2, 192.168.0.2}
        *IS-IS  Preference: 18
                Level: 1
                Downbit: 1
                Next hop type: Router, Next hop index: 1048574
                Address: 0x959465c
                Next-hop reference count: 3
                Next hop: 192.168.1.2 via ge-0/0/1.0 weight 0x1, selected
                Session Id: 0x2
                Next hop: 192.168.0.2 via ge-0/0/0.0 weight 0xf000
                Session Id: 0x1
                State: <Active Int>
                Local AS: 65000
[...]
                                        
inet.3: 24 destinations, 24 routes (24 active, 0 holddown, 0 hidden)

192.168.255.24/32 (1 entry, 1 announced)
        State: <FlashAll>
        *LDP    Preference: 9
                Next hop type: Router
                Address: 0x95961f8
                Next-hop reference count: 6
                Next hop: 192.168.1.2 via ge-0/0/1.0 weight 0x1, selected
                Label operation: Push 300144
                Label TTL action: prop-ttl
                Load balance label: Label 300144: None;
                Session Id: 0x0
                Next hop: 192.168.0.2 via ge-0/0/0.0 weight 0xf000
                Label operation: Push 300144
                Label TTL action: prop-ttl
                Load balance label: Label 300144: None;
[...]

 

The Junos OS routing daemon (RPD) programs a backup next-hop for eligible destinations, like this one, by using a higher weight value. This higher weight is then propagated to kernel and down to the forwarding-plane layer, and used as instrument to enforce local restoration at this level:

 

juniper@R1> show route forwarding-table destination 192.168.255.24/32 extensive    
Routing table: default.inet [Index 0]
Internet:
 
Destination:  192.168.255.24/32
  Route type: user                  
  Route reference: 0                   Route interface-index: 0   
  Multicast RPF nh index: 0             
  Flags: sent to PFE, rt nh decoupled  
  Next-hop type: unilist               Index: 1048574  Reference: 2    
  Nexthop: 192.168.1.2
  Next-hop type: unicast               Index: 596      Reference: 40   
  Next-hop interface: ge-0/0/1.0    Weight: 0x1  
  Nexthop: 192.168.0.2
  Next-hop type: unicast               Index: 593      Reference: 32   
  Next-hop interface: ge-0/0/0.0    Weight: 0xf00

LFA-backup-path-installation.jpg

With this mechanism, the Packet Forwarding Engine (PFE) has direct instantiation of the LFA backup path and can automatically react against local failures before this outage notification reaches the control plane.

 

Per-prefix LFA use cases

 

We have seen in the previous example that a representative use case from a [RFC5286] Section 6.1 multi-homed prefix takes place upon redundant IGP route leaking across layers.

 

Note that R24 becomes significant in this topology because it is the only symmetrically positioned router towards both layers (kind of V-shape) and IGP metrics are kept when leaking routes from L1 to L2 first, and then back to L1 in this case. Per-prefix LFA applicability would be globally much higher if access layers had a different symmetrical placement.

 

Another meaningful use case would be a simultaneous route redistribution into the IGP in more than a single Autonomous System Border Router (ASBR). Because these external prefixes may get injected into the IGP in more than one place, there will be more than a single best path prefix originator in the topology. Per-prefix LFA would provide protection in this case.

 

But a more relevant application is egress protection for VPN services, as described under http://www.juniper.net/documentation/en_US/junos14.2/topics/topic-map/mpls-egress-protection-layer-3.... This implementation is defined by draft-minto-2547-egress-node-fast-protection-03 and provides a fast protection mechanism for VPN services upon egress node failure, by enforcing local repair actions at routers upstream to the egress nodes.

 

In order to be able to associate such protection to multiple VPNs, a common Context Identifier is required to be configured as a multi-homed IPv4 address in several egress nodes (à la anycast). Upstream routers to these nodes could provide local restoration upon detecting last-hop failures and rerouting with per-prefix LFA. Per-prefix LFA at these penultimate routers become a configuration requirement for this mechanism, as depicted in http://www.juniper.net/documentation/en_US/junos14.2/topics/topic-map/mpls-egress-protection-layer-3....

 

This interesting use case deserves more than a single future post 😉 but I just wanted to mention here that per-prefix LFA is a fundamental building block of that solution.

 

Conclusions


Per-prefix LFA activation in Junos OS is simple, seamless and generally benefitial: a per-prefix-calculation extension
added in the IGP stanza that applies globally to all eligible prefixes. It can be considered a best practice when enforcing LFA.

In this article I have reviewed some details from the Junos OS LFA implementation with regards to scaling and illustrated a per-prefix LFA scenario, aligned with a multi-homed prefix as per [RFC5286] Section 6.1
. Such multi-homed prefixes can be considered use cases for per-prefix LFA applicability, due to:

  • route leaking across hierarchies in redundant IGP border systems
  • multi-homed route redistribution into the IGP in more than a single ASBR
  • anycast services
  • egress protection for VPN services

and maybe some readers can surely find some other applications!

If that is the case or you have some feedback, please let us know and share your thoughts by posting a comment or via twitter #TheRoutingChurn !
 

 

0 Kudos
Aug 27, 2017
Carloabeds
RRrrrrrrrrrr.......
Apr 9, 2020

There seems to be some confusion with the term "Per-prefix LFA". Been reading "MPLS in the SDN Era - Chapter 18
Transit Fast Restoration Based on the IGP" and the authors state that Junos does Per-prefix LFA by default. They even go to the extend of saying the the configuration stanza below does not turn on Per-prefix LFA:

 

    [edit protocols isis]
    backup-spf options {
per-prefix-calculation;}

 

Can someone clarify this?

Feedback