Package jline.api.pfqn.ld

Class Pfqn_lldsingle

java.lang.Object
jline.api.pfqn.ld.Pfqn_lldsingle
public final class Pfqn_lldsingle extends Object
Same recursion, same arithmetic and bit-identical results to Pfqn_gldsingle, but with the rate-offset axis truncated at the limited load-dependence threshold instead of at the population.

Unrolling the recursion of Pfqn_gldsingle, 

   g(m,n,t) = g(m-1,n,1) + L_m/mu(m,t) * g(m,n-1,t+1)
shows that its third index is an offset into station m's rate function, 
   g(m,n,t) = sum_{j=0..n} prod_{i=0..j-1} L_m/alpha_m(t+i) * g(m-1,n-j,1)
so once t >= s_m, where s_m is the population past which alpha_m stays constant, every factor is alpha_m(s_m), the product collapses to (L_m/alpha_m(s_m))^j and 
   g(m,n,t) = g(m,n,s_m)   for all t >= s_m
The N-s_m upper slices that Pfqn_gldsingle computes are duplicates of one another. Capping the offset at s_m and reading g(m,n-1,min(t+1,s_m)) keeps every value the answer needs.

COST. O(N * sum_k s_k) time against O(M N^2), and O(N * max_k s_k) space against the dense map Pfqn_gldsingle builds, the levels being rolled. On a multiserver model, where s_k is the server count, this is LINEAR in the population rather than quadratic. The log-domain branch remains a sum of nonnegative terms and loses no digits to cancellation, unlike the closed form of Pfqn_explicit_ld, which reaches the same asymptotics through an alternating sum.

There is no gain on a station whose rates never settle, an infinite server alpha(n)=n being the usual case: it gets s_k = N and costs what it costs in Pfqn_gldsingle. The saving is over the OTHER stations, so a model carrying one delay among M queues drops from O(M N^2) to O(N^2 + N sum_k s_k).

The threshold is detected per station rather than declared, so an arbitrary rate matrix is accepted and simply yields s_k = N, at which point this is Pfqn_gldsingle with its slices rolled.

  • Method Details

    • pfqn_lldsingle

      public static Ret.pfqnNc pfqn_lldsingle(Matrix L, Matrix N, Matrix mu, SolverOptions options)
      Auxiliary function used by Pfqn_ncld and Pfqn_nre to compute the normalizing constant in a single-class limited load-dependent model.
      Parameters:
      L - demands at all stations
      N - number of jobs for each class
      mu - load-dependent scaling factors
      options - solver options
      Returns:
      normalizing constant (G) and its logarithm (lG)