The MMAP[K]/G[K]/1 FCFS queue: K customer types with class-dependent GENERAL service, fed by a marked Markovian arrival process. More...

#include <cmath>
#include <complex>
#include <limits>
#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/lang/distribution.h"
#include "line/lang/lang_types.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_mmapgk1.h:

Classes
struct	line::qsys::MmapGk1Result< T >
	Return value of qsys_mmapgk1, mirroring the MATLAB struct. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
MmapGk1Result< T >	line::qsys::qsys_mmapgk1 (const std::vector< Matrix< T > > &MMAP, const std::vector< lang::Distrib< T > > &svc, const std::vector< T > &w_points, std::size_t num_w_moms, double tol, std::size_t iter_max)
	MMAP[K]/G[K]/1 FCFS, per type.
template<class T>
MmapGk1Result< T >	line::qsys::qsys_mmapgk1 (const std::vector< Matrix< T > > &MMAP, const std::vector< lang::Distrib< T > > &svc)

Detailed Description

The MMAP[K]/G[K]/1 FCFS queue: K customer types with class-dependent GENERAL service, fed by a marked Markovian arrival process.

WHY THIS IS NOT MMAPPH1FCFS. That routine needs every type's service to be PHASE TYPE, because it builds a QBD whose phase carries the service phase. Here the service laws are arbitrary and may differ in family across types – deterministic for one, uniform for another – so no finite phase carries them, and the analysis has to run through transforms instead.

THE METHOD, which is He's, theorem for theorem. FCFS makes the actual waiting time of a customer the WORKLOAD it finds on arrival, so everything follows from the joint transform of workload and arrival phase, f(s)_j = E[exp(-s V) 1{phase = j}], which by He's Theorem 4.1 (eq. 4.6) satisfies

f(s) [ s I + D0 + sum_k Dk gk(s) ] = s v0,                          (*)

with v0 the idle-phase vector, his y0. v0 needs NO root search: the matrix U solving U = D0 + sum_k Dk Fk(U), Fk(U) = int exp(U t) dFk(t), is his eq. (4.4), the generator of the underlying Markov process obtained by EXCISING the busy periods, and eq. (4.5) with Theorem 4.2 give y0 Q = 0 and y0 e = 1 - rho, i.e. v0 = (1 - rho) pi_U. The same vector is what the analyticity of (*) forces, since for every left eigenpair (w, u) of U one has w [D0 + sum_k Dk gk(-u) - u I] = 0, so the roots of the bracket in the closed right half plane are exactly s = -u over the spectrum of U; the two agree to 2.5e-13, and the stationary route is taken because it needs no complex eigenvector.

The per-type actual waiting time is the workload seen by a type-k arrival, biased by that type's own arrival block, his Theorem 5.1 eq. (5.1) summed over the post-arrival phase:

E[exp(-s Wk)] = f(s) Dk e / lambda_k.

SCOPE. He allows an arrival to be a BATCH carrying a sequence of types, and his Theorem 5.3 then multiplies the transform by prod_{i<n} f*_{h_i}(s), the service of the customers ahead of the tagged one WITHIN its own batch. This header covers the single-customer-per-arrival case, his Special case 3.3, where that product is empty, which is exactly the MMAP convention LINE carries.

MOMENTS WITHOUT INVERSION. Differentiating (*) at s = 0 gives sum_i C(j,i) f_i M_{j-i} = [j = 1] v0. M_0 = D is SINGULAR with right null vector e, so each order fixes f_j only up to a multiple of theta, and that multiple is what the NEXT order's solvability condition supplies. At j = 0 the same condition reads theta M_1 e = v0 e, i.e. 1 - rho = 1 - rho, which is the identity that validates the whole setup.

ARITHMETIC. Gated on num_traits<T>::has_transcendental: the U iteration runs to a tolerance, and both the deterministic transform and the inversion need exp. The CDF is the Abate-Whitt Euler sum, which evaluates the transform OFF the real axis, so a small complex layer is carried here rather than in the distribution interface.

Reference: Qi-Ming He, "The versatility of MMAP[K] and the MMAP[K]/G[K]/1 queue", Queueing Systems 38(4):397-418, 2001.

Definition in file qsys_mmapgk1.h.

Classes

Namespaces

Functions

Detailed Description