Gigaflow: Pipeline-Aware Sub-Traversal Caching for Modern SmartNICs

Annus Zulfiqar, Ali Imran, Venkat Kunaparaju, Ben Pfaff, Gianni Antichi and Muhammad Shahbaz

The virtual switch that routes every packet in a cloud server runs a long pipeline of lookup tables, so to go fast it caches the whole path a flow took — but modern SmartNICs have tiny memories, and caching each flow's entire path fills them up and misses constantly; this paper (University of Michigan, Purdue, Politecnico di Milano, and Feldera — Annus Zulfiqar, Ben Pfaff, Gianni Antichi, Muhammad Shahbaz) presents Gigaflow, which caches the small reusable segments of the pipeline that many flows share instead of whole paths, fitting far more coverage into the same NIC memory and hitting far more often.

The argument in one glance

Problem

The virtual switch is on every packet's path, and it is slow to run in full

In a cloud server, a virtual switch (vSwitch) sits between the physical network and the virtual machines and containers running on the host. Every packet in and out passes through it, and the vSwitch enforces the operator's policies — layer-2 forwarding, layer-3 routing, access-control lists, connection tracking, and more — as a pipeline of lookup tables the packet is matched against in sequence. Running that whole multi-table pipeline for every packet in software is expensive: it limits a vSwitch to well under ten gigabits per second per CPU core, which is far too slow for modern link rates and the traffic that distributed training, inference serving, and other tenant workloads generate. To cope, vSwitches like Open vSwitch cache: the first packet of a flow is run through the full pipeline once (the slow path), and the result is stored as a cache rule so that later packets of the flow skip the pipeline entirely (the fast path). As link speeds climbed, operators began offloading this fast-path cache onto SmartNICs — network cards that can do the table lookups in hardware at line rate (400 gigabits per second and beyond), taking the load off the CPU. That should solve the speed problem. But it introduces a new one rooted in what these NICs can hold.
What people did

Cache each flow's whole pipeline path as one rule (Megaflow)

The established caching scheme is Open vSwitch's Megaflow. When a packet traverses the full pipeline, the sequence of table lookups it went through — its "traversal" — is condensed into a single wildcard cache rule that captures the whole path and the final actions. Because the rule uses wildcards, it matches not just that exact flow but every flow that would take the same path, so one Megaflow rule can serve many flows. Later packets match this one rule and skip the pipeline. Offloaded to a SmartNIC's hardware cache, these Megaflow rules let traffic be switched at line rate without touching the CPU.
Why it fell short

Whole-path rules multiply combinatorially and overflow a tiny NIC cache

Caching entire traversals does not scale, because the number of distinct whole paths explodes. A vSwitch pipeline applies several independent policies — say a layer-2 decision, a layer-3 decision, and an access-control decision — and the number of distinct complete paths through the pipeline is roughly the product of the choices at each stage. Two flows that agree on layer-2 and layer-3 but differ in one access-control field are, to Megaflow, two entirely separate traversals needing two separate rules, even though almost all of their path is identical. So the whole-path rule count grows combinatorially with policy complexity. That collides with the hard limit of a SmartNIC: its hardware cache holds only on the order of ten to fifty thousand wildcard rules, far fewer than a software cache, because the fast on-chip memory is small and expensive. The result is that the cache overflows, many packets miss and fall back to the slow CPU path, and the offloaded switch fails to scale — the very growth in flow-rule space that offloading was meant to handle is what breaks it. What was missing was a way to cover that combinatorial path space without storing a rule per whole path.
This paper's idea

Cache the small reusable pipeline segments that flows share, and compose them

