api.fes

mexify_fes

@brief MATLAB Coder script to generate MEX functions for fes_ module.

This script generates MEX (MATLAB Executable) versions of FES (Flow Equivalent Server) functions for improved performance.

Skipped functions (Coder-incompatible):

fes_build_isolated - Uses sn struct + NodeType / GlobalConstants: OOP enums; relies on dynamic typing.
fes_compute_throughputs - Uses a dynamic cell-array BFS queue,: try/catch around pfqn_mva and a cell-of-vector output.
fes_validate - Uses sn struct + NodeType OOP enum and: dynamic isfield()/sprintf() error reporting.

See also CODER, CODER.CONFIG, CODER.TYPEOF, CODEGEN.

fes_compute_metrics(L, mi, isDelay, cutoffs, options)

[QTABLE, UTABLE] = FES_COMPUTE_METRICS(L, MI, ISDELAY, CUTOFFS, OPTIONS)

Per-station metrics of the ISOLATED subnetwork at every population state, the companion of FES_COMPUTE_THROUGHPUTS.

FES_COMPUTE_THROUGHPUTS returns the aggregate throughput X(n) that becomes the flow-equivalent server’s rate. That is all the REDUCED model needs, but it is not enough to report the collapsed stations’ own metrics: those are recovered by conditioning on the FES population,

E[Q_i] = sum_n P(N_fes = n) * Q_i(n),

which is the Chandy-Herzog-Woo hierarchical decomposition and is EXACT when the subnetwork is product-form. This function supplies the Q_i(n) and U_i(n) that the sum is taken over.

Input:: L - (M_sub x K) service demands of the isolated subnetwork mi - (1 x M_sub) servers per station, Inf at a Delay isDelay - (1 x M_sub) logical, true at a Delay cutoffs - (1 x K) per-class population cutoffs options - struct with optional field .verbose

Output (each a cell array indexed by LJD_LINEARIZE, as FES_COMPUTE_THROUGHPUTS indexes its scaling table):

Qtable{idx} - (M_sub x K) queue lengths at that population Utable{idx} - (M_sub x K) utilizations

Throughput needs no table: flow through a station is fixed by the ROUTING, so the caller derives it from the original model’s visit ratios and the chain throughput the reduced solve already reports.

fes_map_solve(FES, thinkMAP, N)

Solves the reduced model made of a delay and a load-dependent MAP flow-equivalent server

Closes the aggregation of Section 5.2.1 of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011. Once a subnetwork has been replaced by the load-dependent MAP of fes_map_aggregate, the model left is a delay holding the think times and one station, which is a finite level-dependent quasi birth-death process: level k is the number of jobs held by the flow-equivalent server and N-k jobs are thinking. The chain is the same block bidiagonal pair used to measure the inter-departure times, now read as a generator rather than as a MAP, so the delay is a station whose process is scaled by the number of jobs it holds and the marked transitions are the arrivals into the flow-equivalent server.

The think time may itself be a MAP, which is how Section 5.3.1 models a bounded flash crowd: burstiness in the stream of requests is carried by (Z0,Z1) and the rates scale with the population at the delay.

Parameters:

FES – Flow-equivalent server, one MAP per level, from fes_map_aggregate
thinkMAP – Think time process {Z0,Z1}; use map_exponential(Z) for
N – Number of jobs in the closed model

Returns:

XN – System throughput RN: Mean response time of the aggregated subnetwork, N/XN-E[Z] QN: Mean number of jobs held by the flow-equivalent server pk: Distribution of the jobs held by the flow-equivalent server,

Examples

[XN,RN,QN,pk] = fes_map_solve(FES, thinkMAP, N)

fes_map_moments(T0, T1, options)

Computes the first three moments, the lag-1 joint moment and the index of dispersion of a MAP without forming (-T0)^-1

Evaluates equations (4), (5) and (7) of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011, on the block bidiagonal MAP returned by fes_map_interdeparture. The inverse (-T0)^-1 is dense even when T0 is sparse, so it is never formed: the moments are obtained by the vector recursion v_{k+1} = v_k (-T0)^-1, each step being a sparse linear solve. Method ‘euler’ replaces the solve by the quadrature

v (-T0)^-1 = v * int_0^inf exp(T0 t) dt

of Section 5.2.2, integrated by the trapezoid rule with the Euler approximation exp(T0 dt) ~ I + T0 dt and step dt below the inverse of the largest diagonal element in absolute value, as in the uniformization method. Method ‘ssolve’ is the default because it is exact and faster; ‘euler’ reproduces the reference implementation of the paper.

