LINE Solver (C++)
Templated C++ port of the LINE queueing solver
Loading...
Searching...
No Matches
qsys_mapdc.h File Reference
Algorithm layer » Single queueing systems (qsys)

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 <string>
#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
 Conservation laws of a layered queueing network, enumerated from its structure.
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, std::size_t num_steps)
 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, std::size_t dist_size, unsigned max_arrivals, std::size_t max_levels, const T &tol)
 qsys_mapdc with the reference's numSteps = 1.
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.

meanWaitingTime is Little's law, meanQueueLength/lambda - s, as in MATLAB; the test asserts the M/D/1 instance D0 = [-2], D1 = [2], s = 1/3 against the Pollaczek-Khinchin value 1/3. Do not return to a one-point quadrature of the Q-MAM waiting-time survival function, which gives 0.444 there (+33%).

meanQueueLength is the mean number in SYSTEM: qsys_mapdc.m computes rho = lambda s / c and returns the Q-MAM queue-length vector unchanged. The .m header documents the field 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 it is the one implemented on both sides.

Definition in file qsys_mapdc.h.