Gigaflow is a caching system for SmartNIC-offloaded vSwitches whose core insight is pipeline-aware locality: flows that take different whole paths through the pipeline still share smaller segments of that path. Gigaflow decomposes each traversal into sub-traversals — reusable subsequences of table lookups (for example, "this layer-2 plus layer-3 decision") that are common across many flows — and caches those instead of whole paths. It keeps several cache tables, each holding sub-traversal rules for a segment of the pipeline, and preserves the correct order so that a packet is matched against the segment caches in sequence and the partial results are composed into the final set of actions. Because a sub-traversal is shared by many flows, a modest number of sub-traversal rules can cover a combinatorially large number of whole paths: the same layer-2-plus-layer-3 segment, cached once, combines with many different access-control segments to serve flows that Megaflow would have needed a separate rule for each. The main design challenge is choosing where to split the pipeline into sub-traversals — the breakpoints that maximize how disjoint and therefore how reusable the segments are. Implemented on FPGA-based SmartNICs and evaluated on five real-world vSwitch pipelines, Gigaflow reports up to a 51 percent higher cache hit rate (25 percent on average), up to 90 percent fewer cache misses, and up to 450 times more rule-space coverage within the same limited NIC memory, all while keeping line-rate performance.

Why this problem is worth solving

The vSwitch is on the critical path of every packet in the cloud, so its scalability directly bounds what the whole end-host network stack can do.

Modern public and edge clouds depend on their end-host networking to support demanding tenant workloads — distributed training that shuffles gigabytes between machines, low-latency inference at the edge, and everything in between — and the vSwitch is the component every one of those packets must pass through. If the vSwitch cannot keep up, no amount of application optimization matters, because the bottleneck is in the path itself. Offloading to SmartNICs was the industry’s answer to the CPU being too slow, but it only helps if the offloaded cache actually holds enough rules to catch most traffic; a cache that overflows and sends packets back to the CPU squanders the offload. So making the SmartNIC cache scale to the growing flow-rule space is what determines whether line-rate offloaded switching is real or only nominal. Because this sits under all cloud communication, improving it is a broad win — the same infrastructure carries every tenant’s traffic.

The obstacle is a combinatorial blow-up, and the escape is to stop storing the product and start storing the factors.

The deep reason Megaflow does not scale on a SmartNIC is a mismatch of granularity. A vSwitch pipeline is built from several independent policy stages, and the number of distinct end-to-end paths through it is the product of the options at each stage — a combinatorial quantity. Caching one rule per whole path means the cache must grow as that product, which quickly dwarfs the tens of thousands of entries a NIC can hold. But the paths are not actually independent objects: they are combinations of a much smaller set of shared segments. Flows that differ in one stage share every other stage. Storing the whole path throws away that structure and re-stores the shared parts over and over. The right move is to cache the factors — the reusable segments — and reconstruct any whole path by composing them, so the cache grows with the sum of the options across stages rather than their product. That is a qualitatively different, far smaller quantity, and it is exactly the leverage a tiny hardware cache needs. The engineering question then becomes where to cut the pipeline so the segments are maximally shared, which is what Gigaflow’s sub-traversal design decides.

What people did before, and where it broke

Run the full pipeline per packet in software. Match every packet through all the vSwitch tables. Where it broke. It caps throughput at well under ten gigabits per second per core — far too slow for modern link rates and tenant workloads.
Cache each flow’s whole path as a Megaflow rule. Condense a full traversal into one wildcard rule so later flows skip the pipeline. Where it broke. The number of distinct whole paths grows combinatorially with policy complexity, so the rule count explodes.
Offload the Megaflow cache to a SmartNIC. Store the fast-path rules in NIC hardware to switch at line rate off the CPU. Where it broke. SmartNIC hardware caches hold only tens of thousands of rules, so the combinatorial rule set overflows, miss rates climb, and traffic falls back to the slow CPU path.
Just make the hardware cache bigger. Add more on-chip cache entries to fit more rules. Where it broke. The fast on-chip memory is small and expensive and cannot grow to the combinatorial rule count, so this does not close the gap.
The gap. No cache covered the combinatorial whole-path space within a tiny NIC memory by storing and composing the small, reusable segments that flows actually share.

