Package jline.solvers.ln

Class SolverLN

java.lang.Object
jline.solvers.Solver
jline.solvers.EnsembleSolver
jline.solvers.ln.SolverLN
Direct Known Subclasses:
LN
public class SolverLN extends EnsembleSolver
Solver for Layered Queueing Networks (LQN) using ensemble-based iterative methods.

SolverLN implements layered queueing network analysis through decomposition into simpler queueing models. LQNs extend traditional queueing networks by modeling software systems with nested service requests, where servers can act as clients to other services, creating layered dependencies.

Key LQN solver capabilities:

  • Multi-layer model decomposition and iteration
  • Software system modeling with nested service calls
  • Client-server interaction patterns
  • Convergence detection across model layers
  • Ensemble-based performance analysis

The solver iterates between layers, updating service demands and arrival rates until convergence is achieved across all layers. This enables analysis of complex distributed software architectures and service-oriented systems.

Since:
1.0
See Also:

  • Field Details

    • nlayers

      public int nlayers

    • lqn

      public LayeredNetworkStruct lqn

    • hasconverged

      public boolean hasconverged

    • averagingstart

      public Integer averagingstart

    • idxhash

      public List<Double> idxhash

    • servtmatrix

      public Matrix servtmatrix

    • joint

      public Matrix joint

    • ptaskcallers

      public Matrix ptaskcallers

    • ptaskcallers_step

      public Map<Integer,Matrix> ptaskcallers_step

    • ilscaling

      public Matrix ilscaling

    • njobs

      public Matrix njobs

    • njobsorig

      public Matrix njobsorig

    • routereset

      public List<Integer> routereset

    • svcreset

      public List<Integer> svcreset

    • maxitererr

      public List<Double> maxitererr

    • util

      public Matrix util

    • tput

      public Matrix tput

    • tputproc

      public Map<Integer,Distribution> tputproc

    • servt

      public Matrix servt

    • residt

      public Matrix residt

    • servtproc

      public Map<Integer,Distribution> servtproc

    • servtcdf

      public Map<Integer,Matrix> servtcdf

    • thinkt

      public Matrix thinkt

    • thinkproc

      public Map<Integer,Distribution> thinkproc

    • thinktproc

      public Map<Integer,Distribution> thinktproc

    • callresidt

      public Matrix callresidt

    • callservt

      public Matrix callservt

    • layerHasRegion

      public boolean[] layerHasRegion
      True per ensemble index if the layer carries an admission constraint.

    • layerChains

      public Matrix[] layerChains
      Cached sn.chains of a constrained layer, per ensemble index.

    • callservtproc

      public Map<Integer,Distribution> callservtproc

    • callservtcdf

      public Map<Integer,Matrix> callservtcdf

    • ignore

      public Matrix ignore

    • arvproc_classes_updmap

      public Matrix arvproc_classes_updmap

    • thinkt_classes_updmap

      public Matrix thinkt_classes_updmap

    • servt_classes_updmap

      public Matrix servt_classes_updmap

    • call_classes_updmap

      public Matrix call_classes_updmap

    • route_prob_updmap

      public Matrix route_prob_updmap

    • unique_route_prob_updmap

      public Matrix unique_route_prob_updmap

    • cell_arvproc_classes_updmap

      public Map<Integer,List<Integer[]>> cell_arvproc_classes_updmap

    • cell_thinkt_classes_updmap

      public Map<Integer,List<Integer[]>> cell_thinkt_classes_updmap

    • cell_servt_classes_updmap

      public Map<Integer,List<Integer[]>> cell_servt_classes_updmap

    • cell_call_classes_updmap

      public Map<Integer,List<Integer[]>> cell_call_classes_updmap

    • cell_route_prob_updmap

      public Map<Integer,List<Integer[]>> cell_route_prob_updmap

    • temp_ensemble

      public List<Network> temp_ensemble

    • curClassC

      public JobClass curClassC

    • entryproc

      public Map<Integer,APH> entryproc

    • relax_omega

      public double relax_omega

    • relax_err_history

      public List<Double> relax_err_history

    • servt_prev

      public Matrix servt_prev

    • residt_prev

      public Matrix residt_prev

    • tput_prev

      public Matrix tput_prev

    • thinkt_prev

      public Matrix thinkt_prev

    • singleReplicaTasks

      public Set<Integer> singleReplicaTasks

    • callservt_prev

      public Matrix callservt_prev

    • callresidt_prev

      public Matrix callresidt_prev

    • stochiterMode

      public String stochiterMode

    • stochiterAuto

      public boolean stochiterAuto

    • stochiterStart

      public Integer stochiterStart

    • stochlayers

      public boolean[] stochlayers

    • stochAvg

      public Map<Integer,SolverResult> stochAvg

    • stochAvgCount

      public int stochAvgCount

    • stochServtAvg

      public Matrix stochServtAvg

    • stochResidtAvg

      public Matrix stochResidtAvg

    • hostLayerIndices

      public List<Integer> hostLayerIndices

    • taskLayerIndices

      public List<Integer> taskLayerIndices

    • solverFactory

      public SolverFactory solverFactory

    • hasPhase2

      public boolean hasPhase2

    • servt_ph1

      public Matrix servt_ph1

    • servt_ph2

      public Matrix servt_ph2

    • util_ph1

      public Matrix util_ph1

    • util_ph2

      public Matrix util_ph2

    • prOvertake

      public Matrix prOvertake

    • il_table_all

      public double[][] il_table_all

    • il_table_ph1

      public double[][] il_table_ph1

    • il_common_entries

      public List<Integer>[] il_common_entries

    • il_source_tasks_all

      public List<Integer>[] il_source_tasks_all

    • il_source_tasks_ph2

      public List<Integer>[] il_source_tasks_ph2

    • il_num_sources

      public double[] il_num_sources

    • lnmethod

      public String lnmethod
      The method the layers were actually BUILT for: 'srvn.ph', 'srvn.cs', 'flat.cs' or 'moment3'. Resolved once in buildLayers, because the alias 'srvn' may fall back; every dispatch reads this and not options.method, so a reconstruction can never disagree with the layers it is reading.

  • Constructor Details

  • Method Details

    • defaultOptions

      public static SolverOptions defaultOptions()

    • analyze

      public SolverResult analyze(int it, int e)
      Specified by:
      analyze in class EnsembleSolver

    • lnRequestedMethod

      public static String lnRequestedMethod(String method)
      Normalise a method name onto one the solver dispatches on. A method name 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' encodes the activity graph as ROUTING, 'srvn.ph' as a composed phase-type server law, 'srvn' is the alias that takes 'srvn.ph' where it can serve the model and 'srvn.cs' otherwise, 'flat.cs' squashes every server into one submodel with the routing encoding, 'flat.ph' squashes them with the composed one ('flat' is the alias of 'flat.cs' and resolves unconditionally rather than probing 'flat.ph', because a model is squashed in order to express what only the routing encoding carries), and 'moment3' is the three-moment distribution pass over the routing layers. 'default' is the srvn alias; an unrecognised method name takes 'srvn.cs'.
      Parameters:
      method - the requested method, may be null
      Returns:
      one of "srvn", "srvn.ph", "srvn.cs", "flat.cs", "moment3"

    • listValidMethods

      public String[] listValidMethods()
      Valid methods for this solver, SolverLN.m verbatim. Each name states the LAYERING and the ENCODING; lnRequestedMethod normalises the alias spellings ('ph', 'cs', 'srvncs', 'flatcs', 'squashed', 'squashed.ph') onto these, and they are left out here to keep the list unambiguous, exactly as the reference does.
      Returns:
      the method names SolverLN accepts

    • supportsModelMethod

      public String supportsModelMethod(String method)
      The encoding rules the layer builders enforce at solve time, stated here so that a CALLER can see them before running.

      srvn.ph and flat.ph compose each entry into ONE phase-type law, and several constructs have nowhere to go in that law: a forwarding call whose target is not in the caller's activity graph, a routed call group whose dispatch order the composition folds away, a cache task, an admission constraint, a queue-dependent rate on a station the composition replaces. flat.ph additionally squashes every layer into one network, which per-layer state (a replica, a powered-down setup thread) cannot survive.

      None of these is a feature name, so none can be a feature-set delta: they are properties of what the METHOD does to the model. Left only in phFlatServerSet and the composer they were invisible to every gate above them, and listValidMethods returns the same eight names for every model, so a report offered every encoding on every layered model.

      Phase 2 is deliberately NOT tested: that refusal reads this.hasPhase2, which is built during layering rather than being a property of the model, so a gate cannot ask it without doing the layering it precedes. Mirrors MATLAB ln_method_refusal.

      Overrides:
      supportsModelMethod in class Solver
      Parameters:
      method - the concrete method name
      Returns:
      empty string when the method can encode this model, else the reason

    • isSrvnPH

      public boolean isSrvnPH()
      True when the layers are the collapsed phase-type ones of method 'srvn.ph'.

    • isPHEncoding

      public boolean isPHEncoding()
      True when the layers carry the COMPOSED phase-type server law rather than the routing encoding of the activity graph, under either layering. The encoding, not the layering, decides which update and reconstruction passes run, so every such dispatch asks this and not for one method name.
      Returns:
      true for 'srvn.ph' and for 'flat.ph'

    • buildLayers

      public void buildLayers()

    • stationIdxOf

      public int stationIdxOf(int e, int elemIdx)
      Station index (1-based) of ELEMIDX inside layer E, falling back to the layer's own server when ELEMIDX is not a server there.

    • stationIdxOfClass

      public int stationIdxOfClass(int e, int c)
      Station of layer E that class C (0-based) is served at: the processor of an activity, the called task of a call, the layer's server otherwise.

    • serverStationsOf

      public List<Integer> serverStationsOf(int e, boolean ishost)
      Station indices of the host (ISHOST true) or task servers of layer E.

    • buildLayersRecursive

      public void buildLayersRecursive(int idx, List<Integer> callers, boolean ishostlayer)

    • buildLayersRecursive

      public void buildLayersRecursive(List<Integer> idxSet, List<Integer> callers, boolean ishostlayer, boolean flat)

    • assertSeriesParallelForks

      public void assertSeriesParallelForks()
      Rejects activity graphs whose AND forks and joins are not properly nested. The traversal in buildLayersRecursive pairs a join with the most recent fork through a LIFO stack of fork classes, so it can only represent series-parallel graphs. A join whose inputs come from different forks pops a class that was never pushed; failing here names the model instead.

    • construct

      public void construct()

    • converged

      public boolean converged(int it)
      Specified by:
      converged in class EnsembleSolver

    • convergedStoch

      public boolean convergedStoch(int it)
      Convergence controller for stochastic layer solvers (Robbins-Monro mode).

      When one or more layer solvers return noisy estimates (simulation, e.g. JMT/SSA/LDES, or Monte Carlo integration, e.g. NC with mci/imci/ls), the deterministic Picard iteration in converged() cannot terminate: the successive-difference error is bounded below by the standard error of the layer estimates, and the layer-reset confirmation step merely resamples the noise. This routine implements a stochastic approximation iteration instead:

      1. Burn-in: for the first stochiter_burnin iterations the plain Picard iteration runs with the relaxation factor configured at init.
      2. Robbins-Monro step: afterwards the relaxation factor applied by updateMetrics to the fed-forward iterate (servt, residt, tput, callservt) decays as omega_k = a0/k^alpha with alpha in (0.5,1]. Under the contraction assumption already made by the deterministic iteration, and zero-mean noise with bounded variance, the iterate converges almost surely to the true fixed point (Robbins and Monro, 1951). Layer seeds are rotated per iteration in pre() so successive evaluations observe independent noise.
      3. Polyak-Ruppert averaging: running averages of the layer results and of the reported iterates are maintained and installed as the final solution in finish(), giving the optimal O(1/sqrt(k)) rate and robustness to the choice of a0 (Polyak and Juditsky, 1992).
      4. Stopping: iteration stops when the drift of the averaged results stays below iter_tol for stochiter_conseq consecutive iterations. The drift of a running average decays like 1/k even under persistent noise, so the test terminates, and it self-calibrates: larger noise keeps the drift above tolerance longer, forcing more averaging.

      Note: the Robbins-Monro step acts through relax_omega, which is applied by the default metric update path; the moment3 update path does not use relaxation, so this controller is primarily intended for method 'default'.

      Parameters:
      it - the completed iteration count
      Returns:
      true when the averaged iterate has converged

    • finish

      public void finish()
      Specified by:
      finish in class EnsembleSolver

    • getArvproc_classes_updmap

      public Matrix getArvproc_classes_updmap()

    • getAvgTable

      public AvgTable getAvgTable()
      Specified by:
      getAvgTable in class EnsembleSolver

    • getAvgTableImpl

      protected AvgTable getAvgTableImpl()
      Body of getAvgTable(), split out so LineResultRecorder sees what the getter RETURNED. The JAVA cross-codebase parity row is measured from that rather than from what an example printed.

    • getCdfRespT

      public List<Matrix> getCdfRespT()
      Response time distribution of every entry of the layered network.

      Counterpart of MATLAB @SolverLN/getCdfRespT.m. The distribution is formed by the moment3 pass alone -- the mean-based update builds no law at all -- so a solver constructed with any other method re-runs the ensemble under moment3 here and restores the caller's method afterwards. The routing layers already built serve moment3 unchanged, so only the update pass changes.

      Returns:
      one entry per entry of the LQN, in the entry-local index space (lqn.eshift + i). Each element is an (n x 2) matrix whose columns are [F(t), t], the column order every CDF getter in LINE uses, or null for an entry the pass fitted no law to.
      Throws:
      RuntimeException - if the layers were built for a phase-type encoding, which carries no activity-graph routing to re-run over

    • getSensitivityTable

      public LayeredNetworkSensitivityTable getSensitivityTable()
      Layer-wise performance sensitivities of the layered network with respect to service rates. Counterpart of MATLAB @SolverLN/getSensitivityTable.m.

      Solves the layered model and then delegates to each layer solver, returning the concatenation of the layer tables with a leading Layer column. Every row is therefore a (Layer, Station, JobClass) triple carrying the derivative of that row's mean measures with respect to that station-class service RATE in that layer: dTput_dRate, dRespT_dRate, dQLen_dRate, dUtil_dRate.

      IMPORTANT, on what these derivatives mean. Each entry is a derivative WITHIN ITS LAYER, taken with the layer parameters that the fixed point produced held fixed. It is a partial derivative of the layer submodel, not the total derivative of the layered model: perturbing a host demand in one layer moves the think times, populations and service rates of the other layers through the fixed-point map, and that indirect term is not included here. The layer table is the right object for attributing a bottleneck inside a layer, and the wrong one for predicting the effect of a parameter change on the solved layered model. For the latter, finite-difference the LayeredNetwork itself.

      Returns:
      the layer-wise sensitivity table
      See Also:

    • getSensitivityTable

      public LayeredNetworkSensitivityTable getSensitivityTable(String method, double step, String scheme)
      Layer-wise performance sensitivities with an explicit branch, step and difference scheme. The options are passed through to the layer solvers unchanged, with the same meaning as in NetworkSolver.getSensitivityTable(String, double, String): each layer independently takes the analytic branch where its own solver supports it and the layer model is in scope, and finite differences otherwise.
      Parameters:
      method - one of "auto", "exact", "fd"
      step - relative step of the rate perturbation; NaN selects the default
      scheme - "forward" or "central"
      Returns:
      the layer-wise sensitivity table, whose LayeredNetworkSensitivityTable.getMethod() is "mixed" when the layers did not all take the same branch
      See Also:

    • getTranAvg

      public LNTranAvgResult getTranAvg()
      Transient average station metrics of the layered network.

      Mirrors MATLAB SolverLN.getTranAvg: runs the ensemble fixed-point solve, then delegates the transient analysis to each layer solver and assembles the per-layer station x class traces block-diagonally (layer e in a disjoint row/column block). Off-block cells are left null.

      Transient traces are only produced by transient-capable layer solvers (Fluid, CTMC, SSA); with steady-state-only layers (MVA, NC) the delegated getTranAvg throws, matching the MATLAB behaviour.

      Returns:
      block-diagonal transient queue lengths, utilizations, throughputs and per-cell time vectors

    • getTranAvgDecoupled

      public LNTranAvgResult getTranAvgDecoupled()
      Decoupled (frozen-demand) layered transient: the inter-layer demands stay pinned at the converged fixed point and each layer's transient runs in isolation. Mirrors MATLAB SolverLN.getTranAvgDecoupled.

    • getTranAvgCoupled

      public LNTranAvgResult getTranAvgCoupled()
      Coupled layered transient by waveform relaxation over the LQN ensemble.

      Port of MATLAB @SolverLN/getTranAvgCoupled.m. Unlike getTranAvgDecoupled(), which freezes inter-layer demands at the converged fixed point, this reconciles the per-layer transients iteratively: each layer's transient is driven by TIME-VARYING inter-layer demand trajectories taken from the other layers' latest transients, and the loop repeats until the trajectories stop changing (sup-norm gap over time). The time-varying demands are injected into each layer solver through the per-(station,class) rate schedule (options.config.rate_sched), honoured by the fluid rate multiplier and by the CTMC time-varying transient.

      Iteration 0 uses the frozen equilibrium demands, so it reproduces getTranAvgDecoupled() exactly; at convergence every layer relaxes to its fixed point, so the endpoint equals getEnsembleAvg. The return layout is the same block-diagonal (station x class per layer).

      Coupled channels: task think times (client delay) and synchronous-call service demands (caller client station). Both are the dominant inter-layer couplings; intra-layer host service stays at its equilibrium value.

    • avgTable

      public AvgTable avgTable()

    • avgT

      public AvgTable avgT()
      Overrides:
      avgT in class EnsembleSolver

    • aT

      public AvgTable aT()
      Overrides:
      aT in class EnsembleSolver

    • getCall_classes_updmap

      public Matrix getCall_classes_updmap()

    • getEnsemble

      public List<Network> getEnsemble()

    • getEnsembleAvg

      public AvgTable getEnsembleAvg()
      Specified by:
      getEnsembleAvg in class EnsembleSolver

    • getEntryServiceMatrix

      public Matrix getEntryServiceMatrix()

    • getEntryServiceMatrixRecursion

      public Matrix getEntryServiceMatrixRecursion(LayeredNetworkStruct lqn, int aidx, int eidx, Matrix U)

    • getIdxhash

      public List<Double> getIdxhash()

    • getRoute_prob_updmap

      public Matrix getRoute_prob_updmap()

    • getServt_classes_updmap

      public Matrix getServt_classes_updmap()

    • getThinkt_classes_updmap

      public Matrix getThinkt_classes_updmap()

    • init

      public void init()
      Specified by:
      init in class EnsembleSolver

    • integerMapToMatrix

      public Matrix integerMapToMatrix(Map<Integer,List<Integer[]>> cell)

    • post

      public void post(int it)
      Specified by:
      post in class EnsembleSolver

    • pre

      public void pre(int it)
      Specified by:
      pre in class EnsembleSolver

    • runAnalyzer

      public void runAnalyzer() throws IllegalAccessException
      Description copied from class: Solver
      Executes the solver algorithm to analyze the model. This abstract method must be implemented by concrete solver classes.
      Specified by:
      runAnalyzer in class Solver
      Throws:
      IllegalAccessException - if access to required resources is denied

    • supports

      public boolean supports(Ensemble ensemble)

    • updateLayers

      public void updateLayers(int it)

    • updateMetrics

      public void updateMetrics(int it)

    • updateMetricsDefault

      public void updateMetricsDefault(int it)

    • updateMetricsMomentBased

      public void updateMetricsMomentBased(int it)

    • updatePopulations

      public void updatePopulations(int it)

    • updateRoutingProbabilities

      public void updateRoutingProbabilities(int it)

    • updateThinkTimes

      public void updateThinkTimes(int it)

    • getState

      public SolverLN.LNState getState()
      Export current solver state for continuation.

      Returns a LNState object containing the current solution state, which can be used to continue iteration with a different solver via setState().

      Returns:
      LNState object containing exported state

    • setState

      public void setState(SolverLN.LNState state)
      Import solution state for continuation.

      Initializes the solver with a previously exported state, allowing iteration to continue from where a previous solver left off.

      Parameters:
      state - LNState object to import

    • updateSolver

      public void updateSolver(SolverFactory newSolverFactory)
      Change the solver for all layers.

      Replaces all layer solvers with new solvers created by the given factory function. This allows switching between different solving methods (e.g., from MVA to JMT) while preserving the current solution state.

      Parameters:
      newSolverFactory - Factory to create new layer solvers

    • overtakeProb

      public double overtakeProb(int eidx)
      Compute overtaking probability using transient Markov chain.

      This computes the probability that a new arrival to entry eidx finds the server in phase-2 (post-reply processing).

      Uses a 3-state Continuous Time Markov Chain (CTMC):

      • State 0: Server idle
      • State 1: Server in phase-1 (caller is blocked)
      • State 2: Server in phase-2 (caller has been released)
      By PASTA (Poisson Arrivals See Time Averages), the overtaking probability equals the steady-state probability of being in phase-2.

      Parameters:
      eidx - Entry index
      Returns:
      Overtaking probability (0 to 1)

    • buildLayersPH

      public void buildLayersPH()

    • buildLayersPH

      public void buildLayersPH(boolean flat)
      Build the ensemble of a PH encoding. FLAT false is method 'srvn.ph', one layer per served element; FLAT true is method 'flat.ph', ONE layer holding a station for every processor and every called task, with the same one closed class per caller task.
      Parameters:
      flat - true to squash every server into a single submodel

    • phComposeEntryLaws

      public void phComposeEntryLaws()
      Recompose the entry service laws from the current fixed-point iterate.

      The composed mean is NOT the sum of the leaf means when the graph forks: the branches of an AND fork phOverlap, and the entry finishes with the last of them. The ratio of the two, the phOverlap factor, is what the caller-side aggregates are scaled by, so that the pieces of a cycle still add up to the cycle.

    • updateLayersPH

      public void updateLayersPH(int it)
      Push the composed laws into the layers.

      A phLayers of this method carries no routing that depends on the iterate: the number of calls a caller makes is folded into its service law rather than into a visit ratio, so only two laws move per (phLayers, class) -- the phase-type service law at the server and the mean of the surrogate delay at the client.

      Parameters:
      it - iteration number

    • updateMetricsPH

      public void updateMetricsPH(int it)
      Reconstruct the LQN metrics.

      A phLayers of this method reports one row per caller task, not one per entry, activity and call, so the per-element quantities the rest of SolverLN reads -- servt, residt, callservt, callresidt, tput -- are recovered analytically from the series-parallel weights of the entry workflows.

      The split is conservative by construction. A station reports a phResidence time R per visit against a service law of mean S, so the queueing inflation R/S is attributed to every leaf of that visit in proportion to its own mean: the pieces sum back to R exactly.

      Parameters:
      it - iteration number

    • updateThinkTimesPH

      public void updateThinkTimesPH(int it)
      Surrogate delay of every caller.

      Same closure as updateThinkTimes -- a thread of the task is idle for whatever of its cycle the task's own station does not hold -- but the rate it is normalised by is the INVOCATION rate of the task and not the throughput of its station. Under this method a caller class reaches the server once per invocation of the caller, carrying its whole call burst in its service law, so the station rate counts caller cycles rather than calls and the two differ by the mean number of calls.

      Parameters:
      it - iteration number

    • getEnsembleAvgPH

      public Matrix[] getEnsembleAvgPH()
      LQN-level results. The layers report per caller task, so every entry, activity and call figure is rebuilt from the converged fixed point rather than read off a class row, in the same layout getEnsembleAvg returns.
      Returns:
      {QN, UN, RN, TN, AN, WN}, each a 1 x (nidx+1) row indexed by element index