ECMP and Source Routing and Multipath Tables — Oh my!

This post does not reflect the views of current, past, or future employers. The opinions in this article are my own.

For our next stop on the Grand Tour of Affinity we’re going to take a look at Equal Cost Multipath (ECMP). This leads to a discussion on source routing and multipath including the new concept of Multipath Tables. Let’s dive in!

ECMP

*Equal-cost multi-path routing (ECMP*) is a technique in routing where next-hop packet forwarding to a single destination can occur over multiple “best paths” which tie for top place in routing metric calculations. ECMP works on routers as they forward packets to their destination. ECMP was conceived circa 2000 and is a stalwart of the Internet. It’s universally supported by most routing protocols and nearly all routers to provide good utilization and high throughput across the Internet.

ECMP starts with routing protocols doing their thing. Routing protocols are used to determine the best path for packets to take to their destination. “Best” can be described as the lowest “cost” route for a packet where cost may be a function of different metrics like the number of hops, delay, and reliability. Often, by design, a router will determine that there are multiple “best routes” to a destination. When a packet is received by a router, the router gets to choose which of the best routes the packet should take. This selection process is ECMP.

Similar to RSS, ECMP endeavors to achieve per-flow affinity. Generally, packets for the same flow should follow the same route to ensure in-order delivery at the destination. The mechanism for this is pretty much the same as that in RSS — the router computes a hash for the 4-tuple in each packet, takes a modulo of the hash by the number of possible nexthops, and then the resulting value is mapped to the selected next hop.

ECMP is cool in that it “just works” with existing protocols. Routers only need the IP addresses and port numbers from a packet, so ECMP works with TCP, UDP, SCTP, etc. Even better, with IPv6 ECMP could alternatively be based on just a three tuple of IPv6 addresses and the flow label — this works for any transport layer protocol and obviates the need for routers to perform deep parsing into packets. **Note to router vendors, please switch to using the IPv6 flow label instead of ports for EMCP, it’s good for everyone!

A side effect of the ECMP is that it facilitates a type of source routing from hosts. A host can affect the routing of a packet by modulating the “entropy value” that is input to ECMP. This is a very powerful tool that is an evolving story even today.

ECMP. This shows an example of ECMP in action where packets for each of the orange, green, magenta, and blue flows take their own path to the destination.

Transmit rehash

The idea of tweaking packets to perform ECMP source routing dates back to a Linux patch I wrote in 2015 titled: “net: Recompute sk_txhash on negative routing advice”. The idea is to monitor connection progress and if a connection is starting to fail, like there are several retransmissions or round trip time goes through the roof, then we “rehash” the transmit hash for the connection. The transmit hash is used to derive entropy values like the IPv6 flow label or UDP source port in UDP encapsulation.

The transmit hash, sk_hash in Linux, is not a computed hash value but simply a random number. So rehashing is done by setting a new random value. When subsequent packets are sent, the new value is used to set the entropy values in packets in hopes of finding a better route. This technique is probabilistic. When we modulate the entropy value we don’t know the exact effects in the network, and it’s possible we’ll wind up using the same route. Nevertheless, it’s lightweight and seems to work well at scale.

We can’t change the TCP ports for an open connection, so for TCP this works only by modulating the IPv6 flow label. UDP offers more flexibility. For UDP encapsulation protocols like VXLAN and Geneve, the UDP source port number isn’t fixed and can be used as an entropy value. Similarly, transport protocols over UDP, like QUIC, also allow the source port to be set as an entropy value.

One issue we hit with this technique is that stateful firewalls don’t like routes to change for connections they’re tracking. If packets for a flow take different routes then they might not always hit the same firewall which can lead to dropped connections. This problem is an artifact of stateful firewalls not being designed to handle multipath, but unfortunately it was significant enough that we had to disable the feature by default. If you’d like to give it a whirl take a look at the SO_TXREHASH socket option!

Transmit rehash. In this example, one of the links in a path to the destination is broken so that packets are being dropped (top). The sending host detects the packet loss and rehashes the connection so that a different route is taken and packets successfully reach the destination (bottom).

Multipath transport protocols

Similar to RSS, a single flow sending all packets over one path can limit throughput. So there’s motivation to send packets across different paths even for a single flow. This is the goal of multipath transport protocols.

Multipath is supported by several transport protocols as Multipath-foo including MPTCP, MP-QUIC, MP-DCCP, and MP-SCTP. The basic idea is to employ simultaneous network connections for a single logical connection, while still presenting a standard socket application programming interface (API) to the application as though it were a single flow. Multipath transport protocols work by creating a bundle of individual sub-connections and presenting it to the application as a single connection. To the network, this just looks like a set of independent connections, but at the destination end hosts data from each connection is assembled into a stream as though it had been received on one connection.

Multipath transport protocols are an impressive innovation and bring additional benefits beyond improved throughput. For instance, in wireless networks, handover leverages multiple paths between a device and the network to ensure a smooth and uninterrupted transition during handover.

Multipath transport protocols. This shows an example of a multipath transport protocol where different sub-flows are created. Packets for each sub-flow, indicated by the different shades of blue, take their own path to the destination At the destination the payload is received on one socket.

Random Packet Spraying

We can take source routing to the extreme by changing the entropy value for every packet. This is called *Random Packet Spraying, or the other RPS as I like to call it :-). For instance, a host could set the flow label to a random value for every packet. The effect of this is that packets will be uniformly distributed across all the best paths even for a single flow. Of course, per-flow affinity to a path is out the window and this pretty much guarantees a bunch of out-of-order packets, but those issues can be addressed in well managed networks. This technique is increasing in popularity for networks running AI/ML workloads where there’s often not enough active flows to achieve a uniform distribution across network links (i.e. they have low flow entropy*).