How Gigaflow works

Caching reusable pipeline segments instead of whole paths

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Store the shared reusable pieces once, not every whole combination. Gigaflow’s founding move is to notice that whole pipeline paths are built from a small set of segments that many flows share, and to cache those segments rather than the exponentially many full paths. Extracting the common, reusable sub-structures out of many larger objects so the shared part is stored once instead of repeatedly is the same undertaking the work on finding reusable instructions via e-graph anti-unification (ISAMORE) covered elsewhere on this site pursues, factoring redundancy out of a combinatorial space by naming its shared building blocks. Gigaflow does this for vSwitch pipelines, turning whole traversals into reusable sub-traversals so a tiny cache covers a huge path space.

Do the packet processing on the NIC, at line rate, off the CPU. Gigaflow lives on the SmartNIC, matching and composing cached segments in hardware so the host CPU is not on the packet’s path — the whole reason the offload exists. Moving network-function work onto the NIC so it runs at line rate without consuming host CPU is the same principle the work on performance prediction of on-NIC network functions covered elsewhere on this site is built on, treating the NIC as the place where per-packet processing should happen. Gigaflow makes that offload actually scale, by fitting far more coverage into the NIC’s scarce cache than whole-path caching could.

Respect the structure of the packet-processing pipeline when you optimize it. Gigaflow’s decomposition is pipeline-aware: it cuts the pipeline at breakpoints chosen so the resulting segments are maximally shareable, and it preserves the pipeline’s order when composing them. Reasoning about the packet-processing pipeline’s structure — its stages and their ordering — to transform it into something more efficient is the same idea the work on a solver-aided compiler for packet-processing pipelines (CAT) covered elsewhere on this site develops, optimizing the pipeline by understanding how its tables compose. Gigaflow applies that structural view to caching, splitting the pipeline exactly where the sharing is greatest.

Following a packet through Gigaflow

Serving a new flow that reuses cached segments from earlier flows

A trace, drawn from the paper, of how Gigaflow matches and composes sub-traversal caches for a packet.

Step 1 of 5

A packet arrives for a flow never seen as a whole

A new flow reaches the SmartNIC. Its exact whole path has never been cached as a Megaflow rule, so a whole-path cache would miss and send it to the slow CPU pipeline — even though other flows sharing most of its path have been seen.

This is the case where whole-path caching wastes the sharing.

Why it works

Sub-traversals turn a product into a sum. Whole paths grow as the product of per-stage options → but caching shared segments and composing them → so coverage grows with the sum of options across stages, a far smaller number that fits a NIC cache.
Shared segments serve flows never cached whole. A whole-path cache misses any combination it has not seen → but if every segment of a new flow’s path was cached by other flows → so the new flow hits by reusing those segments and never touches the CPU.
Ordered composition preserves correctness. Splitting the pipeline could change behavior → but matching the segment caches in the pipeline’s correct order and composing their results → so the composed actions are exactly what the full pipeline would have produced.
Good breakpoints maximize reuse. Arbitrary splits would make segments that few flows share → but choosing breakpoints that keep segments disjoint in their fields → so each segment is shared by as many flows as possible and the cache is dense with reuse.
The scarce NIC memory finally scales. A tiny hardware cache overflows on whole-path rules → but the same memory holds far more coverage as reusable segments → so up to 450 times more rule space fits and hit rates rise while staying at line rate.

What it costs (trade-offs and scope)

