qsys_gig1_bnds_extremal.h File Reference

Extremal two-moment bounds for the GI/GI/1 queue. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/qsys/qsys_types.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for qsys_gig1_bnds_extremal.h:

Go to the source code of this file.

Classes
struct	line::qsys::Gig1ExtremalResult< T >
	The bounds, all as TIMES IN QUEUE: add 1/mu for a response time. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
Gig1ExtremalResult< T >	line::qsys::qsys_gig1_bnds_extremal (const T &lambda, const T &mu, const T &ca, const T &cs, std::size_t K=4000, std::size_t N=2000, bool skipTight=false)
	Extremal two-moment bounds for the GI/GI/1 queue.

Detailed Description

Extremal two-moment bounds for the GI/GI/1 queue.

Templated port of matlab/src/api/qsys/qsys_gig1_bnds_extremal.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_gig1_bnds_extremal.java.

Two moments do not determine E[W]; they determine a SET of possible values, and the width of that set is the honest uncertainty in any two-moment approximation. The ends are attained by extremal laws:

lower D(1) interarrivals and a three-point service law on multiples of it, E[W] = rho((1+cs^2)rho - 1)^+ / (2(1-rho)) (2.12) upper two-point laws: an interarrival atom at 0, and a service law whose upper atom runs to infinity as its probability vanishes (3.2)

Making an interarrival time larger only empties the queue once, but making a service time larger delays every customer behind it, which is why the two ends look so different. The upper end reduces to a D(1/p)/RS(D(rho),p)/1 model with p = 1/(1+ca^2), whose mean wait is evaluated by Spitzer's identity sum_n E[Sn^+]/n with Sn = rho(NB(n,1-p)+n) - n/p (Algorithm 1). The closed form (3.4) uses the D/M/1 root delta = exp(-(1-delta)/rho) and is within about 1% of it.

ARITHMETIC. The tight bound is a truncated infinite sum and delta comes out of a bisection, so nothing here is exact; the instantiation is restricted to the transcendental types.

PARITY. All four codebases form the negative binomial pmf in LOG space, log P(NB(n,1-p)=k) = lgamma(n+k) - lgamma(k+1) - lgamma(n)

• n log p + k log(1-p), from one precomputed table of log-gammas, rather than by the ratio recursion Algorithm 1 prints. The two are equivalent, but the recursion accumulates rounding over thousands of multiplications and would leave the ports agreeing only to about 1e-4.

Reference: Y. Chen, W. Whitt (2020). Algorithms for the upper bound mean waiting time in the GI/GI/1 queue. Queueing Systems 94, 327-356.

Definition in file qsys_gig1_bnds_extremal.h.