api.lqn

lqn_balance_equations(lqn, sol, un)

Enumerate the conservation laws (the “physics”) that any solution of a layered queueing network must satisfy, as symbolic relations over a LayeredNetworkStruct and, optionally, as numeric residuals.

A layered model is not free to report any tuple of throughputs, think times and utilizations: five families of relations tie them together, and every one of them is determined by the STRUCTURE of the model alone. This function walks a LayeredNetworkStruct and emits them, one record per relation, with the index sets to aggregate over, the constant coefficients and a printable form. Nothing is solved here.

The families, with kind as emitted:

little Little’s law on a task’s THREAD POOL. The threads of task t form a closed cycle of one delay stage (the surrogate think time that SolverLN imputes to the task, plus the declared think time of a reference task) and one service stage (holding a request from above). Writing B(t,k) for the mean number of threads of t busy serving caller class k – the per-class utilization expressed in JOB units – the law reads

X(t)*(Z(t) + z(t)) + sum_k B(t,k) = N(t)

which is the update SolverLN.updateThinkTimes iterates on. In the [0,1]-normalized utilization LINE reports for a queueing station, B(t,k) = N(t)*U(t,k) and the law is the familiar X(t)*(Z(t)+z(t)) = N(t)*(1 - sum_k U(t,k)); at an infinite server LINE’s utilization is already a job count, so B = U. The caller classes k are the CALLS that target an entry of t – the in-edges of t in the call graph – plus each entry of t that carries an OPEN ARRIVAL, a stream that holds a thread exactly as a call does and that a task can have alongside its callers. Both are structural neighbours of t, which makes the whole relation node-local. termisentry says which of the two a term is.

callflow Throughput conservation across one call: X(c) = X(src(c))*y(c), with y(c) the mean number of calls and src(c) the dispatching activity (the dispatching ENTRY for a forwarding call).
entryflow The requests an entry serves are the calls that reach it plus its open-arrival stream: X(e) = sum_c X(c) + lambda(e).
actflow An activity executes v(a) times per invocation of its entry: X(a) = X(e)*v(a). The visit counts v come from the activity precedence graph and are returned in out.visits. An AND-JOIN is the one place where flow does not add up – its target executes once per fork, not once per branch – so the arcs into a join are scaled by 1/(number of joined branches); see joinScaledGraph.
hostutil The utilization law at a processor: the host demand executed there per unit time equals its busy servers, sum_a X(a)*D(a) = m(h)*U(h) (again m(h)*U(h) is a job count, and the factor m(h) drops at an infinite server).

Together these close the system: little alone is one equation per task and admits the all-zero solution, so a physics-informed loss built on it should carry the flow and utilization families as well.

Parameters:

lqn – LayeredNetworkStruct (from LayeredNetwork.getStruct())
sol – optional; a solved SolverLN, or any struct exposing the same
UN – optional; the REPORTED utilization per element, the second

Returns:

Field – Description eqs: (1 x M) struct array of relations; see below text: cellstr, the printable report visits: (nidx x 1) activity visit count per invocation of its entry A_little: sparse (ntasks x ncalls) 1 where call c is a caller class of task t A_flow: sparse (ncalls x nidx) call-to-source incidence, weighted by y(c) A_host: sparse (nhosts x nidx) host-to-activity incidence, weighted by D(a) maxresidual: largest absolute residual over the non-degenerate records, NaN without sol

Reference-task, forwarding and open-arrival tasks:

A reference task has no layer above, so its cycle closes on its OWN entries, which enter K(t) as entry classes. A forwarding target and an entry-arrival target are driven by a rate pinned outside the task, but the shape of the relation is identical. All four cases therefore share one template, and the branch field says which one produced the record; what it selects is only the label and whether the utilization is a job count.

Conventions (also returned in out.convention):

