The Two OVS Caches and the Timing Signal
Open vSwitch (OVS) becomes a side-channel subject only when its internal state changes the cost of handling a later packet. This explanation follows the two caches that create that state: the exact-match microflow cache and the wildcarded megaflow cache. The reader should come away able to predict what happens after a hit, a miss, a collision, a subtable reorder, or a timeout—and therefore understand why a remote timing measurement can say something about traffic that the observer cannot directly inspect.
The microflow cache: exact matches and collision replacement
The microflow cache is OVS's first forwarding shortcut. It is small and fast, and it stores one flow per entry. “Exact match” means that a new packet cannot use an entry merely because it arrives at the same location. The relevant packet-header fields must also match the cached flow closely enough for OVS to apply the stored action. When that happens, the packet can take the fast path without consulting the larger cache or the full OpenFlow pipeline.
In the paper's evaluated 8k configuration, the cache has 8,192 entries. OVS combines five fields—source IP address, source port, destination IP address, destination port, and protocol—into a 32-bit hash. Two 13-bit portions of that value select two candidate locations in the cache. The exact details matter because they make the cache index related to the packet header rather than to an unrelated random event. A change in a source address or port can change the candidate locations even when the destination service remains the same.
There is an important qualification about the version label. The paper's abstract describes the 8,192-entry default in OVS v3.6 with the DPDK datapath. Its detailed cache description names OVS v2.17.9, while the characterization section says the cache design has retained the same behavior in the current v3.6 configuration. The safe technical statement is that the paper evaluates an 8k microflow cache and reports the behavior for those tested configurations. It is not safe to detach that number from its version and datapath context and call it a permanent property of every OVS release.
The normal lookup sequence is straightforward. OVS computes the hash, checks the first candidate, and compares the packet with the entry there. If it does not match, OVS checks the second candidate. A match at either location is a microflow hit. If neither candidate matches, the packet moves to the megaflow cache. If the later lookup resolves the flow, OVS can insert the flow into the microflow cache so that subsequent packets have a faster route.
The interesting behavior appears when a new flow needs an entry but both candidate locations are occupied. OVS does not simply append another entry; the table has fixed capacity at those locations. It compares the hash values associated with the two occupied entries and replaces the one with the smaller value. The result is a collision-driven replacement policy. A flow that was previously a fast hit can become a miss after another packet arrives, and a later probe of that flow will take longer because it has to continue down the cache hierarchy.
That transition turns an implementation detail into observable state. Suppose a probe has established that a particular flow is resident. Another flow then generates traffic whose header-derived candidates overlap the probe's entry. If the replacement rule chooses the probe's entry for eviction, the next probe no longer receives the microflow-hit timing. The observer does not see the replacement decision directly. They see a slower response and infer that the state changed. The inference becomes stronger when the observer can repeat the measurement and control which candidate entries are being tested.
The microflow cache also has persistence. In the paper's timeout experiment, a flow remained a microflow hit even after the researchers waited as long as 100 seconds. The authors therefore characterize the microflow cache as evicting by collision rather than by the timeout mechanism they observe in the megaflow cache. This does not mean that a flow is immortal in every implementation or under every capacity pressure. It means that, under the tested configuration and waiting experiment, elapsed time alone did not remove the entry. A collision or other cache pressure was the relevant route to displacement.
The security meaning follows from three linked facts. First, the index is derived from packet-header fields. Second, a collision can displace an existing flow. Third, displacement changes whether a later packet receives the lowest-latency path. A remote observer does not need a readable cache dump if they can turn those links into a repeatable measurement. The microflow cache is therefore both a performance accelerator and a record of which exact flow identities currently occupy its limited locations.
The megaflow cache: order, frequency, and expiry
A microflow miss does not mean that OVS has forgotten how to forward the packet. It means only that the exact-match shortcut did not resolve it. OVS next consults the megaflow cache, which is larger and represents broader rules. A megaflow entry can match a family of packets under a mask rather than one fully specified flow. Entries that use the same mask are grouped into subtables.
The megaflow lookup is sequential. OVS examines one subtable, applies its mask, and checks for a matching entry. If there is no match, it advances to the next subtable. The first matching entry determines the action, so the position of a subtable matters to latency. A frequently used subtable placed near the front can resolve a packet after fewer failed checks than an equally valid subtable near the end. This is why OVS periodically reorders the subtables by their hit counts: the common case is meant to become cheaper.
The optimization introduces a second kind of shared history. With microflow, the important event is often whether an exact entry was displaced. With megaflow, the important event is how often a rule family has been used relative to other rule families. Traffic does not need to change the rule itself to affect this state. Repeatedly hitting one subtable raises its count, and the next reorder can move it toward the front. The resulting position changes the time required by later lookups.
The paper measures a minimum megaflow reorder interval of about one second, with 86% of observed intervals within 1.2 seconds and a tail extending to about 1.43 seconds. The authors attribute longer intervals to software variation, such as threads being busy with rule insertion or slow-path access. These numbers belong to the tested setup, but the causal pattern is broader within the evidence: access frequency influences ordering, ordering influences the number of checks, and the number of checks influences latency.
Megaflow state also has a different lifetime from the microflow state. The paper describes periodic removal of entries without recent hits and observes timeout evictions beginning after about 10 seconds. A megaflow entry that has not been used may therefore disappear even if no competing entry directly displaces it. When the flow returns after that timeout, OVS must do more work to resolve it again, producing a slower path before the cache is repopulated.
A compact state model looks like this:
Before reading the diagram as a simple pipeline, it helps to follow three different packet histories. A new flow can arrive when neither cache contains a usable entry. OVS sends it through the slower rule-processing path, obtains the forwarding action, and can retain the result for subsequent packets. When another packet from the same exact flow arrives, the microflow cache may now resolve it immediately. The second packet has the same intended destination and action as the first, but it consumes less forwarding work because the host remembers the decision.
A different flow can follow the same first steps and still change the future of the first one. If its header-derived candidates overlap locations already occupied in the microflow cache, the fixed locations cannot hold every flow. OVS compares the associated hash values and replaces the entry with the smaller one. The new flow may be forwarded correctly, while the displaced flow is also still valid from the network's perspective. What changes is the route through OVS on the next packet: the displaced flow no longer receives an exact-match hit and must continue to the next cache layer. Correctness of forwarding can therefore coexist with a change in processing time.
The megaflow case has a different history. A packet that misses microflow may match a broad rule in a megaflow subtable. That subtable is one member of an ordered set, so the packet's latency includes the work of checking the subtables before it. Repeated traffic that hits the same subtable increases its hit count. At the next reorder, OVS can move that subtable toward the front, reducing the work for later packets that match it. The forwarding rule has not necessarily changed; its position in the lookup sequence has.
Now consider inactivity. A microflow entry in the paper's waiting experiment continues to produce a hit after long waits, whereas an unused megaflow entry begins to time out after roughly ten seconds. The two caches therefore remember different things in different ways. A microflow observer looks for displacement caused by competing flow placement. A megaflow observer looks for position changes caused by relative activity and for the reset caused by expiry. The word “cache” hides these different lifecycles unless the trigger and termination condition are stated explicitly.
The timing consequence is a chain, not a label. A cache hit can end lookup early. A miss can expose the next level. A collision can remove a previously fast entry. A reorder can move a valid broad rule closer to or farther from the front. A timeout can force a later lookup to rebuild state. Each event changes the work OVS performs, and that work is what a remote observer might estimate. The observer does not receive a field saying “collision” or “subtable 17”; they receive a response whose elapsed time must be interpreted against a baseline.
That interpretation also has a boundary. The same slower response can be evidence of a cache miss, but it is not automatically proof of a particular victim action. The paper's attack designs depend on repeatable probes and controlled knowledge of the flows or subtables being tested. Without those conditions, a timing difference may be too ambiguous to support a useful inference. The cache mechanics explain why a signal can exist; they do not guarantee that the signal will remain readable in every network.
The model is not a claim that every state transition occurs in one uninterrupted transaction. It identifies the security-relevant relationships. A microflow hit terminates lookup early. A microflow miss exposes the megaflow layer to the packet. A megaflow hit depends on subtable order, while a miss in both caches reaches the slow path. Collision replacement changes the exact-match state; reorder changes the broader-rule state; timeout removes stale megaflow state.
Those differences create distinct timing interpretations. A microflow hit tells the observer that the exact flow matched its cached entry. A megaflow hit after a microflow miss says that a broader cached rule resolved the packet, and the time can depend on the subtable's position. A slow-path response indicates that neither shortcut supplied the action at that moment. The observer still sees only elapsed time, so the category must be interpreted against a baseline rather than treated as a direct label. Repeated observations can make the categories statistically useful.
It is also important not to treat the two caches as independent security compartments. A microflow miss is what allows a packet to reach megaflow. An attacker who wants to study megaflow behavior may deliberately create conditions that keep a target flow out of the microflow cache. Conversely, a defense that changes microflow placement can alter how much traffic reaches or can be measured through megaflow. The layers are separate in function but connected in the forwarding lifecycle.
The timeout behaviors impose different observation windows. The microflow experiment suggests that waiting alone does not reliably clear an entry, so a collision-based observer can focus on controlling replacement. The megaflow experiment suggests that an unused entry can disappear after roughly ten seconds, so an order-based observer must work within the cache's persistence and reorder rhythm. An attacker's signal is therefore shaped not just by whether a cache exists, but by the events that create, move, and remove its state.
From forwarding optimization to a measurable history
The two caches preserve different kinds of history. The microflow cache preserves the recent presence of exact flow identities in a limited set of candidate locations. The megaflow cache preserves broader rule matches and their relative activity through subtable hit counts. Neither cache was introduced as a user-facing telemetry system. Yet both can influence the latency of a later request.
That is the critical chain for the OVS side channel: packet headers determine or influence cache placement; packet activity changes occupancy or ordering; cache state changes processing work; processing work changes round-trip time. Each link has conditions, and none alone proves that a secret has been recovered. Together, under a repeatable network setup, they give a remote observer a way to infer hidden forwarding state.
The next step is therefore not to assume that every timing variation is a leak. It is to ask what the characterization actually separates, how many repetitions are needed, and which inferences follow from collision state versus subtable order. Once those measurements are attached to their testbed and noise limits, the cache mechanics can be evaluated as attack primitives rather than as a list of implementation facts.