solver_ba_bpt.h File Reference

Achievable-region LOWER bound on the mean response times of a multiclass open Markovian network, valid for EVERY non-idling scheduling policy at every station. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/npfqn/npfqn_bnd_bpt.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_bpt.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_bpt (const qn::NetworkStruct< T > &L, Solution &out)

Detailed Description

Achievable-region LOWER bound on the mean response times of a multiclass open Markovian network, valid for EVERY non-idling scheduling policy at every station.

Templated port of matlab/src/solvers/BA/solver_ba_bpt_analyzer.m, cross-checked against jar/src/main/java/jline/solvers/ba/analyzers/Solver_ba_bpt_analyzer.java. The polyhedron is npfqn_bnd_bpt; this analyzer maps the LINE model onto it and reads the bound back per station and class.

CLASS SPACE. The reference's "class" is a buffer: one exponential service rate, one Markovian routing law. LINE's (station, job class) pair is exactly that, so a pair carrying traffic becomes one LP class, the Source is absorbed into the external arrival vector, and class switching needs no special treatment because sn.rt already carries it.

BOUND CONVENTION. R(i,r) minimizes x over the polyhedron with the objective set to that pair's unit vector, so each entry is a valid lower bound on its own. Q follows by Little's law from the bounded R and the EXACT throughput T (an open network's per-class rates are fixed by the traffic equations, not by the policy), and so does C. U is exact for the same reason.

TIGHTNESS. Exact on M/M/1 and tight on the externally fed classes, but weak on a class whose arrivals are all internal: the only term coupling x_r to the second-moment block carries the factor lambda0_r, so an internally fed class can fall back to its own mean service time.

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

Reference: D. Bertsimas, I. Paschalidis, J. Tsitsiklis (1994). Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance. Annals of Applied Probability 4(1), 43-75.

Definition in file solver_ba_bpt.h.