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
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.

It is built on the convolution identity of Zahorjan (1980)

Q_jk(N - 1_c) = [X_j^{+k}(N - 1_c) / X_j(N)] Q_jk(N),

with X_j^{+k}(N - 1_c) estimated from the level-0 multiple-class PBH upper bound B_j and X_j(N) from the optimistic response time R_j^(opt). 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 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.