Package jline.api.pfqn.mva

Class Pfqn_looping

java.lang.Object
jline.api.pfqn.mva.Pfqn_looping
public final class Pfqn_looping extends Object
Eager Looping approximate MVA bounds.

D. L. Eager, "Bounding Algorithms for Queueing Network Models of Computer Systems", Ph.D. thesis, Tech. Rept. CSRG-156, University of Toronto, 1984. Looping supplies the initial pessimistic and optimistic estimates that the multiple-class performance bound hierarchy starts from, so it carries a pair of bounds rather than a single fixed point.

A HEAP H_j is the class-j congestion that the current queue-length LOWER BOUNDS have not yet accounted for; it is charged back at the pessimistic inflation factor V_c = max_k D_ck or the optimistic one L_c = min_k D_ck, which are the largest and smallest delays one customer can inflict. The whole bracket rests on Q_jk(N - 1_c) being a lower bound, which is why the queue lengths are seeded from Little's law at the station,

Q_jk(N - 1_c) = X_j(N - 1_c) R_jk(N - 1_c) >= n_j D_jk / (Z_j + U_j),

with R_jk >= D_jk and U_j any UPPER bound on R_j(N - 1_c): the level-0 PBH bound B_j, or the pessimistic R_j(N) of the current iterate, whichever is smaller, since response time is nondecreasing in the population. Each iterate lowers R^(pess), which raises the seed, which lowers R^(pess) again, so the refinement is monotone and every iterate is a bound. It previously refined the queue lengths through the convolution identity of Zahorjan (1980), Q_jk(N - 1_c) = [X_j(N - 1_c)/X_j(N)] Q_jk(N), applied with one class-level ratio at every station; that is not a per-station under-estimate, so the queue lengths stopped being lower bounds, the heaps clamped to zero and R^(opt) collapsed onto R^(pess). The level-0 multiple-class PBH bounds on the mean response time are

J_j(n) = sum_k D_jk,   B_j(n) = sum_k D_jk + (sum(n) - 1) max_k D_jk,

i.e. an arriving customer queues behind nobody, respectively behind every other customer in the network at its own worst centre.