RFC 8662

Entropy Label for Source Packet Routing in Networking (SPRING) Tunnels

📅 published December 2019, from ietf

RFC 8662: Entropy Label for Source Packet Routing in Networking (SPRING) Tunnels 🎀

Okay so bestie, this RFC is from the IETF's Standards Track (so it's an official Internet standard, no cap 👑). It was written by S. Kini, K. Kompella (Juniper), S. Sivabalan (Cisco), S. Litkowski (Orange), R. Shakir (Google), and J. Tantsura (Apstra, Inc.), and it's dated December 2019 📅. It's published as ISSN 2070-1721. Nothing in the header says it obsoletes or updates another RFC, so it stands on its own 🦋.

The whole point is about Segment Routing (SR) 🧚, where a node steers a packet through an ordered list of instructions called segments. SR can run on the MPLS data plane, and entropy labels (ELs) are the MPLS trick for better load-balancing. This doc is all about how ELs should work with Segment Routing MPLS 💖.

Status of This Memo 📝

This is an Internet Standards Track document 🌸.

It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community. It went through public review and was approved for publication by the Internet Engineering Steering Group (IESG). More info on Internet Standards is in Section 2 of RFC 7841 ✨.

You can find the current status, any errata, and how to give feedback at https://www.rfc-editor.org/info/rfc8662 💅.

Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved 💜.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication. Please read these carefully, because they spell out your rights and restrictions 🙈. Code Components pulled out of this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in that license 🫶.

Table of Contents 🗂️

  • 1. Introduction
    • 1.1. Requirements Language
  • 2. Abbreviations and Terminology
  • 3. Use Case Requiring Multipath Load-Balancing
  • 4. Entropy Readable Label Depth
  • 5. Maximum SID Depth
  • 6. LSP Stitching Using the Binding SID
  • 7. Insertion of Entropy Labels for SPRING Path
    • 7.1. Overview
      • 7.1.1. Example 1: The Ingress Node Has a Sufficient MSD
      • 7.1.2. Example 2: The Ingress Node Does Not Have a Sufficient MSD
    • 7.2. Considerations for the Placement of Entropy Labels
      • 7.2.1. ERLD Value
      • 7.2.2. Segment Type
      • 7.2.3. Maximizing Number of LSRs That Will Load-Balance
      • 7.2.4. Preference for a Part of the Path
      • 7.2.5. Combining Criteria
  • 8. A Simple Example Algorithm
  • 9. Deployment Considerations
  • 10. Options Considered
    • 10.1. Single EL at the Bottom of the Stack
    • 10.2. An EL per Segment in the Stack
    • 10.3. A Reusable EL for a Stack of Tunnels
    • 10.4. EL at Top of Stack
    • 10.5. ELs at Readable Label Stack Depths
  • 11. IANA Considerations
  • 12. Security Considerations
  • 13. References
    • 13.1. Normative References
    • 13.2. Informative References
  • Acknowledgements
  • Contributors
  • Authors' Addresses

1. Introduction 🦋

Okay so Segment Routing [RFC8402] is built on source-routed tunnels that steer a packet down a particular path 🧭. That path is encoded as an ordered list of segments. When it's applied to the MPLS data plane [RFC8660], each segment is an LSP (Label Switched Path) with its own MPLS label value 💫. So label stacking is how you represent that ordered list, and the label stack for an SR tunnel can be seen as nested LSPs (an LSP hierarchy) in the MPLS architecture 🪆.

Using label stacking to encode the list of segments has implications for the label stack depth 📚.

Traffic load-balancing over ECMP (Equal-Cost Multipath) or LAGs (Link Aggregation Groups) is usually based on a hashing function 🎲. The local node doing the load-balancing is required to read some header fields in incoming packets and then compute a hash from them. The hash result gets mapped to a list of outgoing next hops. The hash is required to do per-flow load-balancing, which keeps packets from getting misordered 🫶. For IP traffic, the usual fields that get hashed are the source address, the destination address, the protocol type and, if the upper layer provides them, the source port and destination port 💅.

The MPLS architecture gets tricky when an LSR (Label Switching Router) tries to look at header fields 😭. An LSR needs to be able to look at header fields that sit beyond the MPLS label stack, even though the MPLS header doesn't say anything about the upper-layer protocol. An LSR must do a deeper inspection than an ingress router does, and that can be a real challenge for some hardware 💀. Entropy labels (ELs) [RFC6790] fix this in the MPLS data plane by providing entropy for load-balancing 🔥. The idea is that the ingress router computes a hash from several fields in a packet and puts the result in an extra label called the "entropy label". That entropy label can then be part of the hash keys an LSR uses. Using it this way cuts down the need for deep packet inspection in the LSR while keeping good entropy in the load-balancing ✨. When the entropy label is used, the keys for the hash functions are still a local configuration matter. An LSR may use just the entropy label, or a combination of several fields from the incoming packet 🌷.

When you have LSP hierarchies, there are implications for how [RFC6790] should be applied 🍓. This document covers the case where a hierarchy is created at a single LSR, which is what Segment Routing requires 🧚‍♀️.

A use case that needs load-balancing with SR is in Section 3 👑. A recommended solution is in Section 7, keeping in mind the limits implementations have when applying [RFC6790] to deeper label stacks 🌈. The options that were considered on the way to that solution are documented for historical purposes in Section 10 📜.

1.1. Requirements Language 🔑

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 💖.

2. Abbreviations and Terminology 📖

Here's the glossary, bestie. Don't skip it, you'll need it later 🙈:

Adj-SID   Adjacency Segment Identifier

ECMP      Equal-Cost Multipath

EL        Entropy Label

ELI       Entropy Label Indicator

ELC       Entropy Label Capability

ERLD      Entropy Readable Label Depth

FEC       Forwarding Equivalence Class

LAG       Link Aggregation Group

LSP       Label Switched Path

