What the NSDI 2015 OVS Paper Reveals About OpenFlow Performance and Caching

Overview

The NSDI 2015 paper, authored by several core Open vSwitch (OVS) developers, presents the design and implementation of OVS, a software switch that supports OpenFlow. Although the paper is five years old and some implementation details have evolved, its problem statements and solutions remain highly relevant for understanding OVS’s architecture.

Challenges Faced by OVS

Software switches like OVS are far more flexible than traditional hardware switches, enabling network virtualization in virtualized and containerized environments. However, this flexibility introduces performance challenges: OpenFlow’s programmable pipelines require per‑packet rule evaluation, often involving dozens of flow‑table entries and complex priority handling, which can overwhelm CPU resources.

OVS Architecture

OVS consists of a user‑space daemon ( ovs‑vswitchd) that performs flow‑table computation and a kernel‑space datapath that caches the resulting actions. The datapath’s hash table stores entries keyed on L2‑L4 packet fields, unlike hardware switches that typically hash only on destination MAC.

When a packet’s first flow arrives, the datapath misses the cache, forwards the packet to ovs‑vswitchd for rule lookup, and then installs the resulting entry into the kernel cache. Subsequent packets for the same flow hit the cache, avoiding user‑space processing.

This split design improves flexibility and eases development but incurs extra latency due to user‑kernel round‑trips, especially for short‑lived connections.

Performance Optimizations Discussed in the Paper

Tuple Space Search (TSS)

Instead of a single monolithic hash table, TSS groups flow rules into multiple smaller tables based on the fields they actually use (e.g., L2‑only, L3‑only). Packets are matched against each table in priority order, dramatically reducing memory consumption and lookup complexity.

MicroFlow Caching

Early OVS implementations used a simple hash of all packet fields, causing cache misses for any field change. The paper describes engineering tricks such as batch cache updates, multi‑core parallelism, reduced system‑call overhead, and the use of cuckoo hashing and RCU mechanisms to improve cache hit rates.

MegaFlow Caching

For traffic patterns with high variability (e.g., port scans), precise MicroFlow entries miss frequently. MegaFlow introduces fuzzy matching: a single entry can cover a range of packets, eliminating priorities and using a single table for lookup, thereby reducing the number of kernel‑user transitions.

Cache Invalidation

Because MegaFlow entries are coarse‑grained, determining which entries become stale after an OpenFlow rule change is difficult. The authors initially classified rule changes to update only affected MegaFlows, but as rule complexity grew, they abandoned classification and switched to multithreaded full‑revalidation of all MegaFlows.

Additional Engineering Ideas

Merge datapath entirely into the kernel for specific environments (e.g., public clouds) to eliminate user‑kernel handoff.

Pre‑populate the kernel cache during idle periods to reduce first‑packet latency.

Implement incremental cache invalidation for simple rule sets instead of brute‑force MegaFlow revalidation.

Conclusion

The paper provides a solid foundation for understanding OVS’s design trade‑offs between flexibility and performance. While newer hardware offloads (DPDK, SmartNICs) address many throughput concerns, the cache‑centric techniques described remain valuable for pure‑software deployments and for guiding future optimizations.