Package jline.api.qsys

Class Qsys_gig1_bnds_extremal

java.lang.Object
jline.api.qsys.Qsys_gig1_bnds_extremal
public final class Qsys_gig1_bnds_extremal extends Object
Extremal two-moment bounds for the GI/GI/1 queue.

WHAT THE INTERVAL MEANS. Two moments do not determine E[W]; they determine a SET of possible values, and the width of that set is the honest uncertainty in any two-moment approximation. The extremal distributions attain its ends:

  • the lower end with deterministic interarrival times and a three-point service law on multiples of that interval, closed form rho((1+cs^2)rho-1)^+/(2(1-rho)) (eq. 2.12);
  • the upper end asymptotically with TWO-POINT laws: an interarrival law with an atom at 0, and a service law whose upper atom runs off to infinity while its probability vanishes.

Making an interarrival time larger only empties the queue once, but making a service time larger delays every customer behind it, which is why the two ends look so different.

HOW THE UPPER END IS COMPUTED. Chen and Whitt reduce that limit to a D(1/p)/RS(D(rho),p)/1 model with p = 1/(1+ca^2) and RS a geometric random sum, then evaluate its mean waiting time by Spitzer's identity with the negative binomial pmf (their Algorithm 1). The sum is truncated in both indices, so this bound is a numerical limit, not a formula; the closed form of eq. (3.4) is within about 1% of it.

Port of MATLAB qsys_gig1_bnds_extremal.m. All four codebases form the pmf in LOG space rather than by the ratio recursion Algorithm 1 prints: the two are equivalent, but the recursion accumulates rounding over thousands of multiplications and would leave the ports agreeing only to about 1e-4.

Reference: Y. Chen, W. Whitt (2020). Algorithms for the upper bound mean waiting time in the GI/GI/1 queue. Queueing Systems 94, 327-356.

Since:
LINE 3.1.0

  • Field Details

    • DEFAULT_K

      public static final int DEFAULT_K
      Truncation of the negative binomial value.
      See Also:

    • DEFAULT_N

      public static final int DEFAULT_N
      Truncation of the random-walk length.
      See Also:

  • Method Details

    • qsys_gig1_bnds_extremal

      public static Map<String,Double> qsys_gig1_bnds_extremal(double lambda, double mu, double ca, double cs)
      Every bound at the default truncations.
      Parameters:
      lambda - arrival rate
      mu - service rate
      ca - coefficient of variation of the interarrival time
      cs - coefficient of variation of the service time
      Returns:
      map of times in queue, keyed as in the MATLAB struct

    • qsys_gig1_bnds_extremal

      public static Map<String,Double> qsys_gig1_bnds_extremal(double lambda, double mu, double ca, double cs, int K, int N, boolean skipTight)
      Parameters:
      lambda - arrival rate
      mu - service rate
      ca - coefficient of variation of the interarrival time
      cs - coefficient of variation of the service time
      K - truncation of the negative binomial value
      N - truncation of the random-walk length
      skipTight - skip the O(K*N) tight bound and return the closed forms only
      Returns:
      map with trafficIntensity, lowerBound, upperBound, upperBoundClosed, upperBoundDaley, upperBoundKingman, heavyTraffic, delta, relativeWidth and tightComputed; every waiting time is a TIME IN QUEUE, so add 1/mu for a response time

    • delta

      public static double delta(double rho)
      The D/M/1 root of eq. (3.5), delta = exp(-(1-delta)/rho), in (0,1).

      g(delta) = delta - exp(-(1-delta)/rho) is negative at 0 and positive just below 1, where the second root delta = 1 sits, so bisection on [0,1) finds the wanted root without landing on the trivial one.

      Parameters:
      rho - traffic intensity
      Returns:
      the root in (0,1)