Package jline.api.pfqn.ld

Class Pfqn_mvacld

java.lang.Object
jline.api.pfqn.ld.Pfqn_mvacld
public final class Pfqn_mvacld extends Object

  • Method Details

    • pfqn_mvacld

      public static Ret.pfqnMVACLD pfqn_mvacld(Matrix L, Matrix N, Matrix mu)
      MVAC for a load-dependent closed network with no infinite-server center.

    • pfqn_mvacld

      public static Ret.pfqnMVACLD pfqn_mvacld(Matrix L, Matrix N, Matrix Z, Matrix mu)
      MVAC (Mean Value Analysis by Chain) for a closed multichain product-form queueing network that may contain queue-length dependent (QLD) service centers. This is the Section V extension of Conway, de Souza e Silva and Lavenberg, IEEE Trans. Computers 38(3):432-442, 1989; Pfqn_mvac implements Sections II-IV, which cover single-server fixed-rate (SSFR) and infinite-server (IS) centers only.

      Where Pfqn_mvac propagates the MEAN queue-lengths L^k_j(v) through eq. (7) and closes the recursion with the arrival-theorem identity (10), the QLD extension propagates the MARGINAL queue-length DISTRIBUTIONS P^k_j(n,v) instead. That is forced by load dependence -- the rate seen by a job depends on the whole occupancy, so a mean no longer suffices -- but it also SIMPLIFIES the recursion: eq. (21)-(25) read level k-1 only at the shifted vectors v + 1_i, so the basic step sweeps v in I_k alone, where Pfqn_mvac must sweep the larger I_k u ... u I_K. The marginals come almost for free and are returned as a first-class output.

      Notation follows Pfqn_mvac: j, i index centers (j = 1,...,J1 the QLD centers of L, j = J1+1,...,J the IS centers of Z), k, l index the single-customer chains, a_jk = theta_jk T_jk is the demand of chain k at center j, K = sum(N) and I_k = {v : sum_j v_j = K - k} with v_j the number of self-looping single-customer (SCSL) chains pinned at center j. P^k_j(n,v) is the probability of n customers at center j -- EXCLUDING the v_j SCSL customers there -- in the network with normalizing constant G_k(v). Writing tau_k(v,i) for the throughput of an SCSL chain that replaces chain k at center i:

         tau_k(v,i)  = T_ik^-1 sum_{n=0}^{k-1} P^{k-1}_i(n,v+1_i)
                              * mu_i(n+v_i+1)/(n+v_i+1)                     (21)
   tau_k(v,i)  = T_ik^-1,                                     i IS          (22)
   L^k_{jk}(v) = theta_jk tau_k(v,j)^-1 / sum_m theta_mk tau_k(v,m)^-1      (23)
   lambda^k_k(v) = tau_k(v,j(k)) L^k_{j(k)k}(v)                             (24)
   P^k_j(n,v)  = L^k_{jk}(v) P^{k-1}_j(n-1,v+1_j)
                 + sum_{m != j} L^k_{mk}(v) P^{k-1}_j(n,v+1_m)              (25)

      with P^0_j(0,v) = 1 and P^{k-1}_j(n,.) = 0 for n < 0 or n > k-1. Eq. (21) is just "the mean rate at which an SCSL chain is served": given n other customers the processor-sharing rate share is mu_i(n+v_i+1)/(n+v_i+1), averaged over the distribution of those others. The queueing discipline may be assumed PS with no loss of generality, since product-form measures do not depend on it.

      This implementation writes (23)-(24) in the reference-station-free form

         c_i(k,v)      = sum_{n=0}^{k-1} P^{k-1}_i(n,v+1_i) mu_i(n+v_i+1)/(n+v_i+1)
   L^k_{jk}(v)   = (a_jk/c_j) / sum_m (a_mk/c_m)
   lambda^k_k(v) = 1 / sum_m (a_mk/c_m)

      which follows from theta_jk tau_k(v,j)^-1 = a_jk/c_j and theta_{j(k)k} = 1, so only the demands a_jk are needed and the visit ratios never appear separately. For an IS center c_i = 1 identically, which is exactly (22). Eq. (25) is self-normalizing, sum_n P^k_j(n,v) = sum_m L^k_{mk}(v) = 1, so no normalizing constant is formed and the recursion involves only positive quantities: unlike the classic load-dependent MVA of Pfqn_mvald it cannot produce negative probabilities and needs no stabilization.

      Parts 2 and 3 are unchanged from Pfqn_mvac, since eq. (6) holds verbatim in the presence of QLD centers: part 2 resolves the chains that visit at least one IS center, and the chains that visit no IS center are resolved by re-executing part 1 with their label interchanged with K.

      Parameters:
      L - service demand matrix of the QLD centers (M x R)
      N - population vector (1 x R), finite and nonnegative
      Z - demand matrix of the IS centers, (1 x R) or (Mz x R), one row per center
      mu - load-dependent rates (M x Nt) with Nt >= sum(N); mu(j,n-1) is the total service rate of center j with n jobs present. mu(j,:) = 1 is a single-server fixed-rate queue, mu(j,n-1) = min(n,c) a c-server queue, mu(j,n-1) = n an infinite server. A null or empty matrix means all centers are SSFR, in which case results agree with Pfqn_mvac
      Returns:
      per-class throughput, queue-length, per-station utilization, per-class cycle time and the marginal queue-length distributions