State-Compute Replication: Parallelizing High-Speed Stateful Packet Processing

on YouTube ↗16m

" summary

Introduces state-compute replication that replicates only the state-update code and attaches compact per-packet histories so each core fast-forwards private state without locks, implemented as a packet history sequencer on programmable NIC/switch hardware. Prototype uses XDP applications and hardware described as Tophino and net fpj, stores histories in an on‑chip ring buffer, and shows near-linear throughput scaling with cores across three real traces and even a single large flow. Limits appear when state compute dominates CPU or when bandwidth caps are hit (token bucket stalls ~11 cores).

AI-written summary · about

" chapters (11)

1. 0:00State-compute replication intro
2. 1:52Scaling stateful packet processing
3. 3:39Sharing and sharding approaches
4. 5:27SCR overview
5. 7:13Packet processing time breakdown
6. 8:17SCR with programmable NICs
7. 10:03Sequencer hardware design
8. 11:27SCR performance evaluation
9. 13:17SCR limitations and bottlenecks
10. 14:41Loss recovery in SCR
11. 15:25Conclusion and benchmarks

" related talks

• 16mWaverunner: An Elegant Approach to Hardware Acceleration of State Machine ReplicationMohammadreza Alimadadi, Hieu Mai, Shenghsun Cho, Michael Ferdman, Peter Milder, Shuai Mu · NSDI 2023
• 16mA High-Speed Stateful Packet Processing Approach for Tbps Programmable SwitchesDejan Kostić, Hamid Ghasemirahni, Tom Barbette, Marco Chiesa, Mariano Scazzariello, Tommaso Caiazzi · NSDI 2023
• 19mDisaggregating Stateful Network FunctionsRanveer Chandra, Deepak Bansal, Balakrishnan Raman, Sachin Jain, Rishabh Tewari, Neeraj Motwani, Evan Langlais, Soumya Tiwari, Rishiraj Hazarika, Deven Jagasia, Michal Zygmunt, Avijit Gupta, James Grantham, Srikanth Kandula, Stewart Grant, Gerald DeGrace, Silvano Gai, Mario Baldi, Krishna Doddapaneni, Arun Selvarajan, Arunkumar Arumugam, Pranjal Srivastava · NSDI 2023
• 14mEmpower Programmable Pipeline for Advanced Stateful Packet ProcessingYong Feng, Bin Liu, Yang Xu, Zhikang Chen, Haoyu Song, Chuwen Zhang, Yinchao Zhang, Hanyi Zhou, Ruoyu Sun, Wenkuo Dong, Peng Lu, Shuxin Liu · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 17mSwiSh: Distributed Shared State Abstractions for Programmable SwitchesShir Landau Feibish, Dan R. K. Ports, Daehyeok Kim, Lior Zeno, Jacob Nelson, Idit Keidar, Arik Rinberg, Alon Rashelbach, Igor De-Paula, Mark Silberstein · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 21mAccelTCP: Accelerating Network Applications with Stateful TCP OffloadingKyoungSoo Park, YoungGyoun Moon, SeungEon Lee, Muhammad Asim Jamshed · NSDI 2020
• 39mTrust Deterministic Execution to Scale & Simplify Your SystemsFrank Yu · YOW! Perth 2023
• 31mFlow-based Packet Processing Framework on DPDK and VPPHongjun Ni · KubeCon + CloudNativeCon + Open Source Summit China 2019