Package jline.api.pfqn.nc

Class Pfqn_manjunath

java.lang.Object
jline.api.pfqn.nc.Pfqn_manjunath
public final class Pfqn_manjunath extends Object
Exact normalizing constant of a closed multiclass product-form network whose state space carries arbitrary linear integer constraints. This is the queueing-network half of the transform technique of Manjunath and Sikdar, of which Lossn_manjunath is the loss-network half. The two solve the same problem -- sum a product form over an irregular integer state space -- from opposite ends of the paper: Lossn_manjunath implements Section 2.2, a set of '<=' rows over the Poisson terms nu^n/n!, while this routine implements Section 3 together with Section 5.3, a MIXED set of '=', '<=' and '>' rows over the BCMP terms, where the population constraint of a closed network is itself one of the equalities. THE MODEL. M queueing stations (FCFS, PS or LCFS; rows of L) and Mz delay stations (rows of Z) serve R closed classes with populations N. Writing n_ir for the class r jobs at station i and n_i = sum_r n_ir, the BCMP product form of Baskett-Chandy-Muntz-Palacios is 
   p(n) = (1/G) prod_{i queueing} n_i! prod_r L_ir^{n_ir}/n_ir!
                prod_{i delay}         prod_r Z_ir^{n_ir}/n_ir!
Every state obeys the R population equalities sum_i n_ir = N_r; on top of those the caller may impose any number of further rows 
   sum_{i,r} A(j, i + S*r) n_ir  {=, <=, >}  b(j),   S = M + Mz,
i.e. A acts on the (M+Mz)-by-R occupancy read column by column with the queueing stations first. With no extra rows the routine returns exactly the normalizing constant of Pfqn_ca, which is the parity oracle used by the tests; with extra rows it answers a question no other routine in the pfqn family can, the convolution and MVA recursions having nowhere to carry a second constraint. WHY THE GENERATING FUNCTION IS A PRODUCT, AND WHERE THE n_i! GOES. Marking class r by z_r and row j by y_j, and abbreviating the monomial one class r job at station i contributes as u_ir = z_r prod_j y_j^{A(j, i + S*r)}, the sum over the occupancies of a single QUEUEING station is, by the multinomial theorem, 
   sum_{n_i.} n_i! prod_r (L_ir u_ir)^{n_ir}/n_ir!
     = sum_k (sum_r L_ir u_ir)^k = 1 / (1 - sum_r L_ir u_ir),
so the n_i! that couples the classes at a queueing station is exactly what turns its factor from an exponential into a geometric one. The paper reaches the same place through the Euler integral n! = int_0^inf e^-t t^n dt (Eqns 16-18), which is that geometric series evaluated; the closed form is used here because there is then no quadrature to discretize. A DELAY station has no n_i! and keeps its exponential. Hence 
   F(z,y) = prod_i 1/(1 - sum_r L_ir u_ir) prod_k prod_r exp(Z_kr u_kr)
