Package jline.solvers.ba.analyzers

Class Solver_ba_snc_analyzer

java.lang.Object
jline.solvers.ba.analyzers.Solver_ba_snc_analyzer
public final class Solver_ba_snc_analyzer extends Object
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. The api domain jline.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 at that station, 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.

WHAT IS ASSUMED, and refused when it does not hold: a fully open network with a Source, no delay station, one server per station, exponential service (the Source may be any Markovian (D0,D1) process), a FEED-FORWARD station graph, DETERMINISTIC routing downstream of the Source (splitting AT a Poisson Source is exact and is allowed), and EQUAL service rates among the classes sharing a station.

TIGHTNESS. This is a policy-robust bound, so it is loose on the mean: 2.4x the exact M/M/1 mean response time at rho = 0.1 and 10.4x at rho = 0.95. Its sharp object is the TAIL, whose decay rate it reproduces exactly; reach it through the SolverBA quantile accessors rather than through the mean columns.

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

  • Method Details

    • solver_ba_snc_analyzer

      public static MVAResult solver_ba_snc_analyzer(NetworkStruct sn, SolverOptions options)
      Parameters:
      sn - the model
      options - solver options (unused: the family has no tunable)
      Returns:
      the (Q,U,R,T,C,X) block of the 'snc.upper' family

    • envelopes

      public static Solver_ba_snc_analyzer.Envelopes envelopes(NetworkStruct sn)
      Builds the per-pair (arrival, service) envelopes of a feed-forward model.

      Every gate of the family is checked here rather than in the caller, so that the quantile accessors refuse an unsupported model with the same reason as the mean columns.

      Parameters:
      sn - the model
      Returns:
      the envelopes of the pairs that carry traffic