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)[source]

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 (ndarray) – Service time matrix (M x K)
V (ndarray | None) – Visit ratios matrix (M x K), optional
SCV (ndarray) – Squared coefficient of variation matrix (M x K)
Tin (ndarray) – Initial throughput matrix (M x K)
Uin (ndarray) – Initial utilization matrix (M x K)
gamma (ndarray) – Gamma correction matrix (M x 1)
nservers (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)[source]

Bases: object

Result of non-exponential approximation.

ST: ndarray

gamma: ndarray

nservers: ndarray

rho: ndarray

scva: ndarray

scvs: ndarray

eta: ndarray

npfqn_traffic_merge(MMAPa, config_merge='default', config_compress=None)[source]

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[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[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')[source]

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[ndarray]]) – Dictionary of MMAP traffic flows indexed by source.
prob (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[ndarray] | None

Algorithm:

Apply mmap_mark to each source MMAP to encode class switching
Superpose all marked MMAPs
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)[source]

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[ndarray]) – Input MMAP as list [D0, D1, D2, …].
P (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[ndarray] | None]

Algorithm:

Parse dimensions from P matrix
For each destination, create MMAP with weighted marking matrices
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)