Package jline.api.pfqn.nc

Class Pfqn_mcmc

java.lang.Object
jline.api.pfqn.nc.Pfqn_mcmc
public final class Pfqn_mcmc extends Object
Markov chain Monte Carlo estimator of the class throughputs X(r) = G(N-e_r)/G(N) and of the mean queue lengths Q(i,r) of a CLOSED multiclass product-form (BCMP, no type changes) network, by the REGULARIZATION algorithm of

W. Chen, C. A. O'Cinneide, "Towards a Polynomial-Time Randomized Algorithm for Closed Product-Form Networks", ACM TOMACS 8(3):227-253, 1998.

The three steps of the paper are:

I. CONSTRUCT THE REGULARIZED NETWORK. Write rho(i,r) for the surrogate traffic intensity of class r at station i -- here the service demand, since rho = lambda/mu is a visit ratio over a service rate -- and rho(r) = sum_i rho(i,r). The regularized network has the same stations, classes and populations, UNIT service rates at every station, the processor-sharing discipline, and a routing matrix that depends on the destination only, P*(i->m | class r) = rho(m,r)/rho(r). By Theorem 2.1 it is a REVERSIBLE chain with the SAME steady-state distribution as the original network, and its throughputs satisfy Theta*(r) = rho(r)*Theta(r).

II. SIMULATE IT at service-completion epochs. With Y(i,r) the number of class-r jobs at station i, Y(i) their total and Psi_i(k)=min(s_i,k) the number of busy servers,

     r(i,r) = Y(i,r)/Y(i) * Psi_i(Y(i)),   r(r) = sum_i r(i,r),
     r      = sum_i Psi_i(Y(i)),

the next completion is of class r at station i with probability r(i,r)/r, and the conditional expected time to it is 1/r. Equation (10) of the paper is the holding-time weighted ratio estimator Theta*(r) = sum_t r(r,t)/r(t) / sum_t 1/r(t), and the same weights give the time-average queue lengths, which need no transformation at all because the two networks share their steady state.

III. TRANSFORM BACK: X(r) = Theta*(r)/rho(r).

Because P* forgets the station of origin and every station serves at unit rate, the regularized chain has neither the slowly mixing routing chain nor the customer-trapping slow station that make the original chain converge slowly. The paper proves O(N^2*M^3) mixing in two special cases (Section 4) and reports the general behaviour experimentally (Section 5).

Delay (infinite-server) demand enters as ONE extra station with s = Inf and demand Z. Aggregating infinite-server stations that way is exact in the product form, since their joint term is multinomial in the per-class totals.

Confidence: the run is split into non-overlapping batches (Schmeiser 1982, 30 by default, the count used in the tables of the paper), the batch means of the ratio estimator give a standard error, and the result reports the paper's two-sigma interval. The estimator is a ratio of correlated averages, so it carries an O(1/samples) bias on top of the initialization bias; the paper ignores both, this implementation additionally discards a warm-up fraction (10% by default).

See Also:

  • Method Details

    • pfqn_mcmc

      public static Ret.pfqnMcmc pfqn_mcmc(Matrix L, Matrix N, Matrix Z, SolverOptions options)
      Single-server form: every queueing station serves one job at a time.
      Parameters:
      L - (M x R) per-class service demands at the M queueing stations
      N - (1 x R) closed population vector; finite and integer
      Z - (1 x R) aggregated think times, or a matrix summed over its rows
      options - solver options; may be null
      Returns:
      the throughput and queue-length estimates with their two-sigma intervals

    • pfqn_mcmc

      public static Ret.pfqnMcmc pfqn_mcmc(Matrix L, Matrix N, Matrix Z, Matrix s, SolverOptions options)
      Multiserver form, the paper's own selling point (its Tables IV and V).
      Parameters:
      L - (M x R) per-class service demands at the M queueing stations
      N - (1 x R) closed population vector; finite and integer
      Z - (1 x R) aggregated think times, or a matrix summed over its rows
      s - (M x 1) servers per station, infinite for an infinite server; null means all stations single-server
      options - solver options; may be null
      Returns:
      the throughput and queue-length estimates with their two-sigma intervals