Non-Product-Form Networks

Approximations for intractable queueing networks.

The npfqn module provides approximation methods for non-product-form queueing networks that do not satisfy BCMP conditions.

Key function categories:

• Traffic merging: npfqn_traffic_merge(), npfqn_traffic_merge_cs()

• Traffic splitting: npfqn_traffic_split_cs()

• Service approximations: npfqn_nonexp_approx()

Non-Product-Form Queueing Network (NPFQN) algorithms.

Native Python implementations for approximating performance of non-product-form queueing networks.

Key algorithms:

npfqn_nonexp_approx: Non-exponential distribution approximation npfqn_traffic_merge: Merge multiple MMAP traffic flows npfqn_traffic_merge_cs: Merge traffic flows with class switching npfqn_traffic_split_cs: Split traffic flows with class switching

npfqn_nonexp_approx(method, sn, ST, V, SCV, Tin, Uin, gamma, nservers)

Approximates non-product-form queueing networks using the specified method.

This function adjusts service times and other parameters to account for non-exponential service time distributions in product-form analysis.

Parameters:

• method (str) – Approximation method (“default”, “none”, “hmva”, “interp”)

• sn (NetworkStruct) – Network structure

• ST (numpy.ndarray) – Service time matrix (M x K)

• V (numpy.ndarray | None) – Visit ratios matrix (M x K), optional

• SCV (numpy.ndarray) – Squared coefficient of variation matrix (M x K)

• Tin (numpy.ndarray) – Initial throughput matrix (M x K)

• Uin (numpy.ndarray) – Initial utilization matrix (M x K)

• gamma (numpy.ndarray) – Gamma correction matrix (M x 1)

• nservers (numpy.ndarray) – Number of servers matrix (M x 1)

Returns:

NpfqnNonexpApproxResult with updated matrices

Raises:

ValueError – If unknown approximation method is specified

Return type:

NpfqnNonexpApproxResult

class NpfqnNonexpApproxResult(ST, gamma, nservers, rho, scva, scvs, eta)

Bases: object

Result of non-exponential approximation.

ST: numpy.ndarray

gamma: numpy.ndarray

nservers: numpy.ndarray

rho: numpy.ndarray

scva: numpy.ndarray

scvs: numpy.ndarray

eta: numpy.ndarray

npfqn_traffic_merge(MMAPa, config_merge='default', config_compress=None)

Merge multiple MMAP traffic flows.

Combines multiple MMAPs using specified aggregation strategies. Supports various merge configurations for different network topologies.

Parameters:

• MMAPa (Dict[int, List[numpy.ndarray] | None]) – Dictionary of MMAP traffic flows to be merged. Keys are integer indices, values are MMAP lists [D0, D1, …].

• config_merge (str) – Merge configuration. Options: - “default”, “super”: Use MMAP superposition - “mixture”: Apply mixture fitting after superposition - “interpos”: Interposition method (falls back to super)

• config_compress (str | None) – Compression configuration. Options: - None, “none”: No compression - “default”: Apply default compression

Returns:

Merged and normalized MMAP, or None if input is empty.

Raises:

RuntimeError – If unsupported merge configuration is provided.

Return type:

List[numpy.ndarray] | None

Example

>>> mmap1 = [np.array([[-1.0]]), np.array([[1.0]])]
>>> mmap2 = [np.array([[-2.0]]), np.array([[2.0]])]
>>> result = npfqn_traffic_merge({0: mmap1, 1: mmap2})

npfqn_traffic_merge_cs(MMAPs, prob, config='default')

Merge MMAP traffic flows with class switching.

Combines multiple MMAPs while applying class switching transformations based on the probability matrix.

Parameters:

• MMAPs (Dict[int, List[numpy.ndarray]]) – Dictionary of MMAP traffic flows indexed by source.

• prob (numpy.ndarray) –

  Class switching probability matrix ((n*R) x R) where: - n is the number of sources - R is the number of classes - prob[(i-1)*R + r, s] = probability that class r from source i

  becomes class s in the merged stream

• config (str) – Merge configuration (“default” or “super”).

Returns:

Merged MMAP with class switching applied, or None if empty.

Return type:

List[numpy.ndarray] | None

Algorithm:

1. Apply mmap_mark to each source MMAP to encode class switching

2. Superpose all marked MMAPs

3. Return result

Example

>>> mmap1 = [np.array([[-1.0]]), np.array([[0.5]]), np.array([[0.5]])]
>>> mmap2 = [np.array([[-2.0]]), np.array([[1.0]]), np.array([[1.0]])]
>>> prob = np.array([[0.8, 0.2], [0.3, 0.7], [0.6, 0.4], [0.5, 0.5]])
>>> result = npfqn_traffic_merge_cs({0: mmap1, 1: mmap2}, prob)

npfqn_traffic_split_cs(MMAP_input, P)