LSR       Label Switching Router

MPLS      Multiprotocol Label Switching

MSD       Maximum SID Depth

Node SID  Node Segment Identifier

OAM       Operations, Administration, and Maintenance

RLD       Readable Label Depth

SID       Segment Identifier

SPT       Shortest Path Tree

SR        Segment Routing

SRGB      Segment Routing Global Block

VPN       Virtual Private Network

3. Use Case Requiring Multipath Load-Balancing 🛣️

Traffic engineering is one of the applications of MPLS, and it's also a requirement for Segment Routing [RFC7855] 💅. Picture the topology in Figure 1. LSR S needs to send data to LSR D along a traffic-engineered path that goes over link L1. Good load-balancing is also needed across equal-cost paths (including parallel links) 🎀.

To steer traffic along a path that crosses link L1, the label stack LSR S creates has a label for the Node SID of LSR P3, stacked over the label for the Adj-SID (Adjacency Segment Identifier) of link L1, and that is in turn stacked over the label for the Node SID of LSR D 🧚. To keep things simple, let's assume all LSRs use the same label space for Segment Routing (a reminder: it's called the SRGB, Segment Routing Global Block) 🌸. Let L_N-Px denote the label used to reach the Node SID of LSR Px. Let L_A-Ln denote the label used for the Adj-SID of link Ln. In our example, LSR S must use the label stack <L_N-P3, L_A-L1, L_N-D> 💫. But to get good load-balancing over the equal-cost paths P2-P4-D and P2-P5-D, and over the parallel links L3 and L4, a mechanism like entropy labels [RFC6790] should be adapted for Segment Routing 🌈. The reason is that the Source Packet Routing in Networking (SPRING) architecture with the MPLS data plane [RFC8660] uses nested MPLS LSPs to compose the source-routed label stack 🪆.

                         +------+
                         |      |
                 +-------|  P3  |-----+
                 | +-----|      |---+ |
               L3| |L4   +------+ L1| |L2     +----+
                 | |                | |    +--| P4 |--+
   +-----+     +-----+            +-----+  |  +----+  |  +-----+
   |  S  |-----| P1  |------------| P2  |--+          +--|  D  |
   |     |     |     |            |     |--+          +--|     |
   +-----+     +-----+            +-----+  |  +----+  |  +-----+
                                           +--| P5 |--+
                                              +----+
       Key:
           S = Source LSR
           D = Destination LSR
           P1, P2, P3, P4, P5 = Transit LSRs
           L1, L2, L3, L4 = Links

                   Figure 1: Traffic-Engineering Use Case

An MPLS node may have limits on how many labels it can push 🙃. It may also have a limit on how many labels it can inspect when looking for hash keys during load-balancing 😤. The entropy label normally goes at the bottom of the transport tunnel, but that can stop an LSR from using the EL in its load-balancing function if the EL is buried too deep in the stack 🥲. In a Segment Routing environment, it's important to define what needs to be considered when inserting an EL 🫠. Several ways to apply entropy labels were considered, and they're documented in Section 10 along with their trade-offs 💜. A recommended solution is described in Section 7 ✨.

Part 1 of 5. More parts coming, so stay tuned, bestie 💖🎀

4. Entropy Readable Label Depth ✨

okay so, the Entropy Readable Label Depth (ERLD) 🎀 is basically how many labels a router can both:

  • a. read in an MPLS packet that shows up on its incoming interface(s), starting from the top of the stack 👀
  • b. actually use in its load-balancing function 💅

the ERLD means the router will load-balance using the EL if the EL sits within the first ERLD labels. it's giving "you can only use what you can see" energy 🧚

a router that can read N labels but can't use an EL sitting inside those N labels MUST consider its ERLD to be 0 💀

in a distributed switching setup, each line card might have a different ERLD 🌸 so for simplicity an implementation MAY use the minimum ERLD of all line cards as the system's ERLD value. lowkey smart 🫶

there's also the case where a router has a fast switching path (an ASIC or network processor) and a slow one (a CPU), each with its own ERLD. same deal: for simplicity's sake, an implementation MAY use the minimum ERLD as the system value 🦋

the drawback of using one system-wide ERLD that's lower than what one or more components can actually do is that it may increase the number of ELI/ELs inserted. that means a bigger label stack, which can affect whether the ingress node is able to push that stack at all 😭

Examples:

                                                    | Payload  |
                                                    +----------+
                                       | Payload  | |    EL    | P7
                                       +----------+ +----------+
                          | Payload  | |    EL    | |    ELI   |
                          +----------+ +----------+ +----------+
             | Payload  | |   EL     | |    ELI   | | Label 50 |
             +----------+ +----------+ +----------+ +----------+
|  Payload | |     EL   | |   ELI    | | Label 40 | | Label 40 |
+----------+ +----------+ +----------+ +----------+ +----------+
|     EL   | |    ELI   | | Label 30 | | Label 30 | | Label 30 |
+----------+ +----------+ +----------+ +----------+ +----------+
|    ELI   | | Label 20 | | Label 20 | | Label 20 | | Label 20 |
+----------+ +----------+ +----------+ +----------+ +----------+
| Label 16 | | Label 16 | | Label 16 | | Label 16 | | Label 16 | P1
+----------+ +----------+ +----------+ +----------+ +----------+
  Packet 1     Packet 2     Packet 3     Packet 4     Packet 5

                  Figure 2: Label Stacks with ELI/EL

in Figure 2 we're looking at the displayed packets arriving on a router interface, and we're assuming a single ERLD value for the router 🍓

  • if the router has an ERLD of 3, it can load-balance Packet 1 using the EL as part of the load-balancing keys. the router can read and use the entropy label if it's placed between position 1 (top of the MPLS label stack) and position 3 🌈
  • if the router has an ERLD of 5, it can load-balance Packets 1 to 3 using the EL. Packets 4 and 5 have the EL at a position greater than 5, so the router can't read it or use it for load-balancing 🙈
  • if the router has an ERLD of 10, it can load-balance all the packets in Figure 2 using the EL 👑

