Effective arrival processes of a network under the Robust Queueing calculus. More...

#include <cstddef>
#include <limits>
#include <vector>
#include "line/api/qsys/qsys_types.h"
#include "line/num/number.h"
#include "line/util/linalg.h"
#include "line/util/matrix.h"

Include dependency graph for npfqn_traffic_rqt.h:

Classes
struct	line::npfqn::TrafficRqt< T >

Namespaces
namespace	line
namespace	line::npfqn

Functions
template<class T>
TrafficRqt< T >	line::npfqn::npfqn_traffic_rqt (const std::vector< T > &lambda0, const std::vector< T > &Gamma0, const std::vector< T > &alpha0, const Matrix< T > &F)
	Effective arrival processes of a network under the Robust Queueing calculus.

Detailed Description

Effective arrival processes of a network under the Robust Queueing calculus.

Templated port of matlab/src/api/npfqn/npfqn_traffic_rqt.m, cross-checked against jar/src/main/java/jline/api/npfqn/Npfqn_traffic_rqt.java.

The network characterization composes three operators: passage through a queue with adversarial servers leaves the uncertainty set unchanged (robust Burke, Theorem 4), superposition merges sets by Theorem 5, and thinning by a fraction f scales the rate by f and the variability by f^(-1/alpha) (Theorem 6). The resulting equations are

lambda_j = lambda0_j + sum_i lambda_i f_ij, Gamma_j = (1/lambda_j) [ 1{a0_j=ab_j} (lambda0_j Gamma0_j)^(p_j)

sum_i 1{ab_i=ab_j} (lambda_i Gamma_i)^(p_i) f_ij ]^(1/p_j),

with p_j = ab_j/(ab_j-1) and ab_j the minimum tail coefficient among the streams feeding j: the heaviest tail upstream dominates. Both are solved exactly rather than iteratively. The rate equations are the usual traffic equations, and in the variables z_j = (lambda_j Gamma_j)^(p_j) the variability equations are linear as well, so each is one linear system; ab is obtained by propagating the minimum to a fixed point.

ARITHMETIC. Real exponents make this transcendental.

Reference: C. Bandi, D. Bertsimas, N. Youssef (2015). Robust Queueing Theory. Operations Research 63(3), 676-700, Theorems 4-7 and 10.

Definition in file npfqn_traffic_rqt.h.

Classes

Namespaces

Functions

Detailed Description