Rates and populations in a little record are PER REPLICA, matching SolverLN.updateThinkTimes: X per replica is tput/repl and N is the declared multiplicity of one copy. Utilizations and throughputs elsewhere are as the solver reports them, i.e. totalled over replicas – which is why the server count in hostutil is mult and not mult*repl.
N(t) is lqn.mult. SolverLN instead iterates on njobs, which carries the interlocking corrections and, under replication, may be maxmult; both are returned per record so a caller can substitute.
A task whose multiplicity is infinite has no finite thread pool, so its little record is emitted with const = Inf and degenerate set. The sustainable multiplicity maxmult is the finite surrogate SolverLN uses.
S(k) is the entry SERVICE time servt (phase 1 plus phase 2), the time a thread is held, not the residence time residt the caller waits for. The difference is the phase-2 tail, and corr.phase2 marks the tasks that have one. corr.setup marks a task that pays a setup charge, which lands on Z.

Saturation:

SolverLN clamps the think time at zero, so the little equality is an INEQUALITY at a saturated task: when sum_k U(t,k) -> 1 the right-hand side reaches zero and Z can no longer absorb the imbalance. Records carry clamped once instantiated, true when the equality is not attainable. A loss built on these relations should use a one-sided (hinge) form there.

Examples

out = lqn_balance_equations(lqn)            % symbolic only
out = lqn_balance_equations(lqn, sol)       % also numeric residuals
out = lqn_balance_equations(lqn, sol, UN)   % including the host utilization law
lqn_balance_equations(lqn)                  % print the report

lqn_ref_routes(lqn, callers, maxpaths, serverSet)

Synchronous call DAG carrying reference-task customers into a layer.

Parameters:

lqn – LayeredNetworkStruct.
callers – Task indices that call the layer’s server.
maxpaths – (Optional) Refuse the layer above this many reference-task routes into it. Default 32. The count is derived, never enumerated.
serverSet – (Optional) Server elements of the layer. A prefix node whose task is one of them is recursion and refuses the layer.

Returns:

R – Struct array, one element per reference task reaching CALLERS. WHY: Non-empty when the layer must fall back to another interlock

method; R is then empty.

[R, WHY] = LQN_REF_ROUTES(LQN, CALLERS, MAXPATHS, SERVERSET)

Resolves, for the caller set of one layer, the synchronous call graph along which reference (REF) task customers descend to those callers, and the mean number of times each entry and each call is invoked per REF cycle.

SolverLN gives every caller of a layer its own client chain, each carrying its own thread pool as a population, so a layer holds one customer per caller even when those callers are the same REF customers arriving by different routes. The caller set of this group, .members, is what has to become ONE chain.

The result carries a single DAG and two readings of it:

.members every caller of the layer on the DAG, in descent order. The
first is the chain head when the REF task is itself a caller.

.prefixPos the entries from the REF task down to, but not past, the first
caller on each path. Below that first caller the layer already holds an activity subgraph, and the descent through it is spliced call by call, so the prefix has nothing left to say.

Nodes are ENTRIES, because the work a hop charges depends on which entry was called. Visits are computed TOPOLOGICALLY, v(u) = sum over parents of v(p)*w(a)*callmean, and routes are COUNTED in the same pass rather than enumerated: the weights a route decomposition would produce are obtainable in one linear pass, and two sources of truth for one quantity is one too many.

Only SYNC calls are followed. An ASYNC call is send-no-reply, so it terminates blocking and the customer below it is not the REF customer; forwarding is already flattened into pseudo-SYNC arcs by lqn_fwd_rendezvous before the layers are built, and any CallType.FWD left in the struct carries no blocking.

R(g) carries:

.reftask task index of the REF task at the root .headIsCaller true when the REF task is a caller of this layer .members callers of this layer on the DAG, descent order .entries every DAG entry, topologically ordered, root entries first .etask lqn.parent of each entry .ismember true where that entry’s task is a caller of this layer .vEntry mean invocations of each entry per REF cycle .actweight cell, per entry, [aidx; executions per invocation] .calls [cidx, fromPos, toPos, aidx, vCall] rows, vCall being the

mean invocations of that call per REF cycle

.prefixPos positions in .entries forming the prefix, topological order .prefixTerm true where that prefix position is a first caller .npaths distinct REF-to-caller routes, counted .poolmin min of lqn.maxmult over the DAG tasks. A DIAGNOSTIC: the

chain population is never capped by it.

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)