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"

Include dependency graph for qsys_mapmc.h:

Classes
struct	line::qsys::MapMcResult< T >
	Return value of qsys_mapmc and qsys_mapm1, mirroring the MATLAB struct. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
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 500 materialized levels, the reference's maxNumComp default.

Detailed Description

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. Since 2026-10-18 MATLAB, the JAR and Python do the same: Q_CT_MAP_M_C returns the closed-form L and Lq, and the four codebases agree to about 1e-13 (e.g. 3.12185040294165 / 1.67587177394999 on the correlated MMPP2 instance, mu = 1, c = 2).

THE REFERENCE USED TO BE THE INACCURATE ONE. It summed ql truncated at maxNumComp = 500 levels and took meanWaitingTime from the waiting-time PH, whose Sylvester fixed point stops at a 1e-10 step while converging at a rate near sp(R). At moderate load that cost 1e-9 (M/M/2: 1.874999996296936 / 0.5624999998489539 against Erlang-C 1.875 / 0.5625); at high load with slowly modulated arrivals it cost 8% (a 3-phase KPC fit at rho = 0.8 gave Wq 663.96 against 723.766), and the JAR's 1000-iteration cap on that fixed point made it worse.

That the closed form 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.

Classes

Namespaces

Functions

Detailed Description