Efficient and Correct Test Scheduling for Ensembles of Network Policies

on YouTube ↗27m

" summary

Mikado is a scheduling layer that takes test traces from black‑box tools (bust, ATPG, simnet per uploader) and guarantees correctness by formalizing stateful network behavior and detecting read-write conflicts between traces. It builds a conflict graph and uses graph coloring to produce a safe, parallel schedule. Evaluation shows Mikado is open source, schedules thousands of policies across networks with 1000+ nodes in minutes, and yields up to orders of magnitude speed‑ups over sequential runs while preserving per‑trace behavior.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:27Background: Network Testing
3. 1:40Network Testing in Practice
4. 3:09Problem: How to Run Test Traces in Stateful Networks?
5. 4:23Example: Incorrect Testing Results
6. 7:18Mikado: Efficient and Correct Test Scheduling for Ensembles of Network Policies
7. 8:27Ideal Scheduling for Running Test Traces
8. 9:53Key Challenges
9. 10:31Formal Framework of Stateful Networks
10. 13:08Correctness of Running Multiple Tests
11. 14:35Naive Scheduling Algorithm
12. 15:53Read-write Conflict
13. 17:58Scheduling Generation via Graph Coloring
14. 18:25Implementation
15. 18:50Reduction in Testing Time
16. 20:46Scheduling Generation Scalable to 10K Test Traces
17. 21:11Mikado Extensions
18. 21:44Conclusion
19. 22:46THE ADVANCED COMPUTING SYSTEMS ASSOCIATION

" related talks

• 14mFeedback-guided Adaptive Testing of Distributed Systems DesignsAnkush Desai, Ao Li, Rohan Padhye · NSDI '26
• 12mMetha: Network Verifiers Need To Be Correct Too!Martin Vechev, Laurent Vanbever, Rüdiger Birkner, Tobias Brodmann, Petar Tsankov · NSDI ’21
• 16mAutomatic Parallelization of Software Network FunctionsFrancisco Pereira, Fernando M. V. Ramos, Luis Pedrosa · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 14mMeshTest: End-to-End Testing for Service Mesh Traffic ManagementXuanzhe Liu, Xin Jin, Naiqian Zheng, Tianshuo Qiao · NSDI '25
• 16mToward Orchestration of Complex Networking ExperimentsAlefiya Hussain, Prateek Jaipuria, Geoff Lawler, Stephen Schwab, Terry Benzel · 13th USENIX Workshop on Cyber Security Experimentation and Test (CSET '20)
• 16mHeteroSketch: Coordinating Network-wide Monitoring in Heterogeneous and Dynamic NetworksAnup Agarwal, Srinivasan Seshan, Zaoxing Liu · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 19mNetcastle: Network Infrastructure Testing At ScaleWei Zhang, Ying Zhang, Neil Spring, Hany Morsy, Srikrishna Gopu, Srikanth Sundaresan, Rob Sherwood, Jinghao Shi, Jasmeet Bagga, Prathyusha Peddi, Vineela Kukkadapu, Rashmi Shrivastava, Manikantan KR, Pavan Patil, Varun Varadan, Ethan Shi, Yuting Bu, Renjie Yang, Rasmus Jönsson, Jesus Jussepen Arredondo, Diana Saha, Sean Choi · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 21mModel-Agnostic and Efficient Exploration of Numerical State Space of Real-World...Wei Sun, Lisong Xu, Sebastian Elbaum, Di Zhao · NSDI 2019