Network Decision Diagram (NDD) is a new decision diagram, built on the classical Binary Decision Diagram (BDD). For BDD, each node looks at a single bit each time, and branches based on whether the bit is true or false; in contrast, each NDD node looks at a field consisting of a fixed number of bits each time, and branches based on the value of the field. As a result, there can be more than 2 branches for each NDD node.
Different from other multi-valued decision diagram like MDD, NDD encodes the branching condition with external data structures. Currently, our NDD libray supports several external data structures, including: BDD, complemented-edge BDD (BCDD), and zero-suppressed decision diagrams (ZDD). An example of using BDD as the external data structure is shown in the figure below. In this figure, the BDDs in (a) can be equivalently represented by the NDDs in (c), where each branching condition is represented by a BDD, as shown in (b).
NDD can be seen as wrapping a lower-level decision diagram with an outer field-aware layer, and therefore the name of NDD can also be interpreted as "Nested Decision Diagram".
The following table compares the performance of our NDD libray with the JDD library, and our original version of NDD submitted to NSDI '25.
We use different sizes of NQueens problem, and the time is in seconds.
| N | BDD (JDD) | NDD-Original | NDD |
|---|---|---|---|
| 10 | 0.5479 | 0.7315 | 0.2136 |
| 11 | 2.7947 | 2.7497 | 0.7619 |
| 12 | 19.0108 | 10.2289 | 3.4391 |
| 13 | 148.9701 | 66.7104 | 23.6618 |
Detailed benchmark results, compared with more BDD libraries, are available on nqueensBenchmarkDDs
The following table compares the performance of different external data structures for N-Queens N=12.
| target | time (s) | memory (MB) |
|---|---|---|
| ndd-bdd | 3.0199 | 567.2 |
| ndd-zdd | 2.8683 | 559.4 |
| ndd-bcdd | 3.0480 | 742.1 |
Full backend comparison results are in results/nqueens_backend_results.md and the wiki.
NDD was originally proposed for network verification, where each NDD node represents a packet header field (destination IP address) We observed NDD was more efficient than BDD in terms of memory and computation. The reason is due to the locality of field-based matching semantics, NDD can significantly reduce the number of label decision-diagram nodes for each field.
The current NDD libary is by far not the end, and we are working on extending it to support: (1) multiple terminals, (2) parallel computation, (3) using NDD for more applications like modeling checking.
- Main: Featuring an efficient design of node table.
- Reuse: Featuring the reuse of label decision-diagram variables among all fields.
- Original: The original prototype for NSDI '25 paper.
@inproceedings{NDD,
title={NDD: A Decision Diagram for Network Verification},
author={Li, Zechun and Zhang, Peng and Zhang, Yichi and Yang, Hongkun},
booktitle={22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25)},
pages={237--258},
year={2025}
}- Peng Zhang (p-zhang@xjtu.edu.cn)
- Yichi Zhang (augists@outlook.com)
- Zechun Li (1467874668@qq.com)
Apache-2.0. See LICENSE.