A Hierarchical Algorithm for Achieving Proportional Fairness in Data Networks

Proportional fairness criterion which is proposed the first time by F.P.Kelly and his colleagues has outstanding properties in allocating users’ rates. For example, it resembles the Jacobson’s AIMD method in rate allocation to users and there exists a well-established stability analysis in Kelly’s work relating to stability of rate allocation algorithm. Unfortunately, in large networks such as the current Internet, there will exist a great overhead in implementing the algorithm and this makes the algorithm practically useless and shows that the algorithm is not scalable. Furthermore, using highspeed algorithms such as Newton’s method in Kelly’s algorithm is computationally cumbersome and difficult. In this paper, we have proposed a novel hierarchical method in rate allocation, which tries to solve the above problems in some networks that their topology can be expressed in a hierarchical manner. Our simulations justify our method.

Keywords:

Proportional fairness , Elastic traffic , Scalability , Penalty function