Synchronous approximation of the M/G/c/K queue with dual bounds (German, EPEW 2025). More...

#include <algorithm>
#include <cctype>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "line/api/qsys/qsys_mapg1k.h"
#include "line/api/qsys/qsys_svclaw_coeffs.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/line_console.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mgck_sync.h:

Classes
struct	line::qsys::MgckSyncResult< T >
	Return value of qsys_mgck_sync, mirroring the MATLAB result struct. More...
struct	line::qsys::mgck_sync_detail::Triplets< T >
	A sparse transition list, summed into a dense matrix as MATLAB's sparse() does. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::qsys
namespace	line::qsys::mgck_sync_detail

Functions
template<class T>
Matrix< T >	line::qsys::mgck_sync_detail::rowmask (const Matrix< T > &M, const std::vector< bool > &keep)
	Row-masked copy: rows with keep[i] false are zeroed, i.e.
template<class T>
Matrix< T >	line::qsys::mgck_sync_detail::colmask (const Matrix< T > &M, const std::vector< bool > &keep)
	Column-masked copy: M diag(keep).
template<class T>
Matrix< T >	line::qsys::mgck_sync_detail::matadd (const Matrix< T > &A, const Matrix< T > &B)
template<class T>
void	line::qsys::mgck_sync_detail::unif (const Matrix< T > &QG, const std::vector< T > &cn, const T &theta, Matrix< T > &Om, Matrix< T > &Ps)
	i_unif: Om = E[exp(QG S)], Ps = E[int_0^S exp(QG t) dt] from c_n at rate theta, with d_n = (1 - sum_{k<=n} c_k)/theta.
template<class T>
std::vector< T >	line::qsys::mgck_sync_detail::emc (const Matrix< T > &Q, const std::vector< bool > &inE, const Matrix< T > &OmDelta, const Matrix< T > &Psi, const Matrix< T > &Qbar)
	i_emc: stationary law of the embedded chain at regenerations, converted to time.
template<class T>
std::vector< T >	line::qsys::mgck_sync_detail::coefficients (const ServiceLaw< T > &svc, const T &lambda, const T &tol, std::size_t nmaxCap)
template<class T>
std::vector< T >	line::qsys::mgck_sync_detail::plain (const T &lambda, std::size_t c, std::size_t K, const ServiceLaw< T > &svc, bool faster, const T &tol, std::size_t nmaxCap, std::vector< std::size_t > &level)
	i_plain: synchronous approximation without state expansion; state i <-> i jobs.
std::vector< int >	line::qsys::mgck_sync_detail::tick (int a, int q, const std::vector< int > &B, int nph)
	i_tick: advance every non-owner phase by one tick; a completed job frees its server for a waiting one, which starts at phase 0 on the boundary.
std::vector< int >	line::qsys::mgck_sync_detail::make_state (int a, int q, const std::vector< int > &B)
template<class T>
std::vector< T >	line::qsys::mgck_sync_detail::expanded (const T &lambda, std::size_t c, std::size_t K, const T &d, std::size_t nphU, bool faster, const T &tol, std::size_t nmaxCap, std::vector< std::size_t > &level)
	i_expanded: synchronous phase expansion; states are [a, q, sorted B phases].
template<class T>
MgckSyncResult< T >	line::qsys::qsys_mgck_sync (const T &lambda, std::size_t c, std::size_t K, const ServiceLaw< T > &svc, const std::string &variant, std::size_t nphases, const T &tol, std::size_t nmaxCap)
	Synchronous approximation of the M/G/c/K queue with dual bounds.
template<class T>
MgckSyncResult< T >	line::qsys::qsys_mgck_sync (const T &lambda, std::size_t c, std::size_t K, const ServiceLaw< T > &svc, const std::string &variant, std::size_t nphases=0)
	qsys_mgck_sync with the reference defaults tol = 1e-12, nmax = 200000.

Detailed Description

Synchronous approximation of the M/G/c/K queue with dual bounds (German, EPEW 2025).

Port of matlab/src/api/qsys/qsys_mgck_sync.m. The concurrent service clocks of the c servers are replaced by synchronized ones, so that at most one non-Markovian activity is enabled at any time and the process is solved exactly by Markov renewal theory through its embedded Markov chain. Every customer receives either its true service time or a shorter one (variant "faster") or a longer one ("slower"), which brackets the M/G/c/K measures: the faster model gives a lower bound on the mean number in system, on the response time and on P(full), and an upper bound on P(idle) and the throughput; the slower model the opposite bounds. The argument is customer-wise and holds without losses; with blocking the bounds are observed, not proven.

MODEL WITHOUT EXPANSION (nphases = 0), state i = jobs in system. All jobs in service share one clock. "faster": an arrival that finds a free server joins the running batch and completes with it. "slower": such an arrival preempts the clock, so the whole batch restarts with it. On expiry min(i,c) jobs depart and the next min(i-c,c) start together. For c = 1 both variants are the exact M/G/1/K queue.

MODEL WITH EXPANSION (nphases = N >= 1, deterministic service only), state (a, q, B): a = 1 when the owner server is busy, q the waiting jobs, B the sorted multiset of phases completed by the other busy servers. While the owner is busy a tick of length d/N advances every phase and the owner completes after N ticks; a newcomer to another server starts at phase 0 ("faster") or -1 ("slower"). With the owner idle the ticks continue; an arrival takes the owner role and preempts the tick, the other phases being rounded up ("faster") or kept ("slower"). An arrival to the empty system takes the owner role with probability 1/c.

Embedded chain (German 2000, cascaded embedding for the expansion): P = I_E - diag^{-1}(Q_E) Q_E + Omega Delta + Psi Qbar C = -diag^{-1}(Q_E) + Psi, pi = u C/(u C e), u = u P with Omega = I_G E[exp(Q_G S)] and Psi = I_G E[int_0^S exp(Q_G t) dt], both evaluated by uniformization of Q_G at rate lambda from the service-law coefficients of qsys_svclaw_coeffs.h.

A truncated uniformization series (residual above 1e-6) warns and continues, as the reference does.

ARITHMETIC. Gated on num_traits<T>::has_transcendental: the coefficients need exp and the series truncation is a tolerance.

References: [1] R. German, On Synchronous Approximations of Non-Markovian Processes with Dual Bounds, EPEW 2025. [2] R. German, Performance Analysis of Communication Systems with Non-Markovian Stochastic Petri Nets, Wiley, 2000.

Definition in file qsys_mgck_sync.h.

Classes

Namespaces

Functions

Detailed Description