How OpenVSwitch Optimizes Packet Forwarding with Megaflow and Microflow Caches

Over the past decade, virtualization has transformed the deployment of applications, data, and services. Gartner reported in 2016 that 80% of x86 workloads were virtualized, mostly as VMs, while container usage is rapidly increasing.

Server virtualization fundamentally changes data‑center networking by adding an access layer inside physical servers. This layer consists of vSwitches running on x86 servers, connecting multiple workloads (containers and VMs) within a single host.

The early vSwitch, Linux bridge, simply emulated a ToR switch and integrated with the existing physical network, inheriting its protocols but tightly coupling virtual workloads to the physical network, reducing the flexibility promised by virtualization.

Network virtualization introduces an overlay network (e.g., VXLAN) managed independently of the underlay physical network. Open vSwitch (OVS) implements this design, supporting both overlay and VLAN/FLAT networks.

OpenFlow

OVS’s second key feature is its reliance on OpenFlow, which makes the switch programmable. OpenFlow defines a pipeline of tables that process packets, allowing software‑defined functionality.

OpenFlow pipelines can become long and slow in practice, so OVS has explored many optimizations.

In Linux, networking spans user space and kernel space. Early OVS implementations handled the entire OpenFlow pipeline in the kernel, but this proved impractical due to update difficulty and CPU overhead.

Modern OVS (2.x) separates fast‑path processing (kernel module) from slow‑path processing (ovs‑vswitchd in user space). The first packet of a flow is sent to ovs‑vswitchd, which computes actions and generates a simplified datapath action for the kernel. Subsequent packets use this cached action, decoupling OpenFlow changes from the kernel.

OVS uses a hash‑based microflow cache in the kernel for fast lookups. However, microflow caching can suffer when many short connections cause frequent cache misses.

Megaflow Caching

Megaflow caches store more generic matches (e.g., only destination IP prefix) so that many flows share a single entry, drastically reducing user‑space upcalls.

Both microflow and megaflow caches coexist: microflow handles the first packet of a flow, then points to the appropriate megaflow hash table.

Tuple Space Search (TSS)

TSS provides O(1) lookup by hashing the match fields of OpenFlow rules. It supports any field, and memory usage grows linearly with rule count.

Tuple Priority Sorting

Each hash table records the maximum rule priority (pri_max). During lookup, tables are examined from high to low pri_max, allowing early termination when a higher‑priority match is found.

Staged Lookup

Hash tables are split into four stages based on field stability (metadata → L2 → L3 → L4). Lookup proceeds stage by stage, aborting early if a mismatch occurs, effectively prioritizing less‑volatile fields.

Prefix Tracking

OVS traverses a trie of IP prefixes to determine the minimal prefix length needed for a megaflow, avoiding overly specific matches and keeping caches sufficiently fuzzy.

OpenFlow Table Management

OVS provides simple CRUD interfaces for OpenFlow tables, which are managed by an external SDN controller.

Megaflow Cache Maintenance

When OpenFlow rules change, OVS recomputes the entire megaflow cache (the older tag‑based approach was removed). The revalidation and handler threads are sized based on CPU cores, allowing megaflow updates without blocking packet processing.

By default, OVS maintains up to 200 000 megaflow entries and ages out unused entries after about 10 seconds.

Microflow Cache

In recent OVS versions, the microflow cache simply points to megaflow hash tables and is managed passively; it has a fixed size and replaces entries randomly when full.

Overall, OVS balances multiple caching layers and lookup optimizations to achieve high‑performance, flexible packet forwarding in virtualized data‑center environments.

priority=200,ip,nw_dst=10.0.0.0/16 actions=output:1

priority=200,ip,nw_dst=10.0.0.0/16 actions=output:1
priority=100,ip,nw_dst=20.0.0.0/16,tcp_dst=22 actions=drop

# ovs-appctl memory/show
handlers:35 ofconns:2 ports:6 revalidators:13 rules:735