Home

NDD Wiki

This wiki holds the long-form documentation for the NDD repository.

NDD is a field-aware decision diagram for packet-processing and network-verification workloads. Instead of branching on one bit at a time like a classical BDD, an NDD node represents a whole field such as destination IP, source port, protocol, or TCP flags. That field-oriented structure is what makes NDD a good fit for forwarding and reachability analysis.

This repository also includes the optimized array-backed implementation that the benchmark pages refer to as NDD-Array. Historical branch notes may also describe the same optimization line as the SoA implementation; this wiki uses NDD-Array consistently because that is the name used in the result tables.

What You Will Find Here

• library setup and build instructions
• how to use the low-level JNDD API and the JavaNDD compatibility layer
• parameter and field-modeling guidance
• detailed benchmark methodology and full result tables
• how NDD is used in network-verification experiments and Batfish-style integrations
• implementation notes for the optimized array-backed branch

Recommended Reading Order

If you are new to the project:

1. Installation
2. Usage
3. Parameters
4. Network Verification Applications
5. Benchmarks

If you are reviewing the optimization work:

1. Optimization Summary
2. Design Notes
3. Results: NQueens
4. Results: SRE

Repository Pointers

• Front-page overview: README.md
• Source tree: src/main/java/
• JNDD implementation: org/ants/jndd
• JavaNDD facade: org/ants/javandd
• Example applications: application/
• Benchmark artifacts: results/
• Dedicated NQueens benchmark repository: https://github.com/XJTU-NetVerify/nqueensBenchmarkDDs
• API docs: doc/javadoc/

Where The Old README Material Went

The repository README.md is intentionally short. Material that used to live there now belongs here:

• quick-start and build details: Installation
• API snippets and example entry points: Usage
• variant naming, benchmark interpretation, and artifacts: Benchmarks
• network-verification motivation and integrations: Network Verification Applications

Key Result Snapshot

• On the Java NQueens workload, NDD-Array is about 3.4x to 3.6x faster than the original NDD baseline at sizes 10 to 12, while also using much less memory.
• On the WAN/SRE benchmark set, the optimized branch cuts both runtime and BDD-node count sharply on medium and large fattree cases, for example bgp_fattree12, MF=3: 636.086s -> 230.906s.

Use the sidebar or the links above for the full details.