pfqn_scb.h File Reference

Dowdy-Carlson-Krantz-Tripathi (1992) single-class bounds of multi-class queueing networks, J. More...

#include <algorithm>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for pfqn_scb.h:

Go to the source code of this file.

Classes
struct	line::pfqn::ScbBounds< T >
	Return value of pfqn_scb, mirroring [Xlo, Xhi, Ulo, Uhi]. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
ScbBounds< T >	line::pfqn::pfqn_scb (const std::vector< T > &L, long N)
	Bracket on the throughput and the per-device utilizations of the UNKNOWN multiclass system whose single-class counterpart has demands L at population N.
template<class T>
T	line::pfqn::pfqn_scbgap (long N, long K, long r, bool undominated)
	Demand-free bound on the relative throughput error incurred when r of the N single-customer classes are merged into one class.
template<class T>
T	line::pfqn::pfqn_scbgap (long N, long K)
	Full single-class aggregation: r = N, dominating classes allowed.
template<class T>
T	line::pfqn::pfqn_usumbound (long R, long K, long N)
	Largest value the sum of device utilizations can take in any closed product-form network with R classes, K devices and N customers (Theorem 6): sum_k U_k,R <= (H-1) + (K-H+1)(N-H+1)/(K+N-2H+1), H = min(R,K).
template<class T>
long	line::pfqn::pfqn_minclasses (const T &Usum, long K, long N)
	Smallest number of customer classes R consistent with an observed sum of device utilizations, by inverting the nondecreasing pfqn_usumbound.

Detailed Description

Dowdy-Carlson-Krantz-Tripathi (1992) single-class bounds of multi-class queueing networks, J.

ACM 39(1):188-213.

Templated port of matlab/src/api/pfqn/pfqn_scb.m, pfqn_scbgap.m, pfqn_usumbound.m and pfqn_minclasses.m.

SEMANTICS DIFFER FROM EVERY OTHER pfqn_* BOUND IN THIS TREE. aba/bjb/gb/... bracket the exact solution OF THE GIVEN MODEL; pfqn_scb brackets the multiclass system that the given single-class model aggregates. Its lower side is therefore the EXACT single-class solution, not an approximation of it, and mixing the family into an auto composite would compare two different quantities.

ARITHMETIC. pfqn_scb runs the exact single-class MVA recursion (additions, multiplications and one division per population step) and then scales by a rational factor, so it stays in the field and is left ungated. The three combinatorial bounds are pure rational expressions in N, K and r.

Definition in file pfqn_scb.h.