Fluid priority queue: per-class fluid level and sojourn time of an MMAP[K]/PH[K]/1-type continuous fluid queue served in priority order. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/mam/mfq_multiregime.h"
#include "line/api/mam/mfq_solve.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/expm.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for mfq_prio_queue.h:

Classes
struct	line::mam::FluidPrioOptions
	Which measures to compute, and the numerical options. More...
struct	line::mam::FluidPrioResult
	One entry per analyzed class, in the order given by FluidPrioOptions::classes. More...

Namespaces
namespace	line
namespace	line::mam

Functions
FluidPrioResult	line::mam::mfq_prio_queue (const Matrix< double > &Q, const Matrix< double > &R, double d, const FluidPrioOptions &opt)
	Fluid priority queue.

Detailed Description

Fluid priority queue: per-class fluid level and sojourn time of an MMAP[K]/PH[K]/1-type continuous fluid queue served in priority order.

Port of matlab/src/api/mam/mfq_prio_queue.m and the BUTools FluidPrioQueue it wraps, which implements G. Horvath, "Efficient analysis of the MMAP[K]/PH[K]/1 priority queue", EJOR 246(1):128-139, 2015. A background chain with generator Q modulates the per-class fluid input rates R (one row per class) and the server drains fluid at the constant rate d, higher priority fluid first.

PRIORITY ORDER: ROW K IS THE HIGHEST PRIORITY, ROW 1 THE LOWEST. This is the opposite of the obvious reading and is worth stating first, because a port that assumes row 1 is highest produces plausible and wrong numbers. Two things in the reference fix it: the workload seen by class k is built from sum(R(k:end,:)), i.e. class k together with every class ABOVE it, and the k == K branch analyses class K as if no other class existed, which only the highest priority class can be.

METHOD. For each class k, the workload of classes k..K is a fluid queue with net drift diag(sum(R(k:end,:)))/d - I, solved by mfq_general_solve. That gives (mass0, ini, K, clo), which is put in the canonical similarity where the closing vector sums to one. For the highest priority class the answer follows directly from those matrices: its sojourn time is the matrix exponential law they define, and its fluid level is the ordinary fluid queue with constant service rate d (the needQL half of BUTools FluFluQueue, which is a handful of lines given mfq_general_solve, so it is inlined here rather than ported as a separate entry point).

For a lower priority class the server is interrupted by everything above it, so the measure is a BUSY PERIOD REWARD of the fluid queue formed by stacking the class-k workload on top of the background chain: F = [K clo; 0 Q], C = [I 0; 0 diag(sum(R(k+1:end,:)))/d - I], D = [0 0; 0 I] for sojourn time, or D = [0 0; 0 diag(R(k,:))] for fluid level. Its moments come from a recursion in the derivatives of F(v) closed by a Sylvester solve at each order; its distribution comes from ERLANGIZATION, replacing the deterministic horizon t by an Erlang of order L and rate L/t, which converges as O(1/L) and is why erlMaxOrder is an explicit option rather than a hidden constant.

AN EMPTY UP-DRIFT SET IS AN ANSWER HERE, NOT AN ERROR. The workload drift diag(sum(R(k:end,:)))/d - I is entirely negative whenever classes k..K never together exceed the service rate, and then that class simply never queues: every moment is zero and every distribution is one at every point. MATLAB returns exactly that, and it looks like a broken reference until the drift signs are checked. mfq_general_solve returns the degenerate law (no density, a point mass at zero equal to the stationary distribution) rather than refusing, which is what makes this path work.

DOUBLE ONLY. mfq_general_solve is gated on transcendental arithmetic and the erlangization is a tolerance-controlled truncation, but neither of those is the binding constraint: this function is written on Matrix<double> for the same reason mfq_multiregime is, namely that it is only ever consumed alongside them, and templating it would advertise a precision tier nobody has asked for and no test covers. If a Real50 instantiation is ever wanted, nothing in the algorithm forbids it – unlike mfq_multiregime, there is no eigendecomposition anywhere in this path.

References: G. Horvath, EJOR 246(1):128-139, 2015.

Definition in file mfq_prio_queue.h.

Classes

Namespaces

Functions

Detailed Description