 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
The MAP/PH/c FCFS queue, solved exactly. More...
#include <cstddef>#include <vector>#include "line/api/mam/map_moment.h"#include "line/api/mam/ldqbd_mphc.h"#include "line/api/mam/qbd_r.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"Go to the source code of this file.
Classes | |
| struct | line::qsys::MapPhcResult< T > |
| Return value of qsys_mapphc, mirroring the MATLAB struct. More... | |
Namespaces | |
| namespace | line |
| namespace | line::qsys |
Functions | |
| template<class T> | |
| MapPhcResult< T > | line::qsys::qsys_mapphc (const mam::Map< T > &arrival, const std::vector< T > &alpha, const Matrix< T > &S, unsigned c, std::size_t dist_size, std::size_t num_w_moms, const std::vector< T > &w_points) |
| MAP/PH/c FCFS, exactly. | |
| template<class T> | |
| MapPhcResult< T > | line::qsys::qsys_mapphc (const mam::Map< T > &arrival, const std::vector< T > &alpha, const Matrix< T > &S, unsigned c) |
The MAP/PH/c FCFS queue, solved exactly.
THE STATE SPACE, AND WHY IT IS A MULTISET. With c identical servers the server identities carry no information, so the service phases are held as a MULTISET: a configuration is n = (n_1..n_ms) with sum(n) = k servers busy in phase i. There are binomial(ms+k-1,k) of those, the count of Asmussen and Moller (2001), against ms^k for the ordered space – for ms = 5, c = 6 that is 210 against 15625, which is what makes the exact solve feasible at all. Levels 0..c-1 are the boundary (level = servers busy), levels >= c repeat and carry the queue, so the tail is matrix-geometric in R.
THE WAITING TIME, AND WHY IT IS ONE LINEAR ODE. An arrival that finds j customers waiting ahead of it waits for exactly j+1 service completions, so Wq is the (j+1)-st event time of the configuration MAP (Lc, Cdep) started at the arrival-epoch configuration. The level distribution seen by an arrival is matrix-geometric, x_j = pi_c R^j kron(D1,I)/lambda, and folding over j gives
G'(t) = G(t) Lj + R G(t) Cj, G(0) = (I-R)^-1 kron(D1,I)/lambda, P(Wq > t) = pi_c G(t) e.
That is LINEAR in G, so Wq is matrix-exponential; vectorizing it column-major turns it into a single expm of order (ma*nc)^2. Its Laplace transform obeys the generalized Sylvester equation g(sI-Lj) - R g Cj = G(0), and differentiating that identity leaves the OPERATOR unchanged and only moves the right-hand side, so every moment is one more solve with the same matrix.
WHY NOT REUSE qsys_mapmc. That function is MAP/M/c: its phase is the arrival phase alone, because an exponential server has nothing to remember. Here the phase must also carry which service phase each busy server occupies, and the down block is a completion followed by an IMMEDIATE restart at alpha, which has no counterpart in the exponential case. The two agree exactly when ms = 1, and the test file checks that they do.
ARITHMETIC. Gated on num_traits<T>::has_transcendental: logarithmic reduction drives R to a tolerance and never terminates in a finite number of field operations, as in qbd_r.h. Everything consuming R is finite exact matrix algebra, except the CCDF, which needs expm.
References: S. Asmussen and J.R. Moller, "Calculation of the steady state waiting time distribution in GI/PH/c and MAP/PH/c queues", Queueing Systems 37(1):9-29, 2001. D.P. Gaver, P.A. Jacobs, G. Latouche, "Finite birth-and-death models in randomly changing environments", Adv. Appl. Probab. 16:715-731, 1984.
Definition in file qsys_mapphc.h.
1.18.0