Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2009 | Published
Journal Article Open

Understanding XCP: Equilibrium and Fairness

Abstract

We prove that the XCP equilibrium solves a constrained max-min fairness problem by identifying it with the unique solution of a hierarchy of optimization problems, namely those solved by max-min fair allocation, but solved by XCP under an additional constraint. This constraint is due to the "bandwidth shuffling" necessary to obtain fairness. We describe an algorithm to compute this equilibrium and derive a lower and upper bound on link utilization. While XCP reduces to max-min allocation at a single link, its behavior in a network can be very different. We illustrate that the additional constraint can cause flows to receive an arbitrarily small fraction of their max-min fair allocations. We confirm these results using ns2 simulations.

Additional Information

© 2009 IEEE. Manuscript received February 27, 2008; revised October 24, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING. Editor S. Shakkottai. First published August 18, 2009; current version published December 16, 2009. This work was supported by NSF Grant 0303620. Partial results have appeared in the Proceedings of IEEE INFOCOM, 2005. The authors would like to thank D. Katabi of Massachusetts Institute of Technology (MIT), Cambridge, for helpful discussions.

Attached Files

Published - Andrew2009p6706Ieee_Acm_T_Network.pdf

Files

Andrew2009p6706Ieee_Acm_T_Network.pdf
Files (716.7 kB)
Name Size Download all
md5:b516c69ab46715117fb6ef36db40e971
716.7 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 19, 2023