to get efficient entropy-label load-balancing, a router running SPRING SHOULD advertise its ERLD (or ERLDs) so every other SPRING router knows what it's capable of 📣 how that advertisement works is outside the scope of this document (see Section 7.2.1 for potential approaches) ✨

to advertise an ERLD value, a SPRING router:

  • MUST be entropy label capable and, as a consequence, MUST apply the data-plane procedures defined in [RFC6790]. 💖
  • MUST be able to read an ELI/EL that's located within its ERLD value. 🫶
  • MUST take into account an EL within the first ERLD labels in its load-balancing function. 💅

5. Maximum SID Depth 👑

the Maximum SID Depth (MSD) defines the maximum number of labels a particular node can impose on a packet 🦋 that can include any kind of labels (service, entropy, transport, etc.). in an MPLS network, the MSD is a limit on the head-end of an SR tunnel, or on a Binding SID anchor node that imposes additional labels onto an existing label stack 🧚

depending on how many MPLS operations (POP, SWAP, etc.) have to happen before the PUSH, the MSD can change because of hardware or software limits 💀 and just like the ERLD, different MSD limits can exist within a single node depending on the line-card types in a distributed switching system. so the MSD is a per-link and/or per-node property 🌸

an external controller can be used to program a label stack on a particular node. this node SHOULD advertise its MSD to the controller so the controller knows the maximum label stack depth supported on the head-end for the computed path 📣 how that advertisement works is outside the scope of this document. ([RFC8476], [RFC8491], and [MSD-BGP] provide examples of advertisement of the MSD.)

the controller doesn't know the whole label stack the node will push, so along with the MSD value, the node SHOULD advertise the type of the MSD 🎀 for instance, the MSD value might only represent the limit for pushing transport labels, even though the node can push an extra service label. or the MSD value might represent the full limit of the node including all label types (transport, service, entropy, etc.) 🍓 that way the controller can program a label stack while leaving room for the local node to add more labels (e.g., service, entropy, etc.) without hitting the hardware/software limit ✨

if the node doesn't give the meaning of the MSD value, the controller could program an LSP using a number of labels equal to the node's full limit. but when the ingress node gets that label stack from the controller, it may not be able to add any service label (L2VPN, L3VPN, EVPN, etc.) on top of it 😭 the consequence could be that the ingress node drops service packets that should've been forwarded over the LSP 💔

              P7 ---- P8 ---- P9
            /                   \
    PE1 --- P1 --- P2 --- P3 --- P4 --- P5 --- P6 --- PE2
                                        |  \            |
   ---->                                  P10  \           |
   IP Pkt                                  |    \          |
                                          P11 --- P12 --- P13
                                              100    10000

        Figure 3: Topology Illustrating Label Stack Reduction

in Figure 3, an IP packet enters the MPLS network at PE1 🦋 all metrics are equal to 1 except P12-P13, which is 10000, and P11-P12, which is 100. PE1 wants to steer traffic over a SPRING path to PE2 along PE1 -> P1 -> P7 -> P8 -> P9 -> P4 -> P5 -> P10 -> P11 -> P12 -> P13 -> PE2 🌈 if we only use Adj-SIDs, PE1 (acting as an ingress LSR, also known as an I-LSR) will need to push 10 labels on the IP packet, so it requires an MSD of 10. if the IP packet should go over an MPLS service like a regular layer 3 VPN, an extra service label has to be imposed, which means an MSD of 11 for PE1 💅 and if PE1 wants to insert an ELI/EL for load-balancing, PE1 will need to push 13 labels, requiring an MSD of 13 😭

in the SPRING architecture, Node SIDs or Binding SIDs can shrink the label stack 🫶 as an example, to steer traffic on the same path as before, PE1 could use this label stack: <Node_P9, Node_P5, Binding_P5, Node_PE2>. this example combines Node SIDs with a Binding SID advertised by P5, which stitches the traffic along the path P10 -> P11 -> P12 -> P13. the instruction for the Binding SID at P5 is to swap Binding_P5 to Adj_P12-P13 and then push <Adj_P11-P12, Node_P11>. P5 is a stitching node that pushes extra labels onto an existing label stack, so P5's MSD also needs to be taken into account, since it may limit how many labels can be imposed 🔥

6. LSP Stitching Using the Binding SID ✨

okay so the Binding SID lets you attach a segment identifier to an LSP that already exists 💅 Examples are an RSVP-TE tunnel, an LDP path (through the Mapping Server Advertisement), or a SPRING path. Every tail-end router of an MPLS LSP tied to a Binding SID has its own entropy label capability, and that capability gets advertised in the control-plane protocol used to signal the LSP 🎀

In Figure 4, here's the setup:

  • P6, PE2, P10, P11, P12, and P13 are pure LDP routers.
  • PE1, P1, P2, P3, P4, P7, P8, and P9 are pure SPRING routers.
  • P5 is running SPRING and LDP.
  • P5 acts as a Mapping Server and advertises Prefix-SIDs for the LDP FECs: an index value of 20 is used for PE2.
  • All SPRING routers use an SRGB of [1000, 1999].
  • P6 advertises label 20 for the PE2 FEC.
  • Traffic from PE1 to PE2 uses the shortest path.
        PE1 ----- P1 -- P2 -- P3 -- P4 ---- P5 --- P6 --- PE2
    -->    +----+                   +----+   +----+  +----+
  IP Pkt   | IP |                   | IP |   | IP |  | IP |
           +----+                   +----+   +----+  +----+
           |1020|                   |1020|   | 20 |
           +----+                   +----+   +----+
                                    SPRING    LDP

       Figure 4: Example Illustrating Need for ELC Propagation

