npfqn_feedback_elim.h File Reference

Near-immediate feedback elimination for the robust queueing network analyzer. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for npfqn_feedback_elim.h:

Go to the source code of this file.

Classes
struct	line::npfqn::FeedbackElimResult< T >
	Outcome of the feedback elimination. More...

Namespaces
namespace	line
namespace	line::npfqn

Functions
template<class T>
FeedbackElimResult< T >	line::npfqn::npfqn_feedback_elim (const Matrix< T > &P, const std::vector< T > &rho, const std::vector< T > &cs2=std::vector< T >(), const std::vector< T > &lambda=std::vector< T >(), bool immediateOnly=false)
	Near-immediate feedback elimination for the robust queueing network analyzer.

Detailed Description

Near-immediate feedback elimination for the robust queueing network analyzer.

Templated port of matlab/src/api/npfqn/npfqn_feedback_elim.m, cross-checked against jar/src/main/java/jline/api/npfqn/Npfqn_feedback_elim.java.

WHY FEEDBACK BREAKS DECOMPOSITION. A parametric decomposition treats the arrival stream at each station as renewal. Feedback destroys that badly: a customer that leaves a busy station and comes straight back arrives exactly when the station is busy, so the flow is strongly correlated with the queue it feeds. The fix is not to model the correlation but to REMOVE the feedback, by folding the repeated visits into the service time:

effective mean service E[S]/(1-p) effective service SCV p + (1-p)cs^2 (37) fresh arrival rate lambda(1-p) per-visit waiting time (1-p) times the wait in the modified system

The modified system has the SAME heavy-traffic limits for queue length, workload, waiting time and external departures, so this is asymptotically exact rather than merely plausible.

NEAR-IMMEDIATE, NOT JUST IMMEDIATE. What matters is whether the customer returns WITHOUT PASSING A BUSIER STATION: a detour through a station of lower traffic intensity is fast on the time scale of the busy station. The probability computed here is therefore the probability of returning to station i through stations of strictly smaller rho only, obtained from the absorbing chain restricted to those stations.

ARITHMETIC. Only a linear solve, so this instantiates at T = Rational too.

Reference: W. Whitt, W. You (2022). A robust queueing network analyzer based on indices of dispersion. Naval Research Logistics 69(1), 36-56, Section 4.

Definition in file npfqn_feedback_elim.h.