mdd_descriptor.h File Reference

Kronecker rate descriptor of a single-class closed queueing network. More...

#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/mdd/mdd_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for mdd_descriptor.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mdd

Functions
template<class T>
MddDescriptor< T >	line::mdd::mdd_descriptor (const std::vector< T > &mu, const Matrix< T > &P, const std::vector< double > &servers, int N, const std::vector< MddServiceLaw< T > > &proc=std::vector< MddServiceLaw< T > >(), const std::vector< std::string > &sched=std::vector< std::string >())
	Build the descriptor.

Detailed Description

Kronecker rate descriptor of a single-class closed queueing network.

Port of matlab/src/api/mdd/mdd_descriptor.m, jline.api.mdd.Mdd_descriptor and python/line_solver/api/mdd/descriptor.py, for the Miner-Ciardo-Donatelli aggregation mdd_mcd (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.

Definition in file mdd_descriptor.h.