Exact analysis of a loss network by the Manjunath-Sikdar transform. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <numeric>
#include <string>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for lossn_manjunath.h:

Classes
struct	line::lossn::LossnManjunathOptions
	Controls of lossn_manjunath. More...
struct	line::lossn::LossnManjunathResult< T >
	Result of lossn_manjunath. More...

Namespaces
namespace	line
namespace	line::lossn

Functions
template<class T>
LossnManjunathResult< T >	line::lossn::lossn_manjunath (const std::vector< T > &nu, const Matrix< T > &A, const std::vector< T > &C, const LossnManjunathOptions &options=LossnManjunathOptions())
	Exact normalizing constant, carried load and blocking of a loss network.

Detailed Description

Exact analysis of a loss network by the Manjunath-Sikdar transform.

Templated port of matlab/src/api/lossn/lossn_manjunath.m. Calls on route r arrive Poisson at rate nu_r with unit mean holding time and are admitted only while every constraint holds, sum_r A(j,r) n_r <= C(j). The admissible set is coordinate convex, so Kelly's truncation theorem gives the truncated product form p(n) = nu^n / n! / g(C) and every metric is a ratio of normalizing constants:

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.

WHY IT IS A COEFFICIENT COMPUTATION AND NOT A QUADRATURE. Writing each indicator as a contour integral turns g(C) into a J-fold integral over the unit circle whose integrand factorizes into the per-route z-transforms. Inside the circle the only pole in z_j sits at the origin with order C_j+1, so each integration is a residue, i.e. a Taylor coefficient. The routine therefore never evaluates an integral: it 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 discharges each '<=' constraint 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.

THE ELIMINATION ORDER IS THE MEMORY BOUND. Contour integrations are interleaved with the product rather than deferred: 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. Peak memory is therefore the product of (C_j+1) over the SIMULTANEOUSLY LIVE links, an induced width of the route-link incidence, not over all J links. That product is bounded by LossnManjunathOptions::max_live_states and a region above it is refused by name rather than allowed to exhaust the machine: the algorithm is exact but not unconditionally cheap, and lossn_mci answers the same question at any size.

WHY THIS ONE RUNS AT EXACT ARITHMETIC AND ITS TWO SIBLINGS DO NOT. lossn_erlangfp stops on a tolerance and lossn_mci returns a random variable, so both are transcendental-gated. Here every operation on the series is an addition or a multiplication of terms nu_r^n / n!, which is rational whenever nu is, and the reported quantities are RATIOS of series values, so QLen and Loss come out exact under Arith::Exact. Only lG is transcendental, and it is a double in the result for all three arithmetics anyway, obtained through num_traits<T>::log_as_double (which is defined for Rational via log_bigint, so no logarithm is ever taken of a value that has to be representable as a double).

OVERFLOW, AND WHY THE SCALING IS ARITHMETIC-DEPENDENT. The term nu^n/n! peaks near n = nu at roughly e^nu / sqrt(2 pi nu), which overflows a double for loads above ~700. The reference builds the sequence in log space and divides it by its largest entry, accumulating the discarded logarithm and adding it back in log g; the port does the same under an inexact T. Under an exact T there is no overflow to avoid and the scaling would only inflate the denominators of the rationals, so it is skipped. The scale cancels in every ratio, so QLen and Loss are unaffected and lG is identical either way.

A and C must be integer valued, since the residue argument counts whole units of capacity; a fractional entry is refused rather than rounded, naming lossn_mci which compares in real arithmetic. Each row is divided by the greatest common divisor of its entries together with its right-hand side, which is exact and shrinks the truncation degree. Routes appearing in no constraint never block and contribute a factor exp(nu_r) to g(C).

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

Definition in file lossn_manjunath.h.

Classes

Namespaces

Functions

Detailed Description