|
Abstract : |
We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria interacts in a complex fashion with the optimization of network utilization and throughput; in this work, we undertake an investigation of this relationship through the framework of approximation algorithms. In a range of settings including both high-speed networks and Internet applications, max-min fairness has emerged as a widely accepted formulation of the notion of fairness. Informally, we say that an allocation of bandwidth is max-min fair if there is no way to give more bandwidth to any connection without decreasing the allocation to a connection of lesser or equal bandwidth. Given a collection of transmission routes, this criterion imposes a certain, |
