qbd_depproc.h File Reference

Departure process of a MAP/MAP/1 queue: the ETAQA-truncated MAP descriptor under FCFS and under PS, and the joint moments of consecutive inter-departure times. More...

#include <cstddef>
#include <utility>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/api/mam/qbd_mapmap1.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/matrix.h"

Include dependency graph for qbd_depproc.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mam

Functions
template<class T>
Map< T >	line::mam::qbd_depproc_etaqa (const Map< T > &arrival, const Map< T > &service, std::size_t n)
	MAP descriptor of the departure process of a MAP/MAP/1-FCFS queue, ETAQA-truncated at level n (qbd_depproc_etaqa.m).
template<class T>
Map< T >	line::mam::qbd_depproc_etaqa_ps (const Map< T > &arrival, const Map< T > &service, std::size_t n)
	MAP descriptor of the departure process of a MAP/MAP/1-PS queue, ETAQA-truncated at level n (qbd_depproc_etaqa_ps.m).
template<class T>
T	line::mam::qbd_depproc_residual (const Map< T > &m)
	||(D0 + D1) e||_inf, zero for a genuine MAP.
template<class T>
std::vector< T >	line::mam::qbd_depproc_jointmom (const Map< T > &arrival, const Map< T > &service, const std::vector< std::pair< unsigned, unsigned > > &iset)
	Joint moments E[X_0^i X_1^j] of consecutive inter-departure times of a MAP/MAP/1-FCFS queue (qbd_depproc_jointmom.m).

Detailed Description

Departure process of a MAP/MAP/1 queue: the ETAQA-truncated MAP descriptor under FCFS and under PS, and the joint moments of consecutive inter-departure times.

Templated port of matlab/src/api/mam/qbd_depproc_etaqa.m, qbd_depproc_etaqa_ps.m and qbd_depproc_jointmom.m.

The queue is the usual MAP/MAP/1 QBD, level = number in system, phase = (arrival phase, service phase) with the arrival phase major:

F  = D1^a (x) I_ns       L  = D0^a (+) D0^s
B  = I_na (x) D1^s       L0 = D0^a (x) I_ns

ETAQA keeps levels 0..n-1 explicitly and lumps every level from n upwards into a single aggregate block, using G to describe how the aggregate returns to level n-1: Bbar = B + F G and Bhat = F G, with Lhat = F + L. The descriptor has (n+1) blocks of order na*ns; a transition that carries a departure goes into D1 and everything else into D0.

ARITHMETIC. All three entry points call qbd_fundmat for R and G, so they are gated on num_traits<T>::has_transcendental; see qbd_r.h for why cyclic reduction cannot be exact. Everything downstream of R and G is a finite sequence of matrix products and inverses.

REFERENCE DEFECTS (reproduced here verbatim, see the tests).

1. qbd_depproc_etaqa returns a pair (D0, D1) that is NOT a conservative generator: (D0 + D1) e is nonzero in the last two block rows, so the result is not a MAP and map_lambda / map_prob applied to it are meaningless. Two independent causes, both an off-by-one in the block index arithmetic: a) the line D0(((n-1)*lvlsz+1):n*lvlsz, ((n-1)*lvlsz+1):n*lvlsz) = Lhat addresses the FULL padded matrix, whose block rows are 0..n after the two zero paddings, so it writes Lhat = F + L into block (n-1, n-1), the last EXPLICIT level, and not into block (n, n), the aggregate. Block (n-1, n-1) already has the up-block F sitting at (n-1, n), so that row acquires F twice and its row sum becomes F e instead of 0, while the aggregate keeps a bare L. b) the aggregate row carries both Bbar = B + F G at (n, n-1) and Bhat = F G at (n, n), so F G is counted twice there; the row sum is F G e = F e rather than 0. Measured on the M/M/1 instance of the test (lambda = 0.6, mu = 1, n = 4): ||(D0 + D1) e||_inf = 0.6 = lambda, concentrated in exactly those two rows and zero everywhere else.
2. qbd_depproc_etaqa_ps additionally puts the FULL down-block Bbar at (n, n-1) into BOTH D0 and D1, instead of splitting it (1 - 1/n) / (1/n) the way it splits B at every explicit level and Bhat at the aggregate. The aggregate therefore fires that transition at twice its rate, once as a departure and once silently, and (D0 + D1) e picks up a further Bbar e. It also divides by j at level j starting from j = 1, so the level-1 row gets B * (1 - 1/1) = 0 for the non-departure part, which is right, but the loop stops at n-1 and never treats the boundary the same way.

The port does NOT repair either: these functions are the reference for the JAR and Python ports and a silent divergence would be worse than a reproduced defect. qbd_depproc_etaqa_residual below measures ||(D0+D1)e||_inf so a caller can see it, and the tests pin the measured value.

Definition in file qbd_depproc.h.