The MAP/G/1/K queue with tail drop: Markovian arrivals, an arbitrary service law F, and a buffer of K packets counting the one in transmission. More...

#include <cmath>
#include <cstddef>
#include <functional>
#include <limits>
#include <string>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mc/dtmc_solve.h"
#include "line/api/qsys/qsys_quadrature.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mapg1k.h:

Classes
struct	line::qsys::ServiceLaw< T >
	Service-time descriptor, the C++ form of the MATLAB svc struct. More...
struct	line::qsys::MapG1kResult< T >
	Return value of qsys_mapg1k, mirroring the MATLAB result struct. More...

Namespaces
namespace	line
namespace	line::qsys

Enumerations
enum class	line::qsys::ServiceKind { line::qsys::Gamma , line::qsys::Deterministic , line::qsys::PhaseType , line::qsys::Density }
	Which family the service law belongs to. More...

Functions
template<class T>
MapG1kResult< T >	line::qsys::qsys_mapg1k (const mam::Map< T > &arrival, const ServiceLaw< T > &svc, std::size_t K, const T &tol, std::size_t nmaxCap)
	MAP/G/1/K with tail drop.
template<class T>
MapG1kResult< T >	line::qsys::qsys_mapg1k (const mam::Map< T > &arrival, const ServiceLaw< T > &svc, std::size_t K)
	qsys_mapg1k with the reference defaults tol = 1e-12, nmax = 200000.

Detailed Description

The MAP/G/1/K queue with tail drop: Markovian arrivals, an arbitrary service law F, and a buffer of K packets counting the one in transmission.

Port of matlab/src/api/qsys/qsys_mapg1k.m, which is self-contained (it calls no Q-MAM and no BUTools), so this is a faithful transcription rather than a reconstruction. The service law is NOT fitted to a phase-type distribution: F enters exactly through the functionals A_m and Q_m, evaluated by uniformizing the arrival MAP at theta = max_i (-D0(i,i)).

METHOD. The chain embedded at departure epochs has state (n, j) with n = 0..K-1 the packets left behind and j the MAP phase. With A_m the matrix of "m arrivals during one service, phase i -> phase j", n >= 1: n' = n - 1 + min(m, K - n), the overflow being sum_{m >= K-n} A_m n == 0: the phase first jumps through Psi = (-D0)^-1 D1, because the idle period ends at an arrival, and the service then proceeds as from 1. Its stationary law sigma gives, by Markov renewal reward over one inter-departure cycle, E[cycle] = S + sigma_0 (-D0)^-1 e, T = 1/E[cycle], p0 = 1 - T S, and the level-holding times come from Q_m, the expected time within a service during which exactly m arrivals have occurred. No PASTA argument is used anywhere: the MAP phase resolution does that work instead, which is what lets qsys_mmapg1k read exact PER-CLASS loss ratios off pKvec.

WHERE THE PORT DIFFERS FROM THE REFERENCE, AND WHY.

The uniformization coefficients c_n = E[e^{-theta S}(theta S)^n/n!] are built by RECURSION rather than from log-gamma. For the gamma law they are the negative binomial pmf, c_0 = (1+theta th)^-al and c_n = c_{n-1} p (al+n-1)/n with p = theta th/(1+theta th); for the deterministic law they are the Poisson pmf, c_0 = e^{-theta d} and c_n = c_{n-1} theta d/n; for a PH law c_n = theta^n alpha M^{n+1} t with M = (theta I - T)^-1, accumulated as a running row vector. The reference evaluates each term independently through gammaln, which is the same number to rounding but costs a special function the port would otherwise not need at Real50. The recursions are also monotone in n and cannot lose the leading digits to cancellation.
The reference WARNS and continues when the c_n series is truncated with a residual above 1e-6; the port throws. A residual that large means the uniformization has not converged and every downstream quantity is wrong by an unknown amount, and a warning nobody reads is the worse failure mode. The residual is reported in the result either way.
The density path integrates over an EXPANDING finite window in u = log x rather than over (-Inf, log tmax] in one call, because the port's adaptive Gauss-Kronrod rule takes finite endpoints. The window is widened geometrically until a whole new panel contributes less than the tolerance, so the truncation is measured rather than assumed. The substitution itself is the reference's: it turns an integrable singularity x^(al-1) at the origin into e^(al u), which decays smoothly, so the singularity disappears instead of being resolved.

ARITHMETIC. Gated on num_traits<T>::has_transcendental: c_0 needs exp or a non-integer power for every service law, and the series truncation is a tolerance. Everything after the c_n – the A_m and Q_m sums, the embedded chain, its stationary vector and the reward averaging – is finite exact matrix algebra and adds no error of its own.

MEASURED AGREEMENT: see cpp/tests/test_qsys_mapg1k.cpp. The M/M/1/K collapse is checked against the closed form (1-rho)rho^K/(1-rho^(K+1)), the M/G/1/K and MAP/G/1/K instances against MATLAB, and three identities are asserted on every instance: sum_l plevel(l) = 1, p0 = 1 - T S, and lossProbability = 1 - T/lambda = pK-weighted arrival loss.

References: [1] Chydzinski, A. Per-Flow Throughput of a FIFO Buffer. Applied System Innovation 2026, 9, 112. [2] Niu, Z.; Cooper, R.B. Transform-Free Analysis of M/G/1/K and Related Queues. Mathematics of Operations Research 1993, 18, 486-510.

Definition in file qsys_mapg1k.h.

Classes

Namespaces

Enumerations

Functions

Detailed Description