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

    • 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

    • 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

  • Constructor Details

  • Method Details

    • defaultOptions

      public static SolverOptions defaultOptions()

    • analyze

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

    • buildLayers

      public void buildLayers()

    • buildLayersRecursive

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

    • 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()

    • 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()

    • aT

      public AvgTable aT()

    • 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)