The BMAP/PH/N/N bufferless retrial queue with flexible retrial admission control. More...

#include <cmath>
#include <cstddef>
#include <vector>
#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_bmapphnn_retrial.h:

Classes
struct	line::qsys::BmapPhNnRetrialOptions
	Options of qsys_bmapphnn_retrial. More...
struct	line::qsys::BmapPhNnRetrialResult< T >
	Result of qsys_bmapphnn_retrial. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
BmapPhNnRetrialResult< T >	line::qsys::qsys_bmapphnn_retrial (const std::vector< Matrix< T > > &D, const std::vector< T > &beta, const Matrix< T > &S, int N, const T &alpha, const T &gamma, const T &p, const std::vector< long > &R, const BmapPhNnRetrialOptions &opt)
	The BMAP/PH/N/N bufferless retrial queue.
template<class T>
BmapPhNnRetrialResult< T >	line::qsys::qsys_bmapphnn_retrial (const std::vector< Matrix< T > > &D, const std::vector< T > &beta, const Matrix< T > &S, int N, const T &alpha, const T &gamma, const T &p, long R)
	qsys_bmapphnn_retrial with the reference's automatic truncation level.

Detailed Description

The BMAP/PH/N/N bufferless retrial queue with flexible retrial admission control.

Templated port of matlab/src/api/qsys/qsys_bmapphnn_retrial.m, which implements Dudin et al., "Analysis of BMAP/PH/N-Type Queueing System with Flexible Retrials Admission Control", Mathematics 2025, 13(9), 1434.

THE MODEL. N servers and no waiting room. Arrivals come in batches from a BMAP (D0, D1, ..., DK) on V states; a batch that finds fewer than its size free servers fills what it can and the excess either joins the orbit, with probability 1 - p, or is lost, with probability p. Service is PH (beta, S) on M phases, so the server-side state with n busy servers is the multiset of their phases, of which there are T_n = C(n+M-1, M-1); the level of the generator is the orbit population and each level carries V * sum_n T_n states. Each orbiting customer retries at rate alpha and abandons at rate gamma, and a retrial SUCCEEDS only while n <= R(nu), which is the admission control: above the threshold the retrial finds the system closed and the customer stays in orbit.

THE STATE SPACE IS A LEVEL-DEPENDENT QBD and the reference does not solve it as one: it truncates the orbit at a finite level, assembles the whole generator densely, and solves pi Q = 0 with the last column replaced by the normalization. This port does the same, so that the two agree, including on the truncation. See the two reference defects below, which are both about that truncation.

WHAT THE PORT CHANGES, AND WHY IT DOES NOT CHANGE THE ANSWER. The reference rebuilds B, B_bar, Gamma and B_tilde inside buildGeneratorLevel, i.e. once per (i, j) block pair, although none of them depends on i or j; on the default truncation that is over a hundred rebuilds of the same matrices. They are hoisted here. The generator entries are identical.

REFERENCE DEFECTS in qsys_bmapphnn_retrial.m:

AN UNSTABLE MODEL RETURNS A FINITE, PLAUSIBLE-LOOKING ANSWER. The truncated chain is always positive recurrent, and line 202 renormalizes it (pi = pi / sum(pi)), so divergence appears as a number rather than as an error. MATLAB reproduction, from matlab/: for L = [100 200 400 800 1600] r = qsys_bmapphnn_retrial({-2,2}, 1, -1, 3, 0.5, 0, 0, 0, 'MaxLevel', L); fprintf('d g g
', L, r.L_orbit, sum(r.pi(end,:))); end gives L_orbit 94.5, 194.0, 393.7, 793.6, 1593.5 – growing linearly with the truncation level – while the mass sitting at the TOP level stays at about 0.18 instead of decaying, and the reported throughput drifts from 1.8607 to 1.8741. With R = 0 a retrial succeeds only when the system is completely empty, so the orbit is not stable even though the offered load rho = 2/3 is well below one. Nothing warns.
THE DEFAULT TRUNCATION LEVEL IGNORES EVERY ORBIT PARAMETER. Line 127 sets truncLevel = max(100, ceil(50/(1 - min(rho, 0.99)))) with rho = lambda b1 / N, so it depends on neither alpha nor gamma nor the blocking probability, which are exactly what govern the decay of the orbit tail. MATLAB reproduction: with alpha = 0.02 the default level is 150, and L_orbit converges to 57.73566168 (reached by MaxLevel 400), while MaxLevel 100 gives 57.5935191, an error of 0.25 per cent with no indication that anything was truncated.

Neither is worked around here. The port returns truncLevel and, as the diagnostic the reference lacks, topLevelMass: the probability mass at the highest retained level. A caller can test it (it should be negligible, of the order of 1e-16 on a converged instance) and raise maxLevel when it is not. The default level and the returned means are the reference's, unchanged.
THE DOCUMENTED MEANING OF R DOES NOT MATCH THE CODE. The header of the .m file says "When n > R(nu), arriving customers go to orbit", but R enters the generator only through computeGamma and computeBbar, both of which act on RETRIALS from the orbit. A fresh arrival always takes a free server if there is one, whatever R is. The code is consistent with the paper's "flexible retrials admission control"; the docstring is not.
computeC's first branch builds a (T_n x 1) zero column, a shape that cannot be a valid block, and the caller silently discards it through a size test (size(C_nk, 2) == T(N+1)). It also assigns the same zero matrix twice under an if that cannot change it. Harmless, and the port simply does not create the malformed shape.

ARITHMETIC. Nothing here needs a transcendental function: the generator is a rational expression in the inputs and the solution is one linear solve, so the header is instantiable at T = Rational and the exact instantiation returns the stationary law of the TRUNCATED chain exactly. That is worth having for a small truncation, where it makes the generator itself checkable, and impractical for the default one, where the dense solve is hundreds of dimensions wide.

Definition in file qsys_bmapphnn_retrial.h.

Classes

Namespaces

Functions

Detailed Description