Here's how the packets move 🦋 By learning the Mapping Server Advertisement from P5, PE1 imposes a label 1020 on an IP packet destined to PE2. The SPRING routers along the shortest path to PE2 switch the traffic until it reaches P5. Then P5 does the LSP stitching: it swaps the SPRING label 1020 for the LDP label 20 advertised by the next hop, P6. P6 finally forwards the packet using the LDP label toward PE2.

PE1 cannot push an ELI/EL for the Binding SID without knowing that the tail end of the LSP associated with the binding (PE2) is entropy label capable. Main character problem, honestly 😭

To accommodate the mix of signaling protocols involved in the stitching, the entropy label capability SHOULD be propagated between the signaling domains. Each Binding SID SHOULD have its own entropy label capability that MUST be inherited from the entropy label capability of the associated LSP. If the router advertising the Binding SID does not know the ELC state of the target FEC, it MUST NOT set the ELC for the Binding SID. An ingress node MUST NOT push an ELI/EL associated with a Binding SID unless this Binding SID has the entropy label capability. How the entropy label capability is advertised for a Binding SID is outside the scope of this document (see Section 7.2.1 for potential approaches) 🧚

In our example, if PE2 is LDP entropy label capable, it adds the entropy label capability to its LDP advertisement. When P5 receives the FEC/label binding for PE2, it learns about the ELC and can set the ELC in the Mapping Server Advertisement. So PE1 learns about the ELC of PE2 and may push an ELI/EL associated with the Binding SID 🎉

The proposed solution only works if the SPRING router advertising the Binding SID is also performing the data-plane LSP stitching. In our example, if the Mapping Server function is hosted on P8 instead of P5, P8 does not know about the ELC state of PE2's LDP FEC. As a consequence, it does not set the ELC for the associated Binding SID. 💀

7. Insertion of Entropy Labels for SPRING Path 🌈

7.1. Overview

This solution follows the data-plane processing defined in [RFC6790]. Within a SPRING path, a node may be ingress, egress, or transit (for entropy label processing as described in [RFC6790]), or any combination of those. For example:

  • The ingress node of a SPRING domain can be an ingress node from an entropy label perspective.
  • Any LSR terminating a segment of the SPRING path is an egress node (because it terminates the segment), but it can also be a transit node if the SPRING path is not terminated because there is a subsequent SPRING MPLS label in the stack.
  • Any LSR processing a Binding SID may be a transit node and an ingress node (because it may push additional labels when processing the Binding SID).

As described earlier, an LSR may have a limit (the ERLD) on how deep into the label stack it can read and process in order to do multipath load-balancing based on entropy labels 👑

If an EL does not occur within the ERLD of an LSR in the label stack of an MPLS packet it receives, that LSR will load-balance poorly. So an ELI/EL pair must be within the ERLD of the LSR for the LSR to use the EL during load-balancing.

Adding a single ELI/EL pair for the entire SPRING path can also lead to poor load-balancing, because the ELI/EL may not occur within the ERLD of some LSR on the path (if it's too deep), or may not be in the stack when it reaches some LSRs (if it's too shallow) 😵‍💫

So that the EL occurs within the ERLD of the LSRs along the path corresponding to a SPRING label stack, multiple <ELI, EL> pairs MAY be inserted in this label stack.

The insertion of an ELI/EL MUST occur only with a SPRING label advertised by an LSR that advertised an ERLD (that is, the LSR is entropy label capable), or with a SPRING label associated with a Binding SID that has the ELC set.

The ELs among multiple <ELI, EL> pairs inserted in the stack MAY be the same or different. The LSR inserting <ELI, EL> pairs can have limits on how many pairs it can insert and how deep it can insert them. If, because of those limits, the inserted ELs land in positions where an LSR along the path gets an MPLS packet without an EL in the label stack within that LSR's ERLD, then that LSR's load-balancing will be poor. An implementation MAY consider multiple criteria when inserting <ELI, EL> pairs. ✨

7.1.1. Example 1: The Ingress Node Has a Sufficient MSD

                    ECMP          LAG           LAG
  PE1 --- P1 --- P2 --- P3 --- P4 --- P5 --- P6 --- PE2

              Figure 5: Accommodating MSD Limitations

In Figure 5, PE1 wants to forward some MPLS VPN traffic over an explicit path to PE2, which results in the following label stack pushed onto the received IP header: <Adj_P1P2, Adj_set_P2P3, Adj_P3P4, Adj_P4P5, Adj_P5P6, Adj_P6PE2, VPN_label>. PE1 is limited to pushing a maximum of 11 labels (MSD=11). P2, P3, and P6 have an ERLD of 3, while the others have an ERLD of 10.

PE1 can only add two ELI/EL pairs to the label stack because of its MSD limit. It should insert them strategically so they help load-balancing along the longest part of the path 🍓

PE1 can take multiple parameters into account when inserting ELs. Some examples:

  • The ERLD value advertised by transit nodes.
  • The requirement of load-balancing for a particular label value.
  • Any service provider preference: favor the beginning of the path or the end of the path.

In Figure 5, a good strategy might be the stack <Adj_P1P2, Adj_set_P2P3, ELI1, EL1, Adj_P3P4, Adj_P4P5, Adj_P5P6, Adj_P6PE2, ELI2, EL2, VPN_label>. The original stack asks P2 to forward based on an L3 adjacency-set that will require load-balancing, so it's important to make sure P2 can load-balance correctly. Since P2 has a limited ERLD of 3, an ELI/EL must be inserted just after the label that P2 uses to forward. On the path to PE2, P3 also has a limited ERLD, but P3 forwards based on a regular adjacency segment that may not need load-balancing, so it doesn't seem important to make sure P3 can load-balance despite its limited ERLD. The next nodes along the forwarding path have a high ERLD that causes no issue, except P6. P6 uses some LAGs to PE2 and so is expected to load-balance, which makes it important to insert a new ELI/EL just after the P6 forwarding label 💖

