api.lqn

lqn_mol(lsn, options)

Method of Layers on the SRVN decomposition of a layered queueing network whose entries carry no activity graph.

A compact, self-contained reimplementation of the layered fixed point that

Parameters:

lsn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
options – optional struct: iter_max (200), iter_tol (1e-6),

Returns:

Index – QN (QLen) host: NaN task: sum of entry T*S entry: T*S activity: T*S

Scope:: Entry-only models. Activity graphs (fork/join, OR-branches, loops, second phases, forwarding), asynchronous calls, caches, setup tasks, admission constraints, replication and open arrivals are REFUSED, not approximated.

Examples

[QN,UN,RN,TN] = lqn_mol(lsn)
[QN,UN,RN,TN,info] = lqn_mol(lsn, options)

Solverln:: runs, restricted to LQNs in which every entry binds exactly one activity and there are no activity precedences. It decomposes the model the way lqns –srvn-layering does – one submodel per processor and one per called task – and sweeps them in the two phases of Rolia-Sevcik’s Method of Layers: all software (task) submodels, then all hardware (processor) ones. Every submodel is a closed multiclass queueing network with ONE station and one class per client task, so it is solved by pfqn_qdamva rather than by building a Network object. The surrogate client delay of @SolverLN collapses into the think-time vector Z of that call. Where this differs from @SolverLN’s srvn.cs: a submodel here carries one class per client TASK with visit-weighted demands, where srvn.cs carries one class per activity and encodes the call multiplicities as routing. On an entry-only model the two agree on the structure and differ only in the aggregation, so the throughputs and processor utilizations track closely while entry response times spread more.

[QN,UN,RN,TN,INFO] = LQN_MOL(LSN, OPTIONS)

lqn_setup_charge(self, lqn, tidx)

LQN_SETUP_CHARGE(SELF, LQN, TIDX) Mean cold start one request of task TIDX pays

A SetupTask powers a thread down when it goes idle and pays a setup before it can serve again. The thread is released at a reply and starts a delay-off countdown D of mean d; it powers off only if D expires before the next request arrives, and a request arriving first cancels the countdown and pays nothing. With the idle interval I seen by one thread and exponential D,

p = P(D < I) = E[I] / (E[I] + d), and the charge is p * s.

E[I] comes from the current iterate. Admission takes an ACTIVE idle thread before it wakes a sleeping one, so the pool that actually cycles is only as large as the load needs: with offered load b = X*S = RHO*MULT threads, about max(1,b) stay hot, each seeing arrivals at rate X/max(1,b) and busy S per arrival, so

E[I] = max(1,b)/X - S = (max(1,b) - b) / X.

At MULT = 1 this is (1-RHO)/X and is EXACT given p: with one customer, caller mean a and callee mean b it returns p = a/(a+d), the closed form the LDES engine is checked against in SolverLDESLayeredSetupTest and test_ldes_ln_engine.cpp. Above one thread it is an approximation, the exact answer for c servers with setup being matrix-analytic (Gandhi, Harchol-Balter and Adan, Performance Evaluation 67(11), 2010).

Shared by method ‘srvn.cs’ (updateMetricsDefault) and method ‘srvn.ph’ (phComposeEntryLaws/phSetupProb), so the two charge the same thing.

lqn_ref_thinktime(lqn, tidx)

Z = LQN_REF_THINKTIME(LQN, TIDX)

Declared think time of task TIDX as it enters the thread cycle: the value for a REFERENCE task, zero for any other.

A think time is an attribute of the closed customer population a reference task stands for, and it is what separates one request of that population from the next. On a served task it has no such meaning, and charging it per request throttles the task: lqn_basic’s T3 has 25 threads and a declared think time of 4, and reading it as a per-request delay caps it at 25/(4+0.02) = 6.219 completions per second. Three independent oracles refuse that reading and put the rate at 5 calls per caller request instead – lqsim 66.5, LDES 66.955, lqns 75.6 – so the think time of a non-reference task does not enter the cycle. BOTH SolverLN methods go through this gate: updateThinkTimes and updateThinkTimesPH for the surrogate delay, getTranAvgCoupled for its trajectory, and buildLayersRecursive for the build-time seed. See _kb/06-solver-catalog.md (LN section).

