Package jline.api.npfqn

Class Npfqn_bnd_bgt

java.lang.Object
jline.api.npfqn.Npfqn_bnd_bgt
public final class Npfqn_bnd_bgt extends Object
Piecewise-linear Lyapunov UPPER bound on the steady-state queue lengths of a multitype (deterministic-routing) multiclass Markovian queueing network, valid for EVERY work-conserving Markovian policy.

Port of matlab/src/api/npfqn/npfqn_bnd_bgt.m.

MODEL. J single-server stations; I customer types; type i arrives as a Poisson stream of rate lambda[i] and passes through stages k = 0..mu[i].length-1, stage k being served at station sigma[i][k] at exponential rate mu[i][k]. Class (i,k) is the buffer of type i at stage k; N = sum_i mu[i].length is the number of classes.

METHOD. Solve the Down-Meyn global-stability linear program GLP[dm], eq. (25)-(28) of the reference, in the piecewise-linear Lyapunov function Phi(x) = max_j L^j'x:

   L^j(i,1) lambda_i + mu(i,k) (L^j(i,k+1) - L^j(i,k)) + V_j <= -gamma
                                                    for (i,k) in station j
   mu(i,k) (L^j(i,k+1) - L^j(i,k)) <= V_j           for (i,k) not in j
   (1/(J-1)) sum_{j' != j} L^j'(i,k) >= L^j(i,k)    for (i,k) not in j
   L, V, gamma >= 0

with L^j(i,Ji+1) = 0. A feasible solution with gamma > 0 certifies that EVERY work-conserving policy is stable, and a smoothed Phi is then a Lyapunov function with drift gamma/4 and an explicit exception parameter, giving the reference's Theorem 4 bound

   E[L^j'Q] <= 16 N J^2 (J-1) (Lmax+gamma)^3 / gamma^2
               + 8 (Lmax + gamma/2)^2 / gamma  =: U

for every j, whence E[Q(i,k)] &lt;= U / max_j L^j(i,k).

THE RATES ARE RESCALED so that sum_i lambda_i + sum_{i,k} mu(i,k) = 1, the uniformization the reference imposes before Theorem 4. Queue lengths are counts and are unaffected by the time scale.

NORMALIZATION, WHICH THE REFERENCE LEAVES OPEN. GLP[dm] is homogeneous and so is the bound, so this routine fixes L^j(i,k) &lt;= 1 and MAXIMIZES gamma, then breaks ties among gamma-optimal solutions by maximizing sum L: a degenerate optimum can otherwise zero some L^j(i,k) and report an infinite bound for a class for no reason.

THE BOUND IS LOOSE, and knowingly so: the exception parameter carries (Lmax+gamma)^3/gamma^2 and dominates as soon as J > 1. What is sharp is the STABILITY CERTIFICATE gamma > 0 and the geometric tail RATE.

Reference: D. Bertsimas, D. Gamarnik, J. N. Tsitsiklis (2001). Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability 11(4), 1384-1428, Section 5.1 (GLP[dm] of Down and Meyn 1997, and Theorem 4).

  • Method Details

    • npfqn_bnd_bgt

      public static Npfqn_bnd_bgt.Result npfqn_bnd_bgt(double[] lambda, double[][] mu, int[][] sigma, int J)
      Parameters:
      lambda - Poisson arrival rate of each type
      mu - mu[i][k] = service rate of stage k of type i
      sigma - sigma[i][k] = zero-based station of stage k of type i
      J - number of stations