Split MMAP traffic flows with class switching.

Decomposes a single MMAP into multiple MMAPs based on routing probabilities and class switching matrix.

Parameters:

• MMAP_input (List[numpy.ndarray]) – Input MMAP as list [D0, D1, D2, …].

• P (numpy.ndarray) –

  Class switching probability matrix (R x J) where: - R is the number of arrival classes - J = M * R where M is the number of destinations - P[r, (jst-1)*R + s] = probability that class r arrival

  becomes class s at destination jst

Returns:

Dictionary mapping destination index to split MMAP. Keys are 0-indexed destination indices.

Return type:

Dict[int, List[numpy.ndarray] | None]

Algorithm:

1. Parse dimensions from P matrix

2. For each destination, create MMAP with weighted marking matrices

3. Normalize each result

Example

>>> mmap = [np.array([[-3.0]]), np.array([[1.0]]), np.array([[2.0]])]
>>> P = np.array([[0.8, 0.2, 0.5, 0.5], [0.3, 0.7, 0.6, 0.4]])
>>> result = npfqn_traffic_split_cs(mmap, P)

npfqn_sqd(sn, N=None, calibration_mode=0, server_blocking_time=True, neighbor_mode='downstream', v1_policy='compound', initial_v1=None)

Solve a BAS closed network from its NetworkStruct.

Parameters:

• sn (NetworkStruct) – chain-aggregated network structure

• N (int | None) – total closed-class population (defaults to sn.nclosedjobs)

• calibration_mode (int) – 0=base, 1=fixed heuristic, 2=blocking-aware

• server_blocking_time (bool) – add a manufacturing-blocking term to server time

• neighbor_mode (str) – ‘downstream’ (routed) or ‘ownserver’ blocking aggregation

• v1_policy (str) – ‘compound’ or ‘fresh’ load-dependent rate-scale update

• initial_v1 (numpy.ndarray | None) – optional per-station initial V1 (None = _INITIAL_V1)

Returns:

NpfqnSqdResult with per-station X, Q, U, R.

Return type:

NpfqnSqdResult

class NpfqnSqdResult(X, Q, U, R)

Bases: object

Per-station results of the BAS approximation (single chain).

X

(M,) per-station throughput

Type:

numpy.ndarray

Q

(M,) per-station queue length

Type:

numpy.ndarray

U

(M,) per-station utilization

Type:

numpy.ndarray

R

(M,) per-station residence time

Type:

numpy.ndarray

X: numpy.ndarray

Q: numpy.ndarray

U: numpy.ndarray

R: numpy.ndarray

npfqn_rqna_weight(t)

Canonical RBM correlation weight function w*(t) used by the RQNA.

w*(t) = 1 - (1 - c*(t))/(2 t), where c*(t) is the correlation function of the stationary version of canonical reflected Brownian motion (drift -1, diffusion coefficient 1),

c*(t) = 2(1 - 2t - t^2) Phi^c(sqrt(t)) + 2 sqrt(t) phi(sqrt(t)) (1 + t),

with Phi^c the standard-normal complementary cdf and phi its density. The weight is monotonically increasing with w*(0)=0 and w*(Inf)=1.

Reference: Whitt and You (2018), eqs. (24)-(25).

Parameters:

t – scalar or array of nonnegative time arguments

Returns:

Weight(s) w*(t) in [0,1], same shape as t (scalar in -> float out).

npfqn_traffic_idc(lambda0, P, c2a0, a0IdcFun, mu, cs2, sIdcFun, corrections=None)

Traffic variability equations for the RQNA. Assembles and solves:

• the limiting variability equations (eq. 42/44) for the asymptotic total-arrival variability parameters c2_{a,i} = I_{a,i}(Inf);

• a solver (ctx.IaFun) for the time-dependent IDC equations (eq. 40/43), returning I_{a,i}(t) for all internal arrival flows, using the default correction terms alpha_{i,j} (eq. 34) and beta_i (eqs. 38-39) and tuning function h(rho)=rho^2.

Models a single-class open network of K single-server FCFS queues with Markovian routing P (P[i,j]=p_{i,j}).

Parameters:

• lambda0 – (K,) external arrival rate into each queue

• P – (K,K) routing matrix among queues

• c2a0 – (K,) asymptotic IDC (SCV) of each external arrival process

• a0IdcFun – callable a0IdcFun(t) -> (K,) external arrival IDC I_{a,0,i}(t)

• mu – (K,) service rate at each queue

• cs2 – (K,) service SCV c2_{s,i}

• sIdcFun – callable sIdcFun(t) -> (K,) service IDC I_{s,i}(t)

• corrections – optional dict with ‘alpha’/’beta’ bool toggles

Returns:

_TrafficIdcContext with lambda, rho, Xi, c2a, c2d, c2aij, c2x fields and method IaFun(t).