Package jline.api.lqn

Class LqnBalanceEquations

java.lang.Object
jline.api.lqn.LqnBalanceEquations
public final class LqnBalanceEquations extends Object
Conservation laws of a layered queueing network, enumerated from its structure.

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 fixed by the STRUCTURE of the model alone. This class 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 SolverLN imputes to the task, plus the declared think time of a reference task) and one service stage (holding a request from above). With B(t,k) the mean number of threads of t busy serving caller class k -- the per-class utilization in JOB units --

    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), giving X(t)*(Z(t)+z(t)) = N(t)*(1 - sum_k U(t,k)); at an infinite server the utilization is already a job count, so B = U. The caller classes k are the CALLS targeting an entry of t -- the in-edges of t in the call graph -- plus each entry of t carrying 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 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 reaching 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), with v from the activity precedence graph. 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).

hostutil -- the utilization law at a processor, sum_a X(a)*D(a) = m(h)*U(h); 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.

TWO INDEX SPACES, and they differ by one. The JAR LayeredNetworkStruct is 0-BASED: an element is 0..nidx-1, a call is 0..ncalls-1, callpair is (ncalls,2) with columns 0/1, and a not-found index is -1 because 0 is the first host. Everything this class EMITS is 1-BASED instead -- Relation.target, Relation.terms, Result.visits and the rows and columns of the incidence matrices are the struct index plus one -- which is also how a LqnBalanceEquations.Solution is indexed, so that a padded slot 0 can carry "unset" and the records read like the MATLAB and C++ twins. Internally the class works in the STRUCT's space throughout: the conversion happens exactly twice, at readSolution on the way in and at the r.target / r.terms assignments on the way out. Reading a struct field with a 1-based index is the standing trap here -- most of them are shorter than nidx (mult and sched stop after the tasks), so the slip surfaces as a silent NaN rather than as an error; see _kb/11-conventions-and-gotchas.md.

Twin of the MATLAB lqn_balance_equations.m, the Python line_solver.api.lqn.balance_equations and the C++ line/api/lqn/lqn_balance_equations.h. MATLAB and C++ are 1-based in their struct as well, so they need no conversion; Python is 0-based on both sides and emits 0-based indices.

Since:
LINE 3.0

  • Method Details

    • compute

      public static LqnBalanceEquations.Result compute(LayeredNetworkStruct lqn)
      Enumerate the relations of LQN symbolically.

    • compute

      public static LqnBalanceEquations.Result compute(LayeredNetworkStruct lqn, LqnBalanceEquations.Solution sol)
      Enumerate the relations of LQN and, when SOL is given, instantiate each one and report its residual.

      Conventions: rates and populations in a little record are PER REPLICA, matching updateThinkTimes -- X is tput/repl and N is the multiplicity of one copy. Elsewhere throughputs and utilizations are as the solver reports them, totalled over replicas, which is why the server count in hostutil is mult and not mult*repl. N(t) is lqn.mult; SolverLN iterates on njobs, which carries the interlocking corrections and may be maxmult under replication, so both are returned per record. S(k) is the entry SERVICE time (phase 1 plus phase 2), the time a thread is held, not the residence time the caller waits for; the difference is the phase-2 tail, flagged by phase2.