Package jline.api.mdd

Class Mdd_descriptor

java.lang.Object
jline.api.mdd.Mdd_descriptor
public class Mdd_descriptor extends Object
Kronecker rate descriptor of a single-class closed queueing network.

For the Miner-Ciardo-Donatelli approximate-aggregation solver (Mdd_mcd), after A.S. Miner, G. Ciardo, S. Donatelli, "Using the exact state space of a Markov model to compute approximate stationary measures", SIGMETRICS 2000.

The transition rate matrix is expressed compositionally as R = sum_e (kron_k W_k^e) restricted to the reachable set, with W_k^e[i,j] = lambda_k^e[i] * Prob_k^e(i,j) (Eq. 1). Each level k is a station and each event e is a completion at station a routed to b.

Exponential stations. The local state is the population alone: W_a^e[i,i-1] = mu[a]*min(i,servers[a])*P[a][b] for i >= 1 (departure), W_b^e[i,i+1] = 1 for i <= N-1 (arrival), and the identity elsewhere.

Phase-type stations. The local state is the PAIR (population, phase of the job in service), encoded in one level rather than two. Splitting them does not work: on a completion routed into station b the phase at b restarts only when b was empty, a joint condition on b's two components, which is not a product of per-level terms. Merging them keeps every event local:

   index 0                   : station empty
   index 1 + (n-1)*h + (a-1) : n jobs present, job in service in phase a
   domain                    = 1 + N*h    (h = 1 reproduces index = n)

With exit vector t = D1*1 and entry law pie, departure (n,a)->(n-1,b) at t[a]*P[a][b]*pie[b] for n >= 2 and (1,a)->0 at t[a]*P[a][b]; arrival 0->(1,b) at pie[b] and (m,c)->(m+1,c) at 1 for m >= 1; internal (n,a)->(n,b) at D0[a][b] for n >= 1, a != b.

Restrictions. A phase-type station must be single-server: with c > 1 or an infinite server the local state would have to count jobs per phase rather than name one phase, a different and much larger encoding. It must also be NON-preemptive, because the composite level names the phase of the one job in service and restarts it at pie when the next job starts; under preemptive resume an arrival suspends that job and its phase has to be remembered, so the local state would need a stack of phases. That matters for LCFSPR, which is BCMP type 2 and stays product-form under general service: the insensitivity is real but is NOT reachable through this encoding. Exponential service is unaffected, preemption being immaterial by memorylessness. Pass the disciplines to have the case rejected rather than silently modelled as non-preemptive.

  • Method Details

    • mdd_descriptor

      public static MddDescriptor mdd_descriptor(double[] mu, double[][] P, double[] servers, int N, MddServiceLaw[] proc, String[] sched)
      Build the descriptor.
      Parameters:
      mu - station service rates, 1/E[S]; entry i is ignored when station i is given a phase-type law through proc
      P - station-to-station routing matrix, row-stochastic
      servers - servers per station, Double.POSITIVE_INFINITY for delay/IS
      N - closed population
      proc - per-station service law, or null for an exponential station; the array itself may be null when every station is exponential
      sched - per-station discipline names, consulted only to REJECT a phase-type law at a preemptive-resume or shared-server station; may be null when every station is non-preemptive