Fair Allocation of Network Resources for Internet Users

Abstract

In a commercial Internet, the traffic behavior is determined by the contracts between the ISPs and the users, where a user can be a dial-up user, or one corporate network or a group of individual customers or networks. Since the user is the entity with whom the contract is signed, it should also be the unit to which network resources are allocated. However, while much research in the past has been directed to fair resource allocations for flows (e.g. maxmin fairness and proportional fairness), much less effort has been invested on fair allocation of resources for users. The work done in this thesis tries to fill this gap: we study how to share fairly the network resources among users, when a user can possibly send several flows through different paths.<br/><br/>The first part of the thesis focuses on the definition of a fairness criterion for the above problem: user maxmin fairness. The proposed criterion is based on the concepts of utility and welfare developed in the field of political science and political economics. We subdivide the problem of fairly allocating the network resources among users in two subproblems: 1) achieve fairness with respect to the utility experienced by the different users (inter-user fairness) and 2) achieve fairness with respect to the utility experienced by the different flows of a user (intra-user fairness). User maxmin fairness is the result of combining the two welfare functions that solve these two subproblems.<br/><br/>Along with the user maxmin fairness criterion, in this thesis we propose a mechanism to implement it: the User Fair Queuing (UFQ) mechanism. In UFQ, a user is allowed to assign any label values to his packets to indicate their relative priority. At the ingress, an algorithm is used to control these labels assigned by the user. We have shown mathematically that: (a) the proposed label control does not allow the asymptotic throughput of a user to exceed its fair rate, and (b) if users label their packets in order to maximize their level of satisfaction or utility, then the resulting bandwidth allocation is user maxmin fair.<br/><br/>In the last part of the thesis, we propose a network architecture for the Internet: the User Fair Differentiation (UFD) architecture. The UFD architecture extends the UFQ mechanism in such a way that its good features for resource sharing are preserved. In addition, UFD provides service differentiation, inter-domain communication, real-time traffic support and extensions for multicast and wireless. The fact that neither admission control nor signaling are required strongly contributes to the simplicity of UFD. The fact that no per-user state is kept at core nodes makes the proposed architecture scalable.<br/><br/>The performance of the UFD architecture has been extensively evaluated via simulations and a prototype implementation. Both simulation and experimental results have validated the architecture proposed in this thesis.