Scaling Data Plane Verification via Parallelization
Open Access
- 3 August 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 81-87
Abstract
The data plane verification of networks in hyperscale environments is challenging due to the complexity and size of modern networks. In this paper, we introduce Medusa, a novel verifier that efficiently analyzes large data plane models using parallel processing on multi-core CPUs. First, we propose a new data structure called RANGESET, which overcomes the parallelism limitations of existing popular data structures such as Binary Decision Diagrams (BDD) used in data plane verifiers. Next, we leverage multi-core processing by dividing the network into distinct groups and assigning each group to a separate thread for computation. The results are then integrated for comprehensive verification. By optimizing the use of multi-core systems, we enhance computational efficiency and accelerate the verification process. Experimental results demonstrate that Medusa outperforms existing tools in terms of speed and memory. For instance, in a network with O(10K) devices and O(1M) forwarding rules, Medusa can detect loops in approximately 5 seconds, outperforming other Data Plane Verifiers (DPVs) where some cannot model and analyze the network. Moreover, in networks that we could compare with other state-of-the-art DPVs, Medusa provides a substantial improvement, with speedups up to 600X, 4000X, and 800X compared to alternatives like Flash, APKeep, and Tulkun, respectively.Keywords
This publication has 7 references indexed in Scilit:
- Poster: Scaling Data Plane Verification with Throughput-Optimized Atomic Predicates2023
- Beyond a Centralized Verifier: Scaling Data Plane Checking via Distributed, On-Device Verification2023
- HermesBDD: A Multi-Core and Multi-Platform Binary Decision Diagram Package2023
- Flash2022
- PJBDD: A BDD Library for Java and Multi-Threading2021
- Validating datacenters at scale2019
- A Thread-Safe Library for Binary Decision Diagrams2014