Fairness in Routing and Load Balancing

✍ Scribed by Jon Kleinberg; Yuval Rabani; Éva Tardos

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 177 KB
• Volume: 63
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2001.1752

✦ Synopsis

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 equilibrium condition on the bandwidth allocation, and some simple flow control mechanisms converge quickly to this equilibrium state. Indeed, the vast majority of previous work on