The MAP/MAP/1 FCFS queue: mean number in system, waiting time, sojourn time, utilization and the queue-length distribution. More...

#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/api/mam/mmapph1fcfs.h"
#include "line/api/mam/qbd_mapmap1.h"
#include "line/api/mam/qbd_r.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mapmap1.h:

Classes
struct	line::qsys::MapMap1Result< T >
	Return value of the MAP/MAP/1 family (qsys_mapmap1, qsys_mapph1, qsys_phph1), carrying the same quantities as the MATLAB result struct. More...

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

Functions
template<class T>
MapMap1Result< T >	line::qsys::qsys_mapmap1 (const mam::Map< T > &arrival, const mam::Map< T > &service, std::size_t dist_size, std::size_t numQLMoms, std::size_t numSTMoms)
	MAP/MAP/1 as the reference solves it: the service MAP collapsed to its PH marginal (mapToPh), then the MAP/PH/1 queue by the exact QBD solution.
template<class T>
MapMap1Result< T >	line::qsys::qsys_mapmap1 (const mam::Map< T > &arrival, const mam::Map< T > &service, std::size_t dist_size)
	qsys_mapmap1 with the reference's defaults numQLMoms = 3, numSTMoms = 3.
template<class T>
MapMap1Result< T >	line::qsys::qsys_mapmap1 (const mam::Map< T > &arrival, const mam::Map< T > &service)
	qsys_mapmap1 with 100 materialized levels, the reference's numQLProbs.

Detailed Description

The MAP/MAP/1 FCFS queue: mean number in system, waiting time, sojourn time, utilization and the queue-length distribution.

ALGORITHM, AND HOW IT DIFFERS FROM THE MATLAB REFERENCE. matlab/src/api/qsys/qsys_mapmap1.m obtains these quantities by calling BUTools' MMAPPH1FCFS, which is not transcribed here; this port computes the SAME quantities from the port's own quasi-birth-death machinery (line/api/mam/qbd_mapmap1.h), which solves the level-independent QBD whose level is the number in system and whose phase is the pair (arrival phase, service phase). The algorithm is therefore different, the quantity is the same.

THE SERVICE MAP IS COLLAPSED TO A PHASE-TYPE LAW, as the reference does. Before calling BUTools, qsys_mapmap1.m replaces the service MAP (D0,D1) by sigma = theta D1 / (theta D1 e), S = D0, theta (D0+D1) = 0, i.e. by the stationary marginal of a service time (its mapToPh). That embedded PH keeps the service-time MARGINAL exactly but DISCARDS the serial correlation between consecutive service times, so the reference solves a MAP/PH/1 queue in place of the MAP/MAP/1 queue it names. This port follows the reference: the service MAP is collapsed the same way and the resulting MAP/PH/1 queue is solved as a QBD, so the two agree also on a correlated service MAP (case 3 below). A caller who wants the genuine MAP/MAP/1 answer, with the service correlation honoured, has it in line::mam::qbd_mapmap1 (line/api/mam/qbd_mapmap1.h).

The higher moments the reference obtains from MMAPPH1FCFS are returned too: queueLengthMoments (numQLMoms raw moments of the number in system, from pi_0 and R in closed form, qbd_qlen_moment) and sojournTimeMoments (numSTMoms raw moments, from the phase-type sojourn-time law of mmapph1fcfs_stdistr_ph, the same age-process construction BUTools uses).

MEASURED AGREEMENT (MATLAB R2025a, T = double). Metric order is meanQueueLength / meanWaitingTime / meanSojournTime / utilization. Arrival MAPs used below: P(2) = Poisson, D0 = [-2], D1 = [2] C = correlated MMPP2, D0 = [-2.5 0.2; 0.1 -0.7], D1 = diag(2.3, 0.6), lambda = 7/6

M/M/1 collapse, qsys_mapmap1(P(2), service D0 = [-3], D1 = [3]). MATLAB 1.999999999999999 / 0.6666666666666656 / 0.9999999999999989 / 0.6666666666666666; port 2 / 0.666666666666668 / 1 / 0.666666666666667, the textbook values. Relative differences 5e-16, 1.8e-15, 1.1e-15.
Renewal service, where the reference's PH reduction is exact. Arrival C, service the Erlang-2 renewal MAP D0 = [-6 6; 0 -6], D1 = [0 0; 6 0]. MATLAB 0.8364637529649164 / 0.3836355977794533 / 0.7169689311127866 / 0.3888888888888888; port 0.836463752964917 / 0.383635597779453 / 0.716968931112786 / 0.388888888888889. Relative differences below 1e-15 on every metric: with a renewal service the two model the same system and the port reproduces the reference to machine precision.
Correlated service, where the reference's PH reduction is NOT exact. Arrival C, service MAP D0 = [-5 0.4; 0.2 -1.4], D1 = diag(4.6, 1.2) (lambda_s = 7/3, so rho = 1/2). MATLAB qsys_mapmap1 reports 2.0305355320573 / 1.311887598906254 / 1.740459027477683 / 0.5. With the service collapsed to its PH marginal as the reference does, the port returns the same MAP/PH/1 answer. The genuine MAP/MAP/1 value, which LINE's own MATLAB qbd_mapmap1 gives as QN = 2.547554867631855, RN = 2.183618457970162, is 20% away: that gap is the service correlation the reference's PH reduction throws away, and it is available through line::mam::qbd_mapmap1. meanWaitingTime is meanSojournTime minus the mean service time 1/lambda_s, and utilization is lambda_a/lambda_s, both matching the reference's own definitions.

ARITHMETIC. The function is gated on num_traits<T>::has_transcendental because qbd_mapmap1 reaches R by cyclic reduction, a fixed-point iteration driven to a tolerance that does not terminate in a finite number of field operations; running it at exact rational arithmetic would produce a rational with a denominator doubling every step and still not the exact R. See qbd_r.h. Everything downstream of R here – the mean, the level probabilities, the Little's-law conversions – is finite exact matrix algebra and carries no additional error.

Definition in file qsys_mapmap1.h.

Classes

Namespaces

Functions

Detailed Description