solvers.LN

solver_ln_nlp_analyzer(self)

[QN,UN,RN,TN,AN,WN] = SOLVER_LN_NLP_ANALYZER(SELF)

SolverLN method=’nlp’: the whole layered model as ONE nonlinear program.

Every other SolverLN method decomposes the model into layers, hands each one to a queueing-network solver and drives the fixed point between them. This one does not decompose at all: the flow, composition and closure relations are linear constraints, the congestion and Little laws are residuals, and the lot is rooted by Newton (LQN_EXPORT_NLP). No submodel is built and no outer iteration runs. The laws are QD-AMVA (Casale, Perez and Wang, PERFORMANCE 2015), a multiserver being the rate r(n) = softmin(n, m); options.config.lld declares a further smooth multiplier per station.

What this trades away against the layered fixed point: interlocking, phase 2, forwarding, replication, caches, open arrivals and anything else the algebraic form cannot state. Those are refused BY NAME (LINE:unsupported:NlpExport), not silently dropped. AND-fork/join is refused by default and carried by options.config.nlp_fork=’exp’ under the exponential-branch closure.

Returns the six (nidx x 1) ensemble arrays in getEnsembleAvg’s convention:

processor Util only, the sum of the shares its activities hold task Tput, QLen, Util summed over its entries and activities, ResidT

the host residence its activities accumulate

entry Tput X(e), RespT S(e), QLen X(e)*S(e), Util of its activities activity Tput X(a), RespT W(a) + sum_c y(c)*R(c), QLen X(a)*RespT,

ResidT v(a)*W(a)

and NaN everywhere else, ArvR included, which is the layered path’s NaN mask. Twin of python solver_ln_nlp_analyzer.

lqn_overtake_markov(phasetab, prvisit, srvresid, ycalls)

PROT = LQN_OVERTAKE_MARKOV(PHASETAB, PRVISIT, SRVRESID, YCALLS)

Overtaking probability for a phased server from the jump chain of Franks (1999), Ch. 5. An arrival that reaches the server while it is still executing phase 2 of an earlier request from the same client is an overtaking arrival; PROT is the probability of that event.

The chain state is (p,x,k): p is the client phase, x the server phase, and k = 0,1,2 marks client execution, client dispatch, and server execution respectively (Franks 1999, Fig. 5.10). The chain has a product form and is solved column by column:

Eq. (3.1) a phase of the client is cut into NSLICES = 1 + sum_j y_ijp
slices of host execution, each of mean SERVICE/NSLICES

Eq. (5.5) Pr(OT_p | S_r,x), absorption into overtaking Eq. (5.8) Pr(NEXT_p | S_r,x), same expression with a_p replacing c_p Eq. (5.6) Pr{OT(x)}, the sum over start states of the column Eq. (5.7) Pr{S_p,2,0}, start probabilities of the first column

This routine solves the first column (x = 2) for the case in which the calling entry is also the conditioning entry, so the start probabilities of Eq. (5.7) reduce to the phase carrying the call and Eq. (5.9) is not needed. Client phases beyond 2 and distinct conditioning entries are not built by SolverLN, so the columns they would generate are absent.

Inputs

PHASETAB(maxphase+1) x 5, row p+1 holds the parameters of client: phase p as [NSLICES SERVICE Y_IJ Y_IK T_K], where SERVICE is the host residence of the phase, Y_IJ the calls to the server task, Y_IK the calls to every other task, and T_K the mean delay incurred at those other tasks. Row 1 (p = 0) is the client think slice, so NSLICES = 1 and SERVICE = Z.
PRVISITprobability that the client visits this entry, 1 for a: reference task or a sole entry.

SRVRESID : residence time of the server phase under test, s_jx. YCALLS : (maxphase+1) vector, YCALLS(1) total calls to the server

task, YCALLS(p+1) the calls issued from client phase p.

Output

PROT : probability that an arrival finds the server in phase x.

