Congestion Avoidance Using Segment Routing

Abstract

This document describes a generic solution of congestion avoidance, which is aimed at providing local link congestion avoidance within the Segment Routing (SR) framework. Based on the concept of Topology Independent Loop-Free Alternate (TI- LFA) Fast Reroute (FRR), the selected shortest path can bypass the congested link while avoiding the formation of micro-loops. The advantage of this solution is that it does not require any protocol extension.¶

2. Conventions

3. Congestion avoidance using TI-LFA Repair Path

The TI-LFA repair path consists of an outgoing interface and a list of segments (a Repair List (RL)) to insert on the SR header in accordance with the data plane used. The RL encodes the explicit path to the destination, which avoids the congested link (corresponds to the protected link). At the same time, the RL is guaranteed to be loop-free.¶

The TI-LFA repair path is found by intersecting P(S, X) and Q(D, X) with the post-convergence path to D and computing the explicit SR- based path EP(P, Q) from a node P in P(S, X) to a node Q in Q(D, X) when these nodes are not adjacent along the post-convergence path. The TI-LFA RL is expressed generally as [Node-SID(P), EP(P, Q)].¶

The post-convergence path in this document designates the shortest path from the source to its destination that can bypass the congested link, as if this link fails. Actually, when a link encounters congestion, IGP convergence does not occur,and the FIB in each router (including local node detecting the congestion) remains unchanged.¶

Take Figure 1 as an example. The target is to find a TI-LFA backup for the traffic from S to D, considering the congested link S-N1.¶

     S --------- N1--------- D
     |\                      |
     | \                     |
     |  \                    |
     |   N2----- R1**********R2
     |           *
     N3 **********

       ***** : link with high metric (100)
       ----- : link with metric 1

• First, P(S, N1) is computed and results in [N3, N2, R1].¶

• Then, Q(D, N1) is computed and results in [R2].¶

• The expected post-convergence path from S to D considering the congested link S-N1 is: [N2 ->R1 ->R2 ->D] (we are naming it "PCPath" in this example).¶

• P(S, N1) intersection with PCPath is [N2, R1]. With R1 being the deeper downstream node in PCPath, it can be assumed to be used as a P node (this is an example, and an implementation could use a different strategy to choose the P node).¶

• Q(D, N1) intersection with PCPath is [R2], so R2 is picked as a Q node. An SR-explicit path is then computed from R1 (P node) to R2 (Q node) following PCPath [R1 -> R2]: Adj-SID(R1-R2).¶

As a result, the TI-LFA RL of S for destination D considering the congested link S-N1 is: [Node-SID(R1), Adj-SID(R1-R2)].¶

4. Congestion Detection and FIB Modification

Typically, We only need to provide congestion avoidance backup paths for loss or delay sensitive services. First, the PLR is required to configure TI-LFA based on link protection for the destination prefixes of those protected traffic flows (for VPN services, they can be IP addresses of Egress PEs ). Then the corresponding TI-LFA RLs are automatically generated based on local Link State Database (LSDB) and installed into FIB as backup path.¶

A link congestion event can be quickly detected by the hardware (e.g., ASIC) at milliseconds or even microseconds interval. Though a transient congestion can be detected due to the instantaneous queue size reaching a threshold, it may be a noisy signal of congestion, which should not be used as a typical congestion event. Preferably, a persistent congestion event lasting for at least tens of milliseconds is of value for the protected traffic flows. On the other hand, transient congestion could lead to frequent switchover of the protected traffic between the primary link and backup path, and this will excessively consume the processing resources required for packet encapsulation and decapsulation. Therefore, a persistent congestion can be most likely detected based on the average queue length exceeding a threshold, and used as the trigger for traffic switching. The Exponentially Weighted Moving Average (EWMA) is widely adopted to estimate the average queue length, and is recommended for use in this document. The specific specification of capturing a reliable congestion is out of the scope of this document.¶

Upon detection of a congestion event, the PLR MUST set in FIB the forwarding entries corresponding to the protected destination prefixes at "invalid" state. At the moment, TI-LFA paths can be activated and remain in effect until the forwarding entries get available again. Upon detection of the congestion recovery of the link, the PLR MUST set in FIB the forwarding entries corresponding to the protected destination prefixes at "valid" state. The mechanisms for disabling the forwarding entries in FIB upon detection of congestion and enabling the forwarding entries in FIB upon detection of congestion recovery depend on implementations, and are outside the scope of this document.¶

To prevent frequent switchover of traffic flows between the protected link and backup path, the PLR is required to support a persistent timer before the protected trffic flows are switched to the protected link upon detection of the congestion recovery of the link. The time for the persistent timer should be configurable.¶

5. Example Application of TI-LFA for End-to-End Congestion Avoidance

An example application of TI-LFA backup path for end-to-end congestion avoidance is shown in Figure 2. It is a commonly deployed topology.¶

     S --------- N1--------- D
     |           |           |
     |           |           |
     |           |           |
     N2----------R1---------R2

In the above topology, all links have the same metric. The traffic flow with loss or delay-sensitivity from the source (S) to the destination (D) selects the shortest path: [S -> N1 -> D]. To realize end-to-end congestion avoidance, both link S-N1 and link N1-D need to be protected when they encounter congestion.¶

Asuming that link S-N1 is congested, the TI-LFA backup from S to D is computed as follows.¶

• The extended P-space P'(S, N1) is computed and results in [N2, R1].¶

• Q(D, N1) is computed and results in [R1, R2].¶

• So PQ node is R1.¶

As a result, the TI-LFA RL of source S for destination D considering the congested link S-N1 is: Node-SID(R1).¶

The post-convergence path from S to D has two equal cost paths:¶

• [S -> N2 -> R1 -> N1 -> D].¶

• [S -> N2 -> R1 -> R2 -> D].¶

In SRv6 network, when the protected traffic flow is switched to TI-LFA backup path, the node S serving as the PLR needs to support the H.Encaps behavior, and adds the outer IPv6 header to the original IPv6 packet unmodified (with the exception of IPv6 Hop Limit that is decremented), with the source IPv6 address being the address of the node S (e.g., assigned to its loopback) and the destination IPv6 address being the SID of the node R1. The SID of the node R1 may be End.DT6, End.DT46 or End with USD flavor.¶

Asuming that link N1-D is congested, the TI-LFA backup from N1 to D is computed as follows.¶

• P(N1, D) is computed and results in [N2, R1].¶

• Q(D, N1) is computed and results in [R2].¶

An SR-explicit path is then computed from R1 (P node) to R2 (Q node) is: Adj-SID(R1-R2).¶

As a result, the TI-LFA RL of N1 for destination D considering the congested link N1-D is: [Node-SID(R1), Adj-SID(R1-R2)].¶

In SRv6 network, when the protected traffic flow is switched to TI-LFA backup path, the node N1 serving as the PLR needs to support the H.Encaps behavior, and add the outer IPv6 header to the original IPv6 packet unmodified (with the exception of IPv6 Hop Limit that is decremented), with the source IPv6 address being the address of the node N1 (e.g., assigned to its loopback) and the destination IPv6 address being the SID of the node R1. The SID of the node R1 may be End.DX6 or End.X with USD flavor, which has a cross-connect to R2.¶

8. References