Package jline.api.pfqn.mva

Class Pfqn_mvac

java.lang.Object
jline.api.pfqn.mva.Pfqn_mvac
public final class Pfqn_mvac extends Object

  • Method Details

    • pfqn_mvac

      public static Ret.pfqnMVAC pfqn_mvac(Matrix L, Matrix N)
      MVAC algorithm for a closed product-form network with no infinite-server center.

    • pfqn_mvac

      public static Ret.pfqnMVAC pfqn_mvac(Matrix L, Matrix N, Matrix Z)
      MVAC (Mean Value Analysis by Chain) algorithm for closed multichain product-form queueing networks composed of single-server fixed-rate (SSFR) queues and infinite-server (IS) centers.

      Unlike the classic MVA recursion of Pfqn_mva, which recurs on the population vector and costs O(prod(N+1)), MVAC recurs on the chains: each class is reduced to single-customer chains and the removed chains are replaced by self-looping single-customer (SCSL) chains pinned at a service center, so the multiplicity vector v = (v_1,...,v_J), with v_j the number of SCSL chains at center j, indexes the recursion in place of the population vector. MVAC is thus attractive for networks with few centers and many chains, and is the mean-value counterpart of the RECAL normalizing-constant recursion of Pfqn_recal. Since no normalizing constant is formed, MVAC does not suffer the floating-point underflow/overflow that complicates RECAL and convolution.

      With j, i indexing centers (j = 1,...,J1 SSFR and j = J1+1,...,J IS), k, l indexing single-customer chains, a_jk the relative utilization (service demand) of chain k at center j, a_k = sum_j a_jk, K the total number of single-customer chains and I_k = {v : sum_j v_j = K - k}, the recursion of Section II of the paper reads

         lambda^k_k(v) = 1 / (a_k + sum_{j=1}^{J1} a_jk (L^{k-1}_j(v) + v_j))     (10)
   L^k_{jk}(v)   = lambda^k_k(v) a_jk (1 + L^{k-1}_j(v) + v_j),  j SSFR     (9a)
   L^k_{jk}(v)   = lambda^k_k(v) a_jk,                           j IS       (9b)
   L^k_i(v)      = sum_j L^k_{jk}(v) L^{k-1}_i(v + 1_j) + L^k_{ik}(v)       (7)
   L^k_{il}(v)   = sum_j L^k_{jk}(v) L^{k-1}_{il}(v + 1_j),  l = 1,...,k-1  (6)

      with L^0_j(v) = 0, where L^k_j(v) is the mean number of customers at center j (SCSL customers excluded), L^k_{jl}(v) the mean number of chain-l customers at center j, and lambda^k_k(v) the throughput of chain k, all for the network with normalizing constant G_k(v). Equation (10) is the arrival-theorem closure obtained by summing (9a)-(9b) over all centers, since chain k holds a single customer. The measures of the original network are read off at k = K and v = 0.

      Part 1 of the basic step evaluates (10), (9) and (7) and yields the measures of chain K; part 2 evaluates (6) and yields those of the chains that visit at least one IS center, whose throughput then follows from Little's law at that center. Chains that visit only SSFR centers require a re-execution of part 1 with their label interchanged with K, which is cheap because the levels below the interchanged label are unaffected and are reused from the first execution. Classes with N_r > 1, and classes with identical demand columns, collapse into a single subset of identical single-customer chains: only one representative per subset is analyzed and its per-chain measures are scaled by the class population, so the cost depends on the number D of distinct chains rather than on K.

      Reference: A. E. Conway, E. de Souza e Silva and S. S. Lavenberg, "Mean Value Analysis by Chain of Product Form Queueing Networks", IEEE Trans. Computers, 38(3):432-442, 1989.

      Parameters:
      L - service demand matrix of the SSFR queues (M x R)
      N - population vector (1 x R), finite and nonnegative
      Z - service demand matrix of the IS centers, (1 x R) or (Mz x R), one row per IS center
      Returns:
      the per-class throughput, queue-length, utilization and residence time