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. More...

#include <cstddef>
#include <string>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lp_highs.h"
#include "line/util/simplex.h"

Include dependency graph for npfqn_bnd_bgt.h:

Classes
struct	line::npfqn::BndBgt< T >

Namespaces
namespace	line
namespace	line::npfqn

Functions
template<class T>
BndBgt< T >	line::npfqn::npfqn_bnd_bgt (const std::vector< T > &lambda, const std::vector< std::vector< T > > &mu, const std::vector< std::vector< std::size_t > > &sigma, std::size_t J)
	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.

Detailed Description

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.

Templated port of matlab/src/api/npfqn/npfqn_bnd_bgt.m, cross-checked against jar/src/main/java/jline/api/npfqn/Npfqn_bnd_bgt.java.

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..Ji-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 Ji is the class count.

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)] <= 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) <= 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.

ARITHMETIC. Rational-clean: the LP data and the bound are polynomial in the rates and the dense simplex is exact.

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).

Definition in file npfqn_bnd_bgt.h.

Classes

Namespaces

Functions

Detailed Description