api.lossn

lossn_rec(nu, A, C)

[QLEN, LOSS, LG, NITER] = LOSSN_REC(NU, A, C) Exact analysis of a loss network by MDD-rec: the normalising constant is the sum of a product form over the admissible set {n >= 0 : A n <= C}, which is what a decision diagram holding that set computes in one memoised walk.

A Kelly loss network carries offered load nu_r on route r and admits a call only while the resource constraint A n <= C still holds after it. The stationary law is the truncation of independent Poisson counts to that set,

P(n) = (1/G) prod_r nu_r^{n_r} / n_r!, G = sum_{A n <= C} prod_r …,

so g_r(k) = nu_r^k/k! and MDD_REC returns G. By PASTA the acceptance probability of a class-r call is the ratio of two such constants,

1 - B_r = G(C - A e_r) / G(C),

which is one further diagram per class.

WHY THIS EXISTS ALONGSIDE LOSSN_MANJUNATH. The Manjunath-Sikdar transform evaluates G exactly as a multidimensional residue, and the residue argument counts WHOLE UNITS: it needs an integral A and C. On a region declaring a fractional class size or capacity the analyzer had no exact route at all and fell back to the Erlang fixed point, an approximation. MDD-rec needs only that the admissible set be finite and bounded coordinate by coordinate, which a fractional constraint still is, so it is exact there too. It is also an exact alternative to the Monte Carlo summation LOSSN_MCI estimates.

– Input NU : 1 x K offered load per class A : J x K non-negative resource requirement matrix C : J x 1 capacity vector – Output QLEN : 1 x K mean number of class-r calls in progress (the carried load) LOSS : 1 x K blocking probability LG : log of the normalising constant G(C) NITER: number of diagram walks performed, K + 1

– Reference F. P. Kelly, “Loss networks”, Annals of Applied Probability 1(3), 1991. S. Balsamo, A. Marin, I. Stojic, “Computation of the normalising constant for product-form models of distributed systems with synchronisation”, Future Generation Computer Systems 111 (2020) 475-490.

See also LOSSN_MANJUNATH, LOSSN_ERLANGFP, LOSSN_MCI, MDD_REC.

mexify_lossn

@brief MATLAB Coder script to generate MEX functions for lossn_ module.

This script generates MEX (MATLAB Executable) versions of loss-network functions for improved performance.

See also CODER, CODER.CONFIG, CODER.TYPEOF, CODEGEN.

test_lossn_manjunath(): TEST_LOSSN_MS Validate the Manjunath-Sikdar transform for loss networks against Erlang-B, exact box enumeration, and the Monte Carlo estimator.

lossn_manjunath(nu, A, C)

Exact normalization constant and blocking probabilities of a loss network

Calls on route r arrive according to a Poisson process of rate nu_r with unit mean holding time, so nu_r is the offered load. A call is admitted only if it leaves every link within capacity,

sum_r A(j,r) n_r <= C(j), j = 1 … J,

and is lost otherwise. The admissible set is coordinate convex, so by Kelly’s truncation theorem the stationary distribution is the truncated product form

p(n) = (1/g(C)) prod_r nu_r^{n_r} / n_r!, A n <= C,

and every metric follows from ratios of the normalization constant

g(C) = sum_{A n <= C} prod_r nu_r^{n_r} / n_r! E[n_r] = nu_r g(C - A e_r) / g(C) Loss_r = 1 - g(C - A e_r) / g(C)

because a class r call is blocked exactly when the state cannot absorb one more unit of its own requirement vector.

g(C) is evaluated exactly by the transform technique of Manjunath and Sikdar. Writing the indicator of each constraint as a contour integral turns the sum into a J-fold integral over the unit circle whose integrand factorizes into the z-transforms of the per-route terms,

g(C) = oint … oint prod_j [ (z_j^{C_j+1}-1) / (z_j^{C_j+1}(z_j-1)) ] prod_r Fcal_r(z_1^{A_1r} … z_J^{A_Jr}) dz_1 … dz_J.

Inside the unit circle the only pole in z_j is at the origin, of order C_j+1, so each integration is a residue and hence a Taylor coefficient. The routine therefore builds the generating function as a multivariate power series truncated at degree C_j in z_j, one shift-and-accumulate convolution per route, and each ‘<=’ constraint is discharged by summing the coefficients of degrees 0 … C_j along that dimension. Truncation is exact because A is nonnegative: a monomial above degree C_j can never contribute to an extracted coefficient.

Contour integrations are interleaved with the product rather than deferred to the end: variable z_j is created when the first route with A(j,r) ~= 0 is multiplied in and integrated out immediately after the last one, so the peak memory is the product of (C_j+1) over the simultaneously live links, an induced width, rather than over all J links.