In this case, the ingress node supported a sufficient MSD to ensure end-to-end load-balancing while taking the path attributes into account. However, there might be cases where the ingress node doesn't have the necessary label imposition capacity 🥺

7.1.2. Example 2: The Ingress Node Does Not Have a Sufficient MSD

                  ECMP          LAG           ECMP         ECMP
PE1 --- P1 --- P2 --- P3 --- P4 --- P5 --- P6 --- P7 --- P8 --- PE2

                    Figure 6: MSD Considerations

In Figure 6, PE1 wants to forward MPLS VPN traffic over an explicit path to PE2, resulting in the following label stack pushed onto the IP header: <Adj_P1P2, Adj_set_P2P3, Adj_P3P4, Adj_P4P5, Adj_P5P6, Adj_set_P6P7, Adj_P7P8; Adj_set_P8PE2, VPN_label>. PE1 is limited to pushing a maximum of 11 labels. P2, P3, and P6 have an ERLD of 3, while the others have an ERLD of 15.

Using a similar strategy to the previous case could be a dilemma, because PE1 can only push a single ELI/EL while we may need a minimum of three to load-balance the end-to-end path. An optimized stack that would enable end-to-end load-balancing might be: <Adj_P1P2, Adj_set_P2P3, ELI1, EL1, Adj_P3P4, Adj_P4P5, Adj_P5P6, Adj_set_P6P7, ELI2, EL2, Adj_P7P8, Adj_set_P8PE2, ELI3, EL3, VPN_label>.

A decision needs to be made to favor some part of the path for load-balancing, since load-balancing may not work on the other parts. A service provider may decide to place the ELI/EL after the P6 forwarding label, which allows P4 and P6 to load-balance. Placing the ELI/EL at the bottom of the stack is also an option, enabling load-balancing for P4 and P8 🌸

7.2. Considerations for the Placement of Entropy Labels

The sample cases in the previous section showed that ELI/EL placement isn't an easy call when the maximum number of labels that can be pushed is limited, and multiple criteria may need to be considered 🫶

This section describes some considerations that an implementation MAY take into account when placing ELI/ELs. This list of criteria is not exhaustive, and an implementation MAY take additional criteria or tiebreakers into account that aren't documented here. Since the ingress node does the ELI/EL insertion, ingress nodes that don't use the same criteria don't cause an interoperability issue. Still, from a network design and operations perspective, it's better for all ingress routers to use the same criteria 🔥

An implementation SHOULD try to maximize the chance of load-balancing along the path by inserting an ELI/EL where multiple equal-cost paths are available, and to minimize the number of ELI/ELs that need to be inserted. In case of a trade-off, an implementation SHOULD give the operator flexibility to select the criteria considered when placing ELI/ELs, or to specify a subobjective for optimization 👑

                        2      2
  PE1 -- P1 -- P2 --P3 --- P4 --- P5 -- ... -- P8 -- P9 -- PE2
                    |             |
                    P3'--- P4'--- P5'

                      Figure 7: MSD Trade-Offs

Figure 7 is the reference for the following subsections. All metrics are equal to 1 except P3-P4 and P4-P5, which have a metric of 2. We consider the MSD of nodes to be the full limit of label imposition (including service labels, entropy labels, and transport labels) 🎀

7.2.1. ERLD Value

okay bestie, remember Section 7.1 said the ERLD value is a big deal when you insert an ELI/EL 🎀. If an ELI/EL doesn't fall within the ERLD of a node on the path, that node can't load-balance the traffic efficiently 😭.

The ERLD value can be advertised through protocols, and those extensions are described in separate docs (like [ISIS-ELC] and [OSPF-ELC]) 🦋.

Let's look at a path from PE1 to PE2 with the stack pushed by PE1: <Adj_P1P2, Node_P9, Adj_P9PE2, Service_label> 🧚.

Using the ERLD as an input can help minimize how many ELI/EL pairs you need to insert ✨. An ERLD value has to be retrieved for each SPRING label in the label stack, because every label is its own little main character 💅.

For a label bound to an adjacency segment, the ERLD is the ERLD of the node that advertised that adjacency segment. In the example, the ERLD for Adj_P1P2 would be the ERLD of router P1, since P1 is the one forwarding based on the Adj_P1P2 label 💖.

For a label bound to a node segment, multiple strategies MAY be implemented. An implementation MAY try to evaluate the minimum ERLD value along the node segment path. If an implementation can't find the minimum ERLD along the path of the segment, or it doesn't support computing the minimum ERLD, it SHOULD instead use the ERLD of the tail-end node. Using the ERLD of the tail end of the node segment mimics the behavior of [RFC6790], where the ingress only cares about the egress of the LSP 🫶. In the example, if the implementation supports computing the minimum ERLD along the path, the ERLD for the label Node_P9 would be the minimum ERLD between nodes {P2,P3,P4 ..., P8}. If the implementation doesn't support that computation, it will use the ERLD of P9 (the tail-end node of the Node_P9 SID). Evaluating the minimum ERLD gives the more optimal ELI/EL placement, but it makes insertion more complex 🤯. The path to the Node SID may change over time, so the minimum ERLD has to be recomputed for each topology change, and that recomputation may mean the ELI/ELs have to move.

For a label bound to a Binding Segment, if the Binding Segment describes a path, an implementation MAY also try to evaluate the minimum ERLD along that path. If the implementation can't find the minimum ERLD along the path of the segment, or it doesn't support that evaluation, it SHOULD instead use the ERLD of the node advertising the Binding SID. Just like with the node segment, evaluating the minimum ERLD adds complexity to the ELI/EL insertion process 🌸.

7.2.2. Segment Type

Depending on the type of segment a particular label is bound to, an implementation can deduce that this label will be subject to load-balancing on the path 🦋.

7.2.2.1. Node SID

