Sequential algorithms for exact and approximate max-min fair bandwidth allocation
Włodzimierz Ogryczak, Tomasz Śliwiński · 2012
Allocating bandwidth to maximize service flows with fair treatment of all the services is a key issue in network dimensioning. In such applications, the so-called Max-Min Fairness (MMF) solution concept is widely used. It is based on the worst service performance maximization with additional regularization by the lexicographic maximization of the second worst performance, the third one etc. The basic sequential procedure is applicable only for convex models, thus it allows to deal with basic design problems but fails if practical discrete restrictions commonly arriving in telecommunications network design are to be taken into account. We analyze alternative sequential approaches allowing to solve non-convex MMF network dimensioning problems. The directly defined sequential criteria can be introduced into the original model with some auxiliary variables and linear inequalities. The approaches guarantee the exact MMF solution for a complete set of criteria. However, they can be simplified by reducing the number of criteria thus generating effectively approximated MMF solutions.