The MAP/G/1 FCFS queue, by moment-matching the general service time to a phase-type distribution. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/mam/aph_fit.h"
#include "line/api/mam/map_moment.h"
#include "line/api/qsys/qsys_mapmap1.h"
#include "line/api/qsys/qsys_mapph1.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mapg1.h:

Classes
struct	line::qsys::MapG1Result< T >
	Result of qsys_mapg1. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::qsys

Enumerations
enum class	line::qsys::MapG1ServiceFit { line::qsys::Exponential , line::qsys::Erlang , line::qsys::Hyperexponential , line::qsys::Acyclic }
	Which branch of fitServiceToPH was taken, for the caller and for tests. More...

Functions
template<class T>
mam::Map< T >	line::qsys::qsys_mapg1_service_fit (const std::vector< T > &moments, MapG1ServiceFit &kind)
	Fit a general service time to a PH, following qsys_mapg1.m's fitServiceToPH.
template<class T>
MapG1Result< T >	line::qsys::qsys_mapg1 (const mam::Map< T > &arrival, const std::vector< T > &moments, std::size_t dist_size, std::size_t numQLMoms, std::size_t numSTMoms)
	The MAP/G/1 FCFS queue.
template<class T>
MapG1Result< T >	line::qsys::qsys_mapg1 (const mam::Map< T > &arrival, const std::vector< T > &moments, std::size_t dist_size)
	qsys_mapg1 with the reference's defaults numQLMoms = 3, numSTMoms = 3.
template<class T>
MapG1Result< T >	line::qsys::qsys_mapg1 (const mam::Map< T > &arrival, const std::vector< T > &moments)
	qsys_mapg1 with the reference's default of 100 materialized levels.

Detailed Description

The MAP/G/1 FCFS queue, by moment-matching the general service time to a phase-type distribution.

Templated port of matlab/src/api/qsys/qsys_mapg1.m. The reference has two parts: a service fit, written in the .m file itself, and the queue solution, delegated to BUTools' MMAPPH1FCFS. This port transcribes the first and replaces the second with the port's own QBD route, exactly as qsys_mapph1.h already does – MAP/PH/1 is a MAP/MAP/1 queue with a renewal service process, and qsys_mapph1 reproduces MMAPPH1FCFS to 1e-15 on that family (see the measured agreement table in qsys_mapph1.h).

THE SERVICE FIT, branch by branch, is the reference's own fitServiceToPH:

3 or more moments : an acyclic PH matching (m1, m2, m3) exactly 2 moments : cv2 = m2/m1^2 - 1, and then cv2 <= 0 -> Erlang-k, k = max(1, round(1/max(cv2, 0.01))) cv2 < 1 -> Erlang-k, k = max(2, round(1/cv2)) cv2 == 1 -> exponential cv2 > 1 -> balanced-means 2-phase hyperexponential, p = (1 + sqrt((cv2-1)/(cv2+1)))/2, rates 2p/m1 and 2(1-p)/m1 1 moment : exponential

The Erlang branches match m1 exactly and m2 only through the rounded k, and the hyperexponential branch matches both m1 and cv2 exactly (its cv2 is 1/(2p(1-p)) - 1, which is the requested one for that p). Both are the reference's approximations, reproduced rather than improved.

THE 3-MOMENT BRANCH IS THE ONE SUBSTITUTION. The reference calls BUTools' APHFrom3Moments, which this port does not transcribe (the same position qsys_mapph1.h takes on MMAPPH1FCFS). It uses line::mam::aph_fit instead, the m3a implementation of the same Bobbio-Horvath-Telek canonical APH. MEASURED: on (m1, m2, m3) = (1/3, 1/6, 1/9), the moments of Erlang(2) with mean 1/3, the two agree on the order (3), on the sub-generator ([-12 12 0; 0 -12 12; 0 0 -5]) and on the entry vector ([0.8 0 0.2]) to 1e-14, so the queue results agree as well. They are not guaranteed to pick the same representation everywhere – the order search and the branch conditions are written differently – and where they differ the queue results will differ too, because a queue depends on the whole service distribution and not on its first three moments. A caller who needs the reference's exact PH can pass it to qsys_mapph1 directly. The reference's fallback chain is reproduced: when the APH fit throws, BUTools' PH2From3Moments (transcribed below, with its feasibility bounds) is tried, and when that throws too the service is an exponential of mean m1.

MOMENTS. MMAPPH1FCFS also returns higher queue-length and sojourn-time moments (ncMoms, stMoms). qsys_mapmap1 now provides both – the queue-length moments in closed form from pi_0 and R, the sojourn-time moments from the phase-type sojourn law of the age process – and they are passed through here as queueLengthMoments and sojournTimeMoments under the reference's numQLMoms / numSTMoms options (default 3 each).

REFERENCE DEFECTS in qsys_mapg1.m:

THE cv2 <= 0 BRANCH SILENTLY BUILDS AN ERLANG-100. Line 128 computes k = max(1, round(1/max(cv2, 0.01))), and for any cv2 <= 0 the max pins the denominator at 0.01, so k = 100 whatever the moments were. Nothing warns. Deterministic service therefore enters the QBD with a 100-phase service process (cv2 = 0.01, not 0), which is both expensive and a silent modelling decision. MATLAB reproduction, from matlab/: r = qsys_mapg1(-2, 2, [1/3, (1/3)^2]) % cv2 = 0 exactly r.meanQueueLength -> 1.33999999999909 against the exact M/D/1 value 4/3 + ... (the Erlang-100 answer is 1.3399999999 rather than the M/D/1 1.3333...). Reproduced here, since it is the reference's model choice, and pinned by a test that asserts the phase count is 100.
m2 and m3 are read without any feasibility check: a moment set that is not PH-representable reaches the fit and fails there.
The reference computes rho from the INPUT mean 1/serviceMoments(1) and not from the fitted PH, so a branch whose fit does not preserve m1 would report a utilization inconsistent with its own service process. Every branch does preserve m1, so this is latent rather than active; the port reproduces the reference's formula.

ARITHMETIC. Gated on num_traits<T>::has_transcendental, inherited from qsys_mapmap1 (the cyclic reduction behind R) and from aph_fit.

Definition in file qsys_mapg1.h.

Classes

Namespaces

Enumerations

Functions

Detailed Description