qsys_mapdc.h File Reference

The MAP/D/c FCFS queue: c servers, deterministic service of length s, fed by a Markovian arrival process. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mam/qbd_r.h"
#include "line/api/qsys/qsys_mapd1.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/expm.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mapdc.h:

Go to the source code of this file.

Classes
struct	line::qsys::MapDcResult< T >
	Return value of qsys_mapdc, mirroring the MATLAB result struct. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
MapDcResult< T >	line::qsys::qsys_mapdc (const mam::Map< T > &arrival, const T &s, unsigned c, std::size_t dist_size, unsigned max_arrivals, std::size_t max_levels, const T &tol)
	MAP/D/c by Crommelin's exact embedded lattice chain.
template<class T>
MapDcResult< T >	line::qsys::qsys_mapdc (const mam::Map< T > &arrival, const T &s, unsigned c)
	qsys_mapdc with 100 materialized levels, an arrival-count cap of 4096, a super-level cap of 20000 and tolerance 1e-14, matching the qsys_mapd1 defaults.

Detailed Description

The MAP/D/c FCFS queue: c servers, deterministic service of length s, fed by a Markovian arrival process.

The multiserver generalization of qsys_mapd1.

ALGORITHM, AND HOW IT DIFFERS FROM THE MATLAB REFERENCE. matlab/src/api/qsys/qsys_mapdc.m calls Q-MAM's Q_CT_MAP_D_C, which is not transcribed here. This port computes the same quantities by Crommelin's embedded lattice chain, which is exact for deterministic service and is NOT an Erlang-k or a heavy-traffic approximation.

THE LATTICE CHAIN IS EXACT, AND WHY. Sample the system at the epochs t_n = n s and let N_n be the number in system at t_n, J_n the arrival phase. Every job in service at t_n started somewhere in (t_n - s, t_n], so it departs inside (t_n, t_{n+1}]; every job that starts service inside that interval departs after t_{n+1}. Hence exactly min(N_n, c) departures occur per interval – all of them when the system is below capacity, since then no job waits – and

N_{n+1} = max(N_n - c, 0) + A_n,

with A_n the number of MAP arrivals in the interval. (N_n, J_n) is therefore a Markov chain with transition blocks A_k = P_k(s), the MAP counting probabilities over an interval of exact length s. No residual service time has to be carried, which is what makes the deterministic case tractable where a general one would not be.

The stationary law of that chain IS the time-stationary law of N. N(t) converges in distribution as t -> infinity (the system is non-lattice: the MAP has continuous interarrival times), so N(n s) converges to the same limit, and a positive recurrent Markov chain converges only to its own stationary law. No PASTA argument and no time-averaging step are involved – unlike qsys_mapd1, whose chain is embedded at DEPARTURE epochs and therefore needs the explicit inter-departure averaging of its step 4.

FOUR STEPS.

1. A_k = P_k(s), k = 0..K, as the top block row of exp(M s) with M block bidiagonal carrying D0 on the diagonal and D1 above it. Shared with qsys_mapd1 (line::qsys::detail::map_counting_at). K grows from a Poisson tail estimate until the missing mass max_i (1 - sum_k (A_k e)_i) is under the tolerance, so the truncation is a measured quantity.
2. Grouping. The chain is skip-free to the left by c, not by 1, so c consecutive levels are grouped into one super-level: level n = L c + u becomes super-level L, sub-level u. Skip-freeness by one super-level then holds and the blocks are c m x c m with m the MAP order: repeating A^(i)[(u,v)] = A_{i c + v - u}, for i c + v - u >= 0 boundary B^(i)[(u,v)] = A_{i c + v}, independent of u, the boundary row being the levels 0..c-1, from which max(n-c,0) = 0.
3. Ramaswami's recursion, exactly as in qsys_mapd1: G the minimal solution of G = sum_i A^(i) G^i, the partial sums Ahat_i = sum_{k>=i} A^(k) G^(k-i) and Bhat_i likewise, then x_0 (B^(0) + Bhat_1 (I - Ahat_1)^-1 A^(0)) = x_0, x_L = [x_0 Bhat_L + sum_{k=1}^{L-1} x_k Ahat_{L-k+1}] (I - Ahat_1)^-1.
4. Unfolding. Super-level L, sub-level u, phase j is the level L c + u, so P(N = n) is read off directly and E[N] = sum_n n P(N = n).

meanWaitingTime is E[N]/lambda - s by Little's law and meanSojournTime is E[N]/lambda. This is exactly the definition the MATLAB reference adopted when its one-point quadrature was replaced; see the reference-defect note below.

INVARIANTS THE TESTS ASSERT (both are identities of the construction, not fitted quantities):

• sum_n P(N = n) = 1 up to the level-tail truncation;
• sum_n min(n, c) P(N = n) = lambda s. Taking expectations in the recursion gives E[min(N,c)] = E[A] = lambda s, i.e. the mean number of departures per interval equals the mean number of arrivals. Equivalently the utilization is rho = lambda s / c, which is what the result reports.

ORACLES.

• c = 1 collapses to MAP/D/1 and is cross-checked against qsys_mapd1, which reaches the same numbers by the departure-epoch chain, a genuinely different construction.
• Poisson arrivals and c = 1 collapse to M/D/1, where Pollaczek-Khinchin gives L = rho + rho^2/(2(1-rho)) and Wq = rho s/(2(1-rho)) exactly.
• Poisson arrivals and c > 1 are checked against the MATLAB reference and against the M/D/c heavy-traffic ordering Wq(M/D/c) < Wq(M/M/c).

ARITHMETIC. Gated on num_traits<T>::has_transcendental for two independent reasons, both inherited from qsys_mapd1: step 1 calls expm, which is a tolerance-controlled Pade approximation and cannot be exact in any arithmetic, and step 3 obtains G by a fixed-point iteration that does not terminate in a finite number of field operations. Steps 2 and 4 are finite exact matrix algebra and add no error of their own.

REFERENCE DEFECTS.

• FIXED IN MATLAB, and this port matches the fixed behaviour. qsys_mapdc.m used to return meanWaitingTime as a one-point left-rectangle quadrature of the Q-MAM waiting-time survival function (numSteps defaulting to 1). On the M/D/1 instance D0 = [-2], D1 = [2], s = 1/3 it returned 0.4444444443 against the exact Pollaczek-Khinchin value 1/3, an error of +33%. It now uses Little's law, meanQueueLength/lambda - s. This port reproduces the FIXED behaviour and is asserted against 1/3, never against the superseded number.
• STILL OPEN. qsys_mapdc.m computes the utilization as rho = lambda s / c and returns the Q-MAM queue-length vector unchanged, so meanQueueLength is the mean number in SYSTEM; the Little's law line is consistent with that reading. No defect is claimed here, but note that the field is documented as "Mean number of customers in system" while the inline comment on the Q-MAM output says "ql(i) = Prob[(i-1) customers in the queue]". The two readings differ by rho c, and only the system reading makes meanWaitingTime non-negative at high load, so the system reading is the one implemented on both sides.

Definition in file qsys_mapdc.h.