Flex-Algo
A Flex-Algo is a flexible algorithm that allows you to create a separate topology and calculate paths in an IGP. It is currently used mainly on SR networks. A Flex-Algo provides a simple solution with separated routing planes, constrained TE paths, and low-delay routes, meeting differentiated requirements of various services in the 5G era.
Why Do We Need a Flex-Algo?
With the advent of the 5G era, various service applications with differentiated features will coexist, posing new requirements on network flexibility. Carriers want to define Interior Gateway Protocol (IGP) path calculation rules based on their requirements; for example, they want to forward traffic along the path with the minimum delay or exclude some links for forwarding on networks.
A traditional IGP can only use the Shortest Path First (SPF) algorithm to calculate the shortest path to a destination address on the entire network topology based on the link cost. When all packets select the shortest path with the lowest cost, the traffic paths of all services are fixed. This prevents network resources from being flexibly used.
Carriers have been exploring traffic engineering (TE) technologies for many years. Based on certain constraints, TE enables network traffic to be transmitted along specified paths. However, TE technologies, such as MPLS TE, are complex to configure and have poor scalability. In addition, devices need to maintain a large amount of status information.
To address these issues, Flexible Algorithm (Flex-Algo) technology is introduced. A Flex-Algo allows an IGP (IS-IS or OSPF) to calculate constraint-based network paths, implementing TE capabilities in an easier and more flexible manner.
Flex-Algo technology was proposed in draft-ietf-lsr-flex-algo and is mainly used on SR (SR-MPLS and SRv6) networks. Its technical advantages are as follows:
- NEs involved in the same Flex-Algo natively form an independent logical topology. Constraints of the IGP path algorithm can be defined to further exclude some links in the logical topology. As such, the network may be divided into multiple independent computing units and network slices as required.
- The types of metrics used in the IGP path algorithm can be defined. In addition to the link cost value, you can use the SPF algorithm to calculate the shortest path to the destination address based on the link delay and TE metric values. As such, a Flex-Algo can meet the requirements of different services, including high-bandwidth and low-delay services.
- Since the birth of SR, a Flex-Algo is an inherent component of the SR technical architecture. This means that a Flex-Algo can be natively used on SR networks and is compatible with ECMP load balancing and TI-LFA backup paths in these networks. Furthermore, the load balancing and backup paths meet the constraints of a Flex-Algo.
How Is a Flex-Algo Defined?
Flex-Algo Definition
You can customize 128 Flex-Algos; specifically, you can customize Flex-Algo (128) to Flex-Algo (255).
Each Flex-Algo can be represented by Flex-Algo (k). Flex-Algo (k) has local significance only in the logical topology that participates in this algorithm. Each Flex-Algo has a unique definition.
The definition of Flex-Algo (k) contains three elements:
- Calculation type (Calc-Type):
- 0: SPF in a traditional IGP. Dijkstra's SPF algorithm is used and the local policy is allowed to change the paths calculated by SPF to different ones. Currently, only SPF (0) is supported.
- 1: strict SPF. Dijkstra's SPF algorithm is used, but the local policy is not allowed to change the paths calculated by SPF to different ones.
- Metric type (Metric-Type):
- 0: IGP metric, that is, the link cost in a traditional IGP.
- 1: minimum unidirectional link delay
- 2: TE metric
- Constraints:
- Admin Group: administrative group. Exclude, Include-Any, and Include-All are used to describe link constraints.
- Exclude Admin Group: A link is excluded from path calculation if any bit in the link's administrative group has the same name as an affinity bit referenced by the administrative group.
- Include-Any Admin Group: A link is included in path calculation as long as one bit in the link's administrative group has the same name as an affinity bit referenced by the administrative group.
- Include-All Admin Group: A link is included in path calculation only if all bits in the link's administrative group have the same names as the affinity bits referenced by the administrative group.
- SRLG: A shared risk link group (SRLG) is a set of links with the same failure risk. An Exclude SRLG is used to describe the constraints on an SRLG.
- Admin Group: administrative group. Exclude, Include-Any, and Include-All are used to describe link constraints.
Flex-Algo Example
Flex-Algo (0) to Flex-Algo (127) are reserved by the IETF/IANA as standard algorithms.
Strictly speaking, standard algorithms do not belong to Flex-Algos. The following uses Flex-Algo (0) as an example to describe the three elements contained in a Flex-Algo:
- Calculation type. 0 (SPF)
- Metric type: 0 (IGP metric)
- Constraints: NULL
According to the three elements, Flex-Algo (0) is a traditional IGP algorithm.
The algorithms that can be customized are Flex-Algo (128) to Flex-Algo (255).
Here, we create Flex-Algo (128) and define its three elements as follows:
- Calculation type. 0 (SPF)
- Metric type: 1 (minimum unidirectional link delay)
- Constraints: NULL
The following topology is used as an example to compare the path calculation results of Flex-Algo (0) and Flex-Algo (128).
Assumptions:
- All nodes participate in the path calculation of Flex-Algo (128). By default, all nodes participate in the path calculation of Flex-Algo (0).
- The cost of the link between nodes 2 and 5 and between nodes 4 and 7 is 100, and that of other links is 10.
- The delay value of the link between nodes 1 and 4, between nodes 3 and 5, and between nodes 5 and 9 is 100, and that of other links is 10.
Flex-Algo example topology
Take the path from node 1 to node 9 as an example. The SPF algorithm can be used to obtain the path calculation results of Flex-Algo (0) and Flex-Algo (128).
- Flex-Algo (0) uses the cost value as the metric to calculate the shortest path from node 1 to node 9 as follows: node 1 > node 4 > node 6 > node 9 or node 1 > node 3 > node 5 > node 9.
- Flex-Algo (128) uses the delay value as the metric to calculate the shortest path from node 1 to node 9 as follows: node 1 > node 3 > node 4 > node 6 > node 9 or node 1 > node 2 > node 5 > node 6 > node 9.
Path calculation results of Flex-Algo (0) and Flex-Algo (128)
How Does a Flex-Algo Work?
The working process of a Flex-Algo mainly includes four steps: algorithm definition, algorithm advertisement, topology generation, and path calculation.
Step 1: Algorithm Definition
In the logical topology that participates in Flex-Algo (k) calculation, a definition of Flex-Algo (k) needs to exist first and contain at least three elements of Flex-Algo (k).
The definition of Flex-Algo (k) does not need to be configured for each node. Instead, it needs to be configured only for some nodes (at least one) and advertised to the topology.
To ensure that all nodes in the topology have a unified and unique understanding of Flex-Algo (k)'s definition and avoid definition conflicts, you are advised to configure the same definition for two nodes and advertise it.
IS-IS uses a protocol packet carrying the IS-IS FAD sub-TLV to define Flex-Algo (k). FAD is short for flexible algorithm definition.
The format and fields of the IS-IS FAD sub-TLV are described as follows:
Format of the IS-IS FAD sub-TLV
Field |
Length |
Meaning |
|---|---|---|
Type |
8 bits |
Sub-TLV type. The value is 26. |
Length |
8 bits |
Total length of the sub-TLV (excluding the Type and Length fields). |
Flex-Algo |
8 bits |
Flex-Algo ID, which ranges from 128 to 255. |
Metric-Type |
8 bits |
Metric type used during calculation. This field can be set to an IGP metric, minimum unidirectional link delay, or TE metric value. |
Calc-Type |
8 bits |
Calculation type, which can currently only be SPF and does not need setting. |
Priority |
8 bits |
Priority of the sub-TLV. If a receiver receives multiple advertisements with the same algorithm ID or the algorithm ID in a received advertisement is the same as that in a locally generated advertisement, the receiver compares the priorities in these advertisements. If the priorities are different, the advertisement with the highest priority is selected. If the priorities are the same, the advertisement with the highest SID (System-ID, in the case of IS-IS) is selected. |
Sub-TLVs |
Variable |
Optional sub-TLVs, which can be used to define constraints. |
Algorithm definition example
According to the fields in the IS-IS FAD sub-TLV, in addition to the three elements, Flex-Algo (k) defined in IS-IS needs to include the Flex-Algo ID (value of k) and priority.
In the following topology, we can define the same Flex-Algo (128) on nodes 1 and 9 as follows:
- Flex-Algo ID: 128 (the value ranges from 128 to 255)
- Calculation type: SPF (configuration not required)
- Metric type: delay (the value can be IGP, delay, or TE)
- Constraints: This parameter is optional. We do not need to configure it here.
- Priority: 200 (the value ranges from 0 to 255, and the default value is 128)
FAD example
Step 2: Algorithm Advertisement
The algorithm advertisement involves three parts:
- Some nodes (at least one) advertise the locally defined algorithm to the topology. This advertisement is implemented through the IS-IS FAD sub-TLV mentioned in Step 1. The IS-IS FAD sub-TLV can be propagated only throughout the same IS-IS level but not across level boundaries.
- All nodes advertise their own Flex-Algo capabilities (that is, IDs of all supported algorithms) to the topology by using the SR-Algorithm sub-TLV. This sub-TLV can be propagated only throughout the same IS-IS level but not across level boundaries.
- All nodes advertise the prefix SID information (including the association between the prefix SID and algorithm ID) to the topology by using the Prefix-SID sub-TLV.
The following figure shows the format of the SR-Algorithm sub-TLV.
Field |
Length |
Meaning |
|---|---|---|
Type |
8 bits |
Unassigned. The recommended value is 2. |
Length |
8 bits |
Packet length. |
Algorithm |
8 bits |
Algorithm ID. |
The following figure shows the format of the Prefix-SID sub-TLV.
Field |
Length |
Meaning |
|---|---|---|
Type |
8 bits |
Unassigned. The recommended value is 3. |
Length |
8 bits |
Packet length. |
Flags |
8 bits |
Flags field. |
Algorithm |
8 bits |
Algorithm ID. |
SID/Index/Label |
Variable |
- |
Algorithm advertisement example
In the following topology, an advertisement information example of each node is as follows:
Flex-Algo advertisement example
At this stage, all nodes in this topology have a unified and unique understanding of Flex-Algo (128)'s definition. In addition, the association between Flex-Algo (128) and the prefix SID is also specified.
Step 3: Topology Generation
Each Flex-Algo (k) generates its own logical topology based on the following rules:
- Node range: Only the nodes that participate in Flex-Algo (k) are contained in the Flex-Algo (k) topology, which includes the local generator and advertisement receiver of the Flex-Algo (k) definition.
- Link range: If constraints (such as Admin Group or SRLG) are configured in the Flex-Algo (k) definition, the topology is adjusted based on these constraints to reserve or exclude some links. If some links in the topology do not have the metric used by Flex-Algo (k), they are also excluded.
A topology generated by Flex-Algo (k) according to the preceding rules can be referred to as Topo (k).
Topology generation example
In the following topology:
- All nodes participate in the path calculation of Flex-Algo (128).
- No constraints are defined in Flex-Algo (128).
- Assume that the links between nodes 3 and 5 and between nodes 5 and 6 do not have the delay metric.
All nodes in the topology are reserved, and the links between nodes 3 and 5 and between nodes 5 and 6 are excluded.
Example of Flex-Algo topology generation
Step 4: Path Calculation
On the basis of Topo (k), Flex-Algo (k) uses the calculation type and metric type in its definition to calculate paths.
A Flex-Algo supports ECMP load balancing and can generate multiple paths with the same Flex-Algo cost.
Any node that participates in Flex-Algo (k) performs path calculation. If a node participates in multiple Flex-Algos, it performs independent calculation for each Flex-Algo. Because all nodes support Flex-Algo (0) by default, the corresponding traditional IGP path is always calculated.
A node uses the prefix SID associated with Flex-Algo (k) to install the path calculation result into its MPLS-MPLS forwarding table instead of any IP-MPLS or IP-IP forwarding table.
Path calculation example
On the basis of Topo (128), Flex-Algo (128) uses the SPF algorithm in its definition to calculate paths based on the delay metric.
A path from node 1 to node 9 is used as an example. Here, the path calculation result Path (128) is node 1 > node 3 > node 4 > node 7 > node 9 or node 1 > node 3 > node 4 > node 6 > node 9.
Example of Flex-Algo path calculation
- Author： Wu Zhuoran
- Updated on： 2023-04-08
- Views： 10120
- Average rating：
