solvers.LN

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.

‘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’.

ln_method_refusal(lqn, method, layering)

[OK, REASON] = LN_METHOD_REFUSAL(LQN, METHOD, LAYERING) 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.

ln_layer_refcell(layerSn, classidx)

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

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.

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_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.