Reference: G. Franks, “Performance Analysis of Distributed Server Systems”, PhD thesis, Carleton University, 1999, Sec. 5.4; published as G. Franks and M. Woodside, “Effectiveness of early replies in client-server systems”, Perform. Eval. 36 (1999) 165-183.

lqn_ln_method(method)

REQUESTED = LQN_LN_METHOD(METHOD)

Normalise a SolverLN method name onto one the solver dispatches on. A method name here carries TWO decisions: the LAYERING, which fixes what a submodel is, and the ENCODING, which fixes how an activity graph is written into it.

‘srvn.cs’ srvn layering, activity graph as ROUTING: one class per task,
entry, activity and call, plus the Fork/Join/Router nodes and the ClassSwitch that an off-diagonal P{r,s} mints. Serves every layered feature this solver implements.

‘srvn.ph’ srvn layering, activity graph as a composed PHASE-TYPE server
law, so a layer is a two-station cycle with one class per caller task. Far smaller and faster, but it cannot represent second phases, forwarding, cache tasks, quorum joins, routed call groups or per-entry admission constraints.

‘srvn’ the ALIAS, and the default: ‘srvn.ph’ where it can serve the
model, ‘srvn.cs’ otherwise. The choice is made once, at layer build time, and reported in SolverLN.lnmethod.

‘flat.cs’ the squashed layering, in which every server is a station of ONE
submodel, again with the routing encoding.

‘flat.ph’ the squashed layering with the PHASE-TYPE encoding: the same
single submodel, but a caller visits each server once per invocation under the composed law rather than once per activity or call under a class chain. Squashing does not conflict with the composition, because a task station’s service law is ALREADY the inflated entry law that the outer fixed point updates, exactly as lqns does under –squashed-layering. It cannot represent what ‘srvn.ph’ cannot, and additionally loses the routed call groups, whose dispatch only the routing encoding carries.

‘flat’ the ALIAS for ‘flat.cs’. It resolves unconditionally rather than
probing ‘flat.ph’, because a model is squashed in order to express what only the routing encoding carries.

‘moment3’ the three-moment response-time distribution pass, which builds
the routing layers and adds a distribution propagation.

‘nlp’ not a layering: the whole model stated as ONE nonlinear program
(QD-AMVA laws, lqn_export_nlp) and rooted, with no layers built. Aliases ‘qdamva’ and ‘qd-amva’.

‘default’ is the srvn alias, so a model solved without naming a method takes the better of the two srvn encodings rather than always the routing one. An unrecognised method name takes ‘srvn.cs’, as every name other than ‘moment3’ did before the alias existed.

A method that names a layering SETS it: ‘flat’/’flat.cs’ squash the model even when options.config.layering is unset. Conversely options.config.layering is still honoured on its own, and SolverLN.lnmethod then reports what was built, so config.layering=’flat’ with the default method reports ‘flat.cs’.

lqn_fwd_rendezvous(lqn)

LQN = LQN_FWD_RENDEZVOUS(LQN) Forwarding transformation of Franks (1999), Sec. 3.3.1 and Fig. 3.8: each forwarding chain reachable from a synchronous call is reconnected to the client that issued the original rendezvous, as a pseudo rendezvous (SYNC) call whose mean is the original call mean times the product of the forwarding probabilities along the path. One level of servers disappears from the layering, and the forwarded workload is then carried by ordinary SYNC call classes, so layer construction, think times, populations and the interlock analysis all see plain rendezvous arcs.

As the thesis notes, the transformed model is not one in which the client makes two remote procedure calls directly: the pseudo arcs are excluded from the slice times and from the overtaking and interlock probabilities. FWD calls are kept in the struct but no longer contribute blocking anywhere in SolverLN.

Asynchronous calls into a forwarding chain are left untouched, since a send-no-reply terminates the chain of blocking.

lqn_act_thinktime(lqn, aidx)

ZT = LQN_ACT_THINKTIME(LQN, AIDX)

Think time of activity AIDX, zero when it has none.

An activity think time is a delay in series with that activity’s host demand, held at the activity’s own task: the task keeps its thread for the whole hostdem+thinktime interval, so it serializes against the task multiplicity, but the host processor is released for it. This mirrors lqns, whose think-time attribute LINE already writes out in writeXML.

