Package jline.api.pfqn.mva

Class Pfqn_scb

java.lang.Object

jline.api.pfqn.mva.Pfqn_scb

public final class Pfqn_scb
extends Object

Method Summary

Modifier and Type	Method	Description
static int	pfqn_minclasses(double Usum, int K, int N)	Smallest number of customer classes R consistent with an observed sum of device utilizations, obtained by inverting the demand-free Expression (6) bound of pfqn_usumbound(int, int, int), which is nondecreasing in R.
static double[]	pfqn_scb(Matrix L, int N)	Bracket on the total throughput and the per-device utilizations of the UNKNOWN multiclass system whose single-class counterpart has demand vector L at population N.
static double	pfqn_scbgap(int N, int K)	Full single-class aggregation, dominating classes allowed: r = N, undominated = false.
static double	pfqn_scbgap(int N, int K, int r, boolean undominated)	Demand-free bound on the relative throughput error incurred when r of the N single-customer classes of a closed product-form network are merged into one class.
static double	pfqn_usumbound(int R, int K, int N)	Largest value the sum of device utilizations sum_k U_k,R can take in any closed product-form network with R classes, K devices and N customers (their Theorem 6): sum_k U_k,R <= (H-1) + (K-H+1)(N-H+1)/(K+N-2H+1), H = min(R,K).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

pfqn_scb

public static double[] pfqn_scb(Matrix L,
 int N)

Bracket on the total throughput and the per-device utilizations of the UNKNOWN multiclass system whose single-class counterpart has demand vector L at population N.

SEMANTICS DIFFER FROM EVERY OTHER pfqn_* BOUND. aba/bjb/gb/... bracket the exact solution OF THE GIVEN MODEL; this brackets the multiclass system that the given single-class model aggregates. The lower side is therefore the EXACT single-class solution, not an approximation of it.

Theorem 2 / Corollary 2: aggregating an R-class model into its single-class counterpart can only understate performance, U_k,1 <= U_k,R and X_1 <= X_R, and Corollary 1 makes the utilization ratio uniform, U_k,R/U_k,1 = X_R/X_1 for every k. Theorem 3 (their Expression 3) caps the relative throughput error at (m-1)/(N+m-1), m = min(N,K), independently of the demands. The single-server capacity U_k,R <= 1 caps the same ratio at 1/(X_1*max(L)), tight on the paper's own worst case, so both are applied.

Parameters:

L - service demand vector of the single-class model (K x 1), queueing stations only; delay stations are not admitted because Theorem 3 rests on the delay-free balanced-network throughput

N - total population (N >= 1)

Returns:

{Xlo, Xhi, Ulo(0..K-1), Uhi(0..K-1)} flattened as a length-(2+2K) array

pfqn_scbgap

public static double pfqn_scbgap(int N,
 int K,
 int r,
 boolean undominated)

Demand-free bound on the relative throughput error incurred when r of the N single-customer classes of a closed product-form network are merged into one class. With r = N this is the full single-class aggregation error of their Theorem 3, at most 50%; with r < N it is the partial-aggregation error of their Theorem 4.

General case, dominating classes allowed (Expression 4, and with r = N Expression 3): e = (min(r,K)-1)/(r+min(r,K)-1). Undominated case, every customer placing the same total demand (Theorem 5 and its comment (3), which lifts the N = R restriction): e = r(r-1)/(min(N,K)(2r-1)), valid for r <= K only, smaller than the general case by the factor r/min(N,K) and equal to it at r = K. THE DOMAIN IS NOT COSMETIC: Theorem 5 gives each of its R classes a dedicated device, so r never exceeds K there, and comment (3) states the generalization for r < K. Evaluated at r > K the expression climbs past the general bound and past the 50% cap of Theorem 3, i.e. it stops being a bound, so r > K is refused rather than returned.

Parameters:

N - total number of customers; one per class, so also the number of classes before merging

K - number of queueing devices

r - number of classes merged into one (1 <= r <= N)

undominated - true for the tighter Theorem-5 form, valid only when no class dominates, i.e. every customer's total device demand is equal, and only for r <= K

Returns:

maximum relative throughput error, in [0,1/2]

pfqn_scbgap

public static double pfqn_scbgap(int N,
 int K)

Full single-class aggregation, dominating classes allowed: r = N, undominated = false.

pfqn_usumbound

public static double pfqn_usumbound(int R,
 int K,
 int N)

Largest value the sum of device utilizations sum_k U_k,R can take in any closed product-form network with R classes, K devices and N customers (their Theorem 6): sum_k U_k,R <= (H-1) + (K-H+1)(N-H+1)/(K+N-2H+1), H = min(R,K). The bound is demand-free and nondecreasing in R, which is what makes it invertible into a lower bound on the number of necessary classes; see pfqn_minclasses(double, int, int).

Parameters:

R - number of single-customer classes (1 <= R <= N)

K - number of devices

N - total number of customers

Returns:

upper bound on sum_k U_k,R

pfqn_minclasses

public static int pfqn_minclasses(double Usum,
 int K,
 int N)

Smallest number of customer classes R consistent with an observed sum of device utilizations, obtained by inverting the demand-free Expression (6) bound of pfqn_usumbound(int, int, int), which is nondecreasing in R. Only measured quantities are needed, so the answer is available BEFORE any class-specific demand has been characterized. An upper bound on R is meaningless and none is returned.

The paper's example: K = 2 devices, N = 3 customers, measured sum_k U_k = 1.6. A single class admits at most 2N/(N+1) = 1.5, so Rmin = 2.

Parameters:

Usum - measured sum of device utilizations

K - number of devices

N - total number of customers

Returns:

least R in 1..N with pfqn_usumbound(R,K,N) >= Usum; -1 when Usum exceeds min(N,K) and so is unattainable by ANY class structure