Skip to content

Parameters

Jump to bottom
Augists edited this page Apr 22, 2026 · 3 revisions

Parameters

This page explains the initialization parameters, field-layout controls, and benchmark terms used throughout the repository.

Core Initialization

NDD.initNDD(nddTableSize, nddCacheSize, bddTableSize, bddCacheSize)

Parameter Meaning Practical guidance
nddTableSize Initial capacity of the NDD node table Start large enough to avoid repeated growth on your target workload
nddCacheSize Size of the NDD operation caches Increase when repeated logical subproblems dominate runtime
bddTableSize Capacity of the underlying BDD node table This matters directly because edge labels are still BDDs
bddCacheSize Cache size for the underlying BDD engine Raise it when label operations are heavy

There are also convenience overloads:

  • initNDD(nddTableSize, bddTableSize, bddCacheSize) uses the default NDD cache size
  • initNDD(..., LabelMode mode) selects a non-default label backend

Field Declaration And Layout

declareField(bitNum)

Registers one field width, but does not create any BDD variables yet.

generateFields()

Finalizes the full field layout after all declarations:

  • computes the maximum field width across declared fields
  • creates the shared BDD-variable pool
  • right-aligns each field against that pool
  • materializes the positive and negative literals used by NDD operations

This right-alignment is the key reuse optimization in the optimized branch. If two packet fields have compatible suffix widths, they can reuse the same underlying BDD variables rather than duplicating the label structure.

Modeling Rule

Treat each semantic packet field as one declared NDD field. For example:

  • a 32-bit IPv4 address field should usually be one declareField(32)
  • source and destination ports should be separate 16-bit fields
  • primed and unprimed versions of the same logical header should still be separate fields if the algorithm distinguishes them

Do not flatten everything into one long bitstring unless you explicitly want plain BDD-like behavior.

JavaNDD Parameters

For the BDDFactory-style API, the main extra method is:

((NDDFactory) factory).setVarNum(fieldBitWidths, nddTableSize);

Here:

  • fieldBitWidths is the full field partition, for example {32, 32, 16, 16, 8, ...}
  • nddTableSize is the NDD node-table capacity used by the factory-backed implementation

This repository's Batfish patch and JavaNDD examples both use the "declare all fields up front" style. That is the recommended approach.

Label Modes

The low-level API currently exposes three label modes:

Mode Meaning Status
BOOLEAN_BDD Standard BDD labels Default and maintained
COMPLEMENTED_BDD Complemented-edge BDD labels Experimental
FINITE_DOMAIN_ZDD Finite-domain ZDD labels Experimental

The NQueens example can be invoked with --bcdd or --finite-domain-zdd to exercise the non-default modes.

Example Sizing From This Repository

The example programs are a useful guide for scale, but not a universal tuning rule:

  • application.nqueen.NDDSolution uses NDD_TABLE_SIZE = 100000000
  • the same example chooses the NDD cache size with a simple workload-dependent heuristic based on n
  • application.wan.ndd.verifier.apkeep.utils.Parameters currently sets BDD_TABLE_SIZE = 10000000 for the WAN/SRE research path

Use those values as starting points for similar workloads, not as one-size-fits-all defaults.

Common Pitfalls

  • Calling generateFields() before all fields are declared
  • Trying to add fields dynamically after the layout has been fixed
  • Under-sizing the BDD table while tuning only the NDD table
  • Modeling packet headers as one monolithic field and then expecting NDD-style locality benefits
  • Mixing maintained example code with WAN/SRE experiment code without accounting for the older dependencies in the latter

Benchmark Terms

The benchmark and result pages use the following columns:

Column Meaning
time_sec / total(s) End-to-end runtime
src(s) Source or preprocessing portion reported by the WAN/SRE harness
max_rss_kb / peak rss Peak resident memory
nodes_created Total decision-diagram nodes created during the run
nodes_alive Nodes still alive at the measurement point
ndd_nodes_* Counts attributed to NDD nodes only
bdd_nodes_* Counts attributed to BDD label nodes only
MF Harness parameter used in the WAN/SRE datasets

For workload-specific interpretation, see Benchmarks, Results: NQueens, and Results: SRE.

Clone this wiki locally