lossn_asy.h File Reference

Large-capacity (Kelly limit) approximation of loss networks. More...

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

Include dependency graph for lossn_asy.h:

Go to the source code of this file.

Classes
struct	line::lossn::LossnAsyResult< T >
	Result of lossn_asy. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::lossn

Functions
template<class T>
LossnAsyResult< T >	line::lossn::lossn_asy (const std::vector< T > &nu, const Matrix< T > &A, const std::vector< T > &C)
	Fluid (Kelly) limit of a loss network by convex duality.

Detailed Description

Large-capacity (Kelly limit) approximation of loss networks.

Templated port of matlab/src/api/lossn/lossn_asy.m.

Scales offered loads nu and capacities C together, nu -> N nu and C -> N C, and returns the limit of the class loss probabilities as N grows (Kelly 1986; Ross 1995, Theorem 5.13). In this limit link j blocks independently with probability a_j, and the a_j solve the complementary slackness conditions

sum_k A(j,k) nu_k prod_i (1-a_i)^A(i,k) = C_j if a_j > 0, <= C_j if a_j = 0,

the route loss being 1 - prod_j (1-a_j)^A(j,k). With y_j = -log(1-a_j) these are the optimality conditions of the strictly convex problem

minimize sum_k nu_k exp(-sum_j A(j,k) y_j) + sum_j C_j y_j, y >= 0,

solved here by cyclic coordinate descent, each coordinate by Newton's method on a concave increasing function. The result needs no summation over states and costs O(J R) per sweep, so it scales to any capacity; it reports zero loss on links that are underloaded at the fluid scale, so it is accurate in heavy (overloaded) traffic and for large C. A and C need not be integral.

ARITHMETIC. Tolerance-driven Newton steps on exponentials: gated on num_traits<T>::has_transcendental.

References: F. P. Kelly, "Blocking probabilities in large circuit-switched networks", Adv. Appl. Probab. 18, 1986. F. P. Kelly, "Loss Networks", Ann. Appl. Probab. 1(3), 1991. K. W. Ross, "Multiservice Loss Models for Broadband Telecommunication Networks", Springer, 1995, Sec. 5.8.

See also

lossn_erlangfp, lossn_links

Definition in file lossn_asy.h.