pfqn_hst.h File Reference

Operational sensitivity of throughput to homogeneous-service-time (HST) violations, and the constrained worst case (Suri 1983). More...

#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <vector>
#include "line/api/pfqn/pfqn_rgf.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for pfqn_hst.h:

Go to the source code of this file.

Classes
struct	line::pfqn::HstResult< T >
	Everything the HST certificate reports about one station. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
HstResult< T >	line::pfqn::pfqn_hst (const std::vector< T > &L, int N, const T &Z, std::size_t ist)
	Operational sensitivity of throughput to homogeneous-service-time (HST) violations, and the constrained worst case (Suri 1983).
template<class T>
HstResult< T >	line::pfqn::pfqn_hst (const std::vector< T > &L, int N, const T &Z)
	MATLAB default: the bottleneck station, argmax L.
template<class T>
HstResult< T >	line::pfqn::pfqn_hst (const std::vector< T > &L, int N)
	MATLAB default: no think time and the bottleneck station.

Detailed Description

Operational sensitivity of throughput to homogeneous-service-time (HST) violations, and the constrained worst case (Suri 1983).

Templated port of matlab/src/api/pfqn/pfqn_hst.m.

A robustness certificate for a single-class closed product-form solution: how far the predicted throughput can move when the HST assumption fails at one station. That assumption states that the mean service time at station i does not depend on the queue length there. Suri (1983) perturbs it to S_i(n) = S_i (1 + a_n), one relative deviation per queue-length level n, and shows (eq. 3.11) that to first order

(1/X0) dX0/da_n = c_n = P(n_i >= n+1)/u_i - P(n_i >= n),

with u_i = L_i X0 the station utilization and the marginals taken from the product-form solution, P(n_i >= n) = L_i^n G(N-n)/G(N). The naive certificate |dX0/X0| <= (sum_n |c_n|) d follows from |a_n| <= d alone, and by Lemma 3.1 that total equals Q_i(N) - Q_i(N-1).

That bound is loose because the deviations are not free: an operationally consistent perturbation must leave the OBSERVED mean service time unchanged, sum_n p_n a_n = 0 with p_n = P(n_i = n). The constrained problem (P1),

max |sum_n c_n a_n| s.t. |a_n| <= d, sum_n p_n a_n = 0,

is a one-constraint linear program, solved here exactly: its optimum sets a_n = +/- d according to whether the ratio c_n / p_n exceeds a threshold, with at most one fractional coordinate. On the paper's Figure 1 system it collapses 0.831 d to 0.102 d.

Reference: R. Suri, "Robustness of Queuing Network Formulas", JACM 30(3):564-594, 1983 (eq. 3.11, Lemma 3.1, problem (P1)).

Arithmetic: TRANSCENDENTAL. The marginals come from pfqn_rgf, whose recursion is carried in the log domain.

Definition in file pfqn_hst.h.