Exact analysis of a loss network by MDD-rec. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/mdd/mdd_rec.h"
#include "line/api/mdd/mdd_reachset.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/num/number.h"

Include dependency graph for lossn_rec.h:

Classes
struct	line::lossn::LossnRecResult< T >
	Carried load, blocking, log normalising constant and walk count. More...

Namespaces
namespace	line
namespace	line::lossn

Functions
template<class T>
LossnRecResult< T >	line::lossn::lossn_rec (const std::vector< T > &nu, const Matrix< T > &A, const std::vector< T > &C)
	Exact loss-network analysis by MDD-rec.

Detailed Description

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 AND lossn_erlangfp. 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. This port's lossn_erlangfp needs integrality too, for its own reason – it raises (1-E_i) to an unsigned integer power – so before MDD-rec a FRACTIONAL region had no route here at all except the Monte Carlo lossn_mci, whose answer is a random variable. 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 and is the default the fractional case now takes.

ARITHMETIC. Everything here is a sum, a product and one factorial, so the whole method is rational and available under exact arithmetic; only the reported lG needs a logarithm, and it is a double diagnostic rather than a T, exactly as the other analyzers treat it.

References: 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

Definition in file lossn_rec.h.

Classes

Namespaces

Functions

Detailed Description