polling_qsys_exhaustive.h File Reference

Mean waiting times of a polling system under exhaustive service. More...

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

Include dependency graph for polling_qsys_exhaustive.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::polling

Functions
template<class T>
std::vector< T >	line::polling::polling_qsys_exhaustive (const PollingMoments< T > &m)
	Exhaustive service: the server empties a queue completely before switching.
template<class T>
std::vector< T >	line::polling::polling_qsys_gated (const PollingMoments< T > &m)
	Gated service: only the jobs found at the polling instant are served.

Detailed Description

Mean waiting times of a polling system under exhaustive service.

Templated port of matlab/src/api/polling/polling_qsys_exhaustive.m, which is the station-time method of Ferguson and Aminetzah (1985) as reported by Takagi, ACM Computing Surveys 20(1), 1988, eq. (15). The MATLAB version takes MAP descriptors and immediately reduces them to the first two moments of the arrival, service and switchover processes; this port takes those moments directly through line::polling::PollingMoments, exactly as the 1-limited and decrementing ports do, so the MAP reduction stays in line::mam.

The method solves an n^2 x n^2 linear system for the station times r_ij and then reads the waiting times off them. Everything is a rational function of the input moments plus one exact linear solve, so the whole computation stays in the field: a polling system with rational parameters has an exactly representable mean waiting time and the port is instantiable at Rational. That is worth having here because the denominators 1 - rho and 1 - rho_i both vanish at a stability boundary and appear cubed, so a rounded evaluation near one can return a finite but meaningless number.

ORACLES USED IN THE TESTS.

• n = 1 collapse. The formula reduces to the M/G/1 queue with multiple vacations, W = lambda b2/(2(1-rho)) + E[R^2]/(2 E[R]), which the port reproduces exactly (in Rational, digit for digit).
• Pseudo-conservation law of Boxma and Groenendijk (1987), sum_i rho_i W_i = rho/(2(1-rho)) sum_i lambda_i b2_i
  • rho (delta2tot + R^2)/(2R)
  • R (rho^2 - sum_i rho_i^2)/(2(1-rho))
  • sum_i E[M_i], with E[M_i] = 0 under exhaustive service and E[M_i] = rho_i^2 R/(1-rho) under gated service. The port satisfies it as an identity, so exhaustive and gated are cross-checked against one common invariant.

A simulator is deliberately NOT used as an oracle: LINE's LDES polling server parks at the last visited queue rather than roving, which puts a systematic negative offset of a few percent on its waiting times relative to Takagi.

Definition in file polling_qsys_exhaustive.h.