sn_to_qrf_blocking.h File Reference

The QRF BAS blocking tables (f, MR, BB, MM, ZZ, MM1), derived from an sn. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <map>
#include <sstream>
#include <string>
#include <vector>
#include "line/api/sn/sn_get_buffer_size.h"
#include "line/lang/qn/network_struct.h"

Include dependency graph for sn_to_qrf_blocking.h:

Go to the source code of this file.

Classes
struct	line::sn::QrfCapacity
	Per-station occupancy bounds, and which of them bind. More...
struct	line::sn::QrfBlocking
	The derived blocking tables, in the reference's 1-based queue indexing. More...

Namespaces
namespace	line
namespace	line::sn

Functions
template<class T>
QrfCapacity	line::sn::sn_to_qrf_capacity (const qn::NetworkStruct< T > &sn)
	F is an OCCUPANCY BOUND, not a declared capacity: the station's buffer where that buffer BINDS, and the population N everywhere else, since no queue of a closed model can hold more than N jobs.
template<class T>
QrfBlocking	line::sn::sn_to_qrf_blocking (const qn::NetworkStruct< T > &sn, int Ktot, double max_vars=kQrfDefaultMaxVars)
	The QRF BAS blocking tables (f, MR, BB, MM, ZZ, MM1), derived from an sn.

Variables
const double	line::sn::kQrfDefaultMaxVars = 5e5
	Variable-count ceiling of the derived LP.

Detailed Description

The QRF BAS blocking tables (f, MR, BB, MM, ZZ, MM1), derived from an sn.

Port of matlab/src/api/sn/sn_to_qrf_capacity.m and matlab/src/api/sn/sn_to_qrf_blocking.m.

qrf_bas describes a Blocking-After-Service network by a finite-capacity queue f and an enumeration of the BLOCKING CONFIGURATIONS reachable behind it. Everything in that enumeration is implied by the model, so it is derived here rather than demanded from the caller; options.config.qrf_params remains an explicit override.

The tables, and the constraint that reads each one in qrf_bas:

f the ONE finite-capacity queue. The formulation carries a scalar f (ZERO4/ZERO7/ZERO8, THM30, THM3I, THM3L all index it), so a model with two binding buffers is refused here. F(i) min(buffer size, N) for every queue; N where the buffer is unbounded, since no queue can hold more than the population. BB(m,i) 1 iff queue i is blocked in configuration m. ZZ(m) the blocking depth of configuration m. MM(m,0) head of the FIFO blocking order: the queue that takes the slot when f completes. qrf_bas reads ONLY the first column. MM1(m,j) index of the configuration reached from m when j becomes blocked. Read by THM3L alone, at depth ZM-1.

THREE INVARIANTS, each a correctness condition rather than a convention:

1. Configuration 1 MUST be the empty one. ZERO4 iterates m = 2:MR and ZERO5/ZERO7/ZERO8 test m >= 2 to mean "some queue is blocked".
2. ZM = max(ZZ) MUST be the reachable maximum. qrf_bas recomputes ZM from ZZ and closes the depth ladder there, so a truncated enumeration excises states the real chain visits and the polytope stops containing the true distribution – the bound stops bounding. The size guard therefore REFUSES; it never truncates.
3. Blocking APPENDS at the tail: a queue that becomes blocked joins behind those already waiting, so MM1's successor is the configuration with j appended, and the head MM(m,0) names never moves.

THE ENUMERATION IS THE FULL ORDERED ONE, and it has to be. A (set, head) collapse looks sound – the LP reads configurations only through BB, ZZ, MM(:,0) and MM1, and both objective and readout sum over m – and it would shrink MR from sum_z P(B,z) to 1 + sum_z C(B,z)*z. It was tried and it is WRONG. Merging the depth-ZM configurations that share a set and a head makes several THM3L rows, one per depth-(ZM-1) predecessor, reference the SAME merged successor block. That is extra coupling the fine system does not have, so the collapsed polytope is strictly SMALLER, not a projection of the fine one, and it can cut off the true distribution. Measured on a 4-station model with three feeders (B=3, ZM=3, MR 13 collapsed vs 16 full), the collapse reported upper bounds of 0.681/0.979/0.768 where the full enumeration gives 0.709/0.982/0.800: tighter, from a coarser state space, which is the signature of a cut that is not valid.

So MR is factorial in the number of feeders B, and the size guard is what keeps that honest: it REFUSES an oversized instance rather than trimming the enumeration, because trimming is the same unsound cut by another name.

WHO CAN BE BLOCKED is read from sn.isbasblocking, not from sn.droprule: LINE accepts the BAS declaration on the upstream station or on the full destination, and reading droprule at the capped station sees only the second (BUG-83).

Definition in file sn_to_qrf_blocking.h.