Loss Networks

Analysis of networks with blocking.

The lossn module implements algorithms for loss networks where arrivals can be blocked when resources are unavailable.

Key function categories:

Loss Network Analysis Algorithms.

Native Python implementations for analyzing loss networks using Erlang formulas and related methods.

Key algorithms:

lossn_manjunath: Manjunath-Sikdar transform, exact normalization constant lossn_rec: exact normalization constant by MDD-rec, integral A and C not needed lossn_erlangfp: Erlang fixed-point algorithm for loss networks lossn_mci: Monte Carlo importance-sampling summation (Ross-Wang) erlang_b: Erlang B blocking probability erlang_c: Erlang C delay probability

lossn_erlangfp(nu, A, c, tol=1e-8, max_iter=1000)[source]

Erlang fixed point approximation for loss networks.

Calls (jobs) on route (class) r arrive according to Poisson rate nu_r. Call service times on route r have unit mean.

The link capacity requirements are:

sum_r A[j,r] * n[j,r] < c[j]

for all links j, where n[j,r] counts calls on route r on link j.

Parameters:

  • nu (ndarray) – Arrival rates vector (R,) for each route.

  • A (ndarray) – Capacity requirement matrix (J, R) - A[j,r] is capacity required on link j by route r.

  • c (ndarray) – Capacity vector (J,) - c[j] is capacity of link j.

  • tol (float) – Convergence tolerance.

  • max_iter (int) – Maximum iterations.

Returns:

  • qlen: Mean queue-length for each route (R,)

  • loss: Loss probability for each route (R,)

  • eblock: Blocking probability for each link (J,)

  • niter: Number of iterations

Return type:

Tuple of (qlen, loss, eblock, niter) where

Example

>>> nu = np.array([0.3, 0.1])
>>> A = np.array([[1, 1], [1, 4]])  # 2 links, 2 routes
>>> c = np.array([1, 3])
>>> qlen, loss, eblock, niter = lossn_erlangfp(nu, A, c)
erlang_b(offered_load, servers)[source]

Compute Erlang B blocking probability.

The Erlang B formula gives the probability that an arriving call is blocked in an M/M/c/c loss system.

Parameters:

  • offered_load (float) – Traffic intensity (arrival rate * service time).

  • servers (int) – Number of servers.

Returns:

Blocking probability.

Return type:

float

Example

>>> erlang_b(10.0, 12)  # Offered load 10 Erlang, 12 channels
0.1054...
erlang_c(offered_load, servers)[source]

Compute Erlang C delay probability.

The Erlang C formula gives the probability that an arriving call must wait in an M/M/c queue.

Parameters:

  • offered_load (float) – Traffic intensity (arrival rate * service time).

  • servers (int) – Number of servers.

Returns:

Delay probability (probability of waiting).

Return type:

float

Example

>>> erlang_c(10.0, 12)  # Offered load 10 Erlang, 12 agents
lossn_mci(nu, A, C, samples=100000, gamma=None, seed=None, alpha=0.05)[source]

Monte Carlo importance-sampling summation for loss networks.

A loss network has links j=1..J with capacity C[j] and classes r=1..R with offered load nu[r] and per-link circuit requirement A[j,r]. The state n is feasible iff A @ n <= C (set Omega). The product-form normalization constant is g(C) = sum_{n in Omega} prod_r nu[r]**n_r/n_r!. Class-r acceptance is g(C-A[:,r])/g(C) = 1 - beta_r.

States are drawn from the importance distribution (Eq. 6):

p(n) = (1/c) prod_r gamma_r**n_r / n_r!

over the box {0..N_1} x … x {0..N_R}, N_r = min_j floor(C_j/A_jr). Ratio estimators (Eq. 8) yield g and blocking with delta-method confidence intervals.

Parameters:

  • nu (ndarray) – Offered load per class (R,).

  • A (ndarray) – Circuit requirement matrix (J, R).

  • C (ndarray) – Link capacity vector (J,).

  • samples (int) – Number of Monte Carlo samples.

  • gamma (ndarray | None) – Importance-sampling parameters (R,); default is the Section 3.4 heuristic.

  • seed (int | None) – RNG seed for reproducibility.

  • alpha (float) – Confidence-interval significance level (default 0.05).

Returns:

  • qlen: Mean carried load E[n_r] per class (R,).

  • loss: Blocking probability beta_r per class (R,).

  • lG: Log of the estimated normalization constant g(C).

  • ci: dict with ‘accept’ (R,2), ‘loss’ (R,2), ‘acceptPoint’ (R,), ‘lossPoint’ (R,), ‘level’.

  • nsamples: Number of samples used.

Return type:

Tuple (qlen, loss, lG, ci, nsamples) where

lossn_manjunath(nu, A, C, max_live_states=None)[source]

Exact normalization constant, carried load and blocking of a loss network.

Parameters:

  • nu (ndarray) – Offered load of route (class) r (R,), nonnegative.

  • A (ndarray) – Capacity requirement of link j for route r (J, R), nonnegative integers.

  • C (ndarray) – Available capacity of link j (J,), nonnegative integers.

  • max_live_states (int | None) – Cap on the simultaneously live series coefficients; defaults to DEFAULT_MAX_LIVE_STATES.

Returns:

  • qlen: Mean carried load E[n_r] per route (R,).

  • loss: Blocking probability per route (R,).

  • lG: Log of the EXACT normalization constant g(C).

  • niter: Always 1; the transform is direct.

Return type:

Tuple (qlen, loss, lG, niter) where

lossn_rec(nu, A, C)[source]

Exact loss-network analysis by MDD-rec.

Parameters:

  • nu (offered load per class, length K)

  • A (J x K non-negative resource requirement matrix)

  • C (capacity vector, length J)

Returns:

  • (QLen, Loss, lG, niter) with QLen the carried load per class, Loss the

  • blocking probability per class, lG the log normalising constant G(C) and

  • niter the number of diagram walks performed, K + 1.

Return type:

Tuple[ndarray, ndarray, float, int]