For random packet spraying to work efficiently, end hosts must be ready to receive out-of-order packets. And not just a few packets, but out-of-order could be a regular occurrence. The upshot is that transport protocols need adapt to seamlessly handle out of order packets. TCP for instance, handles out of order packets correctly but at the cost of losing some optimizations. Emerging transport protocols for high performance datacenter networks are assuming out-of-order from the get-go and so it won’t be a problem.

Random packet spraying. This shows packets for a single connection being randomly sprayed across all paths.

Multipath tables

It’s desirable to combine the best characteristics of transmit rehash, random packet spraying, and multipath transport protocols into one grand solution. For the sake of argument, let’s assume we’d like a solution that adheres to the KISS principle in that it doesn’t require special network support (i.e. uses ECMP and doesn’t depend on adaptive routing), doesn’t require a bunch of protocol or implementation (i.e. no elaborate multipath transport protocols needed), doesn’t require a bunch of configuration, is transparent to the on-the-wire protocol, and leverages existing code.

I’m going to call this solution Multipath Tables. There is one requirement in that we need the transport protocol to define a Packet Sequence Number (PSN) that is used when sending data and for acknowledgements. So QUIC is a candidate for the solution, but probably not a protocol like TCP since its sequence numbers are in units bytes. New transport protocols, like UET and Falcon, also employ PSNs and are over UDP to boot, so this solution should have broad applicability.

The heart of the multipath tables solution is, well, a multipath table :-). Each entry in a multipath table describes one path to the destination of a flow. The information in an entry includes an entropy value that identifies the path in EMCP, and a set of path quality metrics. The metrics might include typical items for congestion control algorithms like:

• Last send time
• Number of retransmissions
• Smoothed round trip time
• Round trip time variance

The big win of this solution is that it doesn’t employ multiple transport connections. Everything is done in the context of just one transport connection. From the point of view of the transport protocol implementation, multipath tables can be entirely transparent. The multipath table is a modular component that operates at a level below the main congestion control algorithm for the connection.

The multipath table is accessed at two times: when a packet is being sent and when a PSN is acknowledged.

Sending packets with multipath tables

When a packet is being sent, a “multipath tables send” function is called. The input is a PSN and boolean indicating a packet retransmission, and the output is an entropy value. The function does the following:

1. Take a modulo of the PSN being sent by the number of elements in the multi-path table. Access the entry in the multipath table by this index.
2. For the identified path, check if a rehash is necessary. This is done by evaluating the quality metrics and determining whether the path is bad. Note that this is a relative comparison of this path versus to the other paths in the table. For instance, if the round trip time of an entry is three times that of other paths in the table then it might be time to rehash.
3. If a rehash is needed then the entropy value is set to a random number and the quality metrics are reset.
4. Return the entropy value. The caller will use that to derive the packet entropy values (i.e. UDP source port or IPv6 flow label).

Acknowledged packets with multipath tables

When an acknowledgement is received the “multipath tables ack” function is called. The input is the acknowledged PSN. The function performs the following:

1. Take a modulo of the acknowledged PSN by the number of elements in the multipath table. Access the entry in the multipath table by this index.
2. Update the quality metrics. For instance, this might entail calculating and setting the round trip time (current time minus send time recorded in the entry) and updating the round trip variance variance.

How big does a multipath table need to be

All this raises a pertinent question: how big do multipath tables need to be? If we make them too small then we won’t have enough entries to get a uniform distribution across paths. On the other hand, we don’t want tables to be too big due to memory constraints especially if tables are maintained per transport connection. Fortunately, the math is straightforward enough to give some reasonable guidance.

Assume there are K paths in the network, and each entropy value maps to one of those paths in ECMP with a uniform distribution. We create a “multipath table” as an array of N entries. Each entry contains a random entropy value that maps to one of the K paths. For a multipath table of N elements with K possible paths, the number of elements that map to a particular path follows a Binomial distribution given as B(N, 1/K). So for some K, we want to find N, i.e. the size of the multipath table, that best meets our requirements.

Network with eight paths. This shows a CLOS network that allows eight different paths between two hosts. Three of the paths from the orange host to the purple host are highlighted.

As an example, let’s assume there are eight paths in the network (i.e. K=8). We assume that N is a power of two, so let’s consider the table sizes of 8, 16, 32, 64, 128, and 256 entries. The graph of the binomial distribution for each N is shown below.

Binomial Distributions for Multipath Tables with K=8 and various values of N.

We can also present the data in tabular form:

Let’s look at the numbers. For table sizes 8, 16, and 32 we see that there’s a real possibility that some paths aren’t even represented in the table (this is an effect of the birthday paradox). Hence for those values it’s really hard to achieve a uniform distribution and for me they’re right out! For table sizes 64, 128, and 256 it’s likely that each of the eight paths will be represented in the table, so let’s consider the path that is minimally represented in the table. As the size of the table increases, the proportion of the minimally represented path increases (up to a maximum of 12.5%). For 64 entries, we expect the least represented path to be about 4.7% of the entries, but for 128 it’s 6.25% and for 256 it’s 8.2%.

Based on these numbers, personally I would choose either 128 or 256 entries in the multipath tables. Sixty-four entries might be tolerable if memory is a real concern, but I wouldn’t want to go below that!