Parameters:

T0 – Hidden transitions of the MAP
T1 – Marked transitions of the MAP
options – (Optional) struct with fields method (‘ssolve’ or

Returns:

e1 – Mean inter-departure time e2: Second moment of the inter-departure times e3: Third moment of the inter-departure times e11: Joint moment E[X_k X_{k+1}] of consecutive samples idc: Asymptotic index of dispersion

Examples

[e1,e2,e3,e11,idc] = fes_map_moments(T0,T1)
[e1,e2,e3,e11,idc] = fes_map_moments(T0,T1,options)

fes_map_levels(FES, n, mi)

Expands a MAP into the per-level processes of a load-dependent server

A flow-equivalent server is described by one MAP (F0^k,F1^k) per population level k=1..n. This function accepts either that cell array, which it validates and returns unchanged, or a single MAP {F0,F1} which it replicates over the levels. When the number of servers mi is given, the replicated MAP is scaled by min(k,mi), which reproduces a queue with mi servers and, for mi=Inf, a delay station serving at rate k*mu. The scaling is exact for exponential service and is the load-dependent rate approximation otherwise.

Parameters:

FES – Either {F0,F1} or a cell array with FES{k}={F0,F1}
n – Number of levels required
mi – (Optional) number of servers, Inf for a delay, default 1

Returns:

FESlev – Cell array with FESlev{k}={F0,F1} for k=1..n

See also

fes_map_interdeparture()

Examples

FESlev = fes_map_levels(FES, n)
FESlev = fes_map_levels(FES, n, mi)

fes_map_interp_edge(h1, h2, del1, del2)

Noncentered three-point endpoint slope with monotonicity clamps

Implements the endpoint rule of de Boor used by shape-preserving cubic Hermite interpolation: the three-point estimate is set to zero when it disagrees in sign with the adjacent secant, and is clipped to three times that secant when the two secants disagree in sign and the estimate is too steep.

Parameters:

h1 – Width of the interval adjacent to the endpoint
h2 – Width of the next interval
del1 – Secant slope adjacent to the endpoint
del2 – Secant slope of the next interval

Returns:

d – Endpoint derivative

See also

fes_map_interp()

Examples

d = fes_map_interp_edge(h1, h2, del1, del2)

fes_map_interp(x, y, xq)

Monotone piecewise cubic Hermite interpolation

Interpolates the descriptors of a MAP flow-equivalent server between the populations at which they were evaluated. Fritsch and Carlson slopes are used, with the noncentered three-point endpoint rule of de Boor, so the interpolant never overshoots and a monotone sequence of throughputs stays monotone. The algorithm is written out rather than delegated to the built-in pchip so that the MATLAB, Java, Python and C++ ports return identical values.

Parameters:

x – Sample abscissae, strictly increasing
y – Sample values, one row per abscissa
xq – Query abscissae

Returns:

yq – Interpolated values, one row per query point

See also

fes_map_aggregate()

Examples

yq = fes_map_interp(x, y, xq)

fes_map_interdeparture(MAPs, FES, n, mi)

Builds the MAP (T0,T1) of the inter-departure times of a closed subnetwork made of one MAP station and one MAP flow-equivalent server

Implements the block bidiagonal construction of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011, Section 5.2.2. The subnetwork holds n jobs that circulate between a station with MAP service (D0,D1) and a flow-equivalent server whose MAP (F0^k,F1^k) depends on the number k of jobs it holds. Level k of (T0,T1) is the population of the flow-equivalent server, so the station holds n-k jobs and both processes may be load dependent. Marked transitions are the completions of the station, which are the departures fed to the rest of the model.

T0 = [ D0 (x) I 0 0 0 I (x) F1^1 D0 (+) F0^1 0 0 … … … … 0 I (x) F1^{n-1} D0 (+) F0^{n-1} 0 0 0 I (x) F1^n I (x) F0^n ]

T1 = superdiagonal blocks D1 (x) I, last block row zero

Parameters:

MAPs – Service process of the station, either {D0,D1} or a cell
FES – Flow-equivalent server, either {F0,F1} or a cell array
n – Number of jobs circulating in the subnetwork
mi – (Optional) [mi_station mi_fes] servers used to scale a load

Returns:

T0 – Hidden transitions of the inter-departure MAP, sparse T1: Marked transitions of the inter-departure MAP, sparse

Examples

[T0,T1] = fes_map_interdeparture(MAPs, FES, n)
[T0,T1] = fes_map_interdeparture(MAPs, FES, n, mi)

fes_map_grid(n, nhead, ntail)

Returns the population levels at which the inter-departure MAP is evaluated

Fitting one MAP per population is wasteful because the processes of neighbouring populations are similar. Section 5.2.2 of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011, evaluates the first ten populations and ten further equispaced points, which is what this function returns. Populations up to the grid size are returned in full, so no approximation is introduced on small models.

Parameters:

n – Largest population
nhead – (Optional) leading populations kept in full, default 10
ntail – (Optional) equispaced points above them, default 10

Returns:

grid – Sorted vector of populations to evaluate

See also

fes_map_aggregate()

Examples

grid = fes_map_grid(n)
grid = fes_map_grid(n, nhead, ntail)

fes_map_euler(v, T0, dt, tol, iter_max)

Integrates v*int_0^inf exp(T0 t) dt by the trapezoid rule

Evaluates the product v*(-T0)^-1 without any factorization, as done in Section 5.2.2 of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011. The propagated vector uses the Euler approximation exp(T0 dt) ~ I + T0 dt, so only sparse vector-matrix products are performed and the sparsity of T0 is preserved throughout. The integration stops when the propagated vector has lost the fraction tol of its initial mass.

Parameters:

v – Row vector to be multiplied by (-T0)^-1
T0 – Hidden transitions of the MAP, a stable matrix
dt – Integration step, below 1/max(abs(diag(T0)))
tol – Relative mass left when the integration stops
iter_max – Maximum number of integration steps

Returns:

y – Row vector approximating v*(-T0)^-1

See also

fes_map_moments()

Examples

y = fes_map_euler(v, T0, dt, tol, iter_max)

fes_map_deaggregate(pk, L, mi, isDelay)

Recovers the per-station metrics of an aggregated subnetwork by conditioning on the population held by the flow-equivalent server

fes_map_solve returns the distribution pk of the jobs held by the aggregate. The metrics of the stations behind it follow by conditioning, E[Y_i] = sum_k pk(k) Y_i(k), with Y_i(k) the metric of station i when the isolated subnetwork holds k jobs. This is the decomposition step of the hierarchical analysis of Chandy, Herzog and Woo, IBM J. Res. Dev. 19(1), 1975, and it is exact for a product-form subnetwork. It is an approximation whenever the burstiness that the MAP flow-equivalent server carries also matters inside the subnetwork, because the conditional solve is the product-form one; the aggregate metrics returned by fes_map_solve do not rely on it.

Parameters:

pk – Distribution of the jobs held by the aggregate, pk(k+1) = P(k)
L – (M_sub x 1) service demands of the isolated subnetwork
mi – (1 x M_sub) servers per station, Inf for a delay
isDelay – (1 x M_sub) true where the station is a pure delay

Returns:

QN – (M_sub x 1) mean queue length per station UN: (M_sub x 1) utilization per station XN: (M_sub x 1) throughput per station RN: (M_sub x 1) mean residence time per station

Examples

[QN,UN,XN,RN] = fes_map_deaggregate(pk, L, mi, isDelay)

fes_map_aggregate(maps, servers, n, options)

Aggregates a subnetwork into a load-dependent MAP flow-equivalent server that reproduces mean, variability and burstiness of its output

Implements the recursion of Section 5.2.1 of Casale, Mi, Cherkasova and Smirni, IEEE Trans. Soft. Eng. 37(5), 2011. The first station seeds the flow equivalent server; every further station is folded against the running server by building the inter-departure MAP of the resulting pair at each population level and fitting a MAP(2) to its first three moments and index of dispersion. The result is one MAP per level, which is the service process of a single load-dependent station that replaces the whole subnetwork. Unlike the classic flow-equivalent server, which keeps only the mean throughput of the subnetwork, this one also carries the burstiness of its departure stream, so a bottleneck switch across the aggregated resources remains visible to the rest of the model.

Levels are evaluated on a grid and the four descriptors are interpolated between grid points, as MAPs fitted at neighbouring populations are similar. The MAP is refitted at every level from the interpolated descriptors, never interpolated entrywise.

Parameters:

maps – Cell array of the station service processes {D0,D1},
servers – Number of servers of each station, Inf for a delay
n – Largest population the flow-equivalent server must serve
options – (Optional) struct with fields method (‘ssolve’ or

Returns:

FES – Cell array with FES{k}={F0,F1} for k=1..n info: Struct with fields throughput (1/e1 per level), moments

Examples

[FES,info] = fes_map_aggregate(maps, servers, n)
[FES,info] = fes_map_aggregate(maps, servers, n, options)

fes_beta_handle(scalingTable, cutoffs)

BETA = FES_BETA_HANDLE(SCALINGTABLE, CUTOFFS)

Wrap a flow-equivalent-server (FES) throughput table as a per-class class-dependence function beta_{i,r}(n).

SCALINGTABLE is a cell {1 x K} in which SCALINGTABLE{r} is the linearized vector of class-r throughputs X_r(n) of the aggregated subnetwork, indexed by LJD_LINEARIZE(min(n,CUTOFFS), CUTOFFS). CUTOFFS is the per-class population vector the table was tabulated on.

The returned handle takes the per-class population vector n at the station and returns the length-K vector of DIMENSIONLESS class-dependence scalings

beta_r(n) = X_r(n) * |n| / n_r,

relative to the nominal rate-1 service of the FES station. The |n|/n_r factor cancels the processor-sharing share that the convolution applies (Sauer 1983, “Computational Algorithms for State-Dependent Queueing Networks”, eq. (40), with mu_{r,i}(n) = (n_r/|n|) beta_r(n)), leaving the aggregate completing class r at exactly the subnetwork throughput X_r(n). The population is clamped to CUTOFFS, so the scaling saturates beyond the tabulated range as the underlying table intends. Entries with n_r = 0 are never consulted by the recurrence.

This is the single class-dependence mechanism used across the solvers: the exact convolution (PFQN_CONV) reads mu_{r,i}(n) from it, and AMVA-QD reads the same handle through PFQN_CDFUN. A table is materialized only at a language boundary (see JLINE.handle_to_serializablefun), never in the model.

See also FES_COMPUTE_THROUGHPUTS, PFQN_CDFUN, PFQN_CONV, LJD_LINEARIZE.

fes_compute_throughputs(L, mi, isDelay, cutoffs, options)

Computes throughputs for all population states

Enumerates all population states (n1, n2, …, nK) up to the specified cutoffs and solves the isolated subnetwork with MVA to get per-class throughputs. These throughputs are stored in a linearized scaling table for use as Limited Joint Dependence (LJD) service rates in the Flow-Equivalent Server.

Parameters:

L – Service demands matrix (M_sub x K) from fes_build_isolated
mi – Number of servers per station (1 x M_sub), Inf for Delay
isDelay – Boolean array (1 x M_sub), true if station is a Delay
cutoffs – Per-class population cutoffs [N1, N2, …, NK]
options – Options struct with field .verbose (default: false)

Returns:

scalingTable – Cell array {class} of linearized throughput vectors

Examples

scalingTable = fes_compute_throughputs(L, mi, isDelay, cutoffs, options)

fes_validate(sn, subsetIndices)

Validates inputs for Flow-Equivalent Server (FES) aggregation

Checks that the network structure and station subset are valid for FES aggregation: - Model is a closed product-form queueing network - Station subset is non-empty and not the entire network - Subset contains only Queue or Delay stations - All station indices are valid

Parameters:

sn – Network structure (from model.getStruct())
subsetIndices – Array of station indices to aggregate (1-based)

Returns:

isValid – True if inputs are valid for FES aggregation errorMsg: Error message if validation fails, empty otherwise

Examples

[isValid, errorMsg] = fes_validate(sn, subsetIndices)

fes_build_isolated(sn, subsetIndices, stochCompS)

Builds isolated subnetwork data from a station subset

Extracts the data needed to analyze an isolated subnetwork containing only the specified stations. This data is used with pfqn_mva to compute throughputs for the Flow-Equivalent Server (FES) service rates.

Parameters:

sn – Network structure (from model.getStruct())
subsetIndices – Array of station indices to include (1-based)
stochCompS – Stochastic complement routing matrix for subset (K*M_sub x K*M_sub)

Returns:

L – Service demands matrix (M_sub x K), L(i,k) = visits(i,k) / rate(i,k) mi: Number of servers per station (1 x M_sub), Inf for Delay nodes visits: Visit ratios matrix (M_sub x K) from stochastic complement isDelay: Boolean array (1 x M_sub), true if station is a Delay node

Examples

[L, mi, visits, isDelay] = fes_build_isolated(sn, subsetIndices, stochCompS)