solver_ba_snc.h File Reference

Stochastic network calculus UPPER bound on the mean response times and queue lengths of a feed-forward open network, valid for EVERY work-conserving scheduling policy at every station. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <map>
#include <string>
#include <vector>
#include "line/api/sn/sn_rt_stations.h"
#include "line/api/snc/snc_env_map.h"
#include "line/api/snc/snc_env_poisson.h"
#include "line/api/snc/snc_leftover.h"
#include "line/api/snc/snc_mean_delay.h"
#include "line/api/snc/snc_output.h"
#include "line/api/snc/snc_perc_backlog.h"
#include "line/api/snc/snc_perc_delay.h"
#include "line/api/snc/snc_srv_exp.h"
#include "line/lang/distribution.h"
#include "line/lang/qn/network_struct.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ba_snc.h:

Go to the source code of this file.

Classes
struct	line::ba::SncEnvelopes
	The per-pair envelopes the analyzer built, keyed by (station, class). More...
struct	line::ba::SncPercentiles
	The response-time and queue-length QUANTILES of the 'snc' family. More...

Namespaces
namespace	line
namespace	line::ba

Functions
template<class T>
SncEnvelopes	line::ba::solver_ba_snc_envelopes (const qn::NetworkStruct< T > &L)
	Builds the per-pair (arrival, service) envelopes of a feed-forward model.
template<class T, class Solution>
void	line::ba::solver_ba_snc (const qn::NetworkStruct< T > &L, Solution &out)
template<class T>
SncPercentiles	line::ba::solver_ba_snc_perc (const qn::NetworkStruct< T > &L, double eps)
	Both quantile matrices from one envelope propagation.

Detailed Description

Stochastic network calculus UPPER bound on the mean response times and queue lengths of a feed-forward open network, valid for EVERY work-conserving scheduling policy at every station.

Port of matlab/src/solvers/BA/solver_ba_snc_analyzer.m, cross-checked against jline.solvers.ba.analyzers.Solver_ba_snc_analyzer and the native-Python solver_ba_snc.py. The api domain line/api/snc supplies the envelope algebra; this analyzer maps the LINE model onto it, propagates envelopes hop by hop, and reads the bound back per station and class.

UNITS ARE JOBS, NOT WORK. The arrival envelope counts jobs and the service element is snc_srv_exp, the counting process of an Exp(mu) server. That is what lets a departure envelope from one station be the arrival envelope of the next: a service-time work unit differs from station to station, a job does not. On a single M/M/1 the resulting backlog bound decays as (lambda/mu)^n and the delay bound as exp(-(mu-lambda)*d), both exact rates.

BOUND CONVENTION. R(i,r) is snc_mean_delay of the (arrival, service) envelope pair, i.e. the integral of the delay tail bound, so each entry is a valid upper 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.

ARITHMETIC. The api domain is double-only – every bound is an exp/log expression minimized numerically over theta – so this arm converts at the boundary with num_traits<T>::to_double and from_double rather than pretending to be Rational-clean. It is the one BA family that is not instantiable at exact arithmetic, and registry.h registers the domain as Double for that reason.

Reference: M. Fidler, A. Rizk (2015). A Guide to the Stochastic Network Calculus. IEEE Communications Surveys and Tutorials 17(1), 92-105.

Definition in file solver_ba_snc.h.