An MPLS label bound to a Node SID represents a path that may cross multiple hops. Load-balancing may be needed at the node starting this path, but also at any node along the path 🌈.

In Figure 7, let's consider a path from PE1 to PE2 with the stack pushed by PE1: <Adj_P1P2, Node_P9, Adj_P9PE2, Service_label>.

If, for example, PE1 is limited to pushing 6 labels, it can add a single ELI/EL within the label stack. An operator may want to favor a placement that allows load-balancing along the Node SID path. In Figure 7, P3, which is along the Node SID path, requires load-balancing between two equal-cost paths 👑.

An implementation MAY try to evaluate whether load-balancing is really required within a node segment path. This could be done by running an additional SPT (Shortest Path Tree) computation and analyzing the node segment path, so that a node segment that doesn't really require load-balancing isn't preferred when placing ELI/ELs. This inspection may be time consuming for implementations, and it comes without a 100% guarantee, because a node segment path may use LAGs that are invisible to the IP topology 🙈. As a simpler approach, an implementation MAY consider that a label bound to a Node SID will be subject to load-balancing and require an ELI/EL.

7.2.2.2. Adjacency-Set SID

An adjacency-set is an Adj-SID that refers to a set of adjacencies. When an adjacency-set segment is used within a label stack, an implementation can deduce that load-balancing is expected at the node that advertised this adjacency segment. An implementation MAY favor the insertion of an ELI/EL after the Adj-SID representing an adjacency-set 💜.

When an adjacency segment representing a single IP link is used within a label stack, an implementation can deduce that load-balancing may not be expected at the node that advertised this adjacency segment 💅.

An implementation MAY NOT place an ELI/EL after a regular Adj-SID in order to favor the insertion of ELI/ELs following other segments.

Heads up: an adjacency segment representing a single IP link may still require load-balancing! This is the case when a LAG (L2 bundle) is implemented between two IP nodes and the L2 bundle SR extensions [RFC8668] are not implemented. In that situation, it could be useful to insert an ELI/EL in a readable position for the LSR advertising the label associated with the adjacency segment. To communicate the need for load-balancing for a particular Adjacency SID to ingress nodes, a user can enforce the use of the L2 bundle SR extensions defined in [RFC8668], or can declare the single adjacency as an adjacency-set 🚨.

When the L2 bundle SR extensions [RFC8668] are used, adjacency segments may be advertised for each member of the bundle. In this case, an implementation can deduce that load-balancing is not expected on the LSR advertising this segment, and it MAY NOT insert an ELI/EL after the corresponding label 🍓.

7.2.2.5. Adjacency SID Representing an L2 Bundle

When the L2 bundle SR extensions [RFC8668] are used, an adjacency segment may be advertised to represent the bundle. In this case, an implementation can deduce that load-balancing is expected on the LSR advertising this segment, and it MAY insert an ELI/EL after the corresponding label ✨.

7.2.3. Maximizing Number of LSRs That Will Load-Balance

When placing ELI/ELs, an implementation MAY optimize the number of LSRs that both need to load-balance (i.e., have ECMPs) and will be able to perform load-balancing (i.e., the EL is within their ERLD) 🧠.

Let's look at a path from PE1 to PE2 with the stack pushed by PE1: <Adj_P1P2, Node_P9, Adj_P9PE2, Service_label>. All routers have an ERLD of 10 except P1 and P2, which have an ERLD of 4. PE1 can push 6 labels, so only a single ELI/EL can be added 🎀.

In this example, adding an ELI/EL after Adj_P1P2 only allows load-balancing at P1. Inserting it after Adj_PE2P9 allows load-balancing at P2, P3 ... P9, which maximizes the number of LSRs that can perform load-balancing 👑.

7.2.4. Preference for a Part of the Path

An implementation MAY allow the user to favor a part of the end-to-end path when the number of ELI/ELs that can be pushed isn't enough to cover the entire path. For example, a service provider may want to favor load-balancing at the beginning of the path or at the end of the path, so the implementation favors putting the ELI/ELs near the top or the bottom of the stack 🌷.

7.2.5. Combining Criteria

An implementation MAY combine multiple criteria to determine the best ELI/EL placement. However, combining too many criteria could lead to implementation complexity and high resource consumption. Each time the network topology changes, a new evaluation of the ELI/EL placement will be necessary for each impacted LSP 🥲.

8. A Simple Example Algorithm

A simple implementation might take the ERLD into account when placing ELI/ELs, while trying to minimize the number of ELI/ELs inserted and trying to maximize the number of LSRs that can load-balance 💖.

The example algorithm is based on the following considerations:

  • An LSR that can insert a limited number of <ELI, EL> pairs should insert such pairs deeper in the stack.
  • An LSR should try to insert <ELI, EL> pairs at positions that maximize the number of transit LSRs for which the EL occurs within the ERLD of those LSRs.
  • An LSR should try to insert the minimum number of such pairs while trying to satisfy the above criteria.

The pseudocode of the example algorithm is shown below 🧚.

   Initialize the current EL insertion point to the
     bottom-most label in the stack that is EL-capable
   while (local-node can push more <ELI,EL> pairs OR
             insertion point is not above label stack) {
       insert an <ELI,EL> pair below current insertion point
       move new insertion point up from current insertion point until
           ((last inserted EL is below the ERLD) AND (ERLD > 2)
                             AND
            (new insertion point is EL-capable))
       set current insertion point to new insertion point
   }

   Figure 8: Example Algorithm to Insert <ELI, EL> Pairs in a Label
                                Stack

When this algorithm is applied to the example described in Section 3, it results in ELs being inserted in two positions: one after the label L_N-D and another after L_N-P3. So the resulting label stack would be <L_N-P3, ELI, EL, L_A-L1, L_N-D, ELI, EL> 🎉.

9. Deployment Considerations

