 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
The MAP/M/c FCFS queue: c identical exponential servers of rate mu fed by a Markovian arrival process. More...
#include <cstddef>#include <vector>#include "line/api/mam/map_moment.h"#include "line/api/mam/qbd_r.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"Go to the source code of this file.
Classes | |
| struct | line::qsys::MapMcResult< T > |
| Return value of qsys_mapmc and qsys_mapm1, mirroring the MATLAB struct. More... | |
Namespaces | |
| namespace | line |
| namespace | line::qsys |
Functions | |
| template<class T> | |
| MapMcResult< T > | line::qsys::qsys_mapmc (const mam::Map< T > &arrival, const T &mu, unsigned c, std::size_t dist_size) |
| MAP/M/c by the matrix-geometric solution. | |
| template<class T> | |
| MapMcResult< T > | line::qsys::qsys_mapmc (const mam::Map< T > &arrival, const T &mu, unsigned c) |
| qsys_mapmc with 100 materialized levels, the reference's maxNumComp scale. | |
The MAP/M/c FCFS queue: c identical exponential servers of rate mu fed by a Markovian arrival process.
ALGORITHM, AND HOW IT DIFFERS FROM THE MATLAB REFERENCE. matlab/src/api/qsys/qsys_mapmc.m obtains these quantities by calling Q-MAM's Q_CT_MAP_M_C, which is not transcribed here. This port computes the SAME quantities from the port's own quasi-birth-death machinery, by building the QBD directly: the level is the number in system and the phase is the arrival phase, so for levels n >= c the process is level independent with
A0 = D1 (an arrival), A1 = D0 - c mu I (local), A2 = c mu I (a completion),
while levels 0..c-1 form the boundary, where level k has downward rate k mu instead of c mu. R is the minimal non-negative solution of R^2 A2 + R A1 + A0 = 0, reached by cyclic reduction (qbd_fundmat called with B = A2, L = A1, F = A0), and pi_{c+k} = pi_c R^k. The boundary vectors pi_0..pi_c come from the level balance equations with the last one replaced by the normalization
sum_{n<c} pi_n e + pi_c (I - R)^-1 e = 1,
after which the number in system is
L = sum_{n<c} n pi_n e + pi_c ( c (I-R)^-1 + R (I-R)^-2 ) e
and the queued jobs are Lq = pi_c R (I-R)^-2 e. This is the same construction as qsys_phmc.h with the PH arrival replaced by a general MAP: a PH arrival is the special case D0 = T, D1 = (-T e) alpha. Utilization is lambda/(c mu), the reference's per-server convention.
meanWaitingTime is Lq/lambda by Little's law rather than the mean of the waiting-time PH representation that the reference extracts from Q-MAM; the two are the same quantity and the measurements below confirm they agree.
MEASURED AGREEMENT (MATLAB R2025a, T = double). Metric order is meanQueueLength / meanWaitingTime / meanSojournTime / utilization. Every relative difference below is limited by the REFERENCE, whose maxNumComp = 500 level truncation shows at the 1e-9 level; this port sums the geometric tail in closed form.
That the port and not the reference is the accurate one was checked without MATLAB: at c = 1 the same instance is also a MAP/MAP/1 queue with an exponential service MAP, and qsys_mapmap1 – a completely different route, cyclic reduction on the Kronecker-product QBD followed by the closed-form factorial moment – reproduces this function to 5e-16 on both the correlated and the Erlang-2 arrival instances. The test file carries that cross-check.
ARITHMETIC. Gated on num_traits<T>::has_transcendental: cyclic reduction drives R to a tolerance and never terminates in a finite number of field operations, exactly as in qbd_r.h and qsys_phmc.h. The boundary solve, the geometric-tail sums and the moment formulas that consume R are finite exact matrix algebra and add no error of their own.
Definition in file qsys_mapmc.h.
1.18.0