NDLI: A Unified Framework for Max-Min and Min-Max Fairness With Applications

Content Provider	IEEE Xplore Digital Library
Author	Radunovic, B. Le Boudec, J.-Y.
Copyright Year	1993
Abstract	Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing it; in most, but not all cases, they are based on the notion of bottlenecks. In spite of this wide applicability, there are still examples, arising in the context of wireless or peer-to-peer networks, where the existing theories do not seem to apply directly. In this paper, we give a unifying treatment of max-min fairness, which encompasses all existing results in a simplifying framework, and extend its applicability to new examples. First, we observe that the existence of max-min fairness is actually a geometric property of the set of feasible allocations. There exist sets on which max-min fairness does not exist, and we describe a large class of sets on which a max-min fair allocation does exist. This class contains, but is not limited to the compact, convex sets of R^N. Second, we give a general purpose centralized algorithm, called max-min programming, for computing the max-min fair allocation in all cases where it exists (whether the set of feasible allocations is in our class or not). Its complexity is of the order of N linear programming steps in R^N, in the case where the feasible set is defined by linear constraints. We show that, if the set of feasible allocations has the free disposal property, then max-min programming reduces to a simpler algorithm, called water filling, whose complexity is much lower. Free disposal corresponds to the cases where a bottleneck argument can be made, and water filling is the general form of all previously known centralized algorithms for such cases. All our results apply mutatis mutandis to min-max fairness. Our results apply to weighted, unweighted and util-max-min and min-max fairness. Distributed algorithms for the computation of max-min fair allocations are outside the scope of this paper.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	1073
Ending Page	1083
Page Count	11
File Size	458510
File Format	PDF
ISSN	10636692
Volume Number	15
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-10-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Filling Telecommunication traffic Peer to peer computing Linear programming Water Distributed algorithms Distributed computing Mathematical programming Design optimization Resource management system design Best-effort traffic elastic traffic mathematical programming/optimization max-min fairness
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A unified framework for max-min and min-max fairness with applications

Computing optimal max-min fair resource allocation for elastic flows

Computing Optimal Max-Min Fair Resource Allocation for Elastic Flows

A Unified Framework for Max-Min and Min-Max Fairness with Applications (2002)

A Unified Framework for max-min and min-max fairness with applications (2002)

A Unified Framework for max-min and min-max fairness with applications (2002)

Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation

Max–Min Fairness Optimization for D2D Communications Coexisting with Cellular Networks

A novel flow control scheme for best effort traffics in Network-on-Chip based on Weighted Max-Min-fairness

A Unified Framework for Max-Min and Min-Max Fairness With Applications

Similar Documents

A unified framework for max-min and min-max fairness with applications

Computing optimal max-min fair resource allocation for elastic flows

Computing Optimal Max-Min Fair Resource Allocation for Elastic Flows

A Unified Framework for Max-Min and Min-Max Fairness with Applications (2002)

A Unified Framework for max-min and min-max fairness with applications (2002)

A Unified Framework for max-min and min-max fairness with applications (2002)

Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation

Max–Min Fairness Optimization for D2D Communications Coexisting with Cellular Networks

A novel flow control scheme for best effort traffics in Network-on-Chip based on Weighted Max-Min-fairness

A Unified Framework for Max-Min and Min-Max Fairness With Applications