Package jline.solvers.ba

Class SolverBA

java.lang.Object
jline.solvers.Solver
jline.solvers.NetworkSolver
jline.solvers.ba.SolverBA
Direct Known Subclasses:
BA
public class SolverBA extends NetworkSolver
SolverBA is the dedicated bound-analysis solver for closed queueing networks.

Unlike SolverMVA (point estimates), each method returns an optimistic (.upper) or pessimistic (.lower) throughput/queue-length bound; the two sides of a family bracket the exact solution. Bounds need only demands and populations, so the feature set is narrow (closed product-form-parameterized models).

FINITE-BUFFER BLOCKING IS REFUSED, NOT BOUNDED. Needing only demands and a population is the BCMP parameterization, which presumes UNBOUNDED buffers; a buffer that binds couples the station occupancies and the resulting numbers do not bracket the blocked model. runAnalyzer therefore gates on SnHasBlocking and listValidMethods drops every blocking-blind method. The exceptions are qrf.bas*/qrf.rsrd, which carry the blocking tables explicitly. Use SolverMVA method 'sqd' for a point estimate.

Method families:

  • Noniterative: aba, bjb, pb, gb, sb, mwba (Majumdar-Woodside).
  • Hierarchical: pbh (Eager-Sevcik), pbk/bjbk (iterative PB(k)/BJB(k)), cbh (Dowdy), ssd (Suri-Dallery multiserver), cub (Kerola composite upper) with mbjb (multiclass BJB lower), sib (Srinivasan), ldbcmp (Anselmi-Cremonesi LD-BCMP lower), scb (Dowdy et al. 1992 single-class bounds, the only family that does NOT bracket this model's own solution but the multiclass system the single-class model aggregates; kept out of auto.* for that reason).
  • QRF: qrf.* (Quadratic Reduction Framework, LP-based, PH service), with aliases qr -> qrf.mmi and lr -> qrf.mmi.linear.

  • Constructor Details

  • Method Details

    • defaultOptions

      public static SolverOptions defaultOptions()

    • getStruct

      public NetworkStruct getStruct()

    • runAnalyzer

      public void runAnalyzer() throws IllegalAccessException
      Description copied from class: Solver
      Executes the solver algorithm to analyze the model. This abstract method must be implemented by concrete solver classes.
      Specified by:
      runAnalyzer in class Solver
      Throws:
      IllegalAccessException - if access to required resources is denied

    • getBounds

      public SolverBA.Bounds getBounds()
      Returns the {lower,upper} bracket for the current method's family.
      Returns:
      the throughput/queue-length bracket

    • getDelayPerc

      public Matrix getDelayPerc(double eps)
      Returns the per-station response-time QUANTILE at violation probability eps: the smallest d for which P{D_ir > d} <= eps is certified by the stochastic network calculus bound.

      This is the native output of the 'snc' family, so the accessor runs the SNC envelope propagation directly whatever options.method says; a station-class pair carrying no traffic stays NaN. Every other family bounds means only and has no counterpart.

      Parameters:
      eps - violation probability, 0 < eps < 1
      Returns:
      an (nstations x nclasses) matrix of quantiles, NaN where no traffic

    • getBacklogPerc

      public Matrix getBacklogPerc(double eps)
      Returns the per-station queue-length QUANTILE, in jobs, at violation probability eps. The counterpart of getDelayPerc(double); see it for the conventions.
      Parameters:
      eps - violation probability, 0 < eps < 1
      Returns:
      an (nstations x nclasses) matrix of quantiles, NaN where no traffic

    • getPercTable

      public NetworkPercTable getPercTable(double eps)
      Returns the response-time and queue-length quantiles at violation probability eps, in the layout of getAvgTable. Rows are the station-class pairs that carry traffic.
      Parameters:
      eps - violation probability, 0 < eps < 1
      Returns:
      the quantile table

    • getBoundsTable

      public NetworkBoundsTable getBoundsTable()
      Returns a table of the {lower,upper} bracket per station and class, in the layout of getAvgTable. Columns: Qlower, Qupper, Tlower, Tupper.

      One-sided families (cub upper-only, mbjb/ldbcmp lower-only) carry NaN on the missing side; NaN is preserved, never replaced by zero.

      Returns:
      the bracket table

    • getBoundsTable

      public NetworkBoundsTable getBoundsTable(boolean keepDisabled)
      Returns a table of the {lower,upper} bracket per station and class.
      Parameters:
      keepDisabled - whether to retain station-class pairs whose bounds are all zero
      Returns:
      the bracket table

    • listValidMethods

      public String[] listValidMethods()
      Bound methods this MODEL can run: a narrowing of listAllMethods().

      A name that would always be refused on this model is not offered, so a caller enumerating the list never asks for one. Ask for it by name anyway and runAnalyzer still dispatches, so the analyzer's own reason is what comes back.

    • methodRefusal

      public static String methodRefusal(NetworkStruct sn, String method)
      The STRUCTURAL premises of the SolverBA bound families, in one place: the reason METHOD cannot bound the model SN, or "" when it can.

      ONE PREDICATE, TWO CALLERS. runAnalyzer asks it before dispatching and raises what it returns; supportsModelMethod asks it after the feature gate and reports the same sentence, which is what findSolver, listValidMethods and SolverAUTO's ranked choice all read. A second copy of any rule below is how the report and the run drift apart: the report offers a pair that raises the moment it is run, which is the defect this method exists to remove.

      WHAT BELONGS HERE AND WHAT DOES NOT. Only the rules the feature registry cannot name. FeatureSet has no entry for "one class", for a server count or for a station count, so those are structural and live here. Rules of the form "this family does not accept a delay station" ARE nameable and belong in getMethodFeatureSet(java.lang.String), which drops SchedStrategy_INF from the offending method's set instead: a feature set can refuse a model for HAVING a construct, never for lacking one.

      METHOD is taken as the caller spells it and resolved through resolveMethod, so 'default' is judged as the gb.upper it runs as and the reason names that. The marking-parameterized spnlp and the QRF reduction bounds carry no rule here: the QRF premise is the reducibility test listValidMethods already applies. Of the three OPEN families, 'bpt' and 'bgt' carry none either -- a closed model is refused by their feature set and their analyzers walk the routing matrix for the rest -- while 'snc' carries one, the SERVICE law.

      WHY THE SNC SERVICE LAW IS HERE AND THE bpt/bgt ONE IS NOT. All three analyzers refuse a non-exponential law at a queueing station. For bpt and bgt that rule extends to the SOURCE and is registry-expressible, so it rides in getMethodFeatureSet(java.lang.String) as a dropped law: both are invariant to the arrival law beyond its mean, so a non-exponential source is not something they refuse, it is something they silently bound as if it were Poisson. snc is the opposite: it CONSUMES the arrival law and its analyzer branches on a non-exponential source deliberately. Its rule is about the SERVICE only, and no feature name can say "Erlang at a Queue but not at a Source", so it is structural.

      Mirrors matlab/src/solvers/BA/ba_method_refusal.m and its native python and C++ twins.

      Parameters:
      sn - the network struct to judge
      method - the method name as the caller spells it
      Returns:
      the reason the pair cannot run, or "" when it can

    • methodDegenerate

      public static String methodDegenerate(NetworkStruct sn, String method)
      Whether METHOD APPLIES to SN but its bound carries no information there, and why. Empty when the bound is informative, and empty for every method that has no such regime.

      THIS IS A DIFFERENT QUESTION FROM methodRefusal(jline.lang.NetworkStruct, java.lang.String), which is why it is a different method. That one answers "is this model outside the method's domain", and its answer is what runAnalyzer raises. This one answers "inside the domain, does the formula still say anything", and its answer is NOT raised: a degenerate bound is a VALID bound, just a vacuous one, so an analyzer asked for it by name is entitled to publish it. What must not happen is OFFERING it: findSolver and listValidMethods exist to name the pairs a caller can act on, and a table of zeros over a network with jobs circulating in it is not something anyone can act on.

      THE ONE METHOD WITH SUCH A REGIME IS 'ldbcmp.lower'. The Anselmi-Cremonesi bound is built from the population SURPLUS a = N - Qhat, where Qhat is the occupancy the non-bottleneck stations and the think time would hold in the open network fed at the bottleneck's saturation rate. Pfqn_ldbcmp returns NaN below the regime (a < 0), which the analyzer already refuses by name; AT the boundary a = 0 it returns Xlo = 0, which is formally the trivial bound X >= 0 and propagates into a table whose queue lengths, utilizations and throughputs are all zero. Every entry of that table is a true lower bound and none of them is usable, and a caller cannot tell it from a real answer of zero.

      Parameters:
      sn - the network struct to judge
      method - the method name as the caller spells it
      Returns:
      the reason the bound says nothing here, or "" when it does

    • getMethodFeatureSet

      public FeatureSet getMethodFeatureSet(String method)
      The base envelope with the per-method deltas the registry CAN name.

      A feature set says "I accept this construct", so it can refuse a model for HAVING one and never for lacking one; that is exactly the shape of the delay-station and closed-class premises below, and exactly not the shape of "one class" or "one server", which have no feature name and live in methodRefusal(jline.lang.NetworkStruct, java.lang.String) instead. Judged on the RESOLVED name so that 'default' carries the envelope of the gb.upper it runs as.

      DELAY STATIONS. 'sb' and 'lr' reject an infinite-server station outright, and 'harel', 'sib' and 'scb' reject a nonzero think time, which on these models is the same station: harel extrapolates the exact normalizing constant of a delay-free network, SIB Section 3.2 is the extension that would carry Z and is not implemented, and SCB Theorem 3 rests on the delay-free balanced-network throughput. The three OPEN families reject one too, each being derived for one server per station.

      CLASS TYPES. The three OPEN families drop ClosedClass, which is the whole of their class premise. The MIRROR delta -- dropping OpenClass from every demand-parameterized family -- is deliberately NOT applied: "supports single-class closed networks only" is one rule, its single-class half has no feature name, and splitting it across the two mechanisms would report the closed half here and the single-class half in methodRefusal for the same model. It is stated once, structurally. 'spnlp' takes no delta at all: it is indexed by the marking, and whether that marking is bounded is a question about the P-invariants of the net, which Spn_lpbnd answers.

      Overrides:
      getMethodFeatureSet in class Solver
      Parameters:
      method - the concrete method name
      Returns:
      the per-method feature envelope

    • supportsModelMethod

      public String supportsModelMethod(String method)
      The feature gate above, plus the structural premises no feature name can express.

      methodRefusal(jline.lang.NetworkStruct, java.lang.String) is the same predicate runAnalyzer raises on, so a caller gets one answer whichever of the two it meets first -- which is the point: this gate is what findSolver, listValidMethods and SolverAUTO's ranked choice read, and while it was silent about them a two-class closed network was reported as able to run 36 bound methods of which 30 raised on contact.

      Overrides:
      supportsModelMethod in class Solver
      Parameters:
      method - the concrete method name
      Returns:
      empty string if supported, else the offending reason

    • getFeatureSet

      public static FeatureSet getFeatureSet()
      The feature envelope of the bounds.

      SolverBA DECLARED NO FEATURE SET AT ALL, so it inherited Solver.supports, which returns true: every model in the language was accepted, including the ones whose constructs the analyzer has no representation of. MATLAB had the mirror-image defect -- a set that named no service distribution and therefore refused everything -- and both are fixed to the same list.

      WHAT MAKES A DISTRIBUTION ADMISSIBLE HERE IS ITS MEAN. The analyzer reads sn.rates and sn.visits and nothing else: every bound in the ABA/BJB/PB/GB/SB/Harel/MWBA families is a function of the demands D = V./rates and the think time, so any renewal law with a finite mean is admissible whatever its higher moments. The QRF reduction is the one that needs more, and what it needs is a PH representation (the {D0,D1} pair out of sn.proc), which the phase-type families below carry.

      THE MODULATED LAWS "MAP" AND "MMPP2" ARE IN THE BASE ENVELOPE FOR ONE FAMILY, 'mapamva', AND getMethodFeatureSet(java.lang.String) STRIPS THEM FROM EVERY OTHER. They were out entirely until mapamva landed, on the correct ground that a renewal bound derived for a product-form network says nothing about a correlated one: its mean rate exists, so the utilization law still holds and the formula still returns a number, but that number brackets a DIFFERENT system. MAP-AMVA (Casale-Smirni, DSN 2009) is derived FOR the correlated model -- its variables are the per-phase QN(i,k) and UN(i,k) -- so the same reasoning that refuses the others admits it. The direction is forced: a feature set refuses a model for HAVING a construct and never for lacking one, so the only way to grant a law to one family is to put it in the base envelope and take it away from the rest. MMAP and BMAP stay OUT everywhere, and Cache and Fork/Join stay out for the older reason, that no analyzer here has a representation of either.

      "JobSink" IS DECLARED HERE AND NOT IN MATLAB, and the difference is in the EMITTER, not in the envelope. Network.getUsedLangFeatures marks a Sink with both "Sink" and "JobSink" (the node and its input section); MNetwork.getUsedLangFeatures marks only "Sink". Naming one and not the other therefore refused every OPEN model here while MATLAB accepted it -- and the three open-network bounds 'bpt.lower', 'bgt.upper' and 'snc.upper' are exactly the ones an open model is for, so SolverAUTO.listValidMethods offered no 'ba.*' method name on a model whose bounds this solver computes.

      Returns:
      the features the bounds can consume

    • supports

      public boolean supports(Network model)
      Whether SolverBA can bound this model.

      Finite-buffer blocking is NOT decided here: there is no registry feature name for a capacity, so a blocked model passes this gate and is handled where it can be told apart -- listValidMethods drops the blocking-blind bounds and keeps qrf.bas*/qrf.rsrd, which carry the blocking tables explicitly.

      Overrides:
      supports in class Solver
      Parameters:
      model - the network model to check
      Returns:
      true when every feature the model uses is one the bounds consume

    • listAllMethods

      public static String[] listAllMethods()
      Every bound method the solver implements, independently of the model.