Upward Max Min Fairness

May 18, 2012
EE Conference Room
Hosted by:Columbia University Joint CS/EE Networking Seminar
Speaker: Prof. Danny Raz (Technion - Israel Institute of Technology)


Often one would like to allocate shared resources in a fair way. A common and well studied notion of fairness is Max-Min Fairness where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting each commodity has multiple possible paths to route its demand (for example, a network using MPLS tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths. More importantly, a network operator has limited control and understanding of the inner working of the algorithm. Finally, this approach is inherently centralized and cannot be implemented via a distributed protocol.

In this paper we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation. This algorithm is a natural extension of the well known Water Filling Algorithm for a multiple path setting. We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization. This work was done in Google jointly with: E Danna, A. Hassidim, H. Kaplan, A. Kumar Y. Mansour , and M. Segalov. The paper was a Runner Up for the INFOCOM '12 Best Paper Award.

Speaker Biography

Danny Raz received his doctoral degree from the Weizmann Institute of Science, Israel, in 1995. From 1995 to 1997 he was a post-doctoral fellow at the International Computer Science Institute, (ICSI) Berkeley, CA, and a visiting lecturer at the University of California, Berkeley. Between 1997 and 2001 he was a Member of Technical Staff at the Networking Research Laboratory at Bell Labs, Lucent Technologies. In October 2000, Danny Raz joined the faculty of the computer science department at the Technion, Israel. He served as the general chair of OpenArch 2000, TPC co-chair of MMNS 2007, TPC co-chair of IM2009, and was an Editor of the IEEE/ACM Transactions on Networking (ToN) and of JCN. His primary research interest is the theory and application of management related problems in IP networks and cloud computing.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University