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 | Reference |
|---|---|---|
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. | [13], [83], [36] |
bjb.upper, bjb.lower | Balanced Job Bounds: the ABA bracket refined by substituting the mean and maximum demand into the residence time. | [21], [112] |
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)). | [21], [56] |
gb.upper, gb.lower | Geometric Bounds of Casale-Muntz-Serazzi: geometric-sum bounds on cycle time and throughput, and the matching queue-length bound. | [21] |
sb.upper, sb.lower | Harel's simple closed-network throughput bound, both sides; no delay station. | [53] |
harel.upper | Upper throughput bound extrapolated from the exact throughput at population n <= 7. | [53] |
harel.lower | Lower throughput bound from the first and N-th power sums of the relative utilizations. | [53] |
mw.upper | Majumdar-Woodside robust (worst-case) throughput bound, discipline-insensitive, NBUE service; the only closed family encompassing HOL and the preemptive-priority disciplines. | [72] |
mw.lower | The matching robust throughput guarantee, lower side. | [72] |
pbh.upper, pbh.lower | PBH: the Eager-Sevcik hierarchy initialized from the PB bound. | [43] |
bjbh.upper, bjbh.lower | BJBH: the Eager-Sevcik hierarchy initialized from the BJB bound. | [43] |
cbh.upper, cbh.lower | Convolutional Bound Hierarchy: one column of Buzen's g-array filled with BJB estimates, the remaining stations convolved exactly. | [41] |
ssd.upper, ssd.lower | Dallery-Suri server-station disaggregation bound with the think-time correction; the classical family that accepts multiserver stations. | [34] |
sib.upper, sib.lower | Srinivasan's Successively Improving Bounds on cycle time and throughput; zero think time only. | [102] |
cub.upper | Kerola composite multiclass upper bound on per-class throughput. | [61] |
mbjb.lower | The multiclass Balanced Job Bound that seeds cub.upper. | [61] |
looping.upper, looping.lower | Eager's multiclass looping bound. | [42] |
scb.upper | Demand-free upper bound on multiclass throughput, capped by U <= 1; brackets the multiclass system the single-class model aggregates. | [40] |
scb.lower | Exact single-class throughput as a lower bound on the multiclass throughput, with the single-class utilizations as lower bounds. | [40] |
ldac.lower | Anselmi-Cremonesi lower throughput bound for closed single-class BCMP networks via the asymptotic closed-open equivalence. | [2] |
bpt.lower | Bertsimas-Paschalidis-Tsitsiklis first-order LP relaxation of the achievable region; open networks. | [11] |
bgt.upper | Piecewise-linear Lyapunov function whose linear program certifies stability and bounds the mean queue lengths under any work-conserving policy; open networks. | [10] |
snc.upper | Stochastic network calculus: MGF arrival and service envelopes propagated hop by hop over a feed-forward open network. | [45] |
qr | Alias of the QRF quadratic reduction bound; resolves to qrf.mmi. | [18] |
lr, lr.upper, lr.lower | LP-based Linear Reduction bound, one LP per station; not an alias of qrf.mmi.linear. | [18] |
qrf.mmi | Quadratic reduction on the closed MAP queueing chain, mutual-information objective, nonlinear no-blocking reduction. | [18] |
qrf.mem | The same reduction with the maximum-entropy objective. | [18] |
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. | [18], [106] |
qrf.mmi.ld | MMI quadratic reduction with the load-dependent alpha matrix, which is what lets it serve delay, multiserver and load-dependent stations. | [18] |
qrf.mmi.linear | The same load-dependent envelope with explicit equality constraints in place of the nonlinear reduction. | [18] |
qrf.bas | LP quadratic reduction over the Blocking-After-Service polytope; may derive the blocking tables from station capacities. | [18] |
qrf.bas.mmi | MMI objective over that blocking polytope; concave there, so each codebase settles on the vertex its own solver reaches. | [18] |
qrf.bas.mem | Maximum-entropy objective over the blocking polytope. | [18] |
qrf.bas.bethe | Tree-reweighted (Bethe) free entropy over the blocking polytope, the start-point-independent blocking answer. | [18], [106] |
qrf.rsrd | LP quadratic reduction under repetitive-service random-destination blocking. | [18] |
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. | [23] |
spnlp2.upper, spnlp2.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. | [71] |
spnlp1.upper, spnlp1.lower | Variant dropping the second-moment, covariance and Little's law constraints. | [71] |
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()