lqn.actthink_mean is preallocated as NaN by LayeredNetwork/getStruct and stays NaN for an activity that was never given a think time, so the value is filtered here rather than added by the callers: a NaN reaching servt or residt propagates into the layer solvers, and the NaN-ignoring fallbacks there then launder it into a plausible-looking bare-service figure instead of failing.

ln_zero_capacity(lqn)

ZC = LN_ZERO_CAPACITY(LQN) Reference tasks trapped at a zero-capacity element

A processor or a non-reference task of multiplicity 0 never serves a request. A reference task that reaches one through synchronous calls with positive probability ends, in steady state, with all of its users stuck on that call path (nested blocking): every throughput it drives is 0, the response times along the path are Inf, and each task, entry and activity on the path holds the requests stuck below it, the dead task holding those queued at it. A trapped request holds task threads only, never a processor, so the other reference tasks are solved as if the trapped ones were absent.

Fields of ZC (all nidx x 1 unless stated):: dead zero-capacity processors and tasks trapped reference tasks whose users are all trapped onroute elements on a blocked call path held requests each element holds in the trapped state ignore elements no live reference task or open arrival reaches, to drop from the layers live true when some reference task or open arrival is still served reason non-empty when the trapped state is ambiguous or does not exist

ln_warm_start_commit(self)

LN_WARM_START_COMMIT(SELF) Push a seeded iterate into the layers of SolverLN SELF.

The same laws the tail of post() pushes, from a warm start’s solution instead of from an iteration: updateLayers, then a refresh of every layer model and a reset of its solver. updateRoutingProbabilities is NOT among them, because the call frequencies it writes are already right at construction and it reads a layer result that does not exist yet; iteration 1 runs it normally. Marks the run warm-started, which drops iter_min from converged()’s stopping test. Shared by LN_NLP_WARM_START and LN_MOL_WARM_START.

ln_nlp_warm_start(self)

OBJ = LN_NLP_WARM_START(SELF)

options.config.warmstart=’nlp’: seed the layered fixed point of SolverLN SELF with the QD-AMVA program’s solution (LN_NLP_PROGRAM).

This is not a method but a STARTING POINT. The layers, the layer solvers and the iteration are the layered method’s own; only the state they begin from changes, from the model’s bare host demands to the program’s answer. The iteration then converges to ITS fixed point, not the program’s, so the answer is the layered one and only the path to it is short. converged() drops iter_min for a run seeded this way: that floor keeps a cold iterate from reading an early plateau as convergence, and a warm one starts past it.

OBJ is the program’s objective at its solution, for the caller to log. A model the program cannot express raises LINE:unsupported:NlpExport, by name, rather than falling back to a cold start reported as warm. Twin of python ln_nlp_warm_start.

ln_nlp_program(self)

[P, CFG, RES, X] = LN_NLP_PROGRAM(SELF)

Build the QD-AMVA nonlinear program of SolverLN SELF’s model (LQN_EXPORT_NLP) and root it, under the settings read off SELF.options.config:

lld struct or containers.Map {station name: expression in n} nlp_alpha softmin sharpness (20) nlp_fork ‘refuse’ (default) or ‘exp’, how an AND-fork block is treated nlp_warm warm sweeps at the bottom of the Newton ladder (0); a floor,

not a cap, since solve() escalates on its own

nlp_maxiter budget of the fallback descent (3000). iter_max bounds the
layered FIXED POINT, which this program does not run

Shared by method=’nlp’ (SOLVER_LN_NLP_ANALYZER) and warmstart=’nlp’ (LN_NLP_WARM_START), so the two can never root different programs. X is the solution clipped to the bounds, RES the solve() record.

ln_mol_warm_start(self)

RESID = LN_MOL_WARM_START(SELF)

