SR-TE Pt. 6 (Flex Algo)

Flex Algo stands for Flexible Algorithm. Every prefix SID is associated with an algorithm, with the default being algorithm 0. By using different algorithms, paths to prefix SIDs can be calculated based on other metrics and constraints besides using lowest cost.

Have you noticed in the previous articles that the Prefix-SID IGP advertisements contain an algorithm associated with them?

RP/0/RP0/CPU0:R1#show ospf database opaque-area 7.0.0.1 self-originate 
Wed Sep  7 19:11:59.534 UTC


            OSPF Router with ID (1.1.1.1) (Process ID 2)

                Type-10 Opaque Link Area Link States (Area 0)

  LS age: 303
  Options: (No TOS-capability, DC)
  LS Type: Opaque Area Link
  Link State ID: 7.0.0.1
  Opaque Type: 7
  Opaque ID: 1
  Advertising Router: 1.1.1.1
  LS Seq Number: 80000029
  Checksum: 0x95d8
  Length: 44

    Extended Prefix TLV: Length: 20
      Route-type: 1
      AF        : 0
      Flags     : 0x40
      Prefix    : 1.1.1.1/32

      SID sub-TLV: Length: 8
        Flags     : 0x0
        MTID      : 0
        Algo      : 0
        SID Index : 1

Algorithm 0 is the default IGP best path calculation algorithm. A prefix SID is an instruction to steer traffic towards the prefix using the IGP ECMP-aware best path. However, this is only because it is associated with algorithm 0 by default. We can use different algorithms to steer traffic towards a prefix SID using a completely different calculation. We can use lowest delay or include/exclude link colors just like with SR-TE policies.

Algorithms 0-127 are reserved, and 128-255 are available for you, the operator, to define and use. For example, you can choose for flex algo 128 to be the lowest delay. A router can advertise a prefix with multiple SID indexes, one for each algorithm.

One benefit of using flex algo is that the SID list can be reduced compared to using an SR-TE policy. An SR-TE policy may need to generate a SID list of length 3 or 4 to steer traffic along a TE path. However if all routers agree that flex algo #130 defines the set of constraints, then only a single SID is needed. All routers collectively calculate the best path using flex algo 130, instead of the headend calculating the path and preprogramming a list of SIDs.

Lab

On R1 let’s define flex algo #128 to mean “steer traffic along RED links only.” We’ll advertise the loopback with a prefix sid index of 1000 + R# on each router.

#R1
router ospf 2
 ! We must define the RED affinity under the IGP for flex-algo, even though it is currently present in SR-TE
 affinity-map RED bit-position 20

 ! The following defines the constraints for flex algo 128
 flex-algo 128
  affinity include-all RED 
  ! This instructs the router to advertise the flex-algo definition into the IGP
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1001 
  int Gi0/0/0/0
   affinity flex-algo RED

You can see SID index 1001 for flex algo 128 in R1’s Extended Prefix Opaque LSA.

RP/0/RP0/CPU0:R1#show ospf database opaque-area 7.0.0.1 self-originate 
Wed Sep  7 19:25:22.472 UTC


            OSPF Router with ID (1.1.1.1) (Process ID 2)

                Type-10 Opaque Link Area Link States (Area 0)

  LS age: 11
  Options: (No TOS-capability, DC)
  LS Type: Opaque Area Link
  Link State ID: 7.0.0.1
  Opaque Type: 7
  Opaque ID: 1
  Advertising Router: 1.1.1.1
  LS Seq Number: 8000002a
  Checksum: 0x5687
  Length: 56

    Extended Prefix TLV: Length: 32
      Route-type: 1
      AF        : 0
      Flags     : 0x40
      Prefix    : 1.1.1.1/32

      SID sub-TLV: Length: 8
        Flags     : 0x0
        MTID      : 0
        Algo      : 0
        SID Index : 1

      SID sub-TLV: Length: 8
        Flags     : 0x0
        MTID      : 0
        Algo      : 128
        SID Index : 1001

Additionally, the Router Information Opaque LSA includes Flex Algo 128 now:

