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. 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, in a network the additional constraint can cause a flow to receive an arbitrarily small fraction of its max-min allocation. We present simulation results to confirm our analytical findings. ©2005 IEEE.