M.Sc Thesis

M.Sc StudentStoian Paul
SubjectUser vs. Individual Flow Fairness in Communication
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROFESSOR EMERITUS Israel Cidon


The traditional criterion for fair bandwidth allocation is the Max-Min fairness definition, which fairly allocates bandwidth between individual (source-to-destination pair) flows. The network is shared by “users”, where a "user" is a collection of multiple individual flows (for example the flows belonging to a particular VPN on a transit network, or the flows originating from a node in an RPR network). This work aims to develop criteria that allocate bandwidth fairly amongst the network users.

The fairness criteria proposed in this paper are max-min type definition (i.e. a duality between fair allocation and bottleneck link existence for each flow), maintain compatibility with the standard max-min bandwidth allocation for the edge cases (only one user or only one flow per user), and also respect no zero bandwidth allocation limitation.

We define three user fairness definitions. The first definition, Weighted Max-Min,   achieves user fairness by assigning new weights to each flow which are inversely proportional to the number of flows of the user, thus correcting the unfairness created by different number of flows per user. The second definition, Redefined Vector-space Fairness, improves on the first by also taking into consideration the total bandwidth allocated to a user. This is achieved by defining a vector space where the vector elements are both the individual flows and total users bandwidth allocations, and then derive the fairness definition from the bandwidth allocation which is concurrent with the lex-max lex-ordered vector in this space. The third definition, Local User Max-Min, defines a per-link user max-min fairness criterion, the total user allocation defined as the sum of the users flows per each link, and then substituting this value in place of individual flow in the standard max-min definition.

This paper analyzes the proposed fairness definitions behaviorally and numerically. The simulation results show an advantage for Redefined Vector-space Fairness in both user fairness and throughput.