Tail bounds for a GI/Hn/1 -> . More...

#include <cstddef>
#include <functional>
#include <limits>
#include <string>
#include <vector>
#include "line/api/qsys/qsys_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/rootfind.h"

Include dependency graph for qsys_tandem_ub_ciucu.h:

Classes
struct	line::qsys::TandemUbResult< T >
	Mirrors the struct MATLAB returns from qsys_tandem_ub_ciucu. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
TandemUbResult< T >	line::qsys::qsys_tandem_ub_ciucu (const std::vector< T > &x, const std::function< T(const T &)> &lst, const std::vector< T > &p, const std::vector< T > &mu, const std::function< T(const T &)> &dlst=std::function< T(const T &)>())
	Tail bounds for a GI/Hn/1 -> .

Detailed Description

Tail bounds for a GI/Hn/1 -> .

/Hn/1 tandem of two FCFS single servers.

Templated port of matlab/src/api/qsys/qsys_tandem_ub_ciucu.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_tandem_ub_ciucu.java. Both stations serve the same hyperexponential law Y, Z ~ sum_i p_i Exp(mu_i), a single phase giving exponential service, and the arrivals are renewal with a light-tailed interarrival time supplied through its Laplace-Stieltjes transform E[e^{-s X}].

With theta the positive root of E[e^{theta (Y-X)}] = 1 and alpha = E[X e^{-theta X}], the test function

gamma(u,v) = 1{0<=u<=v} [1 - A e^{-theta u} - (B + C u + D v) e^{-theta v}]

satisfies the integral inequality of Theorem 1(b) of the reference once the five sufficient conditions of its Lemma 4 fix

A = 1, C = theta sum_i p_i/(mu_i-theta) / sum_i p_i mu_i/(mu_i-theta)^2, D = (-C E[U e^{theta V}]/E[V e^{theta V}]) v 0, U = Y-X, V = Z-X, B = C (1/mu_1 - alpha E[e^{theta Z}]) if D = 0, = (C+D)/(mu_1-theta) - theta/mu_1 if D > 0,

with mu_1 the smallest service rate. Corollary 2 then turns gamma into

P(S > x) <= sum_i p_i { e^{-mu_i x}

mu_i/(mu_i-theta) (A+B) (e^{-theta x} - e^{-mu_i x})
mu_i/(mu_i-theta)^2 (C+D) (((mu_i-theta)x-1) e^{-theta x}
- e^{-mu_i x}) }

and the corresponding closed form for W when the service is exponential. E[V e^{theta V}] is positive at any stable load, so D is always well defined: h(s) = E[e^{s(Z-X)}] is convex with h(0) = h(theta) = 1, hence h'(theta) > 0.

The two exponentials mix a polynomial of degree one in x, which is what lets the bound follow the concave bend of the tail on a linear-log scale where a purely exponential bound cannot. In the M/M/1 -> ./M/1 case the five inequalities hold as equalities, so gamma is the exact joint distribution and both bounds are exact, P(S > x) = (1 + theta x) e^{-theta x}. Away from it the bound stays sharp: against an exact CTMC reference for the Erlang(2)/M/1 -> ./M/1 tandem it is within 2% at P(S>x) = 1e-2 and within 0.6% at 5e-10, with the correct asymptotic slope theta^2/(mu(1-alpha mu)). Accuracy degrades with service variability, to about a factor of two at CV(Y) = 2.

Reference: F. Ciucu, S. Mehri, "On the Distribution of Sojourn Times in Tandem Queues", Proc. ACM Meas. Anal. Comput. Syst. 9(2), Article 27, 2025 (ACM SIGMETRICS 2025). Registered in .citations() as 'tandemub'.

ARITHMETIC: transcendental. theta is a root of a transcendental equation and the bound is a mix of exponentials, so this instantiates only at backends carrying exp; the bracketing solve itself is field arithmetic and deterministic, so the digits do not depend on a starting point.

Definition in file qsys_tandem_ub_ciucu.h.

Classes

Namespaces

Functions

Detailed Description