LINE Solver
MATLAB API documentation
Loading...
Searching...
No Matches
solver_ba_analyzer.m
1function [Q,U,R,T,C,X,lG,runtime,iter] = solver_ba_analyzer(sn, options)
2% [Q,U,R,T,C,X,LG,RUNTIME,ITER] = SOLVER_BA_ANALYZER(QN, OPTIONS)
3
4% Copyright (c) 2012-2026, Imperial College London
5% All rights reserved.
6
7T0=tic;
8iter = 1;
9Q = []; U = [];
10R = []; T = [];
11C = []; X = [];
12lG = NaN;
13
14line_debug('MVA bound analyzer starting: method=%s, nclasses=%d, njobs=%s', options.method, sn.nclasses, mat2str(sn.njobs));
15
16switch options.method
17 case {'lr.upper','lr.lower'}
18 % LP-based Linear Reduction bound via mapqn_bnd_lr_pf, distinct from
19 % 'qrf.mmi.linear'. see _kb/06-solver-catalog.md for rationale
20 line_debug('Using LP linear-reduction bound (%s)', options.method);
21 if sn.nclasses ~= 1 || sn.nclosedjobs <= 0
22 line_error(mfilename,'Method lr supports single-class closed networks only.');
23 end
24 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
25 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
26 end
27 if any(sn.sched == SchedStrategy.INF)
28 line_error(mfilename,'Method lr does not support delay (infinite-server) stations.');
29 end
30 if strcmp(options.method,'lr.lower'), sense = 'min'; else, sense = 'max'; end
31 V = sn.visits{1}(:);
32 N = sn.njobs(1);
33 M = sn.nstations;
34 params = struct();
35 params.M = M;
36 params.N = N;
37 params.mu = sn.rates(:,1);
38 totV = sum(V);
39 params.r = repmat((V(:)')/totV, M, 1);
40 params.verbose = false;
41 U = zeros(M,1);
42 for ti = 1:M
43 res = mapqn_bnd_lr_pf(params, ti, sense);
44 U(ti,1) = res.objective;
45 end
46 % Chain throughput implied by the bounded utilizations (U_i = X*V_i/mu_i)
47 cand = U(:,1) .* sn.rates(:,1) ./ V;
48 cand = cand(isfinite(cand));
49 if isempty(cand), X(1,1) = 0; else, X(1,1) = min(cand); end
50 T(:,1) = V * X(1,1);
51 if strcmp(sense,'max')
52 R(:,1) = (1 ./ sn.rates(:,1)) * N;
53 else
54 R(:,1) = 1 ./ sn.rates(:,1);
55 end
56 Q(:,1) = T(:,1) .* R(:,1);
57 D = V ./ sn.rates(:,1);
58 if strcmp(sense,'max'), C(1,1) = N*sum(D); else, C(1,1) = sum(D); end
59 runtime=toc(T0);
60 case 'aba.upper'
61 line_debug('Using ABA upper bound');
62 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
63 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
64 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
65 end
66 V = sn.visits{1}(:);
67 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
68 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
69 Dmax = max(D);
70 N = sn.nclosedjobs;
71 C(1,1) = Z + N * sum(D);
72 X(1,1) = min( 1/Dmax, N / (Z + sum(D)));
73 T(:,1) = V .* X(1,1);
74 R(:,1) = 1 ./ sn.rates * N;
75 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
76 Q(:,1) = T(:,1) .* R(:,1);
77 U(:,1) = T(:,1) ./ sn.rates;
78 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
79 lG = - N*log(X(1,1)); % approx
80 end
81 runtime=toc(T0);
82 case 'aba.lower'
83 line_debug('Using ABA lower bound');
84 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
85 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
86 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
87 end
88 V = sn.visits{1}(:);
89 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
90 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
91 N = sn.nclosedjobs;
92 X(1,1) = N / (Z + N*sum(D));
93 C(1,1) = Z + sum(D);
94 T(:,1) = V .* X(1,1);
95 R(:,1) = 1 ./ sn.rates;
96 Q(:,1) = T(:,1) .* R(:,1);
97 U(:,1) = T(:,1) ./ sn.rates;
98 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
99 lG = - N*log(X(1,1)); % approx
100 end
101 runtime=toc(T0);
102 case 'bjb.upper'
103 line_debug('Using BJB upper bound');
104 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
105 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
106 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
107 end
108 V = sn.visits{1}(:);
109 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
110 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
111 Dmax = max(D);
112 N = sn.nclosedjobs;
113 Xaba_upper_1 = min( 1/Dmax, (N-1) / (Z + sum(D)));
114 Xaba_lower_1 = (N-1) / (Z + (N-1)*sum(D));
115 C(1,1) = (Z+sum(D)+max(D)*(N-1-Z*Xaba_lower_1));
116 X(1,1) = min(1/Dmax, N / (Z+sum(D)+mean(D)*(N-1-Z*Xaba_upper_1)));
117 T(:,1) = V .* X(1,1);
118 % RN undefined in the literature so we use ABA upper
119 R(:,1) = 1 ./ sn.rates * N;
120 %RN = 0*TN;
121 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * D+ max(D) ./ V(sn.sched ~= SchedStrategy.INF) .* (N-1-Z*Xaba_lower_1) / (sn.nstations - sum(sn.sched == SchedStrategy.INF));
122 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
123 Q(:,1) = T(:,1) .* R(:,1);
124 U(:,1) = T(:,1) ./ sn.rates;
125 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
126 lG = - N*log(X(1,1)); % approx
127 end
128 runtime=toc(T0);
129 case 'bjb.lower'
130 line_debug('Using BJB lower bound');
131 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
132 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
133 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
134 end
135 V = sn.visits{1}(:);
136 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
137 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
138 Dmax = max(D);
139 N = sn.nclosedjobs;
140 Xaba_upper_1 = min( 1/Dmax, (N-1) / (Z + sum(D)));
141 Xaba_lower_1 = (N-1) / (Z + (N-1)*sum(D));
142 C(1,1) = (Z+sum(D)+mean(D)*(N-1-Z*Xaba_upper_1));
143 X(1,1) = N / (Z+sum(D)+max(D)*(N-1-Z*Xaba_lower_1));
144 T(:,1) = V .* X(1,1);
145 % RN undefined in the literature so we use ABA lower
146 R(:,1) = 1 ./ sn.rates;
147 %RN = 0*TN;
148 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * 1 ./ sn.rates(sn.sched ~= SchedStrategy.INF,1) + mean(D) ./ V(sn.sched ~= SchedStrategy.INF) .* (N-1-Z*Xaba_upper_1) / (sn.nstations - sum(sn.sched == SchedStrategy.INF));
149 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
150 Q(:,1) = T(:,1) .* R(:,1);
151 U(:,1) = T(:,1) ./ sn.rates;
152 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
153 lG = - N*log(X(1,1)); % approx
154 end
155 runtime=toc(T0);
156 case 'pb.upper'
157 line_debug('Using PB upper bound');
158 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
159 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
160 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
161 end
162 V = sn.visits{1}(:);
163 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
164 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
165 Dmax = max(D);
166 N = sn.nclosedjobs;
167 Xaba_upper_1 = min( 1/Dmax, (N-1) / (Z + sum(D)));
168 Xaba_lower_1 = (N-1) / (Z + (N-1)*sum(D));
169 Dpb2 = sum(D.^2)/sum(D);
170 DpbN = sum(D.^N)/sum(D.^(N-1));
171 C(1,1) = (Z+sum(D)+DpbN*(N-1-Z*Xaba_lower_1));
172 X(1,1) = min(1/Dmax, N / (Z+sum(D)+Dpb2*(N-1-Z*Xaba_upper_1)));
173 T(:,1) = V .* X(1,1);
174 % RN undefined in the literature so we use ABA upper
175 R(:,1) = 1 ./ sn.rates * N;
176 %RN = 0*TN;
177 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * 1 ./ sn.rates(sn.sched ~= SchedStrategy.INF,1) + (D.^N/sum(D.^(N-1))) ./ V(sn.sched ~= SchedStrategy.INF) * (N-1-Z*Xaba_upper_1);
178 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
179 Q(:,1) = T(:,1) .* R(:,1);
180 U(:,1) = T(:,1) ./ sn.rates;
181 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
182 lG = - N*log(X(1,1)); % approx
183 end
184 runtime=toc(T0);
185 case 'pb.lower'
186 line_debug('Using PB lower bound');
187 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
188 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
189 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
190 end
191 V = sn.visits{1}(:);
192 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
193 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
194 Dmax = max(D);
195 N = sn.nclosedjobs;
196 Xaba_upper_1 = min( 1/Dmax, (N-1) / (Z + sum(D)));
197 Xaba_lower_1 = (N-1) / (Z + (N-1)*sum(D));
198 Dpb2 = sum(D.^2)/sum(D);
199 DpbN = sum(D.^N)/sum(D.^(N-1));
200 C(1,1) = (Z+sum(D)+Dpb2*(N-1-Z*Xaba_upper_1));
201 X(1,1) = N / (Z+sum(D)+DpbN*(N-1-Z*Xaba_lower_1));
202 T(:,1) = V .* X(1,1);
203 % RN undefined in the literature so we use ABA lower
204 R(:,1) = 1 ./ sn.rates;
205 %RN = 0*TN;
206 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * 1 ./ sn.rates(sn.sched ~= SchedStrategy.INF,1) + (D.^2/sum(D)) ./ V(sn.sched ~= SchedStrategy.INF) * (N-1-Z*Xaba_upper_1);
207 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
208 Q(:,1) = T(:,1) .* R(:,1);
209 U(:,1) = T(:,1) ./ sn.rates;
210 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
211 lG = - N*log(X(1,1)); % approx
212 end
213 runtime=toc(T0);
214 case 'sb.upper'
215 line_debug('Using SB upper bound');
216 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
217 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
218 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
219 end
220 if any(sn.sched == SchedStrategy.INF)
221 line_error(mfilename,'Unsupported method for a model with infinite-server stations.');
222 end
223 V = sn.visits{1}(:);
224 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
225 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
226 N = sn.nclosedjobs;
227 A3 = sum(D.^3);
228 A2 = sum(D.^2);
229 A1 = sum(D);
230 Dmax = max(D);
231 C(1,1) = Z+A1+(N-1)*(A1*A2+A3)/(A1^2+A2);
232 X(1,1) = min([1/Dmax,N / (Z+A1+(N-1)*(A1*A2+A3)/(A1^2+A2))]);
233 T(:,1) = V .* X(1,1);
234 % RN undefined in the literature so we use ABA lower
235 R(:,1) = 1 ./ sn.rates;
236 %RN = 0*TN;
237 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * 1 ./ sn.rates(sn.sched ~= SchedStrategy.INF,1) + (D.^2/sum(D)) ./ V(sn.sched ~= SchedStrategy.INF) * (N-1-Z*Xaba_upper_1);
238 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
239 Q(:,1) = T(:,1) .* R(:,1);
240 U(:,1) = T(:,1) ./ sn.rates;
241 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
242 lG = - N*log(X(1,1)); % approx
243 end
244 runtime=toc(T0);
245 case 'sb.lower'
246 line_debug('Using SB lower bound');
247 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
248 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
249 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
250 end
251 if any(sn.sched == SchedStrategy.INF)
252 line_error(mfilename,'Unsupported method for a model with infinite-server stations.');
253 end
254 V = sn.visits{1}(:);
255 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
256 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
257 N = sn.nclosedjobs;
258 AN = sum(D.^N);
259 A1 = sum(D);
260 C(1,1) = Z+A1+(N-1)*(AN/A1)^(1/(N-1));
261 X(1,1) = N / (Z+A1+(N-1)*(AN/A1)^(1/(N-1)));
262 T(:,1) = V .* X(1,1);
263 % RN undefined in the literature so we use ABA lower
264 R(:,1) = 1 ./ sn.rates;
265 %RN = 0*TN;
266 %RN(sn.sched ~= SchedStrategy.INF,1) = NaN * 1 ./ sn.rates(sn.sched ~= SchedStrategy.INF,1) + (D.^2/sum(D)) ./ V(sn.sched ~= SchedStrategy.INF) * (N-1-Z*Xaba_upper_1);
267 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
268 Q(:,1) = T(:,1) .* R(:,1);
269 U(:,1) = T(:,1) ./ sn.rates;
270 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
271 lG = - N*log(X(1,1)); % approx
272 end
273 runtime=toc(T0);
274 case 'gb.upper'
275 line_debug('Using GB upper bound');
276 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
277 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
278 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
279 end
280 V = sn.visits{1}(:);
281 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
282 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
283 N = sn.nclosedjobs;
284 Dmax = max(D);
285 X(1,1) = min(1/Dmax, pfqn_xzgsbup(D,N,Z));
286 C(1,1) = N / pfqn_xzgsblow(D,N,Z);
287 T(:,1) = V .* X(1,1);
288 XNlow = pfqn_xzgsblow(D,N,Z);
289 k = 0;
290 for i=1:sn.nstations
291 if sn.sched(i) == SchedStrategy.INF
292 R(i,1) = 1 / sn.rates(i);
293 Q(i,1) = X(1,1) * R(i,1);
294 else
295 k = k + 1;
296 Q(i,1) = pfqn_qzgbup(D,N,Z,k);
297 R(i,1) = Q(i,1) / XNlow / V(i) ;
298 end
299 end
300 R(sn.sched == SchedStrategy.INF,1) = 1 ./ sn.rates(sn.sched == SchedStrategy.INF,1);
301 U(:,1) = T(:,1) ./ sn.rates;
302 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
303 lG = - N*log(X(1,1)); % approx
304 end
305 runtime=toc(T0);
306 case 'gb.lower'
307 line_debug('Using GB lower bound');
308 if sn.nclasses==1 && sn.nclosedjobs >0 % closed single-class queueing network
309 if any(sn.nservers(sn.sched ~= SchedStrategy.INF)>1)
310 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
311 end
312 V = sn.visits{1}(:);
313 Z = sum(V(sn.sched == SchedStrategy.INF) ./ sn.rates(sn.sched == SchedStrategy.INF));
314 D = V(sn.sched ~= SchedStrategy.INF) ./ sn.rates(sn.sched ~= SchedStrategy.INF);
315 N = sn.nclosedjobs;
316 X(1,1) = pfqn_xzgsblow(D,N,Z);
317 C(1,1) = N / pfqn_xzgsbup(D,N,Z);
318 T(:,1) = V .* X(1,1);
319 XNup = pfqn_xzgsbup(D,N,Z);
320 k = 0;
321 for i=1:sn.nstations
322 if sn.sched(i) == SchedStrategy.INF
323 R(i,1) = 1 / sn.rates(i);
324 Q(i,1) = X(1,1) * R(i,1);
325 else
326 k = k + 1;
327 Q(i,1) = pfqn_qzgblow(D,N,Z,k);
328 R(i,1) = Q(i,1) / XNup / V(i) ;
329 end
330 end
331 U(:,1) = T(:,1) ./ sn.rates;
332 U((sn.sched == SchedStrategy.INF),1) = Q((sn.sched == SchedStrategy.INF),1);
333 lG = - N*log(X(1,1)); % approx
334 end
335 runtime=toc(T0);
336 case {'mwba.upper','mwba.lower'}
337 line_debug(['Using Majumdar-Woodside robust box bound: ' options.method]);
338 if sn.nclosedjobs > 0 && ~any(isinf(sn.njobs)) % fully closed multiclass network
339 if any(sn.nservers(sn.sched ~= SchedStrategy.INF) > 1)
340 line_error(mfilename,'Unsupported method for a model with multi-server stations.');
341 end
342 [Lchain,STchain,Vchain,alpha,Nchain] = sn_get_demands_chain(sn);
343 isdelay = (sn.sched == SchedStrategy.INF);
344 Zc = sum(Lchain(isdelay,:),1); % think time per chain
345 Vq = Vchain(~isdelay,:); % queueing stations
346 Sq = STchain(~isdelay,:);
347 % map station scheduling to MW discipline codes
348 % 0=FIFO, 1=PS, 2=non-preemptive priority, 3=preemptive priority
349 qstat = find(~isdelay);
350 schedq = zeros(numel(qstat),1);
351 for kk=1:numel(qstat)
352 schedq(kk) = mwrbb_disc_code(sn.sched(qstat(kk)));
353 end
354 % per-chain priority (lower value = higher priority); use the
355 % reference class priority of each chain
356 prioc = zeros(1,sn.nchains);
357 for c=1:sn.nchains
358 inch = sn.inchain{c};
359 if isfield(sn,'refclass') && ~isempty(sn.refclass) && sn.refclass(c)>0
360 prioc(c) = sn.classprio(sn.refclass(c));
361 else
362 prioc(c) = min(sn.classprio(inch));
363 end
364 end
365 [Xlo,Xup,Wlo] = pfqn_mwrbb(Vq,Sq,Nchain,Zc,schedq,prioc);
366 if strcmp(options.method,'mwba.upper')
367 Xchain = Xup;
368 else
369 Xchain = Xlo;
370 end
371 nq = find(~isdelay);
372 Tchain = zeros(sn.nstations,sn.nchains);
373 Uchain = zeros(sn.nstations,sn.nchains);
374 Qchain = zeros(sn.nstations,sn.nchains);
375 for c=1:sn.nchains
376 for i=1:sn.nstations
377 Tchain(i,c) = Xchain(c) * Vchain(i,c);
378 Uchain(i,c) = Xchain(c) * Lchain(i,c); % utilization law
379 if isdelay(i)
380 Qchain(i,c) = Xchain(c) * Lchain(i,c);
381 else
382 kk = find(nq==i);
383 if strcmp(options.method,'mwba.upper')
384 w = Sq(kk,c); % no-contention residence
385 else
386 w = Wlo(kk,c); % Theorem 1 residence
387 end
388 Qchain(i,c) = Xchain(c) * Vchain(i,c) * w;
389 end
390 end
391 end
392 [Q,U,R,T,C,X] = sn_deaggregate_chain_results(sn, Lchain, [], STchain, Vchain, alpha, Qchain, Uchain, [], Tchain, [], Xchain);
393 lG = NaN;
394 end
395 runtime=toc(T0);
396 case {'pbh.upper','pbh.lower'}
397 line_debug(['Using PBH (Eager-Sevcik) bound: ' options.method]);
398 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
399 ba_reject_multiserver(sn, options.method);
400 [Xlo,Xhi] = pfqn_pbh(D, N, Zt, ba_level(options));
401 up = strcmp(options.method,'pbh.upper');
402 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
403 runtime=toc(T0);
404 case {'cbh.upper','cbh.lower'}
405 line_debug(['Using CBH (Dowdy) bound: ' options.method]);
406 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
407 ba_reject_multiserver(sn, options.method);
408 [Xlo,Xhi] = pfqn_cbh(D, N, Zt, ba_level(options));
409 up = strcmp(options.method,'cbh.upper');
410 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
411 runtime=toc(T0);
412 case {'pbk.upper','pbk.lower'}
413 line_debug(['Using PB(k) bound: ' options.method]);
414 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
415 ba_reject_multiserver(sn, options.method);
416 [Xlo,Xhi] = pfqn_pbk(D, N, Zt, ba_level(options));
417 up = strcmp(options.method,'pbk.upper');
418 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
419 runtime=toc(T0);
420 case {'bjbk.upper','bjbk.lower'}
421 line_debug(['Using BJB(k) bound: ' options.method]);
422 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
423 ba_reject_multiserver(sn, options.method);
424 [Xlo,Xhi] = pfqn_bjbk(D, N, Zt, ba_level(options));
425 up = strcmp(options.method,'bjbk.upper');
426 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
427 runtime=toc(T0);
428 case {'ssd.upper','ssd.lower'}
429 line_debug(['Using SSD (Suri-Dallery) multiserver bound: ' options.method]);
430 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
431 cvec = sn.nservers(sn.sched ~= SchedStrategy.INF);
432 [Xlo,Xhi] = pfqn_ssd(D, N, Zt, cvec(:));
433 up = strcmp(options.method,'ssd.upper');
434 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
435 runtime=toc(T0);
436 case {'cub.upper','mbjb.lower'}
437 % cub.upper: Kerola composite upper bound (upper-only in the paper).
438 % mbjb.lower: the multiclass Balanced Job Bounds lower bound (Kerola
439 % eq. 10) that seeds it; the natural multiclass counterpart of bjb.
440 line_debug(['Using multiclass composite/BJB bound: ' options.method]);
441 if sn.nclosedjobs <= 0 || any(isinf(sn.njobs))
442 line_error(mfilename,'Method ''%s'' supports fully closed networks only.', options.method);
443 end
444 [Lchain,STchain,Vchain,alpha,Nchain] = sn_get_demands_chain(sn);
445 isdelay = (sn.sched == SchedStrategy.INF);
446 Zc = sum(Lchain(isdelay,:),1);
447 Lq = Lchain(~isdelay,:);
448 [Xub,Xlb] = pfqn_mcub(Lq, Nchain, Zc);
449 up = strcmp(options.method,'cub.upper');
450 Xchain = up*Xub(:)' + (~up)*Xlb(:)';
451 Tchain = zeros(sn.nstations,sn.nchains);
452 Uchain = zeros(sn.nstations,sn.nchains);
453 Qchain = zeros(sn.nstations,sn.nchains);
454 for c=1:sn.nchains
455 Tchain(:,c) = Xchain(c) * Vchain(:,c);
456 Uchain(:,c) = Xchain(c) * Lchain(:,c); % utilization law
457 Qchain(:,c) = Uchain(:,c); % coarse (bound on X is primary)
458 end
459 [Q,U,R,T,C,X] = sn_deaggregate_chain_results(sn, Lchain, [], STchain, Vchain, alpha, Qchain, Uchain, [], Tchain, [], Xchain);
460 lG = NaN;
461 runtime=toc(T0);
462 case {'sib.upper','sib.lower'}
463 line_debug(['Using SIB (Srinivasan) bound: ' options.method]);
464 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
465 ba_reject_multiserver(sn, options.method);
466 if Zt > 0
467 line_error(mfilename,'Method ''%s'' supports Z=0 (no delay station) only; delay needs the SIB Section-3.2 extension.', options.method);
468 end
469 [Xlo,Xhi] = pfqn_sib(D, N, 0, ba_level(options));
470 up = strcmp(options.method,'sib.upper');
471 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, up*Xhi+(~up)*Xlo, Zt, D, up);
472 runtime=toc(T0);
473 case {'ldbcmp.lower'}
474 line_debug(['Using LD-BCMP (Anselmi-Cremonesi) lower throughput bound: ' options.method]);
475 [V,Zt,D,N] = ba_sc_demands(sn, options.method);
476 % Fixed-rate / delay parameterization (Heffes c=0); LD stations are
477 % treated as fixed-rate at their limiting demand.
478 [Xlo,~,Qhat] = pfqn_ldbcmp(D, N, Zt, zeros(numel(D),1));
479 if isnan(Xlo)
480 line_error(mfilename,'Method ''%s'' requires the asymptotic regime N >= Qhat (Qhat=%.4f > N=%d).', options.method, Qhat, N);
481 end
482 [Q,U,R,T,C,lG] = ba_fill(sn, V, N, Xlo, Zt, D, false);
483 runtime=toc(T0);
484end
485end
486
487% Single-class demand extraction for the hierarchical bound cases: returns
488% visit vector V, aggregate think time Zt, per-queue demand vector D and the
489% closed population N. Rejects non-single-class models with a clear error.
490function [V,Zt,D,N] = ba_sc_demands(sn, method)
491if sn.nclasses ~= 1 || sn.nclosedjobs <= 0
492 line_error('solver_ba_analyzer', ...
493 'Method ''%s'' supports single-class closed networks only.', method);
494end
495V = sn.visits{1}(:);
496isinf_ = (sn.sched == SchedStrategy.INF);
497Zt = sum(V(isinf_) ./ sn.rates(isinf_));
498D = V(~isinf_) ./ sn.rates(~isinf_);
499N = sn.nclosedjobs;
500end
501
502function ba_reject_multiserver(sn, method)
503if any(sn.nservers(sn.sched ~= SchedStrategy.INF) > 1)
504 line_error('solver_ba_analyzer', ...
505 'Method ''%s'' does not support multi-server stations (use ''ssd'').', method);
506end
507end
508
509function lvl = ba_level(options)
510lvl = 2;
511if isfield(options,'level') && ~isempty(options.level)
512 lvl = options.level;
513end
514end
515
516% Fill per-station [Q,U,R,T,C] from a scalar chain-throughput bound X, using
517% the same optimistic (isUpper) / pessimistic residence construction as the
518% ABA bound so conventions match across the bound families.
519function [Q,U,R,T,C,lG] = ba_fill(sn, V, N, X, Zt, D, isUpper)
520isinf_ = (sn.sched == SchedStrategy.INF);
521T = V .* X;
522if isUpper
523 R = (1 ./ sn.rates(:)) * N;
524 R(isinf_) = 1 ./ sn.rates(isinf_);
525 C = Zt + N*sum(D);
526else
527 R = 1 ./ sn.rates(:);
528 C = Zt + sum(D);
529end
530Q = T .* R;
531U = T ./ sn.rates(:);
532U(isinf_) = Q(isinf_);
533lG = - N*log(X);
534end
535
536% Map a SchedStrategy id to a Majumdar-Woodside discipline code:
537% 0=FIFO, 1=PS, 2=non-preemptive priority, 3=preemptive priority,
538% 4=ABA full-contention (discipline-independent).
539function code = mwrbb_disc_code(s)
540switch s
541 case {SchedStrategy.FCFS}
542 code = 0; % FIFO (Theorem 1 / Lemma 1)
543 case {SchedStrategy.PS, SchedStrategy.DPS, SchedStrategy.GPS, ...
544 SchedStrategy.PSPRIO, SchedStrategy.DPSPRIO, SchedStrategy.GPSPRIO}
545 code = 1; % processor sharing (Lemma 2)
546 case {SchedStrategy.HOL} % HOL == FCFSPRIO: non-preemptive priority
547 code = 2; % non-preemptive priority (Lemmas 4-5)
548 case {SchedStrategy.FCFSPRPRIO, SchedStrategy.LCFSPRPRIO}
549 code = 3; % preemptive-resume priority (Lemma 3)
550 otherwise
551 code = 4; % non-FCFS work-conserving: ABA full-contention bound
552end
553end
Generated by doxygen 1.9.8