 |
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_mam_traffic.m and solver_mam_traffic_mmap.m: the traffic step of the dec.mmap decomposition. More...
#include <cstddef>#include <map>#include <string>#include <utility>#include <vector>#include "line/api/mam/map_moment.h"#include "line/api/mam/mmap_compress.h"#include "line/api/mam/mmap_lambda.h"#include "line/api/mc/dtmc_stochcomp.h"#include "line/api/npfqn/npfqn_traffic_merge.h"#include "line/api/npfqn/npfqn_traffic_split_cs.h"#include "line/lang/qn/network_struct.h"#include "line/solvers/mam/mam_types.h"#include "line/util/error.h"#include "line/util/linalg.h"#include "line/util/matrix.h"Go to the source code of this file.
Classes | |
| struct | line::mam::TrafficConfig |
| The fields of options.config the traffic step reads. More... | |
| struct | line::mam::FjSyncMap |
| sn_build_fj_sync_map: which incoming flows at a Join must be synchronized. More... | |
Namespaces | |
| namespace | line |
| namespace | line::mam |
Typedefs | |
| template<class T> | |
| using | line::mam::DepTable = std::vector<std::vector<Map<T>>> |
| DEP{i,r}, the departure process of class r from i in (D0,D1) form. | |
Functions | |
| TrafficConfig | line::mam::traffic_config (const MamOptions &opt) |
| The traffic step's view of SolverOptions('MAM'). | |
| template<class T> | |
| Mmap< T > | line::mam::mmap_max (const Mmap< T > &a, const Mmap< T > &b, std::size_t k) |
| mmap_max(MMAPa, MMAPb, k): the synchronization of two flows through a join with a queue of length k on each side. | |
| template<class T> | |
| FjSyncMap | line::mam::sn_build_fj_sync_map (const qn::NetworkStruct< T > &sn) |
| sn_build_fj_sync_map. | |
| template<class T> | |
| std::vector< Mmap< T > > | line::mam::solver_mam_traffic (const qn::NetworkStruct< T > &sn, const DepTable< T > &DEP, const TrafficConfig &config) |
| Port of solver_mam_traffic.m. | |
| template<class T> | |
| std::vector< Mmap< T > > | line::mam::solver_mam_traffic_mmap (const qn::NetworkStruct< T > &sn, const DepTable< T > &DEP, const TrafficConfig &config, const FjSyncMap &fjSyncMap) |
| Port of solver_mam_traffic_mmap.m, the fork-join aware traffic step. | |
Port of solver_mam_traffic.m and solver_mam_traffic_mmap.m: the traffic step of the dec.mmap decomposition.
WHAT IT COMPUTES. Given the DEPARTURE process of every class at every station as a (D0,D1) pair, it produces the ARRIVAL process seen by every node. Each station's per-class departures are superposed into one marked MAP, that MAP is split along the routing (npfqn_traffic_split_cs, which also carries the class switching), and the per-link flows arriving at a node are superposed back (npfqn_traffic_merge). The result is the per-link traffic descriptor table the outer fixed point of solver_mam.m iterates on.
IT IS AN APPROXIMATION, and the approximation is not incidental. The exact superposition of n marked MAPs is the Kronecker sum, whose order is the PRODUCT of the operand orders, so a network of any size exhausts memory after a handful of merges. Both the per-station class superposition here and npfqn_traffic_merge therefore compress back to a bounded representation (mmap_compress, an APH(2) mixture fit) whenever the order passes config.space_max. Compression preserves the class probabilities and the first three backward moments per class; it does NOT preserve the correlation structure, and it does not preserve the per-class rates exactly. Nothing here may be compared against an exact solver for equality: the descriptors are moment-matched surrogates of the true superposed processes. What survives the compression exactly is the SPLIT: npfqn_traffic_split_cs is linear in the routing probabilities, so first-moment conservation across a split, and the whole traffic table of a network that never trips space_max and never merges more than one flow into a node, are identities.
INDEXING. The reference works in an indexing over the NON-CLASS-SWITCH nodes ("NCS"): the class-switch nodes are eliminated by taking the stochastic complement of sn.rtnodes over the rows of the surviving nodes, so a switch shows up only as a class change on the edges around it. ARV is returned NODE-indexed and of length nnodes – the reference preallocates it as cell(Inc,1) and then assigns ARV{ind} at node indices, so MATLAB grows it to I; the preallocation size is dead. An entry of order 0 is MATLAB's []: a class-switch node, or a Source, which has no arrivals to describe.
REFERENCE DEFECT in solver_mam_traffic.m, line 104. When a node has no incoming flow above FineTol the fallback reads ARV{ind} = LINKS{jnd,1}. jnd is the loop variable left behind by the for jnd=1:Inc above it, so it is Inc, and the column is the literal 1 rather than inc: the node is handed the link from the LAST non-class-switch node to the FIRST one, which is a flow between two other nodes entirely, or [] when that link was never built. The FJ variant of the same file (solver_mam_traffic_mmap.m, lines 179-188) writes the intended form – any non-empty link INTO this node, and a zero-rate MMAP when there is none – and that is what this port does for both entry points. Propagating the defect would attribute one node's traffic to another, which no downstream consumer could detect.
WHAT IS REFUSED BY NAME. The reference's node switch has a branch only for Source, Delay and Queue (plus Fork and Join in the FJ variant). Any other node that a flow passes THROUGH – a Router, a Logger, a Cache, a Place, a Transition, a Region – silently emits no outgoing link there, so everything downstream of it is described as receiving no traffic at all. That is not a conservative approximation, it is a wrong answer with no symptom, so such a model is refused by name rather than reproduced. A Sink is not refused: it genuinely has no departures.
WHAT IS NOT PORTED. sn_build_fj_sync_map and mmap_max have no home in this tree yet – the first belongs in line/api/fj/, the second in line/api/mam/ next to the rest of the M3A MMAP algebra – and the FJ variant is unusable without both. They are transcribed here under their MATLAB names, exactly as npfqn_traffic_split_cs.h inlines mmap_normalize for the same reason, and should be lifted into their own headers when one is added. Neither is re-derived: both are line-by-line transcriptions.
ARITHMETIC. The merge, the split and the synchronization are Kronecker algebra and are exact in any field. Compression is not: mmap_compress fits an APH(2) and needs square roots, so every call to it is behind the same compile-time gate npfqn_traffic_merge uses, and the exact instantiation refuses at run time only when compression is actually reached.
Definition in file solver_mam_traffic.h.
1.18.0