solver_ctmc_waitq.h File Reference

Port of solver_ctmc_fcr_waitq.m: the reachability-built generator of a model whose finite capacity region applies WAITQ. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <deque>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "line/api/mc/ctmc_solve.h"
#include "line/lang/qn/network_struct.h"
#include "line/lang/qn/solver_feature_sets.h"
#include "line/lang/qn/state.h"
#include "line/lang/qn/state_events.h"
#include "line/solvers/ctmc/solver_ctmc.h"
#include "line/solvers/ctmc/solver_ctmc_analyzer.h"
#include "line/solvers/ctmc/solver_ctmc_fcr.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ctmc_waitq.h:

Go to the source code of this file.

Classes
struct	line::ctmc::WaitqState< T >
	One augmented state: the network state, plus the token FIFO of every region. More...
struct	line::ctmc::WaitqResult< T >
	The chain the WAITQ walk produces, alongside the FIFOs its states carry. More...
struct	line::ctmc::WaitqSolution< T >
	A solved WAITQ model: the usual CTMC solution, plus what the FIFOs hold. More...
struct	line::ctmc::CtmcAnySolution< T >
	A CTMC solve routed to whichever path the model's region rules require. More...

Namespaces
namespace	line
namespace	line::ctmc

Functions
template<class T>
bool	line::ctmc::ctmc_has_waitq_region (const NetworkStruct< T > &sn)
	True when the model declares a region that applies anything other than DROP.
template<class T>
void	line::ctmc::ctmc_check_waitq_support (const NetworkStruct< T > &sn)
	The combinations the reference gates, plus the two this port cannot represent.
template<class T>
WaitqResult< T >	line::ctmc::solver_ctmc_waitq (const NetworkStruct< T > &sn, const CtmcOptions &opt)
	Port of the reachability walk of solver_ctmc_fcr_waitq.m.
template<class T>
std::vector< T >	line::ctmc::ctmc_waitq_parked (const NetworkStruct< T > &sn, const WaitqResult< T > &r, const std::vector< T > &pi)
	The mean number of parked jobs per class, over a stationary law.
template<class T>
WaitqSolution< T >	line::ctmc::solver_ctmc_waitq_analyzer (const NetworkStruct< T > &sn, const CtmcOptions &opt)
	Build the WAITQ chain, solve it, and map it onto the same means every other CTMC path reports.
template<class T>
CtmcAnySolution< T >	line::ctmc::solver_ctmc_analyzer_any (const NetworkStruct< T > &sn, const CtmcOptions &opt)
	The entry point a caller who does not know which path a model needs should use: pick the WAITQ walk when a region asks for anything other than DROP, and the lattice analyzer otherwise.
template<class T>
mva::AvgResult< T >	line::ctmc::solver_ctmc_run_analyzer_any (const NetworkStruct< T > &sn, const CtmcOptions &opt)
	Solve on whichever path applies and format, mirroring solver_ctmc_run_analyzer.

Detailed Description

Port of solver_ctmc_fcr_waitq.m: the reachability-built generator of a model whose finite capacity region applies WAITQ.

WHY THIS IS A SEPARATE GENERATOR AND NOT A FILTER. Under DROP a refused job is destroyed, so the chain never occupies a forbidden state and censoring the enumerated space IS the censored chain – that is solver_ctmc_fcr.h. Under WAITQ the refused job LEAVES its upstream station and parks in a per-region FIFO of (class, destination) tokens that sits outside every station. That FIFO is state, it is owned by the region rather than by any node, and no filter on the per-node state space can represent it. The state here is therefore augmented as [per-node states, buf_1, ..., buf_F] and the transition relation is rebuilt around it.

THE FOUR RULES THAT MAKE WAITQ WHAT IT IS, all from the JMT reference:

1. RELEASE IS STRICTLY HEAD-OF-LINE. After every transition that frees capacity, tokens leave in FIFO order and a head that still does not fit blocks the whole queue behind it, even where a token further back would fit. Releasing the first token that fits instead would be a different discipline with a different mean.
2. A FRESH ARRIVAL IS NOT QUEUED BEHIND THE FIFO. It is admitted whenever the constraints permit, so it overtakes a head stuck on a different constraint. The FIFO gates only the jobs already in it.
3. THE RELEASE CASCADE IS PART OF THE SAME TRANSITION. Freeing one slot can release a token whose admission frees another slot, and so on; the chain jumps straight to the settled state. Splitting the cascade into separate transitions would invent intermediate states with a residence time the model does not have.
4. PARKED JOBS ARE IN NO STATION AND IN NO REGION. Station queue lengths exclude them, which is the JMT report convention; they are visible only through ctmc_waitq_parked, and any population accounting has to add them back by hand.

A CLASS SWITCH INSIDE ONE REGION IS THE SUBTLE CASE. Such a hop leaves the region occupancy unchanged in total but moves one job between the per-class counts, so it can violate a per-class cap that the pre-transition state satisfied. It cannot be tested before the transition either, because the departure frees the old class's slot first. It is therefore deferred: the re-entry is resolved after the release cascade has settled, and parked at the TAIL if it still does not fit, since it was refused after every token already in the queue.

Definition in file solver_ctmc_waitq.h.