As long as LSR node data-plane capabilities are limited (number of labels that can be pushed or number of labels that can be inspected), hop-by-hop load-balancing of SPRING-encapsulated flows will require trade-offs 🫠.

The entropy label is still a good and usable solution, because it allows load-balancing without having to perform deep packet inspection on each LSR. It doesn't seem reasonable to have an LSR inspecting UDP ports within a GRE tunnel carried over a 15-label SPRING tunnel 😭.

Due to the limited capacity for reading a deep stack of MPLS labels, multiple ELI/ELs may be required within the stack. This directly impacts the head-end's capacity to push a deep stack, since each ELI/EL inserted requires two additional labels to be pushed 📚.

Placement strategies for ELI/ELs are required to find the best trade-off. Multiple criteria could be taken into account, and some level of customization (by the user) is required to accommodate different deployments. Analyzing the path of each destination to determine the best ELI/EL placement may be time consuming for the control plane, so we encourage implementations to find the best trade-off between simplicity, resource consumption, and load-balancing efficiency 💕.

In the future, hardware and software capacity may increase data-plane capabilities and remove some of these limitations, which would increase load-balancing capability using entropy labels 🚀.

10. Options Considered

Different options that were considered to arrive at the recommended solution are documented in this section 🗂️.

These options are detailed here only for historical purposes 🕰️.

10.1. Single EL at the Bottom of the Stack ✨

Okay bestie, option one is the simplest vibe: one EL for the whole label stack 🧚. The source LSR S tucks the entropy label at the very bottom. In the Section 3 example, LSR S ends up with <L_N-P3, L_A-L1, L_N-D, ELI, EL> followed by <remaining packet header> 📦. (The notation is the one from [RFC6790], so go look there if you need the full picture 💅.)

The catch is that every new SID makes the stack taller, which pushes the EL deeper and deeper 😭. Transit LSRs then have to read more bytes of the packet header just to make a forwarding decision. In the Section 3 example, if P1 has an ERLD of 3, it can't see the EL because the EL sits below that depth, so it load-balances badly across the parallel links L3 and L4 💀. A load-balanced design using this approach MUST ensure that every intermediate LSR can read the maximum label stack depth that the source-routing application needs. No cap, that's a big ask 🙈.

This option got rejected because plenty of hardware can only read a low maximum label depth 🥲. Going this way could wreck load-balancing with EL across a big chunk of the network, and in a service-provider network, that's a dealbreaker 🚫.

10.2. An EL per Segment in the Stack 🎀

Option two gives every segment (every label) its own EL 💖. When traffic on a segment needs load-balancing, the source LSR pushes an <ELI, EL> pair right before pushing that segment's label. In the Section 3 example, the source LSR S would end up with <L_N-P3, ELI, EL, L_A-L1, L_N-D, ELI, EL>, and all of the ELs can be the same value 🦋. The big win is that reading the EL at an intermediate LSR doesn't depend on how deep the stack is, so it also doesn't depend on which source-routed tunnel application with label stacking is running 🙌.

The downside is that the stack gets almost 3 times as deep as the number of labels 😩. The network design SHOULD ensure source LSRs can actually push a stack that deep. Bandwidth overhead and potential MTU issues from deep stacks SHOULD also be considered in the design 📏.

This option was rejected because some hardware can only push a limited number of labels 🛑. Using it would force hardware to push two extra labels per tunnel label, which caps how many tunnels can be stacked in one LSP and therefore limits what kinds of LSPs you can build. The group considered that totally unacceptable 💅.

10.3. A Reusable EL for a Stack of Tunnels 🌸

This one is clever. An LSR that terminates a tunnel reuses that tunnel's EL for the next inner tunnel 🔁. It saves the EL from the outer tunnel when that tunnel ends, then puts it back below the next inner tunnel's label during the label-swap operation. The LSR that stacks the tunnels SHOULD insert one EL below the outermost tunnel, and it SHOULD NOT insert ELs for any of the inner tunnels 🙅‍♀️. The penultimate hop LSR of a segment MUST NOT pop the ELI and EL, even though they end up as the top labels, because the terminating LSR of that segment is going to reuse that EL for the next segment 🛑.

Walking through the Section 3 example: the source LSR S encodes <L_N-P3, ELI, EL, L_A-L1, L_N-D>. At P1, the outgoing stack is still <L_N-P3, ELI, EL, L_A-L1, L_N-D> after it load-balances onto L3 or L4 ✨. At P3, the outgoing stack becomes <L_N-D, ELI, EL>. At P2, it's also <L_N-D, ELI, EL>, and P2 load-balances onto either P4 or P5 🍓. Reading the EL at an intermediate LSR (like P1) doesn't depend on how deep the stack is, or on the specific use case the label stack serves 🧚.

This option got rejected because existing hardware would need a big change to its label-swap operations 😵.

10.4. EL at Top of Stack 👑

This is a small twist on the reusable EL option: keep the EL at the top of the stack instead of below the tunnel label 🌈. Any LSR that isn't terminating a segment SHOULD keep the received EL at the top when it forwards the packet along the segment. An LSR that does terminate a segment SHOULD use the EL from the terminated segment at the top when it forwards onto the next segment 🫶.

This one was also rejected, because existing hardware would still need a big change to its label-swap operations 💀.

10.5. ELs at Readable Label Stack Depths 🦋

Here the source LSR inserts ELs for the tunnels at depths where every LSR on the path that has to load-balance can reach at least one EL 🎯. The source LSR MAY have to insert several ELs at different depths, since intermediate LSRs can differ in how deep they can read 🤷‍♀️. The label stack depth access value of each intermediate LSR MUST be known before anyone can build that stack. How that value gets determined is outside the scope of this document, but it can be advertised using a protocol such as an IGP 📣.

Applying this to the Section 3 example: if LSR P1 needs to see an EL within a depth of 4, the source LSR S would encode <L_N-P3, ELI, EL, L_A-L1, L_N-D, ELI, EL>, where the ELs would typically all have the same value 💖.

