Match-Action Pipelines and Flow Caching in Software Switches

A software switch that implements a virtual network has to decide, per packet, whether to forward, drop, encapsulate, decapsulate, rewrite an address, or send to a tunnel endpoint. Expressing those decisions as code means recompiling the switch whenever the policy changes. Expressing them as data means a table the switch consults, and the shape of that table determines both what the switch can express and how fast it can decide.

Tables, keys, and actions

The model that software switches converged on is a pipeline of tables. Each table holds rules, each rule has a match over a set of header fields and a set of actions, and a packet traverses the tables in a fixed order. A match can be exact, a prefix, a range, or a wildcard, and the fields available to match on are a fixed list that includes the usual headers plus metadata the pipeline itself attaches to the packet.

The metadata is what makes the model more than a filter. A packet entering the pipeline is assigned a value identifying the virtual network it arrived on, and that value is matchable in later tables. A rule can set a tunnel identifier, and a later table can match on it. The pipeline therefore carries context forward, which is how a switch expresses a decision that depends on both where a packet came from and where it is going, without the policy having to be written as a conjunction in one rule. The value the tunnel identifier holds at the end of the pipeline is the outcome of overlay endpoint resolution, computed once per destination and then matched on per packet.

Actions are equally structured. An action can output to a port, encapsulate toward a tunnel endpoint, decrement a TTL, modify a header field, push or pop a tag, or send the packet to a later table. A rule can have several actions, applied in order, and the last one determines where the packet goes next. The ordering is what allows a rule to both rewrite a header and decide the output in one step.

This is the same computational model as a switch ASIC’s pipeline, and that is deliberate: the same policy description is meant to compile to both. The consequence for a software implementation is that it is a table-driven interpreter, and the cost per packet is the number of tables traversed times the cost of a lookup in each.

A minimal overlay pipeline has three stages, and the stage boundaries are where the interesting decisions live. The first matches the arrival port and the outer headers, and its job is to classify: is this a tunneled frame, and if so which virtual network does its VNI name, or did it arrive directly from a local guest. The second matches on that classification and the inner destination, and its job is to decide the next hop: deliver locally, drop, or send through another table that will encapsulate. The third matches on the resolved destination and produces the output action, which for a tunnel is the encapsulation plus the port. A packet that arrives already tunneled traverses the first stage in the decapsulating direction and is recirculated into the second, which is why the same three tables serve both directions.

Why the first packet is expensive

A pipeline with a thousand rules across a dozen tables can express a great deal, but a naive lookup is linear in the number of rules. The first packet of a flow pays that cost: it must be classified against the full rule set, because the switch does not yet know which rules apply.

That cost is not small. A wildcard match over several fields is a multi-dimensional lookup, and the algorithms for it, such as tuple-space search or decision trees, have their own construction cost and their own memory footprint. Building the structure when a rule is installed is amortized over the rule’s lifetime; traversing it per packet is paid on every packet that takes the slow path.

The observation that makes this tractable is that flows repeat. After the first packet, the remaining packets of a flow have the same headers and will produce the same decisions, so the switch can record the outcome and reuse it. The recorded outcome is a cache entry: a match on the exact header tuple of the flow, and the action set the pipeline produced, possibly already resolved to a single output port or a single encapsulation.

The wildcard cache and the correctness problem

An exact-match cache keyed on the full tuple is safe in the narrow sense: a packet that matches the key is the same packet the pipeline classified, so the cached action is what the pipeline would produce. It is also limited, because a cache entry serves only one flow, and a switch with a million concurrent flows needs a million entries.

The more useful design caches with wildcards, deriving from the pipeline’s rules a set of patterns that cover many flows. If the pipeline sends every packet from a given source subnet to a given tunnel, the cache entry can match on the subnet rather than the full address, and one entry serves every flow in it. Deriving those patterns correctly is the hard part, because a pattern is only valid if it is more specific than, or consistent with, every rule it might bypass.

That is where the design becomes subtle. A cache entry that bypasses the pipeline is a claim that the pipeline’s outcome does not depend on any field the entry does not match. If a rule is installed later that distinguishes on one of those fields, the entry becomes wrong and must be removed. Removal requires the switch to know which cache entries could be affected by a rule change, which means either tracking the dependency or flushing broadly.

The conservative answer is to flush the cache whenever the rule set changes. That is correct and it makes every policy update a performance event, because the next packet of every flow takes the slow path. The refined answer is to version the cache: each entry records the pipeline version it was derived from, and a version bump invalidates entries lazily, at lookup time. The version is a single integer, so the invalidation is cheap, and the entries that are never used again are reclaimed by ordinary eviction.

Recirculation and the multi-pass case

Not every decision fits in one pass. A packet that arrives on a tunnel, is decapsulated, and then must be routed within the overlay has to be classified twice: once on the outer headers, once on the inner. The pipeline expresses this by sending the packet back to an earlier table after the decapsulation action, which is called recirculation.

Recirculation is expensive because the packet re-enters the pipeline with a new set of headers and must be classified again. It is also where the cache gets complicated, because a cache entry that covers the second pass must be keyed on the headers as they exist at that point, which are not the headers that arrived. An implementation that keys the cache on arrival headers only will serve a recirculated packet with the wrong action.

The number of recirculations is bounded by the pipeline’s design, not by the packet. A switch that decapsulates, routes, and re-encapsulates performs two passes and one recirculation; a switch that also applies a service chain of several functions performs one per function. Each pass costs a full classification on the first packet and a cache hit on subsequent ones, so the per-flow cost grows with the number of passes while the per-packet cost in steady state does not.

Where the tables come from

The rules are installed by a control plane, and the interface between the two is the thing that determines whether the design is portable. The OpenFlow protocol is the canonical example: it describes tables, matches, actions, and the messages to install and remove rules, with a specification that fixes the field list and the action set. A controller that speaks OpenFlow can program any switch that implements it, and the switch’s own capabilities are described in the handshake.

That portability has a cost, which is that the field list is a compromise. A switch that can match on a field the specification does not include cannot expose it, and a policy that needs it must be expressed some other way. The list has grown across versions, and the growth is a record of which fields turned out to matter for virtual networks: tunnel identifiers, metadata, and the registers that carry pipeline context were all added because the original list was insufficient.

The alternative is a programmable pipeline expressed in a language such as P4, where the switch is told the structure of its tables and the parser at compile time rather than being handed rules in a fixed format. That removes the compromise and moves the portability problem to the compiler, which must produce something the target can execute. For a software switch the target is the CPU, and the compiler’s job is to turn the pipeline into code that runs at packet rate, which is the subject of XDP and eBPF in the receive path.

The cost model that decides the design

The choice between a rich pipeline and a fast cache is a choice about where the per-packet cost lands. A pipeline-only switch pays the classification cost on every packet and holds no per-flow state; its memory is proportional to the number of rules, and its behaviour is exactly what the rules say, with no staleness. A cached switch pays the classification cost once per flow and a hash lookup thereafter; its memory is proportional to the number of active flows, and its behaviour is the rules as they were when the entry was created.

The second design wins when flows are long relative to the cost of classification, which is the usual case for bulk transfer and for any connection-oriented protocol. It loses when flows are short, because the cache is filled and evicted without being reused, and the eviction traffic becomes the cost. It also loses when the rule set changes often, because every change risks invalidation.

A middle ground is a pipeline for the cases the cache cannot cover and a cache for the ones it can, with the cache’s coverage determined by what the pipeline can prove about its own rules. The correctness argument is that the cache never changes the outcome, only the path to it, and every mechanism described above exists to keep that argument true while the rules change underneath.