Combining fairness with throughput
Ashish Goel, Adam Meyerson, Serge A. Plotkin · 2000
This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions.In fact, the algorithms solve a more difficult problem: for any bandwidth b, the number of sessions that get bandwidth b in the online algorithm is not smaller than the number of sessions receiving vb offiine, where V is the competitive ratio.This problem is provably harder than the problem of maximizing throughput (e.g.[4]) or the problem of maximizing the bandwidth assigned to the most starved session (e.g.[3]).For the case where the algorithm assigns bandwidths, we present an O(log 2 n log 1+~ U/e)-competitive algorithm, for any e, where U is the minimum (over all choices of routes) of the 'maximum number of sessions routed along any single link.We also show an ~(log 1+~ U/e) lower bound in this model.For a more practically interesting model where the algorithm assigns routes and weights, and where these weights are used to drive the Weighted Fair Queuing policy in the routers, we present an O(log2nlogU)competitive algorithm.We also show that the dependence on U is necessary by presenting an ~(~) lower bound. The upper and lower bounds presented in [4] for online maximization of throughput become invalid if we