IGP Flexible Algorithms (Flex-Algo)

In Segment Routing (SR), a prefix segment follows the least-cost path from its source to its destination. An Intradomain Gateway Protocol (IGP) calculates and identifies the least-cost path. A network operator can configure multiple prefix segments ending on the same destination. Flex Algo is a mechanism that allows network operators to influence how the IGP calculates the least cost path for each prefix segment. Therefore, each prefix segment can traverse a unique path to the destination. In this blog, we will explore how Flex-Algo supports lightweight Traffic Engineering (TE) with two common use-cases.

Use Case 1: Low Latency and High Bandwidth Prefix Segments

Figure 1. Reference Topology for Use Case 1.

Figure 1 contains links and nodes. Every link, except for R1->R4, belongs to the blue administrative group. Link R1->R4 belongs to the red administrative group. Blue links can carry 100 gigabits per second while red links can carry only 10 gigabits per second.

In this network, circuit length determines latency. Thus, the lowest latency path from R1 to R4 is through Link R1->R4 (300 km). If Link R1->R4 fails, the following paths from R1 to R4 remain:

The path through R1->R2 and R2->R4 (800 km).
The path through R1->R3 and R3->R4 (800 km).

Each of these paths provides equally low latency.

R1 sends low latency and high bandwidth flows to R4. All flows traverse the lowest latency path available (R1->R4). However, high bandwidth flows must avoid Link R1->R4 because they would congest that link.

Solving Use Case 1 With Flex-Algo

Nodes R1 through R4 use IS-IS or OSPF to advertise information about themselves and their links. Link information includes IGP metrics, TE metrics and administrative groups. Table 1 contains information for each link.

Table 1: Link Information for Use Case 1.

Nodes R2 and R3 use IS-IS or OSPF to advertise Flexible Algorithm Definitions (FAD). A FAD has the following parameters:

Metric type—Metric types include IGP, TE and Minimum unidirectional link delay.
Calculation-type—Calculation types include Shortest Path First (SPF) and Strict SPF.

Table 2 contains the FADs that R2 and R3 advertise.

Table 2: Flexible Algorithm Definitions (FAD) for Use Case 1.

R4 advertises:

A low latency prefix segment that is a member of the low latency flexible algorithm.
A high bandwidth prefix segment that is a member of the high bandwidth flexible algorithm.

R1 through R3 receive these advertisements. So, each node calculates the least-cost path between itself and R4 twice, once using the low latency FAD and once using the high bandwidth FAD. Then, each node creates the following between itself and R4:

A low latency prefix segment.
A high bandwidth prefix segment.

The low latency prefix segment follows a least-cost path that was calculated using the low latency FAD, while the high bandwidth prefix segment follows a least-cost path that was calculated using the high bandwidth FAD.

For example, R1 creates:

A low latency prefix segment that traverses Link R1->R4.
A high bandwidth prefix segment that traverses an Equal Cost Multipath (ECMP). The ECMP can traverse either Links R1->R2 and R2->R4 or Links R1->R3 and R3->R4.

If Link R1->R4 fails, the low latency segment can traverse any other link. If either ECMP member fails, the high bandwidth path traverses the other ECMP member, but it cannot traverse Link R1->R4.

Use Case 2: Path Diversity

Figure 2. Reference Topology for Use Case 2.

Figure 2 contains links and nodes. Links R1->R2 and R2->R4 belong to the red administrative group, while Links R1->R3 and R3->R4 belong to the blue administrative group.

R1 sends violet, green, yellow and orange flows to R4. When all links are operational:

Violet flows and orange flows traverse red links.
Green flows and yellow flows traverse blue links.

When a red link fails:

Violet flows are not delivered to R4.
Green, yellow and orange flows traverse blue links.

When a blue link fails:

Green flows are not delivered to R4.
Violet, yellow and orange flows traverse red links.

Solving Use Case 2 With Flex-Algo

Nodes R1 through R4 use IS-IS or OSPF to advertise information about themselves and their links. Table 3 contains information for each link in Figure 2.

Table 3: Link Information for Use Case 2.

Nodes R2 and R3 use IS-IS or OSPF to advertise Flexible Algorithm Definitions (FAD). Table 4 contains the FADs that R2 and R3 advertise.

Table 4: Flexible Algorithm Definitions (FAD) for Use Case 2.

R4 advertises the following prefix segments:

Violet
Green
Yellow
Orange

It associates each prefix segment with a FAD of the same color.

R1 through R3 receive these advertisements. So, each node calculates the least-cost path between itself and R4 four times, once using each FAD. Then, each node creates the following prefix segments between itself and R4:

Violet
Green
Yellow
Orange

The violet prefix segment follows a least-cost path that was calculated using the violet FAD, while the green prefix segment follows a least-cost path that was calculated using the green FAD and so on.

For example, R1 creates:

A violet prefix segment that traverses Links R1->R2 and R2->R4.
An orange prefix segment that traverses Links R1->R2 and R2->R4.
A green prefix segment that traverses Links R1->R3 and R3->R4.
A yellow prefix segment that traverses Links R1->R3 and R3->R4.

The violet prefix segment cannot traverse link R1->R3 because the violet FAD has a constraint that causes it to avoid blue links. Likewise, the green prefix segment cannot traverse link R1->R2 because the green FAD has a constraint that causes it to avoid red links.

The orange segment can traverse any link but prefers red links because the orange FAD uses IGP metrics and IGP metrics are low on red links. Likewise, the yellow segment can traverse any link but prefers blue links because the yellow FAD uses TE metrics and TE metrics are low on blue links.