dtime.h File Reference

Discrete-time (slotted) matrix-analytic primitives and queues. More...

#include <cstddef>
#include <vector>
#include "line/api/mam/dmap.h"
#include "line/api/mc/dtmc_solve.h"
#include "line/lang/lang_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for dtime.h:

Go to the source code of this file.

Classes
struct	line::mam::Dph< T >
	A discrete phase-type law: initial row vector alpha and transient A. More...
struct	line::mam::DtQueueResult< T >
	Outcome of a slotted station solve. More...

Namespaces
namespace	line
namespace	line::mam

Typedefs
template<class T>
using	line::mam::DBatch = std::vector<Matrix<T>>
	A discrete batch arrival stream, entry k carrying the slots with k events.

Functions
template<class T>
Dph< T >	line::mam::dph_from_dist (lang::ProcessType type, const T &mean_slots, const T &scv)
	Exact discrete phase-type representation of a lattice-valued law.
template<class T>
Dmap< T >	line::mam::dph_to_dmap (const Dph< T > &d)
	Renewal D-MAP (A, a alpha) of a discrete phase-type law.
template<class T>
bool	line::mam::dmap_is_renewal (const Dmap< T > &d)
	True when D1 has rank one, i.e.
template<class T>
Dph< T >	line::mam::dmap_to_dph (const Dmap< T > &d)
	Discrete phase-type law underlying a renewal D-MAP.
template<class T>
T	line::mam::dmap_lambda_batch (const DBatch< T > &A)
	Mean number of EVENTS per slot, pi sum_k k A_k e.
template<class T>
DBatch< T >	line::mam::dmap_super (const DBatch< T > &A, const DBatch< T > &B)
	Superposition, E_k = sum_{i+j=k} kron(A_i, B_j).
template<class T>
DBatch< T >	line::mam::dmap_thin (const DBatch< T > &A, const T &p)
	Bernoulli thinning, B_k = sum_{n>=k} C(n,k) p^k (1-p)^(n-k) A_n.
template<class T>
Dmap< T >	line::mam::dmap_compress (const Dmap< T > &d, std::size_t max_order)
	Reduces the order of a D-MAP by matching interevent moments.
template<class T>
DBatch< T >	line::mam::dmap_compress_batch (const DBatch< T > &A, std::size_t max_order)
	Order reduction of a BATCH stream.
template<class T>
Matrix< T >	line::mam::qbd_dt_g (const Matrix< T > &A0, const Matrix< T > &A1, const Matrix< T > &A2, int max_iter=200)
	G matrix of a discrete-time QBD by logarithmic reduction (Latouche and Ramaswami).
template<class T>
Matrix< T >	line::mam::mg1_dt_g (const std::vector< Matrix< T > > &A, int max_iter=5000, double tol=1e-14)
	G matrix of an M/G/1-type chain by functional iteration on G = sum_k A_k G^k, the blocks being stochastic.
template<class T>
std::vector< T >	line::mam::mg1_dt_pi (const std::vector< Matrix< T > > &B, const std::vector< Matrix< T > > &A, std::size_t max_num_comp=1000)
	Stationary vector of an M/G/1-type chain by the stable Ramaswami formula.
template<class T>
std::vector< T >	line::mam::q_dt_map_map_1 (const Dmap< T > &arv, const Dmap< T > &svc, std::size_t max_num_comp=1000)
	Queue length distribution of a discrete-time D-MAP/D-MAP/1/FCFS queue, the queue-length half of Q_DT_MAP_MAP_1.
template<class T>
std::vector< T >	line::mam::q_dt_ph_ph_1 (const Dph< T > &arv, const Dph< T > &svc, std::size_t max_num_comp=1000)
	Queue length of a discrete-time DPH/DPH/1/FCFS queue, via the D-MAP route.
template<class T>
DtQueueResult< T >	line::mam::mg1_dt_queue (const DBatch< T > &arv, const Dmap< T > &svc, std::size_t max_num_comp=1000, bool want_departure=false)
	Discrete-time single-server queue with batch D-MAP arrivals, DBMAP/D-MAP/1.

Detailed Description

Discrete-time (slotted) matrix-analytic primitives and queues.

Port of matlab/src/api/mam/dph_from_dist.m, dph_to_dmap.m, dmap_to_dph.m, dmap_is_renewal.m, dmap_lambda.m, dmap_super.m, dmap_thin.m and mg1_dt_queue.m, plus the queue-length half of the Q-MAM discrete-time queues Q_DT_MAP_MAP_1.m and Q_DT_PH_PH_1.m.

Everything measures time in SLOTS and follows the late arrival system with delayed access (LAS-DA): within a slot the service completion resolves first, arrivals are appended at the end of the slot and cannot enter service before the next one, and the level is read after both. The QBD blocks state it directly, A1 = kron(C1,D0) being the claim that a job arriving at the end of a slot is not served within it. The LDES slotted engine orders its intra-slot events the same way, so the two are directly comparable.

A discrete phase-type law is (alpha, A) with P[X=k] = alpha A^(k-1) a, a = e - A e, k = 1,2,... A batch stream is a vector [A_0, A_1, ...] whose A_k carries the slots delivering k events; a plain D-MAP is the two-entry case.

Two solver differences from the MATLAB twin, both deliberate and measured against it: the QBD fundamental matrix uses logarithmic reduction rather than SMCSolver's cyclic reduction (same minimal solution, both iterate to 1e-14), and the batch M/G/1-type chain is solved by level truncation rather than by MG1_CR, because C++ carries neither SMCSolver nor BuTools. The truncation level is chosen from the tail mass, so it is an accuracy knob, not a model change.

Definition in file dtime.h.