A packet now traverses several cache tables instead of one. Composing sub-traversals means multiple ordered lookups per packet rather than a single whole-path match; the paper keeps this at line rate on its hardware, but the design trades one lookup for several to gain the coverage, so the per-packet cost structure is different.
Choosing where to split the pipeline is the hard part. The benefit depends on finding breakpoints that make segments maximally shareable; a poor decomposition yields segments few flows share, eroding the reuse advantage, so the quality of the split matters and is pipeline-dependent.
The gains depend on how much flows actually share. Pipelines and traffic where flows genuinely share large segments benefit most; a workload whose flows share little of their paths offers less pipeline-aware locality to exploit.
It composes with, rather than replaces, the vSwitch architecture. Gigaflow keeps the slow-path pipeline and the fast-path cache structure of systems like Open vSwitch, and targets the offloaded cache specifically; it is an improved caching layer, not a redesign of the whole switch.
Reported results are on FPGA SmartNICs and specific pipelines. The headline figures come from FPGA-based SmartNIC implementations and five real-world vSwitch pipelines; the exact hit-rate and coverage gains depend on the pipelines, traffic, and hardware evaluated.

The evaluation

Caching an offloaded vSwitch pipeline on a SmartNIC

Property	Full pipeline in software	Megaflow whole-path cache	Gigaflow
What is cached
Rule count versus policy complexity
Fits a SmartNIC hardware cache
Cache hit rate
Throughput

A comparison of ways to run a vSwitch pipeline on a SmartNIC. By caching the reusable sub-traversals that flows share and composing them per packet, rather than caching each flow's whole path (Megaflow), Gigaflow fits up to 450 times more rule-space coverage in the same limited NIC memory and reports up to a 51 percent higher cache hit rate (25 percent on average) and up to 90 percent fewer misses at line rate, across five real-world vSwitch pipelines on FPGA SmartNICs. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ open-access copy hosted at NSF PAR, of the ASPLOS 2025 paper). The described system is the paper’s: Gigaflow is a caching system for SmartNIC-offloaded virtual switches whose core insight is pipeline-aware locality — that flows taking different whole paths through a vSwitch pipeline share smaller reusable segments. Where Open vSwitch’s Megaflow caches each whole traversal (the complete sequence of table lookups a flow takes) as one wildcard rule, Gigaflow decomposes traversals into sub-traversals (reusable subsequences shared across flows), stores them in several ordered cache tables, and composes the partial results per packet into the final actions, so a small number of segment rules covers a combinatorially large path space. The main design challenge the paper identifies is selecting breakpoints for sub-traversals that maximize how disjoint and reusable the segments are. The paper evaluates Gigaflow on FPGA-based SmartNICs (using Xilinx’s P4-based toolchain) across five real-world vSwitch pipelines with diverse traversal patterns, reporting up to a 51 percent improvement in cache hit rate (25 percent on average), up to 90 percent fewer cache misses, and up to 450 times more rule-space coverage within the same limited NIC memory, while maintaining line-rate performance (the paper also reports figures such as roughly 3 times improvement while covering 335 times more rule space in certain comparisons). The step-by-step walkthrough above is an illustration of the described mechanism. Exact algorithms for choosing breakpoints, the composition and cache-table structure, and the full evaluation should be read from the paper; the artifact is reported to be publicly available.

Background

Why fast cloud networking keeps coming down to fitting more in a small, fast memory

It helps to see Gigaflow within a broad pattern: much of the progress in end-host cloud networking comes from recognizing that the expensive, general-purpose path can be skipped for most traffic if you cache its results cleverly — and that the binding constraint is almost always a small, fast memory. The vSwitch fast path is a cache; the SmartNIC is a smaller, faster cache; and the whole game is covering as much traffic as possible within a memory budget that cannot grow to match the workload. When whole-path caching hits that wall, the answer is not more memory but a better representation — one that exploits the structure and sharing in the workload to pack far more coverage into the same space. Gigaflow’s pipeline-aware sub-traversal caching is a clean instance: it finds the shared segments hiding inside a combinatorial path space and stores those instead. This effort to make the cloud’s end-host network stack fast within tight hardware limits is the same terrain the work on enabling fast networking in the public cloud (Machnet) covered elsewhere on this site occupies, wringing performance from constrained commodity networking hardware. Gigaflow’s contribution is to show that the right caching granularity — segments, not whole paths — lets a tiny SmartNIC cache finally scale to the growing flow-rule space that offloading was meant to handle.

