pfqn_harel_bounds.h File Reference

Harel-Namn-Sturm throughput bounds for a single-class closed network. More...

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

Include dependency graph for pfqn_harel_bounds.h:

Go to the source code of this file.

Classes
struct	line::pfqn::HarelBoundsResult< T >
	Return value of pfqn_harel_bounds, mirroring Ret.pfqnHarelBounds. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
T	line::pfqn::pfqn_harel_lb (const std::vector< T > &rho, int N, const T &Z)
	Lower bound alone.
template<class T>
T	line::pfqn::pfqn_harel_lb (const std::vector< T > &rho, int N)
	Zero think time.
template<class T>
T	line::pfqn::pfqn_harel_ub (const std::vector< T > &rho, int N, int n, const T &Z)
	Upper bound extrapolated from the exact throughput at population n.
template<class T>
T	line::pfqn::pfqn_harel_ub (const std::vector< T > &rho, int N, int n)
	Zero think time.
template<class T>
HarelBoundsResult< T >	line::pfqn::pfqn_harel_bounds (const std::vector< T > &rho, int N, const T &Z, int maxUB)
	Both bounds, plus the exact throughputs the upper bounds extrapolate from.
template<class T>
HarelBoundsResult< T >	line::pfqn::pfqn_harel_bounds (const std::vector< T > &rho, int N)
	Zero think time, default extrapolation ceiling min(N, 7).

Detailed Description

Harel-Namn-Sturm throughput bounds for a single-class closed network.

Templated port of jar/src/main/java/jline/api/pfqn/Pfqn_harel_bounds.java. MATLAB has no counterpart, so the JAR is the reference.

These are the SHARP bounds of the paper, distinct from the sb family already in solver_ba_analyzer: sb uses only the first three power sums in closed form, whereas this family evaluates the normalizing constant exactly at small populations and extrapolates from it. Both cite Harel1999; they are different results in it and neither subsumes the other.

Write A_i = sum_j rho_j^i for the power sums of the relative utilizations. Then

G(n) = h_n(rho), the complete homogeneous symmetric polynomial, TH(n) = G(n-1) / G(n), the exact throughput at population n, LB = N / (A_1 + (N-1) (A_N/A_1)^{1/(N-1)}), UB(n) = N / (A_1 + ((N-1)/(n-1)) (n/TH(n) - A_1)), 2 <= n <= N.

G(n) IS the normalizing constant of the closed load-independent network at population n, which is the oracle the port is tested against: G(n) computed here must equal pfqn_ca on the same demands.

TWO DELIBERATE NOTES ON THE PORT.

First, the reference hardcodes G(0)..G(7) as expanded polynomials in the power sums and REFUSES n > 7 with "G(n) polynomial not available". Those expansions are the Newton-Girard recurrence

n G(n) = sum_{i=1..n} A_i G(n-i)

unrolled by hand. The port evaluates the recurrence instead: it agrees term for term with the reference at every n <= 7, needs no table, and is EXACT-CAPABLE where the expanded form needs pow. The n <= 7 refusal on the PUBLIC entry points is nevertheless kept, so the contract callers see is the reference's; only the internal ceiling is gone. See _kb/03-api-layer.md.

Second, the reference refuses a nonzero think time rather than folding it in, because the bounds are derived for a network with no terminal population. That refusal is reproduced: silently dropping Z would return a bound that does not bound.

Arithmetic: G and UB are EXACT-CAPABLE. LB needs an (N-1)-st root and is TRANSCENDENTAL for N > 2; at N <= 2 the root is trivial and LB is exact too.

Definition in file pfqn_harel_bounds.h.