|
SIGMETRICS 2001 / Performance 2001Using Approximate Majorization to Characterize Protocol Fairness |
| Authors |
|
Rishi Bhargava ONI Systems
Ashish Goel <agoel@cs.usc.edu>
Adam Meyerson <awm@cs.stanford.edu> |
| Abstract |
| 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. |