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