RP/0/RP0/CPU0:R1#show ospf database opaque-area 4.0.0.0 self-originate 
Wed Sep  7 19:46:38.697 UTC


            OSPF Router with ID (1.1.1.1) (Process ID 2)

                Type-10 Opaque Link Area Link States (Area 0)

  LS age: 108
  Options: (No TOS-capability, DC)
  LS Type: Opaque Area Link
  Link State ID: 4.0.0.0
  Opaque Type: 4
  Opaque ID: 0
  Advertising Router: 1.1.1.1
  LS Seq Number: 8000002d
  Checksum: 0x8c3f
  Length: 100

    Router Information TLV: Length: 4
    Capabilities:
      Graceful Restart Helper Capable
      Stub Router Capable
      Traffic Engineering enabled area
      All capability bits: 0x70000000
          
    Segment Routing Algorithm TLV: Length: 3
      Algorithm: 0
      Algorithm: 1
      Algorithm: 128

    Segment Routing Range TLV: Length: 12
      Range Size: 8000

        SID sub-TLV: Length 3
         Label: 16000

    Node MSD TLV: Length: 2
        Type: 1, Value 10

    Segment Routing Local Block TLV: Length: 12
      Range Size: 1000

        SID sub-TLV: Length 3
         Label: 15000

    Segment Routing FAD TLV: Length: 12
      Flex Algo Number : 128
      Flex Algo Metric Type : 0
      Flex Algo Priority : 128
      Flex Algo Calc_type : 0

        FAD Include All sub-TLV: Length 4
          FAD Include All Group : 0x00100000  

    Dynamic Hostname TLV: Length: 2
      Hostname: R1

• Algorithm 0 is SPF, and algorithm 1 is strict SPF

• You can see the Flex Algo definition at the bottom

Let’s repeat this on each router in the topology:

#R2
router ospf 2
 flex-algo 128
  affinity include-all RED 
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1002
  int Gi0/0/0/0
   affinity flex-algo RED
!
router ospf 1
 affinity-map RED bit-position 20
 flex-algo 128
  affinity include-all RED 
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1002
  int Gi0/0/0/0
   affinity flex-algo RED
  int Gi0/0/0/2
   affinity flex-algo RED

#R3
router ospf 1
 affinity-map RED bit-position 20
 flex-algo 128
  affinity include-all RED 
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1003
  int Gi0/0/0/0
   affinity flex-algo RED
  int Gi0/0/0/1
   affinity flex-algo RED

#R4
router ospf 1
 affinity-map RED bit-position 20
 flex-algo 128
  affinity include-all RED 
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1004
  int Gi0/0/0/0
   affinity flex-algo RED
  int Gi0/0/0/2
   affinity flex-algo RED

#R6
router ospf 1
 affinity-map RED bit-position 20
 flex-algo 128
  affinity include-all RED 
  advertise-definition
 !
 area 0 
  int lo0
   prefix-sid algorithm 128 index 1006
  int Gi0/0/0/0
   affinity flex-algo RED

Examine R2’s LFIB. Notice that the outgoing interface for R6’s algo 0 prefix SID is the ECMP path via Gi0/0/0/1 and Gi0/0/0/3. The outgoing interface for R6’s algo 128 prefix SID is Gi0/0/0/2.

RP/0/RP0/CPU0:R2#show mpls forwarding labels 16006
Wed Sep  7 19:48:15.228 UTC
Local  Outgoing    Prefix             Outgoing     Next Hop        Bytes       
Label  Label       or ID              Interface                    Switched    
------ ----------- ------------------ ------------ --------------- ------------
16006  16006       SR Pfx (idx 6)     Gi0/0/0/3    10.2.5.5        367903      
       16006       SR Pfx (idx 6)     Gi0/0/0/1    10.2.4.4        856         

RP/0/RP0/CPU0:R2#show mpls forwarding labels 17006
Wed Sep  7 19:48:18.542 UTC
Local  Outgoing    Prefix             Outgoing     Next Hop        Bytes       
Label  Label       or ID              Interface                    Switched    
------ ----------- ------------------ ------------ --------------- ------------
17006  17006       SR Pfx (idx 1006)  Gi0/0/0/2    10.2.3.3        0

Unlike algo 0 prefix SIDs, there are no IP-to-MPLS forwarding entries in CEF for these algo 128 prefix SIDs. The only situation in which these labels will be used is when using SR-TE policies.

On R2 we’ll create the CUSTOMER_A VRF and observe the path that traffic towards the prefix 10.1.2.0/24 takes. We’ll create the same ODN definition as on R1, but instead of specifying the link affinity colors that must be included, we’ll specify that the path must use sid-algorithm 128.

#R2
vrf CUSTOMER_A
 address-family ipv4 unicast
  import route-target 100:1
  export route-target 100:1
!
int lo1
 vrf CUSTOMER_A
 ip address 2.2.2.2/32
!
segment-routing traffic-eng
 on-demand color 20
   dynamic
    sid-algorithm 128
!
router bgp 100
 vrf CUSTOMER_A
  rd 100:1
  address-family ipv4 unicast
   redistribute connected

