solver_ba_bgt.h File Reference

Piecewise-linear Lyapunov UPPER bound on the steady-state queue lengths of a multitype open Markovian network, valid for EVERY work-conserving Markovian policy. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/npfqn/npfqn_bnd_bgt.h"
#include "line/api/sn/sn_rt_stations.h"
#include "line/lang/qn/network_struct.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ba_bgt.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::ba

Functions
template<class T, class Solution>
void	line::ba::solver_ba_bgt (const qn::NetworkStruct< T > &L, Solution &out)

Detailed Description

Piecewise-linear Lyapunov UPPER bound on the steady-state queue lengths of a multitype open Markovian network, valid for EVERY work-conserving Markovian policy.

Templated port of matlab/src/solvers/BA/solver_ba_bgt_analyzer.m, cross-checked against jar/src/main/java/jline/solvers/ba/analyzers/Solver_ba_bgt_analyzer.java. The polyhedron and the bound are npfqn_bnd_bgt; this analyzer maps the LINE model onto them and reads the bound back per station and class.

CLASS SPACE. The reference's network is a MULTITYPE one: each type follows a FIXED sequence of stages, and stage k of type i is its own buffer. LINE's (station, job class) pair is that buffer, so the analyzer walks the routing matrix from the Source and turns each open class into one type whose stages are the pairs it visits. Two gates follow and are enforced by name rather than approximated: routing must be DETERMINISTIC (a pair sends everything to one successor, or everything to the Sink) and routes must NOT MERGE (a pair belongs to exactly one type, else the reference's class index (i,k) is not defined). A re-entrant line is expressible by giving the revisits distinct LINE classes.

THE BOUND IS LOOSE, and knowingly so: the exception parameter of the smoothed Lyapunov function carries (Lmax+gamma)^3/gamma^2 and dominates as soon as there is more than one station. What is sharp is the STABILITY CERTIFICATE – a feasible gamma > 0 proves every work-conserving policy stable, and the LP correctly refuses the Lu-Kumar network at per-station loads of 0.7, where global stability genuinely fails – and the geometric tail RATE.

ARITHMETIC. Rational-clean, like the API core it calls.

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.

Definition in file solver_ba_bgt.h.