options.config.warmstart=’mol’: seed the layered fixed point of SolverLN SELF with the Method of Layers’ solution (LQN_MOL), the second starting point beside warmstart=’nlp’. Both price a station by QD-AMVA, the program by rooting its stationarity conditions in one shot and LQN_MOL by sweeping software then hardware submodels until the state settles.

LQN_MOL carries the vectors the iterate is made of under the same names (servt, residt, callservt), so they are copied; the surrogate delays are rebuilt with SolverLN’s own law from LQN_MOL’s busy-thread counts, since its own thinkt is the Z of a submodel, a different convention. Its scope is narrower than the program’s: activity graphs, second phases, asynchronous and forwarding calls, caches, setup times, replication, admission constraints and open arrivals are refused by LQN_MOL, by name.

The seed is built to ITS OWN tolerance, read from options.config: mol_iter_max (200), mol_iter_tol (1e-6), mol_relax_factor (0.5). SolverLN’s iter_tol is a stopping rule for a different iteration and would hand over a state still two digits out. RESID is LQN_MOL’s final residual. Twin of python ln_mol_warm_start.

ln_method_refusal(lqn, method, layering, nlpFork)

[OK, REASON] = LN_METHOD_REFUSAL(LQN, METHOD, LAYERING, NLPFORK) Whether a layered method can encode this model, asked as a predicate.

ONE PREDICATE, TWO CALLERS. SolverLN.supportsModelMethod asks it, so a report never offers a pair the builders refuse on contact, and BUILDLAYERS / BUILDLAYERSPH ask it again on the run path and raise its REASON, so the gate and the run cannot say different things about one model. Until this predicate held every rule the builders carried their own copies: ‘flat.cs’ refused a replicated processor, a cache task or a setup task, every routing encoding refused a non-series-parallel fork graph and a routed call group under srvn, and the PH encodings refused a second phase, none of it visible to model.help.

NONE OF THESE IS EXPRESSIBLE AS A FEATURE SET. A feature set says “I accept construct X”, so it can refuse a model for HAVING one; but ‘replicated processors need a submodel each’ is a property of the SQUASHING rather than of the construct, and ‘routed call groups state a dispatch order the composed law folds away’ is a property of the ENCODING. Both are refusals about what the method does to the model, which is what a predicate is for.

METHOD is any method name LQN_LN_METHOD accepts. The alias ‘srvn’ (and ‘default’) takes ‘srvn.ph’ where it can serve the model and ‘srvn.cs’ otherwise, and ‘srvn.ph’ never rescues a model ‘srvn.cs’ refuses, so the alias is gated as ‘srvn.cs’. LAYERING is options.config.layering (‘srvn’ when omitted); a method that names a layering sets it, as in BUILDLAYERS.

ONE RULE STAYS ON THE RUN PATH: whether an activity graph composes into one phase-type law under the PH encodings is found out by composing it (phInitLaws), which ‘srvn’ probes for and falls back from, so it is not a model property this predicate states.

REASON is empty exactly when OK is true, and is the builder’s own wording.

METHOD ‘nlp’ builds no layers, so none of the rules below apply to it: it is gated by the scope check of LQN_EXPORT_NLP instead, under NLPFORK (options.config.nlp_fork, ‘refuse’ when omitted), and REASON is that refusal’s own message.

ln_layer_refcell(layerSn, classidx, normclass)

[HASREF, REFSTAT_K, REFCLASS_C] = LN_LAYER_REFCELL(LAYERSN, CLASSIDX, NORMCLASS)

Locate the (station,class) cell of the chain reference throughput used to normalise a residence time in a layer. HASREF is false when the chain of CLASSIDX carries no reference class, as on an open chain, where LAYERSN.REFCLASS is 0 and the cell does not exist; the caller must then fall back on WN rather than index TN.

NORMCLASS is optional and names, per class, the TASK class whose invocation rate that class is measured against. It exists because a chain may hold more than one caller task: the refpath interlock method merges the client chains of every caller descending from one reference task, and refreshStruct allows at most ONE reference class per chain, so the other callers cannot be found through LAYERSN.REFCLASS any more. Their residence times are still “per invocation of the owning task”, which is what NORMCLASS records. Without it, and with the chain’s single reference class standing in, every merged caller’s residence would be normalised by the head’s rate and come out scaled by the product of the call multiplicities along the path.