If the ERLD varies along the path, and the LSR inserting the <ELI, EL> pairs has no limit on how many pairs it can add and knows exactly where they go, then this option is the same as the recommended solution in Section 7 ✨.

Also, a refined version of this solution balances the number of labels you push against the amount of entropy you want, and that refinement is the solution described in Section 7 🧠.

11. IANA Considerations 🌷

This document has no IANA actions. Nothing to register, no tables to update, we're chillin 😌.

12. Security Considerations 🔐

Okay, this part is serious, so listen up 🚨. Compared to [RFC6790], this document introduces the notion of ERLD and MSD, and it MAY require an ingress node to push multiple ELIs/ELs 😳. These changes do not introduce any new security considerations beyond those already listed in [RFC6790] 🛡️. So the threats are the same ones [RFC6790] already covers, nothing extra on top 💜.

13. References 📚

13.1. Normative References 💌

[RFC6790]: Kompella, K., Drake, J., Amante, S., Henderickx, W., and L. Yong, "The Use of Entropy Labels in MPLS Forwarding", RFC 6790, DOI 10.17487/RFC6790, November 2012, <https://www.rfc-editor.org/info/rfc6790>.

[RFC2119]: Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.

[RFC8174]: Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.

[RFC8402]: Filsfils, C., Ed., Previdi, S., Ed., Ginsberg, L., Decraene, B., Litkowski, S., and R. Shakir, "Segment Routing Architecture", RFC 8402, DOI 10.17487/RFC8402, July 2018, <https://www.rfc-editor.org/info/rfc8402>.

[RFC8660]: Bashandy, A., Ed., Filsfils, C., Ed., Previdi, S., Litkowski, S., and R. Shakir, "Segment Routing with the MPLS Data Plane", RFC 8660, DOI 10.17487/RFC8660, December 2019, <https://www.rfc-editor.org/info/rfc8660>.

13.2. Informative References 🔎

[ISIS-ELC]: Xu, X., Kini, S., Psenak, P., Filsfils, C., Litkowski, S., and M. Bocci, "Signaling Entropy Label Capability and Entropy Readable Label Depth Using IS-IS", Work in Progress, Internet-Draft, draft-ietf-isis-mpls-elc-10, 21 October 2019, <https://tools.ietf.org/html/draft-ietf-isis-mpls-elc-10>.

[OSPF-ELC]: Xu, X., Kini, S., Psenak, P., Filsfils, C., Litkowski, S., and M. Bocci, "Signaling Entropy Label Capability and Entropy Readable Label-stack Depth Using OSPF", Work in Progress, Internet-Draft, draft-ietf-ospf-mpls-elc-12, 25 October 2019, <https://tools.ietf.org/html/draft-ietf-ospf-mpls-elc-12>.

[RFC8668]: Ginsberg, L., Bashandy, A., Filsfils, C., Nanduri, M., and E. Aries, "Advertising Layer 2 Bundle Member Link Attributes in IS-IS", RFC 8668, DOI 10.17487/RFC8668, December 2019, <https://www.rfc-editor.org/info/rfc8668>.

[RFC7855]: Previdi, S., Ed., Filsfils, C., Ed., Decraene, B., Litkowski, S., Horneffer, M., and R. Shakir, "Source Packet Routing in Networking (SPRING) Problem Statement and Requirements", RFC 7855, DOI 10.17487/RFC7855, May 2016, <https://www.rfc-editor.org/info/rfc7855>.

[RFC8476]: Tantsura, J., Chunduri, U., Aldrin, S., and P. Psenak, "Signaling Maximum SID Depth (MSD) Using OSPF", RFC 8476, DOI 10.17487/RFC8476, December 2018, <https://www.rfc-editor.org/info/rfc8476>.

[RFC8491]: Tantsura, J., Chunduri, U., Aldrin, S., and L. Ginsberg, "Signaling Maximum SID Depth (MSD) Using IS-IS", RFC 8491, DOI 10.17487/RFC8491, November 2018, <https://www.rfc-editor.org/info/rfc8491>.

[MSD-BGP]: Tantsura, J., Chunduri, U., Talaulikar, K., Mirsky, G., and N. Triantafillis, "Signaling MSD (Maximum SID Depth) using Border Gateway Protocol Link-State", Work in Progress, Internet-Draft, draft-ietf-idr-bgp-ls-segment-routing-msd-09, 15 October 2019, <https://tools.ietf.org/html/draft-ietf-idr-bgp-ls-segment-routing-msd-09>.

Acknowledgements 💐

The authors would like to thank John Drake, Loa Andersson, Curtis Villamizar, Greg Mirsky, Markus Jork, Kamran Raza, Carlos Pignataro, Bruno Decraene, Chris Bowers, Nobo Akiya, Daniele Ceccarelli, and Joe Clarke for their review, comments, and suggestions 🫶✨.

Contributors 🌟

Xiaohu Xu, Huawei, Email: xuxiaohu@huawei.com 🐣

Wim Hendrickx, Nokia, Email: wim.henderickx@nokia.com 🌼

Gunter Van de Velde, Nokia, Email: gunter.van_de_velde@nokia.com 🌈

Acee Lindem, Cisco, Email: acee@cisco.com 🍭

Authors' Addresses 🎀

Sriganesh Kini, Email: sriganeshkini@gmail.com 💜

Kireeti Kompella, Juniper, Email: kireeti@juniper.net 🦋

Siva Sivabalan, Cisco, Email: msiva@cisco.com 🌸

Stephane Litkowski, Orange, Email: slitkows.ietf@gmail.com 🧚

Rob Shakir, Google, Email: robjs@google.com ⭐

Jeff Tantsura, Apstra, Inc., Email: jefftant.ietf@gmail.com 👑

📦 where this page comes from