NC (Normalizing Constant)

The NC solver implements algorithms based on the normalizing constant of product-form queueing networks. Unlike other solvers, NC is able to compute state and marginal probabilities in queueing networks without the need for simulation. It also offers the most accurate approximations for models including caches.

MethodAlgorithmReference
defaultAutomatic method selection—
exactExact normalizing constant computation—
caMulticlass convolution algorithm (exact)—
comomClass-oriented method of moments (exact)[1]
leLogistic asymptotic expansion[3]
ktKnessl-Tier asymptotic expansion[4]
panaceaPanacea asymptotic expansion[5], [6]
nrpNörlund-Rice integral (direct)[8]
nrlNörlund-Rice integral (Laplace)[8]
imciImproved Monte Carlo integration[7]
lsLogistic sampling (Monte Carlo)[3]
samplingGeneric sampling method—
cubGrundmann-Moeller cubature rules[3]
mmint2Interpolation method—
gleintGauss-Laguerre exponential interpolation—
memMaximum Entropy Method for open queueing networks[9]
rdReduction heuristic[8]
propfairProportional fairness method—
gmGeneral method—

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, lang: matlab] 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, lang: java] 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, lang: python] 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

  1. Casale, G. (2009). CoMoM: A class-oriented method of moments for queueing networks. IEEE Transactions on Software Engineering, 35(5), 692-709.
  2. Reiser, M. (1981). Mean-value analysis and convolution method for queue-dependent servers. Performance Evaluation, 1(1), 7-18.
  3. Casale, G. (2017). Analytical modelling of data-parallel applications. IEEE ICDCS, pp. 2330-2336.
  4. Knessl, C., & Tier, C. (1992). Asymptotic approximations for queueing systems. IEEE Transactions on Computers, 41(6), 771-790.
  5. McKenna, J., & Mitra, D. (1984). Asymptotic expansions and integral representations. Journal of the ACM, 31(2), 346-360.
  6. Robertazzi, T. G. (2000). Computer Networks and Systems (3rd ed.). Springer.
  7. Wang, W., Casale, G., & Sutton, C. (2016). Improved Monte Carlo integration. ACM TOMACS, 26(4), 22.
  8. Casale, G., Harrison, P. G., & Hong, Z. (2021). An efficient algorithm for the Nörlund-Rice integral. Performance Evaluation, 150, 102203.
  9. Kouvatsos, D. D. (1994). Entropy maximisation and queueing network models. Annals of Operations Research, 48, 63-126.
← Back to Solvers