Traffic flows via the RED path, using the prefix SID for algo 128. Only a single prefix SID needs to be imposed at R2.

RP/0/RP0/CPU0:R2#traceroute vrf CUSTOMER_A 10.1.2.1 source lo1 probe 1
Wed Sep  7 20:32:32.545 UTC

Type escape sequence to abort.
Tracing the route to 10.1.2.1

 1  10.2.3.3 [MPLS: Labels 17006/24002 Exp 0] 23 msec 
 2  10.3.4.4 [MPLS: Labels 17006/24002 Exp 0] 14 msec 
 3  10.4.6.6 [MPLS: Label 24002 Exp 0] 16 msec 
 4  100.64.0.6 13 msec

Traffic originated at R1 still uses the prefix SIDs, as the ODN definition uses a link-affinity constraint instead of flex algo constraint.

CE1#traceroute 10.1.2.1 source lo0 probe 1
Type escape sequence to abort.
Tracing the route to 10.1.2.1
VRF info: (vrf in name/id, vrf out name/id)
  1 100.64.0.1 5 msec
  2 10.1.2.2 [AS 65001] [MPLS: Labels 16003/16006/24002 Exp 0] 14 msec
  3 10.2.3.3 [MPLS: Labels 16006/24002 Exp 0] 39 msec
  4 10.3.4.4 [MPLS: Labels 16006/24002 Exp 0] 34 msec
  5 10.4.6.6 [MPLS: Label 24002 Exp 0] 28 msec
  6 100.64.0.6 15 msec

If we change the ODN definition on R1 to use flex algo 128 we will see the flex algo 128 prefix SID used.

#R1
segment-routing traffic-eng
 on-demand color 20
  dynamic
   sid-algorithm 128
   no affinity include-all name RED

RP/0/RP0/CPU0:R1#show segment-routing traffic-eng policy 
Wed Sep  7 20:46:56.319 UTC

SR-TE policy database
---------------------

Color: 20, End-point: 6.6.6.6
  Name: srte_c_20_ep_6.6.6.6
  Status:
    Admin: up  Operational: up for 00:20:31 (since Sep  7 20:26:24.490)
  Candidate-paths:
    Preference: 200 (BGP ODN) (shutdown)
      Requested BSID: dynamic
      Constraints:
        Prefix-SID Algorithm: 128
        Maximum SID Depth: 10 
      Dynamic (invalid)
        Metric Type: TE,   Path Accumulated Metric: 0 
    Preference: 100 (BGP ODN) (active) (reoptimizing)
      Requested BSID: dynamic
      PCC info:
        Symbolic name: bgp_c_20_ep_6.6.6.6_discr_100
        PLSP-ID: 6
      Constraints:
        Prefix-SID Algorithm: 128
        Maximum SID Depth: 10 
      Dynamic (pce 2.2.2.2) (valid)
        Metric Type: IGP,   Path Accumulated Metric: 4 
          17002 [Prefix-SID, 2.2.2.2]
          17006 [Prefix-SID, 6.6.6.6]

R1 does not have 17006 in its LFIB, because R1 is in a different IGP domain compared to R6. However the PCE, R2, calculated the path and passed it onto R1.

CE1#traceroute 10.1.2.1 source lo0 probe 1
Type escape sequence to abort.
Tracing the route to 10.1.2.1
VRF info: (vrf in name/id, vrf out name/id)
  1 100.64.0.1 7 msec
  2 10.1.2.2 [AS 65001] [MPLS: Labels 17006/24002 Exp 0] 33 msec
  3 10.2.3.3 [MPLS: Labels 17006/24002 Exp 0] 41 msec
  4 10.3.4.4 [MPLS: Labels 17006/24002 Exp 0] 24 msec
  5 10.4.6.6 [MPLS: Label 24002 Exp 0] 51 msec
  6 100.64.0.6 79 msec

Conclusion

You’ve now gained a deeper understanding of Prefix SIDs. The introductory definition is that a prefix SID represents the ECMP-aware IGP lowest cost path to a given prefix. The new definition is that a prefix SID represents the ECMP-aware path to a given prefix based on the algorithm for that prefix SID. Algorithm 0 is the default, which means to use basic SPF to find the shortest path based on lowest metric. The operator can define any other algorithms in the range 128-255 to create new shortest path calculations based on lowest delay or constraints. Additional algorithms are advertised in the IGP, and a given prefix can have multiple prefix SIDs associated with it, one per algorithm.

Further Reading

https://www.youtube.com/watch?v=I0_-fTmcxZU&ab_channel=SegmentRouting