lqn_ph_serial_law(wf)

[ALPHA, T] = LQN_PH_SERIAL_LAW(WF)

Composed law of a workflow in which the branches of an AND fork are SERIAL rather than concurrent, that is, the total work the branches request rather than the elapsed time until the last of them finishes.

This is the law of the PROCESSOR demand of an LQN entry. Two branches of an AND fork are two activity threads of the same task instance: they overlap in time, so the entry response time is the maximum of the branches, but they run on ONE processor, so the demand they place on it is the sum. Composing the host law with Workflow.toPH would charge the processor the maximum and let the layer report a utilization below the true one, which no amount of iterating recovers.

Every other node keeps its own composition rule: an OR fork is a mixture, a loop is a geometric compound, so the correlation within a branch survives.

lqn_ph_moments(alpha, T)

[M1, SCV, M2] = LQN_PH_MOMENTS(ALPHA, T)

First two moments of the phase-type law (ALPHA,T) without building a Distribution object, which is what the layered fixed point needs at every iteration for every composed entry law. A defective ALPHA carries an atom at zero and contributes nothing to either moment.

lqn_entry_workflow(model, lqn, eidx, withCalls)

[WF, ACTIDXOF, CALLIDXOF, EXECS, CALLEXECS] = LQN_ENTRY_WORKFLOW(MODEL, LQN, EIDX, WITHCALLS)

Activity graph of LQN entry EIDX as a Workflow, so that the entry service time can be composed exactly into a phase-type law by the series-parallel reduction of Workflow.toPH.

MODEL is the LayeredNetwork the struct LQN was obtained from; the activity precedences are read from the task object rather than reconstructed from LQN.GRAPH, whose loop back-edges carry probabilities and not counts.

WITHCALLS true expands every synchronous call of an activity into a leaf of its own, placed in series after the activity, so that the call response law and the host demand law stay separable across iterations. WITHCALLS false keeps only the host demands, which is the processor-demand law of the entry: the host is released while a call is outstanding.

Returns:

wf - Workflow whose leaves are the activities (and calls) of EIDX actIdxOf - (nidx,1) workflow activity index of each LQN activity, 0 if absent callIdxOf - (ncalls,1) workflow activity index of each call, 0 if absent execs - (nidx,1) expected executions of each LQN activity per entry

invocation

callexecs - (ncalls,1) expected executions of each call per entry invocation,: not counting the mean number of calls per execution

lqn_boxbounds(lqn)

Majumdar-Woodside robust box bounds on throughput for a layered queueing network (LQN), computed on the processor-contention model.

Builds a closed multiclass queueing network from a LayeredNetworkStruct in which the stations are the processors (hosts) and the classes are the reference-task call chains, then applies the Majumdar-Woodside robust box bounds (see pfqn_mwrbb). The per-chain demand at each processor is the total host demand executed on that processor during one cycle of the reference task, obtained by traversing the activity/call graph and scaling by the mean number of synchronous calls. The reference-task multiplicity is the class population and the reference-task think time is the class think time.

This generalizes the classical LQN “Type 1 throughput bound” X_ref <= mult/(Z + D_total) (the no-contention upper bound, as computed by lqns -b) by additionally providing the processor-utilization upper bound and the Majumdar-Woodside lower bound (throughput guarantee, Theorem 2).

Scope: processors are the queueing resources; reference-task chains are the classes. Software (finite-thread task) bottlenecks and non-deterministic activity precedence (OR-branch probabilities, loop repetitions) are not modeled here (sequential activity execution is assumed).

Parameters:: lqn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
Returns:: Field – Description refidx: (1 x R) absolute indices of the reference tasks Xlo,Xup: (1 x R) lower/upper throughput bound per reference chain TN_lo,TN_up: (nidx x 1) throughput bound propagated to all elements UN_lo,UN_up: (nidx x 1) processor utilization bound (util law) D: (nhosts x R) per-chain demand at each processor

Examples

out = lqn_boxbounds(lqn)