The MAP/MAP/1 queue solved as a quasi-birth-death process. More...

#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mam/map_transform.h"
#include "line/api/mam/mmap_lambda.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_mapmap1.h:

Classes
struct	line::mam::QbdMapMap1Blocks< T >
	The four level blocks of the MAP/MAP/1 QBD. More...
struct	line::mam::QbdRg< T >
	R, G and the level blocks of a MAP/MAP/1 queue (qbd_rg.m). More...
struct	line::mam::QbdMapMap1Result< T >
	Result of qbd_mapmap1, mirroring the MATLAB return list. More...

Namespaces
namespace	line
namespace	line::mam

Functions
template<class T>
QbdMapMap1Blocks< T >	line::mam::qbd_mapmap1_blocks (const Map< T > &arrival, const Map< T > &service)
	Level blocks of the MAP/MAP/1 QBD from the arrival and service MAPs.
template<class T>
QbdRg< T >	line::mam::qbd_rg (const Map< T > &arrival, const Map< T > &service_in, const T &util)
	R and G of the MAP/MAP/1 QBD (qbd_rg.m).
template<class T>
QbdRg< T >	line::mam::qbd_rg (const Map< T > &arrival, const Map< T > &service)
	qbd_rg without rescaling the service process.
template<class T>
T	line::mam::qbd_qlen_factmoment (const std::vector< T > &pi0, const Matrix< T > &R, unsigned m)
	Factorial moment of order m of the number in system, computed in closed form from the boundary vector and R:
template<class T>
T	line::mam::qbd_qlen_moment (const std::vector< T > &pi0, const Matrix< T > &R, unsigned m)
	Raw moment of order m of the number in system, E[N^m], assembled from the factorial moments with the Stirling numbers of the second kind, N^m = sum_j S(m,j) N(N-1)...(N-j+1).
template<class T>
QbdMapMap1Result< T >	line::mam::qbd_mapmap1 (const Map< T > &arrival, const Map< T > &service_in, const T &util, std::size_t max_levels)
	MAP/MAP/1 queue (qbd_mapmap1.m).
template<class T>
QbdMapMap1Result< T >	line::mam::qbd_mapmap1 (const Map< T > &arrival, const Map< T > &service)
	qbd_mapmap1 without rescaling and with 20000 materialized levels.
template<class T>
T	line::mam::qbd_mapmap1_qlen_truncated (const QbdMapMap1Result< T > &res)
	The mean number in system computed the way MATLAB's qbd_mapmap1 does it, by summing k over the materialized levels.

Detailed Description

The MAP/MAP/1 queue solved as a quasi-birth-death process.

Templated port of matlab/src/api/mam/qbd_mapmap1.m and qbd_rg.m, cross-checked against jar/src/main/java/jline/api/mam/Qbd_mapmap1.java.

The level is the number in system and the phase is the pair (arrival phase, service phase), so the level blocks are

F    = D1^a (x) I_ns          an arrival, level up
L    = D0^a (+) D0^s          no event, level unchanged
B    = I_na (x) D1^s          a service completion, level down
Lbar = D0^a (x) I_ns          level zero: no server is busy

with (x) the Kronecker product and (+) the Kronecker sum. R and G come from cyclic reduction (qbd_fundmat), the boundary vector from qbd_pi.

ARITHMETIC. qbd_mapmap1 itself is gated on transcendental arithmetic because it calls qbd_fundmat; see qbd_r.h for why the fixed-point iterations cannot be exact. Everything that consumes R afterwards is un-gated and instantiates at Rational: qbd_mapmap1_blocks assembles the level blocks with Kronecker products only, and the moment formulas below are closed forms in R,

E[N (N-1) ... (N-m+1)] = m! pi_0 R^m (I - R)^-(m+1) e,

a finite product of exact matrix operations. Those closed forms are also more accurate than the reference: MATLAB and the JAR sum the truncated level distribution k pi_k e until the accumulated mass reaches 1 - 1e-10, which discards the tail mass times its (unbounded) level index, whereas the closed form sums the whole geometric tail. The difference grows as the caudal characteristic approaches one; see the note on QN_truncated below.

Definition in file qbd_mapmap1.h.

Classes

Namespaces

Functions

Detailed Description