The fast path/slow path mirage

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

A common “go to” optimization in computing is to divide processing into a fast path and a slow path. I’m going to call this the fast path/slow path split. Basically, the fast path/slow path split optimizes for the common case. We apply optimized techniques in either hardware or software to make the fast path, i.e. the common case or normal case, run like gangbusters with high performance and efficiency. For processing the slow path, i.e. uncommon cases, exceptions, or outliers, we perform processing in a generic but slower software environment where we can take our time. On the surface all this sounds great, but reality tells a different story!

As many an engineer has already figured out, the fast path/slow path split is often an alluring mirage. It’s easy enough to design a system with a well defined fast path and slow path. However, time and time again we see the fast path/slow path split fails to deliver results in real deployment. This is one area where reality often butts heads with theory.

The problems caused by over reliance on fast path/slow path are pervasive. I’ll go so far as to say that the fast path/slow path split in routers has to a large extent ruined the Internet by severely limiting our ability to deploy new protocols or innovative features. One might argue that the current Internet infrastructure is based on twenty-five year old designs and back then “we didn’t know any better”. But that was then and this is now. We have the opportunity to address the problems of fast path/slow path split. Spoiler alert: the best way to fix the problem is to simply eliminate the fast path/slow path split :-).

Fast path example. This shows the logical diagram of Azure ExpressRoute FastPath. ExpressRoute FastPath routes network traffic directly to virtual machines, bypassing the ExpressRoute virtual network gateway.

What’s the problem

The fast path/slow path split has a number of inherent problems.

Amdahl’s Law is unforgiving

Understanding *Amdahl’s law *is fundamental if you’re working on system performance. It limits the effectiveness of performance improvements and it’s unyielding — as they “say it’s the Law!”. One way to phrase Amdahl’s Law is that optimizations are restricted by the fraction of the task that can’t benefit from the improvement. This applies to the fast path/slow path split.

Suppose we are designing a processing system and we have a choice between implementing a fast path/slow path split where the slow path is ten times slower than the fast path, or we can avoid the fast path/slow path split with a design that makes all operations fifty percent slower than the projected fast path performance. Which is better? Well it depends on the proportion of time spent in the fast path.

For example, suppose a fast path operation takes 1usec and the slow path operation takes ten times that or 10usecs. If we take the fast path 90% of the time and the slow path 10% of the time then that average performance is 0.9 1usec + 0.1 10usecs = 1.9usecs. The alternative of making all operations 50% slower gives average performance of 1.5usecs. So in this case slowing down actually makes things faster ;-).

It’s about tail latency, stupid

Continuing the above example, suppose we’re clever and we get the slow path down just 1% of the time. Now the average performance is 0.99 1usec + 0.01 10usecs = 1.09usecs. Awesome! That’s way better than 1.5usecs we get from no fast path/slow path so ship it! Well hold your hold horses — there’s the problem of tail latency!

*Tail latency* is another one of those things that needs to be considered when doing system performance work. For large scale distributed applications, including AI/ML, overall performance tends to correlate to the tail of latency. For instance, if I distribute parts of a task to a thousand machines and we need to wait for all of them to reply, then the performance of the application is bound to the slowest machine. So if 999 of the servers respond in 1msec, but one takes 10msecs, then the time for the whole operation is 10msec :-(. Usually we measure tail latency as the 90th, 99th, or 99.9th percentile. Tail latency is so critical that often we don’t even care much about average latency and hardly ever consider best case latency.

Going back to our example, the 99th percentile latency with the fast path/slow path split is 10usecs, but the 99th percentile in the no fast path/slow path alternative is 1.5usecs. So the no fast path/slow path design wins if tail latency matters.

Your slow path is my fast path

As the above examples show, the proportion of time spent in the fast path versus the slow path impacts performance (at least considering average performance). Hmm, this effect sounds familiar, where have we seen it before? Oh, that’s right, we saw this with regards to caches. A cache hit can be considered a fast path operation, and a cache miss is a slow path operation. We can express the overall average performance of a cache by the application’s cache hit rate (or miss rate). Obviously, the goal is to maximize the cache hit rate for best performance.

When we’re designing a system with a fast path/slow path split, there are two factors that will predict performance: 1) the performance of the slow path and the fast path, 2) the percentage of time that the slow path is taken. We can quantify the performance as:

Performance = p slow_path + (1 — p) fast_path

The slow_path and fast_path performance tends to be fixed by the design and implementation. For instance, the latency for a CPU cache hit and cache miss are dependent on the hardware architecture and there’s not a lot of variance between different workloads. On the other hand the percentage of time that fast path is taken, p, can be quite variable between workloads.

So p can be highly variable. In the case of memory caches we didn’t worry too much about this because to a large extent the application can control the cache hit rate with good programming techniques. But for something like networking, all bets are off — we don’t know a priori what the networking load will be and what usage patterns will arise.

When a system is being designed with a fast path/slow path split the designer will often take a guess at what the slow path is. The canonical example is in TCP offload where a designer might assume that connection setup and tear down is the slow path, and normal data operations in TCP established state is the fast path. Such an assumption is valid up to the point that the solution is only used on servers with a low connection rate. If it’s used on an Internet facing server with a high connection rate then we’d find that the fast path probably should have included connection setup and tear down. The effects of mispredicting how the fast path and slow path should be split might be so bad that we find ourselves wishing we didn’t have the optimization in the first place.

Fast path/slow path is an attacker’s paradise

