NC (Normalizing Constant)
Methods · Configuration · Shared options · All solvers
The NC solver computes normalizing constants and uses them to obtain average metrics, state probabilities and marginal distributions. It includes exact, asymptotic, quadrature and sampling methods, plus specialized cache, loss-network, Petri-net and state-dependent-routing analyzers.
Methods
The method names and defaults below describe the MATLAB interface. Aliases share a row; model-specific restrictions and backend differences are noted. Use solver.listValidMethods() to inspect the names available for your model.
| Method | Algorithm and applicability | Reference |
|---|---|---|
default | Let pfqn_nc pick the evaluator adaptively from the model shape, and take the cache, retrieval, loss-network, Petri-net, DPS and state-dependent-routing routes where they apply. | — |
exact | Exact normalizing constant: convolution or RECAL at fixed rates, pfqn_gld/comomld/clw on a rate lattice, the OI convolution, the M/M/1/K closed form, the loss-network residue transform, the paired LCFS convolution. | — |
ca | Multiclass convolution algorithm: Buzen's single-chain recursion generalized to several closed chains. | — |
comom | Class-oriented method of moments for the repairman model (a delay and at most one queueing station). | [1] |
comomld | Load-dependent CoMoM, same shape restriction. | — |
rgf | Recursion by generating functions, single class by construction; multiclass input falls back to the exact convolution. | — |
ger | Exact closed form by iterated residues of the rational generating function, one class per elimination. | — |
divdiff | Divided-difference closed form of the multiclass constant: Gordon's partial fraction at distinct induced demands, the general expansion at repeated ones. | — |
rec | Normalizing constant by one memoised walk of a decision diagram over the reachable set; the only method admissible on a Petri net. | — |
mmint2 | McKenna-Mitra integral by Gauss-Legendre quadrature; a delay plus a single queueing station. | — |
gleint | The same integral and the same shape, second quadrature variant. | — |
cub, gm | Grundmann-Moeller cubature on the simplex, exact for the polynomial integrand at order ceil((N-1)/2). | [3] |
le | Logistic expansion: the Laplace saddle point of the integral after the logistic transform. | [3] |
ble | The logistic expansion with an empirical per-direction correction, better on lG than le. | — |
aghq | Adaptive Gauss-Hermite quadrature of the simplex factor, q nodes per direction; q = 1 reproduces le. | — |
kt | Knessl-Tier asymptotic expansion of the normalizing constant. | [4] |
bkt | Knessl-Tier minus the exact Stirling remainder that steepest descent drops in each Laplaced class direction. | — |
lekt | Whichever of ble and bkt is cheaper: the R-dimensional saddle point when R <= M, the M-dimensional logistic mode otherwise. | — |
bk | Birman-Kogan saddle-point expansion of the multichain partition function. | — |
bkue | Van der Waerden uniform expansion, dominant pole and saddle point in one erfc formula; multichain models fall back to bk. | — |
lc | Birman-Kogan Algorithm 2: load concealment, reducing a multichain network to single-chain problems. | — |
lc.ue | Algorithm 2 with the uniform expansion as its single-chain solver. | — |
pana | PANACEA normal-usage asymptotic expansion of the constant, load-independent. | [5], [6] |
panald | Load-dependent PANACEA expansion and its pseudonetwork coefficients. | — |
mci | Monte Carlo integration of the constant; on a loss network the Ross-Wang importance-sampling summation. | — |
imci | Improved (tilted) Monte Carlo integration of the same integral. | [7] |
ls | Logistic sampling: Monte Carlo on the logistic-transformed integral. | [3] |
is | Sample-an-ordering importance sampling, with load-dependent, OI and pass-and-swap variants; closed populations only. | — |
sampling | Shape-selected sampler: pfqn_mmsample2 for one queue, tilted MCI when stations outnumber classes, otherwise pfqn_ls; the OI importance sampler on a pass-and-swap model. | — |
mcmc | Markov-chain Monte Carlo estimate of the normalizing constant. | — |
propfair | Proportionally fair allocation approximation (Walton). | — |
clw | Numerical inversion of the generating function; the Bertozzi-McKenna transform kernel on a rate lattice. | — |
rd | Reduction heuristic for the load-dependent normalizing constant. | [8] |
nrp | Norlund-Rice probit approximation of the load-dependent constant. | [8] |
nrl | Norlund-Rice logit approximation of the load-dependent constant. | [8] |
nre | Norlund-Rice integral by Daniels steepest descent with the Barndorff-Nielsen-Cox second-order correction. | — |
mem | Kouvatsos maximum entropy (GE/GE/1, GE/GE/c, GE/GE/inf blocks), including finite-buffer open queues. The separate M/M/1/K loss-system route is available under default and exact. | [9] |
morrison | Two-term heavy-usage asymptotic expansion of the generating function for a closed think+DPS network; non-product-form, so it reports no lG. | — |
sdr | State-dependent routing: Krzesinski's product-form joint distribution and routing probabilities for an entry centre. | — |
sdr.mva | Mean value analysis and convolution of the same state-dependent-routing product form, single-centre branches. | — |
ms | Manjunath-Sikdar transform of the loss-network analyzer; loss networks only. | — |
erlangfp | Erlang fixed-point (reduced-load) approximation of the loss network. | — |
rayint | On a Source-Cache-Sink model an alias of spm; on an open delayed-hit retrieval cache the ray/WKB expansion, infinite-server fetch only. | — |
spm | Saddle-point miss-ratio expansion of an isolated cache, size-tilted once items carry storage costs. | — |
Configuration options
The solver-specific fields below belong to options.config. Set them on an options struct, for example opt.config.name = value, and pass that struct to the solver constructor. See shared solver options for all top-level fields, shared configuration, defaults and usage. Options apply only to the methods and model features that consume them.
Relevant top-level options: samples, seed, tol.
NC defaults to samples=1e5 and config.highvar='interp'. Decomposition and loss-network routes also use the shared fixed-point driver.
| Option | Default | Description and values |
|---|---|---|
aghq_nodes | rule default | Adaptive Gauss-Hermite quadrature: nodes per simplex direction, so cost is nodes^dimension. |
algorithm | 'exact' | Response-time CDF kernel of getCdfRespT: 'exact' is pfqn_stdf, 'rd' its heuristic. |
mcmc_batches | 30 | Batch count the MCMC estimator uses for its confidence intervals. |
mcmc_burnin | 0.1 | Fraction of the MCMC chain discarded as warm-up. |
mem_maxiter | 1000 | Maximum iterations of the maximum-entropy (MEM) normalizing-constant solver. |
mem_tol | 1e-6 | Convergence tolerance of that solver. |
mem_verbose | false | Print its per-iteration progress. |
spn_bound | unset | Bound mode handed to spn_pf when a stochastic Petri net is solved by product form. |
Example
This example demonstrates a closed queueing network with 5 jobs. The NC solver computes the normalizing constant using the CoMoM algorithm to obtain exact performance metrics without simulation.
% Create a closed network with delay and queue
model = Network('NC Example');
delay = Delay(model, 'Delay');
queue = Queue(model, 'Queue', SchedStrategy.FCFS);
% Closed class with 5 jobs
jobclass = ClosedClass(model, 'Class1', 5, delay);
delay.setService(jobclass, Exp(1.0));
queue.setService(jobclass, Exp(2.0));
% Circular routing
P = model.initRoutingMatrix();
P.set(jobclass, jobclass, delay, queue, 1.0);
P.set(jobclass, jobclass, queue, delay, 1.0);
model.link(P);
% Solve with NC
solver = NC(model);
NC(model).avgTable()
Output:
NC analysis [method: default/comom; type: exact, deterministic; lang: matlab; env: 2025a] completed in 0.041s.
ans =
2×8 table
Station JobClass QLen Util RespT ResidT ArvR Tput
_______ ________ ______ ______ ______ ______ ______ ______
Delay Class1 1.9266 1.9266 1 1 1.9266 1.9266
Queue Class1 3.0734 0.9633 1.5952 1.5952 1.9266 1.9266
import jline.lang.*;
import jline.lang.constant.SchedStrategy;
import jline.lang.nodes.Delay;
import jline.lang.nodes.Queue;
import jline.lang.processes.Exp;
import jline.solvers.NetworkAvgTable;
import jline.solvers.nc.NC;
import java.util.List;
public class NCExample {
public static void main(String[] args) {
// Create a closed network with delay and queue
Network model = new Network("NC Example");
Delay delay = new Delay(model, "Delay");
Queue queue = new Queue(model, "Queue", SchedStrategy.FCFS);
// Closed class with 5 jobs
ClosedClass jobclass = new ClosedClass(model, "Class1", 5, delay);
delay.setService(jobclass, Exp.fitRate(1.0));
queue.setService(jobclass, Exp.fitRate(2.0));
// Circular routing
RoutingMatrix P = new RoutingMatrix(model,
List.of(jobclass), List.of(delay, queue));
P.addConnection(jobclass, jobclass, delay, queue, 1.0);
P.addConnection(jobclass, jobclass, queue, delay, 1.0);
model.link(P);
// Solve with NC
NC solver = new NC(model);
NetworkAvgTable avgTable = solver.avgTable;
System.out.println(avgTable);
}
}
Output:
NC analysis [method: default/comom; type: exact, deterministic; lang: java; env: 17.0.9] completed. Station JobClass QLen Util RespT ResidT ArvR Tput Delay Class1 1.9266 1.9266 1.0 1.0 1.9266 1.9266 Queue Class1 3.0734 0.9633 1.5952 1.5952 1.9266 1.9266
from line_solver import *
# Create a closed network with delay and queue
model = Network('NC Example')
delay = Delay(model, 'Delay')
queue = Queue(model, 'Queue', SchedStrategy.FCFS)
# Closed class with 5 jobs
jobclass = ClosedClass(model, 'Class1', 5, delay)
delay.setService(jobclass, Exp(1.0))
queue.setService(jobclass, Exp(2.0))
# Circular routing
P = model.initRoutingMatrix()
P.set(jobclass, jobclass, delay, queue, 1.0)
P.set(jobclass, jobclass, queue, delay, 1.0)
model.link(P)
# Solve with NC
solver = NC(model)
print(solver.avg_table)
Output:
NC analysis [method: default/comom; type: exact, deterministic; lang: python; env: 3.13.7] completed. Station JobClass QLen Util RespT ResidT ArvR Tput 0 Delay Class1 1.9266 1.9266 1.0 1.0 1.9266 1.9266 1 Queue Class1 3.0734 0.9633 1.5952 1.5952 1.9266 1.9266
References
- Casale, G. (2009). CoMoM: A class-oriented method of moments for queueing networks. IEEE Transactions on Software Engineering, 35(5), 692-709.
- Reiser, M. (1981). Mean-value analysis and convolution method for queue-dependent servers. Performance Evaluation, 1(1), 7-18.
- Casale, G. (2017). Analytical modelling of data-parallel applications. IEEE ICDCS, pp. 2330-2336.
- Knessl, C., & Tier, C. (1992). Asymptotic approximations for queueing systems. IEEE Transactions on Computers, 41(6), 771-790.
- McKenna, J., & Mitra, D. (1984). Asymptotic expansions and integral representations. Journal of the ACM, 31(2), 346-360.
- Robertazzi, T. G. (2000). Computer Networks and Systems (3rd ed.). Springer.
- Wang, W., Casale, G., & Sutton, C. (2016). Improved Monte Carlo integration. ACM TOMACS, 26(4), 22.
- Casale, G., Harrison, P. G., & Hong, Z. (2021). An efficient algorithm for the Nörlund-Rice integral. Performance Evaluation, 150, 102203.
- Kouvatsos, D. D. (1994). Entropy maximisation and queueing network models. Annals of Operations Research, 48, 63-126.