Unlike lossn_erlangfp this is exact rather than a reduced-load approximation, and unlike lossn_mci it carries no sampling error, which matters for rare blocking: a loss probability of 1e-4 recovered from a simulated or sampled throughput is dominated by the estimator variance. The cost is prod_j (C_j+1) memory over the live links, so it is exact but not unconditionally cheap; use lossn_mci when that product is prohibitive.

A and C must be integer valued, since the residue argument counts whole units of capacity. Each row is divided by the greatest common divisor of its entries and of C(j), which is exact and shrinks the corresponding dimension. Routes appearing in no constraint never block and contribute a factor exp(nu_r) to g(C).

Parameters:

nu – Offered load of route (class) r (1xR vector)
A – Capacity requirement of link j for route r (JxR nonnegative integers)
C – Available capacity of link j (Jx1 nonnegative integers)

Returns:

QLen – Mean carried load E[n_r] for route r (1xR) Loss: Blocking probability for route r (1xR) lG: Log of the exact normalization constant g(C) niter: Number of iterations, always 1 (direct method)

Examples

[QLen, Loss, lG, niter] = lossn_manjunath(nu, A, C)

References

D. Manjunath and B. Sikdar, Integral Expressions for the Numerical Evaluation of Product Form Expressions Over Irregular Multidimensional Integer Spaces.

test_lossn_mci(): TEST_LOSSN_MCI Validate Monte Carlo summation for loss networks against exact enumeration, Erlang-B, and the Erlang fixed point.

lossn_mci(nu, A, C, options)

Estimates the product-form normalization constant and class blocking probabilities of a loss network by Monte Carlo summation.

Implements the importance-sampling Monte Carlo summation method of Ross and Wang, “Monte Carlo Summation Applied to Product-Form Loss Networks”, Probability in the Engineering and Informational Sciences, 6 (1992), 323-348.

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

States are sampled from the importance distribution (Eq. 6) p(n) = (1/c) prod_r gamma_r^n_r / n_r!, n in {0..N_1}x..x{0..N_R}, with N_r = min_j floor(C_j/A_jr) over A_jr>0. Ratio estimators (Eq. 8) give unbiased/consistent g and consistent blocking with delta-method confidence intervals.

Parameters:

nu – Offered load of route (class) r (1xR vector)
A – Circuit requirement of link j for route r (JxR matrix)
C – Available capacity of link j (Jx1 vector)
options – struct with optional fields: samples (default 1e5),

Returns:

QLen – Mean carried load (E[n_r]) for route r (1xR) Loss: Blocking probability beta_r for route r (1xR) lG: Log of the estimated normalization constant g(C) ci: struct with confidence intervals and point estimates: nsamples: Number of Monte Carlo samples used

Examples

[QLen, Loss, lG, ci, nsamples] = lossn_mci(nu, A, C)
[QLen, Loss, lG, ci, nsamples] = lossn_mci(nu, A, C, options)

lossn_erlangfp(nu, A, C)

Computes performance metrics for loss networks using Erlang FP

This function uses the Erlang fixed point approximation to compute performance metrics for loss networks. Calls on route r arrive according to Poisson rate nu_r with unit mean service times. Link capacity requirements are: sum_r A(j,r) n(j,r) <= C(j) for all links j.

Parameters:

nu – Arrival rate of route (class) r (1xR vector)
A – Capacity requirement of link j for route r (JxR matrix)
C – Available capacity of link j (Jx1 vector)

Returns:

QLen – Mean queue-length for route r Loss: Loss probability for route r E: Blocking probability for link j niter: Number of iterations required for convergence

Examples

[QLen, Loss, E, niter] = lossn_erlangfp(nu, A, C)

[QLen,Loss,E] = LOSS_ERLANGFP(rho,A,C) Erlang fixed point approximation for loss networks

Calls (i.e., jobs) on route (i.e., class) r arrive according to Poisson rate nu_r, r=1..R. Call service times on route r have unit mean.

Link capacity requirements are:: sum_r A(j,r) n(j,r) <= C(j)

for all links j=1..J, where n(j,r) counts the calls on route r on link j.

INPUT: nu (1xR): arv. rate of route (class) r = 1..R A (J,R): capacity requirement of link j for route r = 1..R C (J,1): available capacity of link j

OUTPUT: Q (1xR): mean queue-length for route r = 1..R calls L (1xR): loss probability for route r = 1..R calls E (Jx1): blocking probability of for link j = 1..J

NOTE: nu_r may be replaced by a utilization rho_r=nu_r/mu_r, where mu_r is the service rate for route r.