ACM Home
SIGMETRICS 2001 / Performance 2001 Home
Call for Papers
Organizing Committee
Technical Program Committee
Registration Information
Advanced Technical Program
Travel Support for Students
Travel Related Information
Other Links of Interest


SIGMETRICS 2001 / Performance 2001

Using Approximate Majorization to Characterize Protocol Fairness

Rishi Bhargava
ONI Systems

Ashish Goel <>
Department of Computer Science, University of Southern California

Adam Meyerson <>
Department of Computer Science, Stanford University

A good measure of fairness is an essential prerequisite for a systematic development of fair resource allocation protocols as well as for a systematic evaluation of the fairness of existing protocols. We propose the use of approximate majorization as a framework for quantifying the fairness of a resource allocation scheme. We demonstrate how approximate majorization subsumes and generalizes several natural measures of fairness. We then relate majorization to revenue maximization, and sketch (in the full version of the paper) an efficient algorithm to compute the fairness of a given allocation as well as to find the fairest possible allocation. We believe that our framework is quite general and can be applied to several routing, bandwidth allocation, load balancing, and clustering problems. We use this framework to perform a preliminary case study of the fairness of TCP as a bandwidth allocation protocol in communication networks. We discover several interesting trends about the fairness of TCP which merit further study. The fairness of TCP improves as the buffer sizes and/or link capacities are increased. In several realistic cases, the fairness of TCP is comparable to or better than that of max-min fair allocations.

[Last updated Fri Mar 23 2001]