Omitted, or 0 for this class, it falls back to the chain’s reference class, which is the class LAYERSN.REFCLASS would have named anyway when no merging took place. The argument is therefore inert on every other method.

ln_interlock_method(lqn, config, lnmethod)

[ILM, WHY] = LN_INTERLOCK_METHOD(LQN, CONFIG, LNMETHOD) Interlock tracking method a run will actually use, asked as a query.

ONE QUERY, TWO CALLERS, for the reason LN_METHOD_REFUSAL exists: BUILDLAYERS asks it on the run path and stores the answer in SolverLN.interlockMethod, and SolverLN.interlockMethodFor asks it before a solve, so a caller reading the option back can never be told something the builder did not do.

IT DOWNGRADES, IT DOES NOT REFUSE. An encoding or a model feature refpath cannot carry is not a reason to decline the model: ‘ilrate’ analyses it exactly as it did before the option existed. That is why this is not a clause of LN_METHOD_REFUSAL, whose OK=false means the METHOD cannot encode the model at all – ‘srvn.ph’ is fully supported on a model that merely cannot have refpath.

CONFIG is options.config, read unvalidated: a user option struct reaches setOptions without passing through SolverOptions, so every key is isfield- guarded here rather than assumed present. LNMETHOD is the resolved encoding (‘srvn.cs’, ‘srvn.ph’, …), which BUILDLAYERS has already settled by the time it asks.

ILM is one of ‘ilrate’ (the rate-based discount of Franks’ Eq. 4.7, the default and what LINE did before this option existed), ‘refpath’ (the merged reference-path chain in the client Delay) or ‘none’. WHY is empty exactly when the request was honoured, and names the downgrade otherwise.

ln_thread_busy_fraction(layer, station_t, UN, TN)

U = LN_THREAD_BUSY_FRACTION(LAYER, STATION_T, UN, TN)

Busy fraction of a task’s threads read from its own layer model LAYER, for the LN think-time closure Z = njobs*(1-U)/X. That closure conserves throughput across a call only when njobs*U is the mean number of HELD threads, sum_r T_r*S_r over c servers, S_r the nominal service mean of the task station. Without a rate dependence that is the reported Util. With one it is not: a load-, class- or joint-dependent station (server pools lower to the joint form) reports Util normalized by its declared peak instead of its server count, so a 5-thread task with class-dependence peak [2 1] read U = 1.35, abs() folded it and flow balance across the call broke (T0 1.4341 against E1/E2 1.9489). For such a station the fraction is computed from the definition. The dependence lives only in the task’s OWN layer: the host layer charges the unscaled demands. An infinite server returns the plain row sum, a mean number of busy threads. JAR twin: SolverLN.threadBusyFraction (peak form, identical for cd/jd); python twin: SolverLN._thread_busy_fraction. See _kb/06-solver-catalog.md (LN section).

ln_has_quorum_tail(lqn)

LN_HAS_QUORUM_TAIL True when some AND-join fires on a quorum below its branch count.

TF = LN_HAS_QUORUM_TAIL(LQN) A quorum join replies after k of its n branches, but the n-k stragglers still run on the task’s thread, which therefore stays busy after the reply exactly as in a second phase. SolverLN charges that tail through its phase-2 machinery, so the flag decides whether that machinery is switched on.

ln_host_task_priorities(lqn, model, idxSet)

LN_HOST_TASK_PRIORITIES(LQN, MODEL, IDXSET) set task priorities on a host layer

Give every class of the layer MODEL the priority of the task that owns it, for each processor in IDXSET that schedules by priority (HOL, ‘pri’, …). lqns serves a LARGER task priority first while a LINE class priority of 0 is the highest, so the class priority is max(prio on the host) - prio(task). A layer solver with a priority arm (MVA, CTMC, …) then applies it. Without this every class tied at priority 0 and a priority processor ran as FCFS.