qsys_mapg1k_perflow.h File Reference

Per-flow throughput and loss ratio of a tail-drop FIFO buffer fed by N flows of mutually different statistical character. More...

#include <cstddef>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/qsys/qsys_mapg1k.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for qsys_mapg1k_perflow.h:

Go to the source code of this file.

Classes
struct	line::qsys::MapG1kPerflowResult< T >
	Return value of qsys_mapg1k_perflow, mirroring the MATLAB result struct. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
MapG1kPerflowResult< T >	line::qsys::qsys_mapg1k_perflow (const std::vector< mam::Map< T > > &flows, const ServiceLaw< T > &svc, std::size_t K, const T &tol, std::size_t nmaxCap)
	Per-flow analysis of a MAP-fed tail-drop buffer.
template<class T>
MapG1kPerflowResult< T >	line::qsys::qsys_mapg1k_perflow (const std::vector< mam::Map< T > > &flows, const ServiceLaw< T > &svc, std::size_t K)
	qsys_mapg1k_perflow with the qsys_mapg1k defaults tol = 1e-12, nmax = 200000.

Detailed Description

Per-flow throughput and loss ratio of a tail-drop FIFO buffer fed by N flows of mutually different statistical character.

Port of matlab/src/api/qsys/qsys_mapg1k_perflow.m, Theorem 1 of [1].

Flow n has its own MAP, so two flows may share an arrival rate and still differ in the shape and the autocorrelation of their interarrival times.

METHOD, AND WHY IT IS AN APPROXIMATION. The exact model would track the modulating state of every flow jointly with the buffer, prod_n M_n (K+1) states, which [1] notes is already out of reach at N = 10, M_n = 3, K = 10. Instead ONE model is solved per flow: flow n is kept exactly and the other N-1 flows are replaced by a single Poisson stream of rate lambda - lambda_n, which the Palm-Khinchin limiting theorem on superposed point processes justifies as N grows. The substitution is applied N times, once per flow, so no flow is ever the Poissonized one when its own throughput is computed. Superposing MAP_n with the Poisson background gives ([1], eq. 5)

D0 = D0n - lambdaBar I,     D1 = D1n + lambdaBar I,

and the flow throughput is read off the aggregate ([1], eq. 20)

T_n = (1 - p0)/S + pK lambdaBar - lambdaBar,

the aggregate departure rate less the background throughput lambdaBar (1 - pK), the background loss ratio being pK by PASTA BECAUSE the background is Poisson. PASTA is used for the background only, never for the flow being measured. Cost is O(N (K M)^3) against O(M^(3N) K^3): linear rather than exponential in the flow count.

ACCURACY. [1] reports errors against simulation of the exact model below about 8% for N >= 9 with K >= 20, falling to 2.1% at K = 50, 0.5% at K = 100 and 1.2% at N = 900. Errors are largest when flows are few, highly variable and the buffer is small. This is a property of the method, not of the port: the port reproduces the reference's numbers, and the two agree with the published Table 2 of [1] to the precision at which it is printed.

ARITHMETIC. Inherits the transcendental gate from qsys_mapg1k.

Reference: [1] Chydzinski, A. Per-Flow Throughput of a FIFO Buffer. Applied System Innovation 2026, 9, 112.

Definition in file qsys_mapg1k_perflow.h.