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.
© 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.
Published - Andrew2009p6706Ieee_Acm_T_Network.pdf