Locality-Aware, Self-Adjusting Data Structures: A Case Study in Linux Firewalls
summary
Prototype implements the Move-Recursively-Forward algorithm inside nftables using a per-CPU pointer-array view so rule swaps are cheap, and it extracts IP/port tuples from bytecode for dependency checks. Under ideal locality it achieves up to 5x throughput versus static nftables; under worst-case or long dependency chains it slows or falls back to static performance. Rule insertions reset per-CPU order; sets and arbitrary bytecode remain unresolved pain points for dependency detection and correctness.
AI-written summary · about
chapters (12)
- 0:00Introduction and motivation
- 2:08Move-to-front algorithm explained
- 4:16Dependency graph and example
- 7:51NF tables versions and reordering cost
- 9:19Single-core implementation details
- 11:54Evaluation setup and high locality
- 12:37Worst-case traffic performance
- 13:41Impact of dependency chains
- 14:47Multi-core scaling behavior
- 16:35Dependency impact on scaling
- 17:19Conclusion and limitations
- 18:02Q&A session
related talks
27mHigh speed load balancing from the Linux Kernel
20mContra: A Programmable System for Performance aware Routing
14mMultitenancy for Fast and Programmable Networks in the Cloud
24mReal Time Network Policy Checking Using Header Space Analysis
23mFast Software Cache Design for Network Appliances
18mLearning-Enhanced High-Throughput Pattern Matching Based on Programmable Data Plane
22mFirewalld Changes Coming to Your OS
33mbpfilter: a BPF-based packet filtering framework