The fast path/slow path is naturally a Denial of Service attack. All the attacker needs to do is send a flood of requests that force a victim to spend most of its time in the slow path. Case in point is SYN attacks. About “five minutes” after the first commercial servers came up they were subject to SYN attacks. It’s pretty simple really, an attacker just sends a server a bunch of bogus TCP SYN packets so that the server performs a lot of processing and creates a bunch of state in memory that serves no purpose. The attack works because it’s not possible to distinguish an attacker’s packets from legitimate packets, and the attack is effective if it drains resources to the point that SYN packets for legitimate users are dropped so that they can’t connect to the server.

A TCP SYN attack. An attacker sends a bunch of SYN packets with spoofed IP addresses. The victim host processes the packets in the slow path that requires memory allocation in the form of a connection state for each SYN. The host sends a SYN-ACK to the bogus source address of the SYN so there’s no response. Eventually, the connection state will timeout but the damage has been done, the attacker forced the victim to burn processing cycles and allocate memory for no productive effect. The attack is effective when the victim starts dropping SYN packets for legitimate connections. Image is from Research Gate.

Routers and fast path/slow path

Network routers are the poster child for the problems of fast path/slow path split. A network router, especially a core router on the Internet, is under a lot of pressure to forward packets very quickly with just a few nanoseconds of latency and multi-terabits per second of throughput. At these performance requirements, it behooves the router vendors to implement a fast path/slow path split. The fast path is for normal packet forwarding and is implemented completely in high performance hardware ASICs. The slow path is for exception cases like complex packets or for handling full route lookups, connection tracking, or firewall processing. The slow path might be implemented in software running on a CPU and can be 10x or even 100x worse performance than the hardware fast path.

While the need for a fast path/slow path split in routers is understandable, the ramifications of the design can be detrimental. For instance, to process packets quickly, hardware wants them to be simple. In the current Internet, one can expect that sending TCP and UDP packets over IPv4 and IPv6 will result in successful delivery. But that’s it! Sending anything else that doesn’t conform risks packets being dropped. The nature of the risk is similar to Amdahl’s Law in that it just takes one router in the path to dislike a packet and drop it, and it doesn’t matter if all the rest of the routers in the path are happy with the packet.

A particular problem of the fast path/slow path split in the extensibility constructs of network layer protocols — specifically we’re talking IPv4 options and IPv6 extension headers. I’ve already talked about the woes of trying to deploy IPv6 extension headers, and in particular how routers like to defer packets with Hop-by-Hop Options to a slow path CPU. This doesn’t work! Hop-by-Hop Options are a datapath mechanism not a control path mechanism, so the slow path is just slowing down the datapath of some application to the point where the latency is so great the packets aren’t useful (routers may as well drop packet instead of subjecting them to 100x latency). Additionally, if there’s a lot of traffic headed to the slow path it’s very likely that the CPU becomes overwhelmed and starts dropping packets — which also serves as a nice DoS attack.

Router fast path/slow path. Conceptual view of a router with a forwarding fast path in a specialized ASIC and a slow path that runs on the CPU. When a packet is received, it parses the packet headers and determines whether the packet takes the fast path or the slow path. The green arrow shows the processing of a packet in the fast path which is done entirely by the hardware engine. The red arrows show the processing for a packet in the slow path. The hardware sends the packet to a CPU for deep processing. The CPU processes the packet and then may forward it on. The cost of the slow path may be 10x to 100x that of the fast path.

How to fix the slow path/fast path conundrum

A man walks into the doctor’s office, wiggles his arm from side to side and says “Doctor my arm hurts when I do this.” — the doctor says “Then don’t do that!”. Okay, that’s a pretty lame joke, but I think you get the point :-) The way to fix the problems of the fast path/slow path fix is to eliminate it — that is just have “the path”. Obviously, I’m being a bit facetious! If eliminating the fast path/slow path were so simple, surely the problem would have been fixed. Admittedly, it’s not an easy fix, but I think it’s feasible with all the latest advancements in technology. Let’s consider how to fix the fast path/slow path problem in routers.

The extension header problem is a great example where different parties having their own ambitions need to meet halfway for a practical solution. When Hop-by-Hop Options for IPv6 were first specified in RFC2460 there were no limits. Routers were required to process all Hop-by-Hop options in a packet. In hindsight, this was a completely unrealistic requirement! We can’t even reasonably process an unlimited number of options in software, much less in high performance hardware. So router vendors deferred Hop-by-Hop Options processing to a slow path or would outright just drop them— either way the effect is the same to make them unusable.

There’s an old saying: “Don’t throw the baby out with the bathwater”. That’s effectively what the router vendors did. While requirements to process an unlimited number of Hop-by-Hop options in a packet were unrealistic, the router vendors’ response was solutions where they wouldn’t process even one Hop-by-Hop option in a packet. So that’s where we are: the protocol designers over-designed to require unlimited support, and router vendors under-designed to provide zero support. Can we meet in the middle? :-)

RFC9673 describes updated Hop-by-Hop processing requirements. The most interesting aspect is that the RFC acknowledges the existence of a fast path/slow path split in routers (maybe a first for IETF?). The requirements are aligned to that and the simple idea is that we want to avoid defining protocols that are likely to be handled in the slow path. In other words protocols should be designed with the fast path/slow path split in mind, and we want a datapath protocol to always be processed in fast path. So I think this is how protocol designers can do their part.

For router vendors, they need to expand the scope of the fast path a bit. For example, in the case of Hop-by-Hop options they should be able to process a reasonably small number of options in the fast path. To do that, they’ll want to introduce programmability into the forwarding path. Of course, simultaneously getting high performance and programmability at the same time has traditionally been considered an oxymoron (that’s why the slow path was created in the first place), but with emerging technologies in programmable datapaths this route is now feasible. We’ll talk more about this.