Normalizing constant of a closed network of ORDER-INDEPENDENT (OI) stations plus one aggregated delay, by numerical inversion of the multichain generating function (Choudhury-Leung-Whitt, J. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/pfqn/pfqn_clw.h"
#include "line/api/pfqn/pfqn_ncoi.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_clwoi.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
ClwResult< T >	line::pfqn::pfqn_clwoi (const std::vector< T > &Z, const std::vector< int > &N, const std::vector< OiRate< T > > &mu, const Matrix< T > &visits, const ClwOptions &opt)
	Normalizing constant of a closed network of ORDER-INDEPENDENT (OI) stations plus one aggregated delay, by numerical inversion of the multichain generating function (Choudhury-Leung-Whitt, J.
template<class T>
ClwResult< T >	line::pfqn::pfqn_clwoi (const std::vector< T > &Z, const std::vector< int > &N, const std::vector< OiRate< T > > &mu, const Matrix< T > &visits)
	Overload with the CLW default parameters.
template<class T>
ClwResult< T >	line::pfqn::pfqn_clwoi (const std::vector< T > &Z, const std::vector< int > &N, const std::vector< OiRate< T > > &mu)
	Overload with unit visits.

Detailed Description

Normalizing constant of a closed network of ORDER-INDEPENDENT (OI) stations plus one aggregated delay, by numerical inversion of the multichain generating function (Choudhury-Leung-Whitt, J.

ACM 42(5):935-970, 1995).

Templated port of matlab/src/api/pfqn/pfqn_clwoi.m. It is the OI counterpart of pfqn_clw_lld and the transform counterpart of the convolution routine pfqn_ncoi; both return the same G(N) and differ only in cost.

G(z) = exp( sum_r Z_r z_r ) prod_i F_i(z), F_i(z) = sum_n Phi_i(n) z^n,

with Phi_i the v-weighted balanced-fairness balance function of station i, mu_i(n) Phi_i(n) = sum_{r: n_r>0} v_{i,r} Phi_i(n - e_r).

Unlike a load-dependent station, whose factor collapses to a function of the single argument sum_r rho_{ri} z_r, an OI station factor depends on the whole vector z, because mu_i(n) depends on the occupancy only through its SUPPORT supp(n) = {r : n_r > 0}. It is nevertheless rational and available in closed form. Splitting the count lattice by support, on which mu_i(n) = mu_{i,S} is constant, and writing F_{i,S} for the part of F_i carried by the states of support S, the balance recursion gives

( mu_{i,S} - sum_{r in S} v_{i,r} z_r ) F_{i,S}(z) = sum_{r in S} v_{i,r} z_r F_{i,S minus r}(z), F_{i,{}} = 1, F_i(z) = sum_S F_{i,S}(z),

since removing a class-r job from a state of support S lands on support S when n_r >= 2 and on S minus r when n_r = 1. The singularities are the hyperplanes sum_{r in S} v_{i,r} z_r = mu_{i,S}, one per support, in place of the single pole x = c_i of the load-dependent case; a load-independent single-server queue (mu_{i,S} = 1) gives back 1/(1 - sum_r v_{i,r} z_r).

The restrictive static scaling of eqs. 5.41-5.46 is reused verbatim on the EXPANDED constraint matrix that lists one row per (station, nonempty support) pair with unit-pole intensities v_{i,r}/mu_{i,S}, after dropping the rows dominated by a superset of no larger rate. Each surviving row is a binding singular hyperplane, so the contour stays inside the domain of analyticity exactly as the single-pole normalization does for pfqn_clw_lld.

SCOPE. The rates must be support-only, mu_i(n) = mu_i(supp(n)), which is the defining property of an OI station and what makes the transform a finite rational function. Every rate handle is verified EXHAUSTIVELY on the count lattice 0 < n <= N before the inversion, at prod_r (N_r+1) evaluations per station (below the contour points spent afterwards), and a state whose rate differs from that of its support is an error naming that state: a rate that varies inside a support is a general balanced-fairness station and belongs to pfqn_ncoi. It is refused rather than warned-and-inverted because the inversion would otherwise return a plausible but wrong G(N). A non-empty swap graph breaks the closure of Phi on the count vector altogether and requires the microstate routine pfqn_pas_nc.

Arithmetic: TRANSCENDENTAL, double and Real only, for the same reason as the rest of the CLW family (the contour radius 10^{-gamma/(2 l K)} is not in the field of the inputs). Accuracy against the exact pfqn_ncoi is ~1e-9 for two chains and ~1e-8 for three, i.e. the accuracy the method itself has.

COST. prod_r 2 l_r N_r contour points, each costing O(M R 2^R), against O(M prod_r (N_r+1)(N_r+2)/2) for pfqn_ncoi: linear rather than quadratic in each population, so it wins on large populations with few chains and loses as the chain count grows. Unlike pfqn_ncoi it returns G at the single population N; throughputs need the R additional inversions at N - e_r.

Definition in file pfqn_clwoi.h.

Namespaces

Functions

Detailed Description