pfqn_propfair.h File Reference

Proportionally fair allocation estimate of the normalizing constant (Schweitzer 1979; Walton, "Proportional fairness and its relationship with multi-class queueing networks", 2009). More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_asympt_common.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 pfqn_propfair.h:

Go to the source code of this file.

Classes
struct	line::pfqn::PropfairResult< T >
	Return value of pfqn_propfair, mirroring [G, lG, Xasy]. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
PropfairResult< T >	line::pfqn::pfqn_propfair (const Matrix< T > &L, const std::vector< T > &N, const std::vector< T > &Z)
	Proportionally fair allocation estimate of the normalizing constant (Schweitzer 1979; Walton, "Proportional fairness and its relationship with multi-class queueing networks", 2009).

Detailed Description

Proportionally fair allocation estimate of the normalizing constant (Schweitzer 1979; Walton, "Proportional fairness and its relationship with multi-class queueing networks", 2009).

Templated port of matlab/src/api/pfqn/pfqn_propfair.m. The asymptotic throughput vector solves the convex program

maximize sum_r (N_r - X_r Z_r) log(X_r + 1e-6) subject to L X <= 1, X >= 0

after which log G = sum_r (N_r - X_r Z_r) log(1/X_r) - sum_r factln(X_r Z_r). The estimate is asymptotically exact for networks of single-server PS queues; delay stations are handled by the heuristic above.

OPTIMIZER. MATLAB calls fmincon. There is no fmincon here, and a generic nonlinear programming solver is not something to invent, so the port solves the same program with a primal log-barrier Newton method: the objective is separable and strictly concave (d^2/dX_r^2 = -2 Z_r/(X_r+eps) - (N_r - X_r Z_r)/(X_r+eps)^2 < 0 wherever the objective is defined), the feasible set is a polytope, so the barrier path is well defined and the method converges to the same maximizer fmincon reports. The centering parameter is raised geometrically until the duality gap (M+R)/t falls below the tolerance. What differs from MATLAB is only the path taken, not the point reached; the accompanying test asserts agreement with the MATLAB value.

The reference starts fmincon at the origin, which is on the boundary of the feasible set and outside the domain of the barrier. The port starts at the strictly interior point X_r = 1/(2 max_m sum_s L_ms) instead, which is the only deviation the barrier formulation forces.

MATLAB DEAD CODE, noted rather than reproduced: pfqn_propfair.m accumulates a first value of lG in a loop over the classes with Z_r > 0 and then OVERWRITES it on the next line. The loop has no effect on the returned value, so it is not ported.

ARITHMETIC. Logarithms throughout, in the objective and in the barrier, so gated on num_traits<T>::has_transcendental.

Definition in file pfqn_propfair.h.