ProbNV: probabilistic verification of network control planes

Nick Giannarakis, Alexandra Silva, David Walker

Research output: Contribution to journalArticlepeer-review

Abstract

ProbNV is a new framework for probabilistic network control plane verification that strikes a balance between generality and scalability. ProbNV is general enough to encode a wide range of features from the most common protocols (eBGP and OSPF) and yet scalable enough to handle challenging properties, such as probabilistic all-failures analysis of medium-sized networks with 100-200 devices. When there are a small, bounded number of failures, networks with up to 500 devices may be verified in seconds. ProbNV operates by translating raw CISCO configurations into a probabilistic and functional programming language designed for network verification. This language comes equipped with a novel type system that characterizes the sort of representation to be used for each data structure: concrete for the usual representation of values; symbolic for a BDD-based representation of sets of values; and multi-value for an MTBDD-based representation of values that depend upon symbolics. Careful use of these varying representations speeds execution of symbolic simulation of network models. The MTBDD-based representations are also used to calculate probabilistic properties of network models once symbolic simulation is complete. We implement the language and evaluate its performance on benchmarks constructed from real network topologies and synthesized routing policies.

Original languageEnglish (US)
Article number3473595
JournalProceedings of the ACM on Programming Languages
Volume5
Issue numberICFP
DOIs
StatePublished - Aug 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Safety, Risk, Reliability and Quality

Keywords

  • Control Plane Analysis
  • Network Simulation
  • Network Verification
  • Probabilistic Network Analysis
  • Probabilistic verification
  • Router Configuration Analysis

Fingerprint

Dive into the research topics of 'ProbNV: probabilistic verification of network control planes'. Together they form a unique fingerprint.

Cite this