 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
Port of solver_fluid_kp.m: the fluid AND diffusion limits of the (MAP_t/Ph_t/inf)^N network of Y. More...
#include <algorithm>#include <cmath>#include <cstddef>#include <limits>#include <string>#include <type_traits>#include <vector>#include "line/api/mam/map_moment.h"#include "line/api/sn/sn_schedule_nominal.h"#include "line/lang/qn/network_struct.h"#include "line/solvers/fluid/fluid_stiff.h"#include "line/solvers/fluid/solver_fluid.h"#include "line/util/error.h"#include "line/util/lsoda.h"#include "line/util/matrix.h"Go to the source code of this file.
Classes | |
| struct | line::fluid::KpBlock |
| One (station, class) block of the Ko-Pender state vector. More... | |
| struct | line::fluid::KpEvent |
| struct | line::fluid::FluidKpTransient |
| The transient the covariance equation produces, i.e. More... | |
Namespaces | |
| namespace | line |
| namespace | line::fluid |
Enumerations | |
| enum class | line::fluid::KpEventKind { line::fluid::ArrivalPhase = 1 , line::fluid::Arrival = 2 , line::fluid::ServicePhase = 3 , line::fluid::Departure = 4 , line::fluid::Routed = 5 } |
| The five event families of Ko-Pender (3.1)-(3.2). More... | |
Functions | |
| template<class T> | |
| FluidSolution | line::fluid::solver_fluid_kp_core (const qn::NetworkStruct< T > &sn, const FluidOptions &opt, FluidKpTransient *tran) |
| The Ko-Pender solve, returning both the steady table and the covariance trajectory so that neither has to integrate twice. | |
| template<class T> | |
| FluidSolution | line::fluid::solver_fluid_kp (const qn::NetworkStruct< T > &sn, const FluidOptions &opt) |
| Port of solver_fluid_kp.m: the steady table at the horizon. | |
| template<class T> | |
| FluidKpTransient | line::fluid::solver_fluid_tran_avg_var (const qn::NetworkStruct< T > &sn, const FluidOptions &opt) |
| Port of @@SolverFLD/getTranAvgVar: the queue-length VARIANCE along the trajectory, per station and class, plus the full state covariance. | |
Port of solver_fluid_kp.m: the fluid AND diffusion limits of the (MAP_t/Ph_t/inf)^N network of Y.
M. Ko and J. Pender, "Diffusion limits for the (MAP_t/Ph_t/inf)^N queueing network", Oper. Res. Lett. 45 (2017) 248-253.
The mean and the covariance are integrated JOINTLY:
dq/dt = A f(t,q) dSigma/dt = J Sigma + Sigma J' + G, J = A df/dq, G = A diag(f) A'
with A the jump matrix whose column e is the jump vector of event e. G is exactly dH dH' of the paper's Theorem 3.3, each independent Poisson term contributing l_e l_e' f_e. Where f is affine in q – infinite-server stations and the arrival phase process – J does not depend on q and both equations close EXACTLY, so for the (MAP/Ph/inf)^N case the mean and covariance are exact rather than asymptotic. Finite-server stations are admitted through the usual fluid min(x,c) term, where the covariance degrades to a linear noise approximation.
THIS IS THE ONLY FLUID METHOD IN THE PORT THAT RETURNS A SECOND MOMENT FOR AN OPEN NETWORK, and it is the only one whose second moment is TRANSIENT rather than stationary – minnormal solves a stationary Lyapunov equation, this integrates the covariance along the trajectory.
IT DELIBERATELY DOES NOT REUSE THE CLOSING ODE. That formulation routes a departure from the source to the destination station and returns mass through the STATIONARY arrival-instant vector pie, replacing the D1' operator by the rank-one map pie*(D1*e)', i.e. by the PH renewal process with representation (pie, D0). Its stationary arrival rate is exact but its autocorrelation is gone, and a non-renewal arrival stream is the entire point of a MAP.
WHAT THE _t OF (MAP_t/Ph_t/inf)^N IS. A MAPt or PHt carries a piecewise-constant (D0(t), D1(t)) schedule, and kp_pair_at returns the pair in force at time t – the nominal pair for a process with no schedule, which is what the reference's local_pair_at returns in the same case. Three things follow from a schedule being present, and all three are consequences of the SAME fact, that a cyclic model has no fixed point:
THE HORIZON. An unbounded timespan is resolved from the slowest rate, as before, but is then extended to at least ten full periods so that the trajectory has reached its periodic regime before anything is read off it.
THE STEP CAP. LSODA picks its step for accuracy of the SOLUTION and will happily step over a whole segment of a schedule, integrating a rate that was never in force. h_max is capped at a quarter of the narrowest segment.
THE STEADY-STATE ANSWER IS A TIME AVERAGE. The value at the horizon is an arbitrary point of the cycle, at which the source and the station throughput do not even agree. The metrics are instead the trapezoidal average over the last full period, on a mesh refined uniformly and BRACKETED at every segment boundary, so that no trapezoid interval straddles a jump in the arrival rate.
A non-cyclic schedule has a fixed point again – it is constant on its last segment – so it takes none of the three, exactly as in the reference.
State layout, station-major, arrival phases before service phases: u-block one per (EXT station, class): arrival MAP phase occupancy, sum 1 x-block one per (queueing station, class): fluid count in each service phase
Definition in file fluid_kp.h.
1.18.0