BA (Bounds Analysis)
Methods · Configuration · Shared options · All solvers
The BA solver computes performance bounds for queueing networks and stochastic Petri nets. Its methods cover classical closed-network throughput bounds, open-network bounds, blocking reductions and Petri-net moment relaxations. The admissible methods depend on the model structure.
Methods
The method names and defaults below describe the MATLAB interface. Aliases share a row; model-specific restrictions and backend differences are noted. Use solver.listValidMethods() to inspect the names available for your model.
Each method returns one bound; an .upper/.lower pair brackets the exact solution, and getBounds() returns the bracket for a family.
| Method | Algorithm and applicability |
|---|---|
default | The noniterative bound ladder: gb.upper on an ordinary closed model, qrf.bas where a blocking polytope fits. |
auto, auto.upper, auto.lower | Evaluate every feasible noniterative bound and keep the tightest side; a family that rejects the model is skipped. |
aba.upper, aba.lower | Asymptotic Bounds Analysis: X <= min(1/Dmax, N/(Z+sum D)) and its pessimistic counterpart. |
bjb.upper, bjb.lower | Balanced Job Bounds: the ABA bracket refined by substituting the mean and maximum demand into the residence time. |
pb.upper, pb.lower | Proportional bounds: the same bracket with the power-mean demands D^2/sum(D) and D^N/sum(D^(N-1)). |
gb.upper, gb.lower | Geometric Bounds of Casale-Muntz-Serazzi: geometric-sum bounds on cycle time and throughput, and the matching queue-length bound. |
sb.upper, sb.lower | Harel's simple closed-network throughput bound, both sides; no delay station. |
harel.upper | Upper throughput bound extrapolated from the exact throughput at population n <= 7. |
harel.lower | Lower throughput bound from the first and N-th power sums of the relative utilizations. |
mwba.upper | Majumdar-Woodside robust (worst-case) throughput bound, discipline-insensitive, NBUE service; the only closed family keeping HOL and the preemptive-priority disciplines. |
mwba.lower | The matching robust throughput guarantee, lower side. |
pbh.upper, pbh.lower | Eager-Sevcik Performance Bound Hierarchy: options.level MVA steps from an ABA-initialized residence, tightening to exact MVA as the level reaches N. |
pbk.upper, pbk.lower | PB(k): the same hierarchy at iteration count k, evaluated at populations N, N-1, ..., N-k. |
bjbk.upper, bjbk.lower | BJB(k): the iterative Balanced Job Bound, one exact MVA step per iteration from the balanced seed. |
cbh.upper, cbh.lower | Convolutional Bound Hierarchy: one column of Buzen's g-array filled with BJB estimates, the remaining stations convolved exactly. |
ssd.upper, ssd.lower | Dallery-Suri server-station disaggregation bound with the think-time correction; the classical family that accepts multiserver stations. |
sib.upper, sib.lower | Srinivasan's Successively Improving Bounds on cycle time and throughput; zero think time only. |
cub.upper | Kerola composite multiclass upper bound on per-class throughput. |
mbjb.lower | The multiclass Balanced Job Bound that seeds cub.upper. |
looping.upper, looping.lower | Eager's multiclass queue-length bracket built from the unaccounted-congestion heaps. |
scb.upper | Demand-free upper bound on multiclass throughput, capped by U <= 1; brackets the multiclass system the single-class model aggregates. |
scb.lower | Exact single-class throughput as a lower bound on the multiclass throughput, with the single-class utilizations as lower bounds. |
ldbcmp.lower | Anselmi-Cremonesi lower throughput bound for closed single-class BCMP networks via the asymptotic closed-open equivalence. |
bpt.lower | Bertsimas-Paschalidis-Tsitsiklis first-order LP relaxation of the achievable region; open networks. |
bgt.upper | Piecewise-linear Lyapunov function whose linear program certifies stability and bounds the mean queue lengths under any work-conserving policy; open networks. |
snc.upper | Stochastic network calculus: MGF arrival and service envelopes propagated hop by hop over a feed-forward open network. |
qr | Friendly alias of the QRF quadratic reduction bound; resolves to qrf.mmi. |
lr, lr.upper, lr.lower | LP-based Linear Reduction bound, one LP per station; not an alias of qrf.mmi.linear. |
qrf.mmi | Quadratic reduction on the closed MAP queueing chain, mutual-information objective, nonlinear no-blocking reduction. |
qrf.mem | The same reduction with the maximum-entropy objective. |
qrf.bethe | Tree-reweighted (Bethe) free entropy over the same no-blocking polytope; the only convex QRF objective, so the answer is start-point independent. |
qrf.mmi.ld | MMI quadratic reduction with the load-dependent alpha matrix, which is what lets it serve delay, multiserver and load-dependent stations. |
qrf.mmi.linear | The same load-dependent envelope with explicit equality constraints in place of the nonlinear reduction. |
qrf.bas | LP quadratic reduction over the Blocking-After-Service polytope; may derive the blocking tables from station capacities. |
qrf.bas.mmi | MMI objective over that blocking polytope; concave there, so each codebase settles on the vertex its own solver reaches. |
qrf.bas.mem | Maximum-entropy objective over the blocking polytope. |
qrf.bas.bethe | Tree-reweighted (Bethe) free entropy over the blocking polytope, the start-point-independent blocking answer. |
qrf.rsrd | LP quadratic reduction under repetitive-service random-destination blocking. |
mapamva.upper, mapamva.lower | MAP-AMVA LP bound for a closed network with MAP/MMPP2 service at one FCFS station; reads the correlation, not the mean alone. |
spnlp.upper, spnlp.lower | Moment-relaxation LP for a stochastic Petri net: the uniformized evolution equation for the first two moments plus invariants, state equation and Chernoff enabling bounds. Exponential firings. |
spnlp.op.upper, spnlp.op.lower | The operational variant, dropping the second-moment, covariance and Little's-law families; any phase-type law, much looser. |
Configuration options
The solver-specific fields below belong to options.config. Set them on an options struct, for example opt.config.name = value, and pass that struct to the solver constructor. See shared solver options for all top-level fields, shared configuration, defaults and usage. Options apply only to the methods and model features that consume them.
Relevant top-level options: level, iter_max, iter_tol.
The top-level level (default 2) controls the hierarchical bounds. The QRF family shares qrf_alpha, qrf_params and qrf_maxvars with CTMC.
| Option | Default | Description and values |
|---|---|---|
spnlp_assumelive | unset | Assume the Petri net is live, so the LP bound skips the liveness constraints. |
spnlp_init | unset | Initial marking or basis handed to that linear program. |
qrf_alpha | [] | Load-dependent rate matrix (M x N) handed to the queueing-reduction-with-blocking construction. |
qrf_params | [] | Blocking configuration struct (f, MR, BB, F, MM, MM1, ZZ, ZM) for the same construction. |
qrf_maxvars | cap | Refusal threshold on the number of variables the blocking reduction would generate. |
MATLAB example
model = Network('BA Example');
delay = Delay(model, 'Think');
queue = Queue(model, 'Server', SchedStrategy.PS);
jobs = ClosedClass(model, 'Jobs', 10, delay);
delay.setService(jobs, Exp(0.5));
queue.setService(jobs, Exp(1.0));
model.link(Network.serialRouting(delay, queue, delay));
solver = SolverBA(model, 'method', 'gb.upper');
solver.getBoundsTable()