Fairness in Capacitated Networks: A Polyhedral Approach
Gábor Rétvári, József Bı́ró, Tibor Cinkler · 2007
The problem of fair and feasible allocation of user throughputs in capacitated networks is investigated. The main contribution of the paper is a novel geometric approach, which facilitates to generalize several throughput allocation strategies, most importantly max-min fairness, from the traditional "fixed-path" model to a more versatile, routing-independent model. We show that the set of throughput configurations realizable in a capacitated network makes up a polyhedron, which gives rise to a max-min fair allocation completely analogous to the conventional one. An algorithm to compute this polyhedron is also presented, whose viability is demonstrated by comprehensive evaluation studies.