If you remember only three things

1. A virtual switch (vSwitch) sits on every packet's path in a cloud server, applying a multi-table pipeline of policies (layer-2, layer-3, access control, connection tracking). Running the full pipeline per packet is slow (under ten gigabits per second per core), so vSwitches cache: Open vSwitch's Megaflow caches each flow's whole pipeline path (its "traversal") as one wildcard rule, and operators offload this cache to SmartNICs to switch at line rate off the CPU. But the number of distinct whole paths grows combinatorially with policy complexity, while a SmartNIC hardware cache holds only tens of thousands of rules, so the cache overflows, miss rates climb, and offloaded switching fails to scale.
2. Gigaflow's insight is pipeline-aware locality: flows taking different whole paths still share smaller segments of the pipeline. Instead of caching whole traversals, Gigaflow decomposes each into sub-traversals — reusable subsequences of table lookups shared across many flows — stores them in several ordered cache tables, and matches each packet against the segment caches in sequence, composing the partial results into the final actions. Because a segment is shared by many flows, a small number of sub-traversal rules covers a combinatorially large path space (the cache grows with the sum of per-stage options, not their product). The main challenge is choosing breakpoints that make segments maximally disjoint and reusable.
3. Implemented on FPGA-based SmartNICs and evaluated on five real-world vSwitch pipelines, the paper reports Gigaflow achieves up to a 51 percent higher cache hit rate (25 percent on average), up to 90 percent fewer cache misses, and up to 450 times more rule-space coverage within the same limited NIC memory, at line rate. The trade-offs: a packet now traverses several cache tables instead of one, the quality of the pipeline split matters and is pipeline-dependent, and the gains depend on how much flows actually share; Gigaflow improves the offloaded caching layer rather than redesigning the whole switch, and the reported numbers reflect the specific FPGA hardware and pipelines evaluated.

Check yourself

Check your understanding

1. Why does caching each flow's whole pipeline path (Open vSwitch's Megaflow) fail to scale on a SmartNIC?
2. What is Gigaflow's core insight, "pipeline-aware locality," and how does it change what gets cached?
3. How does Gigaflow process a packet whose exact whole path was never cached, and why does it still get a cache hit?
4. What is the main design challenge in Gigaflow, and what does the paper report for its results?

Sources

The paper is “Gigaflow: Pipeline-Aware Sub-Traversal Caching for Modern SmartNICs” by Annus Zulfiqar, Ali Imran, Venkat Kunaparaju, Ben Pfaff, Gianni Antichi, and Muhammad Shahbaz (University of Michigan, Purdue University, Feldera Inc., and Politecnico di Milano), published at ASPLOS 2025, DOI 10.1145/3676641.3716000. It is open access under CC BY, with an author copy hosted at NSF PAR (10608557) and a public artifact.

This explainer is written from the paper’s full text (the NSF PAR open-access copy). Gigaflow is a caching system for SmartNIC-offloaded virtual switches based on pipeline-aware locality: flows taking different whole paths through a vSwitch pipeline share smaller reusable segments. Where Open vSwitch’s Megaflow caches each whole traversal as one wildcard rule, Gigaflow decomposes traversals into sub-traversals (reusable subsequences of table lookups shared across flows), stores them in several ordered cache tables, and composes the partial results per packet, so a small number of segment rules covers a combinatorially large path space; the main design challenge is choosing breakpoints that maximize segment disjointedness and reuse. Evaluated on FPGA-based SmartNICs across five real-world vSwitch pipelines, the paper reports up to a 51 percent improvement in cache hit rate (25 percent on average), up to 90 percent fewer cache misses, and up to 450 times more rule-space coverage within the same limited NIC memory, at line rate. Numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper, and the artifact is publicly available.