Package jline.api.pfqn

Class Pfqn_sdr

java.lang.Object
jline.api.pfqn.Pfqn_sdr
public class Pfqn_sdr extends Object
Product-form state-dependent routing of Krzesinski (1987), "Multiclass Queueing Networks with State-Dependent Routing", Performance Evaluation 7(2):125-143, the multiclass generalization of Towsley (1980), J. ACM 27(2):323-337.

Branch index 1 denotes the complement M-V and is unused; the SDR branches are numbered 2..B, that is indices 1..B-1 of the zero-based arrays, following the paper's own indexing so that d_tb transcribes straight from the text.

See Also:

  • Constructor Details

    • Pfqn_sdr

      public Pfqn_sdr()

  • Method Details

    • pfqn_sdrcoeff

      public static Pfqn_sdr.Coeff pfqn_sdrcoeff(StateDepRouting sdr)
      Validates an SDR structure and returns its derived coefficients.

      The population bounds are consequences of the coefficients, not independent inputs: with C_t negative the routing enforces m_b <= d_tb/(-C_t) and v_t <= D_tt/(-C_t) by itself.

      Parameters:
      sdr - the structure to validate
      Returns:
      its derived coefficients

    • pfqn_sdrprob

      public static double[] pfqn_sdrprob(Pfqn_sdr.Coeff c, double[] n)
      SDR routing probabilities of eq. (10).

      Entry b of the returned array is the probability of proceeding from the entry center e of Q(V,V) to the entry center of branch b; entry 0 is zero because branch index 1 denotes the complement M-V. The residual mass 1 - sum is the probability of proceeding directly to the departure center d, that is of being denied entry into Q(V,V) and returned to e, which is the busy form of waiting of Section 2.5.

      These probabilities are chain independent: they read the total branch and subnetwork populations, not the per-chain ones. The chain-dependent form of eq. (1) has no published product form and is not implemented. A branch population beyond the bound that SDR enforces itself is unreachable, and the probability returned there is zero.

      Parameters:
      c - derived coefficients from pfqn_sdrcoeff(jline.lang.StateDepRouting)
      n - per-center total populations, indexed as the structure is
      Returns:
      the probabilities to each branch entry, index 0 unused

    • pfqn_sdrped

      public static double pfqn_sdrped(double[] P)
      Probability of being denied entry into Q(V,V) and routed straight to the departure center, given the branch probabilities of pfqn_sdrprob(jline.api.pfqn.Pfqn_sdr.Coeff, double[]).
      Parameters:
      P - the branch probabilities
      Returns:
      one minus their sum

    • pfqn_sdr

      public static Pfqn_sdr.Result pfqn_sdr(Matrix S, Matrix xi, Matrix N, StateDepRouting sdr, Matrix alpha)
      Exact product form of eq. (16), by summation over the reachable state space.

      P(n) is G^-1 times the product over centers of f_i(n_i), the product over levels of Omega_{t-1,t}(v_t)/Omega_tt(v_t), and the product over branches of Delta_tb(m_b), with f_i(n_i) = [n_i!/beta_i(n_i)] times the product over chains of gamma_ij^n_ij/n_ij! and gamma_ij = xi_ij/mu_ij.

      This is general in the branch topology: a branch may hold several interconnected centers. Only the paper's Section 4 MVA and convolution algorithm is restricted to single-center branches.

      S and xi are required separately rather than as their product because under SDR the xi are not visit ratios, so the per-center throughputs cannot be recovered from the demands alone.

      Parameters:
      S - mean service times, centers by chains
      xi - coefficients of Section 3.2, centers by chains
      N - chain populations
      sdr - the routing structure, in center indices
      alpha - load-dependent rate scalings, alpha.get(i,k-1) = alpha_i(k); null for fixed rate
      Returns:
      the mean performance measures

    • pfqn_sdrvisits

      public static Matrix pfqn_sdrvisits(StateDepRouting sdr, List<Matrix> P)
      Coefficients xi of Section 3.2.

      P is a list with one center-by-center matrix per chain, holding the state-independent routing probabilities. Three rules fix the coefficients: the complement M-V obeys the ordinary traffic equations with the whole SDR subnetwork collapsed into a single e to d arc of probability one; every branch obeys its own traffic equations driven by an injection of xi_e at its entry center; and xi_e is one.

      The paper states xi_ij = xi_ej for the branch entry and departure centers and works out only single-center branches. The traffic equations above are the reading that extends it: they return xi at the branch departure equal to xi_e because a customer leaves a branch only through it, and xi at the branch entry equal to xi_e whenever that center takes no internal feedback. They have been checked against a brute-force CTMC on a branch that does take such feedback, where the literal rule fails.

      These xi are not relative visit counts: the rate at which customers enter a branch is state dependent, so a ratio of two xi carries no flow meaning.

      Parameters:
      sdr - the routing structure, in center indices
      P - one center-by-center SIR routing matrix per chain
      Returns:
      the coefficients, centers by chains

    • pfqn_sdrmva

      public static Pfqn_sdr.Result pfqn_sdrmva(Matrix S, Matrix xi, Matrix N, StateDepRouting sdr, Matrix alpha)
      Section 4 mean value analysis and convolution.

      Same inputs and outputs as pfqn_sdr(jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.lang.StateDepRouting, jline.util.matrix.Matrix), which evaluates eq. (16) exactly by state enumeration, so the two are directly comparable. This routine costs O(J T M (V_1...V_J)^2) rather than the size of the state space, at the price of two restrictions the paper itself imposes: every SDR branch must hold a single centre, and every C_t must be negative. A C_t other than -1 is rescaled internally, which leaves eqs. (10) and (16) unchanged because the level factors telescope.

      Two formulas of Section 4 are corrected here, both verified against pfqn_sdr(jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.lang.StateDepRouting, jline.util.matrix.Matrix). The initialise step of 4.2.2 divides by T_j(V-1_j,V_T) where the convolution identity G(V)/G(V-1_j) = 1/T_j(V) gives T_j(V,V_T); this implementation forms G = g_mva Omega_{T-1,T}/Omega_TT directly instead. And 4.2.3's T_ij = xi_ij [d_1i - Q_i] T_j drops the state-dependent omega ratios of eq. (10); the exact identity is T_ij = xi_ij T_j(N,M) E_{N-1_j}[P_{e,e(i)}].

      Parameters:
      S - mean service times, centres by chains
      xi - coefficients of Section 3.2, centres by chains
      N - chain populations
      sdr - the routing structure, in centre indices
      alpha - load-dependent rate scalings, or null for fixed rate
      Returns:
      the mean performance measures