Port of solver_mam_bgchain.m and its three helpers: the analyzer that treats the CLOSED classes as a background modulating chain and the OPEN classes as matrix-analytic queues driven by it. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <map>
#include <string>
#include <vector>
#include "line/api/mam/ldqbd.h"
#include "line/api/mam/map_moment.h"
#include "line/api/mam/map_transform.h"
#include "line/api/mam/mmap_assemble.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/api/sn/sn_rt_stations.h"
#include "line/lang/distribution.h"
#include "line/lang/qn/network_struct.h"
#include "line/lang/qn/state.h"
#include "line/solvers/mam/mam_types.h"
#include "line/solvers/mva/mva_types.h"
#include "line/solvers/mva/sn_chain.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/matrix.h"

Include dependency graph for solver_mam_bgchain.h:

Classes
struct	line::mam::BgchainCtmc< T >
	The solved background modulating chain. More...
struct	line::mam::BgchainEnv< T >
	The environment one station sees: the background chain lumped onto its occupancy. More...
struct	line::mam::BgchainStation< T >
	What one modulated station QBD returns. More...

Namespaces
namespace	line
namespace	line::mam

Functions
template<class T>
BgchainCtmc< T >	line::mam::mam_bgchain_ctmc (const std::vector< int > &Nb, const std::vector< std::vector< T > > &STb, const std::vector< Matrix< T > > &Pb, const std::vector< bool > &isinf_i, const std::vector< double > &nsrv, const std::vector< std::vector< double > > &cshare, const std::vector< std::vector< bool > > &supp, std::size_t states_max)
	Build and solve the background chain (mam_bgchain_ctmc.m).
template<class T>
BgchainEnv< T >	line::mam::mam_bgchain_env (const BgchainCtmc< T > &bg, std::size_t i)
	Lump the background chain onto the closed occupancy of station i (mam_bgchain_env.m).
template<class T>
BgchainStation< T >	line::mam::mam_bgchain_station (const Matrix< T > &Da0, const Matrix< T > &Da1, const std::vector< T > &alpha_s, const Matrix< T > &Tsvc, const Matrix< T > &Ain, const std::vector< int > &esup_in, double nservers, const std::vector< double > &gref_in, std::size_t Kmax)
	Solve the open classes of one station as a modulated level-dependent QBD (mam_bgchain_station.m).
template<class T>
double	line::mam::bgchain_states (const qn::NetworkStruct< T > &L, const MamOptions &opt)
	Port of solver_mam_bgchain.m.
template<class T>
mva::MvaSolution< T >	line::mam::solver_mam_bgchain (const qn::NetworkStruct< T > &L, const MamOptions &opt)

Detailed Description

Port of solver_mam_bgchain.m and its three helpers: the analyzer that treats the CLOSED classes as a background modulating chain and the OPEN classes as matrix-analytic queues driven by it.

A purely CLOSED model is the degenerate case of the same construction – with no open work to take a share of the servers the chain alone answers, and it answers with the EXACT closed CTMC at chain granularity – so only a purely OPEN model is refused.

WHY IT EXISTS. dec.source replaces a closed chain by a Poisson surrogate at the current throughput iterate, which is exactly the part of a mixed model it has least information about; measured against SolverCTMC that costs it 10-24% on the queue lengths. But the closed population vector is the one part of a mixed model whose state space is BOUNDED, so it can be solved exactly. This method does that, and hands each open station a station-local Markovian environment read off the chain, turning it into a level-dependent QBD whose phase carries the number of closed jobs competing for its server.

1 background chain the closed population vector over the stations the closed classes visit (mam_bgchain_ctmc) 2 environment that chain lumped onto the closed occupancy of ONE station (mam_bgchain_env) 3 open station a MAP/PH/c queue modulated by that environment, solved as a level-dependent QBD (mam_bgchain_station) 4 fixed point the capacity share feeds step 1 and closes

TAGGED-CLASS ITERATION. Step 1 is a population process of dimension (closed chains) x (stations), so its state space is exponential in the number of closed chains R. The method therefore keeps ONE chain free at a time: the tagged chain r is carried exactly, the other R-1 collapse into flow-equivalent aggregate classes whose population is their total and whose service time and routing at each station are their throughput-weighted means (Chandy-Herzog-Woo). Each chain takes its turn as the tagged one and reads its own metrics off the chain it is exact in; the open results are averaged over the passes.

HOW MUCH TO AGGREGATE is options.config.bgaggr, the number G of aggregate classes; the background chain then carries 1 + G. G = 1 is the classic tagged/aggregate pair and the default, so the chain stays two-class whatever R is; G >= R-1 aggregates nothing, carries every closed chain exactly, and answers in ONE pass instead of solving the same chain R times. Passing R reaches that, so asking for no aggregation needs no magic value. The cost is the state space, the product over the 1 + G classes of nchoosek(N_b + Mc - 1, Mc - 1), capped by bgstates_max.

WHICH CHAINS SHARE A GROUP is decided by similarity of per-station SERVICE DEMAND. An aggregate carries the flow-weighted mean of its members' service times and routing, so it is exact when they place the same demand at every station and distorts in proportion to how far apart they are; grouping the demand-similar chains together keeps the aggregation where it is harmless and away from the chains it would misrepresent.

THE EXCHANGED QUANTITY IS THE SHARE, NOT THE MEAN OCCUPANCY. The two halves iterate on cshare(i,e) = E[min(e+k,c) e/(e+k)], the mean number of servers of station i that its e closed jobs hold, averaged over the open occupancy k. Exchanging the mean open occupancy instead and rebuilding the share from it is what a first cut does and it is WRONG: e/(e+k) is convex in k, so Jensen biases the closed service rate down and the closed throughput with it. The environment generator inside the QBD is level-dependent for the same reason.

EXACTNESS, measured against SolverCTMC and exact MVA on mixed models of two to four stations: PS or INF with ANY service law (exponential, Erlang, HyperExp, Coxian), any number of servers, Poisson or MAP arrivals and one to four closed chains agree to 4-5 significant digits, as does FCFS with class-INDEPENDENT rates. FCFS with class-DEPENDENT rates keeps the closed queue lengths within ~1% while the open queue length reads 14-20% low, the server being held here in random order rather than head-of-line.

PS IS INSENSITIVE to the service law beyond its mean, and the method honours that rather than approximating it: at a PS station the open service is replaced by the exponential of the same mean before the QBD is built. This QBD tracks ONE service phase for the whole station, so carrying the phase-type there makes the open queue length inherit the SCV-sensitivity of an M/PH/1 FCFS queue – measured, a HyperExp of SCV 4 read 21% high where the exact answer is the exponential one to five digits. At an FCFS station the service law IS carried, collapsed into one phase-type process scaled by the share (the same collapse solver_mam_ldqbd documents), and the background chain reads only the MEAN closed service time.

ARITHMETIC. The path runs ctmc_solve on the background chain and the level-dependent QBD recursion on each station, the latter falling back to a pseudo-inverse on a singular level, so it is gated on transcendental arithmetic exactly as solver_mam_ldqbd is.

Definition in file solver_mam_bgchain.h.

Classes

Namespaces

Functions

Detailed Description