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


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 (716.7 kB)
Name Size Download all
716.7 kB Preview Download

Additional details

August 21, 2023
October 19, 2023