pfqn_clust.h File Reference

de Souza e Silva-Lavenberg-Muntz Clustering Approximation (CA). More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_amva_common.h"
#include "line/api/pfqn/pfqn_bs.h"
#include "line/api/pfqn/pfqn_pam.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_clust.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Enumerations
enum class	line::pfqn::ClustInner { line::pfqn::Linearizer , line::pfqn::ProportionalEstimation }
	Which algorithm runs inside a subnetwork. More...

Functions
template<class T>
AmvaResult< T >	line::pfqn::pfqn_clust (const Matrix< T > &L, const std::vector< T > &N, const std::vector< T > &Z, const std::vector< std::vector< std::size_t > > &subnets, const std::vector< std::vector< std::size_t > > &localclasses, ClustInner inner=ClustInner::Linearizer, double tol=1e-6, std::size_t maxiter=1000)
	de Souza e Silva-Lavenberg-Muntz Clustering Approximation (CA).
template<class T>
AmvaResult< T >	line::pfqn::pfqn_clust (const Matrix< T > &L, const std::vector< T > &N, const std::vector< T > &Z)
template<class T>
AmvaResult< T >	line::pfqn::pfqn_clust (const Matrix< T > &L, const std::vector< T > &N)

Detailed Description

de Souza e Silva-Lavenberg-Muntz Clustering Approximation (CA).

Templated port of matlab/src/api/pfqn/pfqn_clust.m, cross-checked against jar/src/main/java/jline/api/pfqn/mva/Pfqn_clust.java. E. de Souza e Silva, S. S. Lavenberg, R. R. Muntz, "A clustering approximation technique for queueing network models with a large number of chains", IEEE Trans. Computers C-35(5), 1986. The network is covered by subnetworks whose union is the whole network but which need not be disjoint. Every class visiting a subnetwork S is either LOCAL to S, and is then solved inside it, or FOREIGN, and is then seen only through the utilization it leaves behind. Each subnetwork is solved by an ordinary approximate MVA algorithm with two replacements: the complement of S is collapsed into a per-class delay P_c and the foreign classes into a per-centre utilization U_k,

X_c(N) = N_c / (sum_{k in S} R_ck(N) + Z_c + P_c), Q_k(N) = [sum_{c in LC(S)} R_ck(N) X_c(N) + U_k] / (1 - U_k).

Choosing the PE algorithm for every subnetwork reproduces global PE exactly, so the useful setting is Linearizer inside, PE outside: the cost then sits between pfqn_bs and pfqn_linearizer, which is the point of the method.

When no decomposition is supplied the criterion of the paper is applied automatically: the cheap PAMB estimate (pfqn_pam) of the centre utilizations is taken, every class is attached to the centre where it loads the most, classes sharing that centre form one cluster, and the subnetwork of a cluster is the set of centres its classes visit. The answer depends on the decomposition, which is why it is an input.

The name avoids pfqn_ca, which is the exact convolution algorithm.

Arithmetic: field operations only, so each iterate is EXACT in rational arithmetic; both the outer and the inner loop stop on a tolerance.

Definition in file pfqn_clust.h.