Package jline.api.qsys

Class Qsys_mapg1k

java.lang.Object
jline.api.qsys.Qsys_mapg1k
public final class Qsys_mapg1k extends Object
The MAP/G/1/K queue with tail drop: Markovian arrivals, an arbitrary service law F, and a buffer of K packets counting the one in transmission.

Port of matlab/src/api/qsys/qsys_mapg1k.m, the twin of cpp/include/line/api/qsys/qsys_mapg1k.h and of the native Python api.qsys.mapg1k. Unlike Qsys_mapg1 the service law is NOT fitted to a phase-type distribution: F enters exactly through the functionals A_m and Q_m, evaluated by uniformizing the arrival MAP at theta = max_i (-D0(i,i)). Unlike Qsys_mg1k_loss, which embeds the same way but assumes Poisson input, arrivals may be a general MAP, so flows of equal rate but different interarrival variability or autocorrelation are told apart.

METHOD. The chain embedded at departure epochs has state (n, j) with n = 0..K-1 the packets left behind by a departure and j the MAP phase. With A_m the matrix of "m arrivals during one service, phase i to phase j", 

   n >= 1: n' = n - 1 + min(m, K - n), the overflow being sum_{m >= K-n} A_m
   n == 0: the phase first jumps through Psi = (-D0)^-1 D1, the idle period
           ending at an arrival, and the service proceeds as from n = 1.
Its stationary law sigma gives, by Markov renewal reward over one inter-departure cycle, E[cycle] = S + sigma_0 (-D0)^-1 e, T = 1/E[cycle] and p0 = 1 - T S; the level-holding times come from Q_m, the expected time within a service during which exactly m arrivals have occurred. No PASTA argument is used anywhere -- the MAP phase resolution does that work instead, which is what lets Qsys_mmapg1k read exact PER-CLASS loss ratios off pKvec.

This is not the transform solution of Theorem 1 of [1], stated through a sequence R_m obeying R(z) = z (A(z) - z I)^-1. That sequence grows geometrically while the quantity extracted from it stays O(s) as s -> 0+, so the conditioning degrades like that ratio^K and crosses the double-precision ceiling near K = 20 under gamma service with CV = 2. Reference [1] evaluates its formulae in arbitrary precision, so the restriction is invisible there. The embedded chain used here has every entry a probability or a time.

The uniformization coefficients c_n are built by RECURSION rather than from log-gamma, as in the C++ twin: for the gamma law they are the negative binomial pmf, for the deterministic law the Poisson pmf, and for a PH law c_n = theta^n alpha M^{n+1} t with M = (theta I - T)^-1 accumulated as a running row vector. The recursions are monotone in n and cannot lose leading digits to cancellation.

References:
[1] Chydzinski, A. Per-Flow Throughput of a FIFO Buffer. Applied System Innovation 2026, 9, 112.
[2] Niu, Z.; Cooper, R.B. Transform-Free Analysis of M/G/1/K and Related Queues. Mathematics of Operations Research 1993, 18, 486-510.

  • Field Details

    • DEFAULT_TOL

      public static final double DEFAULT_TOL
      Default uniformization truncation tolerance.
      See Also:

    • DEFAULT_NMAX

      public static final int DEFAULT_NMAX
      Default cap on the uniformization order.
      See Also:

  • Method Details

    • qsys_mapg1k

      public static QsysMapG1kResult qsys_mapg1k(Matrix D0, Matrix D1, QsysServiceLaw svc, int K)
      qsys_mapg1k with the reference defaults tol = 1e-12, nmax = 200000.

    • qsys_mapg1k

      public static QsysMapG1kResult qsys_mapg1k(Matrix D0, Matrix D1, QsysServiceLaw svc, int K, double tol, int nmaxCap)
      MAP/G/1/K with tail drop.
      Parameters:
      D0 - M x M hidden transition matrix of the arrival MAP
      D1 - M x M arrival matrix; D0 + D1 must be an irreducible generator
      svc - service law
      K - buffer size in packets, K >= 1, the one in service included
      tol - uniformization truncation tolerance
      nmaxCap - cap on the uniformization order