and G is read off F as a coefficient: degree exactly N_r in z_r, and for row j the degree its sense dictates -- exactly b_j for '=', the sum of degrees 0..b_j for '<=' (the multiplier (y^{b+1}-1)/(y-1) of Eqn 5, whose residue is that partial sum), and the complement of the latter for '>' (Eqn 6). WHY IT IS A COEFFICIENT COMPUTATION AND NOT A QUADRATURE. The contour integrals of Eqn 9 all have their only pole at the origin, of order one more than the right-hand side, so each is a residue and hence a Taylor coefficient. The routine therefore never integrates: it carries F as a multivariate power series truncated at degree N_r in z_r and b_j in y_j. Truncation is exact because A is nonnegative -- no monomial above a cut can be brought back down by a later factor. Each queueing station is applied by SOLVING (1 - sum_r L_ir u_ir) x = ser rather than by expanding the geometric series, which keeps the cost at one pass. Every monomial of the operator carries z_r to a strictly higher power, so sweeping the lattice in increasing flat index lets each coefficient read only coefficients already final: a Gauss-Seidel sweep whose result is the exact solve, not an iterate. A delay station has no such recurrence and is convolved with exp term by term, which is where its extra factor of the population in the cost comes from. THE ELIMINATION ORDER IS THE MEMORY BOUND. Variable y_j is created when the first station its row touches is multiplied in and discharged immediately after the last, so peak memory is prod_r (N_r+1) times the product of (b_j+1) over the SIMULTANEOUSLY LIVE rows, not over all rows. A row constraining one station therefore costs essentially nothing. The class axes are live throughout, so prod_r (N_r+1) is a floor -- the same lattice Pfqn_ca walks. SCOPE. Load-dependent and multiserver stations are NOT covered: their per-station term is not geometric, and while the paper admits an arbitrary f_i(n_i) in the single-class case (Section 2), the multiclass n_i! coupling used above then breaks. Use Pfqn_gld or Pfqn_conwayms for those. A and b must be integer valued and A nonnegative, since the residue argument counts whole units; a fractional entry is refused rather than rounded. Reference: D. Manjunath and B. Sikdar, Integral Expressions for the Numerical Evaluation of Product Form Expressions Over Irregular Multidimensional Integer Spaces. Sections 3 and 5.3.

  • Method Details

    • pfqn_manjunath

      public static Ret.pfqnManjunath pfqn_manjunath(Matrix L, Matrix N)
      Exact normalizing constant of an unconstrained closed network.

    • pfqn_manjunath

      public static Ret.pfqnManjunath pfqn_manjunath(Matrix L, Matrix N, Matrix Z)
      Exact normalizing constant of an unconstrained closed network with delay.

    • pfqn_manjunath

      public static Ret.pfqnManjunath pfqn_manjunath(Matrix L, Matrix N, Matrix Z, Matrix A, Matrix b, String sense)
      Exact normalizing constant of a constrained closed product-form network.
      Parameters:
      L - service demand of class r at queueing station i (MxR)
      N - population of class r (1xR nonnegative integers)
      Z - think time of class r at delay station k (MzxR), may be null
      A - extra constraint coefficients on the occupancy read column by column (Jx((M+Mz)*R) nonnegative integers), may be null
      b - extra constraint right-hand sides (Jx1 integers), may be null
      sense - one character per row, 'E' (=), 'L' (<=) or 'G' (>); null means all 'L'

    • pfqn_manjunath

      public static Ret.pfqnManjunath pfqn_manjunath(Matrix L, Matrix N, Matrix Z, Matrix A, Matrix b, String sense, boolean stats)
      As above, additionally returning the per-class decomposition when stats is set. That requires the ONE configuration in which the truncated product form is the EXACT stationary law: a single queueing station inside the region and a SINGLE DELAY STATION OUTSIDE IT. Anything else is refused by name rather than answered wrongly.

      WHY THE CONFIGURATION IS NOT A CONVENIENCE. With one queueing station the state is the queue occupancy alone (the delay holds the complement) and every transition moves one job of one class by one unit, so the chain is a multidimensional birth-death process. That process is reversible, and Kelly's truncation theorem then applies verbatim: restricting it to the coordinate-convex set A n <= b and renormalizing gives exactly the truncated product form. Add a second queueing station and the delay -> q1 -> q2 -> delay cycle destroys reversibility; truncation no longer preserves the product form, measured at 131% relative error on the stationary law of a 2-class, N = [2 2] instance. G and lG stay correct as a sum over the admissible set in every configuration; only the metrics are withheld.

      Everything follows from two ratios of normalizing constants, both taken in the log domain so the internal rescaling cancels without being reconstructed: X_r = G(N - e_r ; b - A(:,qcol_r)) / G(N ; b), and P(n_qr = k) = G(N ; b plus the row n_qr = k) / G(N ; b). The first is the loss network's g(C - A e_r) in another guise.