pfqn_looping.h File Reference

Eager Looping bounds for closed multiclass product-form networks. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_looping.h:

Go to the source code of this file.

Classes
struct	line::pfqn::LoopingBounds< T >
	Return value of pfqn_looping: the throughput bracket plus its queue lengths. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::pfqn

Functions
template<class T>
LoopingBounds< T >	line::pfqn::pfqn_looping (const Matrix< T > &L, const std::vector< T > &N, const std::vector< T > &Z, double tol=1e-6, std::size_t maxiter=1000)
	Eager Looping bounds for closed multiclass product-form networks.
template<class T>
LoopingBounds< T >	line::pfqn::pfqn_looping (const Matrix< T > &L, const std::vector< T > &N)

Detailed Description

Eager Looping bounds for closed multiclass product-form networks.

Templated port of matlab/src/api/pfqn/pfqn_looping.m, cross-checked against jar/src/main/java/jline/api/pfqn/mva/Pfqn_looping.java. 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.

Arithmetic: sums, products, divisions, maxima and minima only, so each iterate is EXACT in rational arithmetic; the stopping rule selects which iterate is returned.

Definition in file pfqn_looping.h.