Using approximate majorization to characterize protocol fairness

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 an efficient algorithm to compute the fairness of a given allocation as well to find the fairest allocation. Our framework is quite general and can be applied to several routing, bandwidth allocation, load balancing, and clustering problems. To illustrate the framework in a concrete setting, we perform a preliminary case study of the fairness of TCP as a bandwidth allocation protocol in communication networks. We demonstrate that the fairness of both TCP Reno and TCP Vegas is incomparable to the fairness obtained by max-min fair allocation. Finally, we explore the connections between approximate majorization and the notion of proportional fairness developed by Kelly, Maulloo, and Tan.