Application of the max-min fairness principle in telecommunication network design
(2005) 1st Euro-NGI Conference on Next Generation Internet Networks p.219-225- Abstract
- The rapid growth of traffic induced by Internet services makes the simple over-provisioning of resources not economical and hence imposes new requirements on the dimensioning methods. Therefore, the problem of network design with the objective of minimizing the cost and at the same time solving the tradeoff between maximizing the service data flows and providing fair treatment of all demands becomes more and more important. In this context, the so-called max-min fair (MMF) principle is widely considered to help finding reasonable bandwidth allocation schemes for competing demands. Roughly speaking, MMF assumes that the worst service performance is maximized, and then is the second worst performance, the third one, and so on, leading to a... (More)
- The rapid growth of traffic induced by Internet services makes the simple over-provisioning of resources not economical and hence imposes new requirements on the dimensioning methods. Therefore, the problem of network design with the objective of minimizing the cost and at the same time solving the tradeoff between maximizing the service data flows and providing fair treatment of all demands becomes more and more important. In this context, the so-called max-min fair (MMF) principle is widely considered to help finding reasonable bandwidth allocation schemes for competing demands. Roughly speaking, MMF assumes that the worst service performance is maximized, and then is the second worst performance, the third one, and so on, leading to a lexicographically maximized vector of sorted demand bandwidth allocations. It turns out that the MMF optimal solution cannot be approached in a standard way (i.e., as a mathematical programming problem) due to the necessity of lexicographic maximization of ordered quantities (bandwidth allocated to demands). Still, for convex models, it is possible to formulate effective sequential procedures for such lexicographic optimization. The purpose of the presented paper is three-fold. First, it discusses resolution algorithms for a generic MMF problem related to telecommunications network design. Second, it gives a survey of network design instances of the generic formulation, and illustrates the efficiency of the general algorithms in these particular cases. Finally, the paper discusses extensions of the formulated problems into more practical (unfortunately non-convex) cases, where the general for convex MMF problems approach fails. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1030478
- author
- Pioro, Michal LU ; Dzida, Mateusz ; Tomaszewski, Artur ; Zagozdzon, Michal ; Kubilinskas, Eligijus LU ; Nilsson, Pål LU and Ogryczak, Wlodzimierz
- organization
- publishing date
- 2005
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- to be added
- host publication
- Next Generation Internet Networks, 2005
- pages
- 219 - 225
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 1st Euro-NGI Conference on Next Generation Internet Networks
- conference location
- Rome, Italy
- conference dates
- 2005-04-18 - 2005-04-20
- external identifiers
-
- scopus:33744486912
- ISBN
- 0-7803-8900-X
- DOI
- 10.1109/NGI.2005.1431669
- language
- English
- LU publication?
- yes
- id
- f831a601-8b5c-41a7-bbaa-ae3f6d0dd4ab (old id 1030478)
- date added to LUP
- 2016-04-04 12:02:10
- date last changed
- 2022-01-29 22:47:17
@inproceedings{f831a601-8b5c-41a7-bbaa-ae3f6d0dd4ab,
abstract = {{The rapid growth of traffic induced by Internet services makes the simple over-provisioning of resources not economical and hence imposes new requirements on the dimensioning methods. Therefore, the problem of network design with the objective of minimizing the cost and at the same time solving the tradeoff between maximizing the service data flows and providing fair treatment of all demands becomes more and more important. In this context, the so-called max-min fair (MMF) principle is widely considered to help finding reasonable bandwidth allocation schemes for competing demands. Roughly speaking, MMF assumes that the worst service performance is maximized, and then is the second worst performance, the third one, and so on, leading to a lexicographically maximized vector of sorted demand bandwidth allocations. It turns out that the MMF optimal solution cannot be approached in a standard way (i.e., as a mathematical programming problem) due to the necessity of lexicographic maximization of ordered quantities (bandwidth allocated to demands). Still, for convex models, it is possible to formulate effective sequential procedures for such lexicographic optimization. The purpose of the presented paper is three-fold. First, it discusses resolution algorithms for a generic MMF problem related to telecommunications network design. Second, it gives a survey of network design instances of the generic formulation, and illustrates the efficiency of the general algorithms in these particular cases. Finally, the paper discusses extensions of the formulated problems into more practical (unfortunately non-convex) cases, where the general for convex MMF problems approach fails.}},
author = {{Pioro, Michal and Dzida, Mateusz and Tomaszewski, Artur and Zagozdzon, Michal and Kubilinskas, Eligijus and Nilsson, Pål and Ogryczak, Wlodzimierz}},
booktitle = {{Next Generation Internet Networks, 2005}},
isbn = {{0-7803-8900-X}},
keywords = {{to be added}},
language = {{eng}},
pages = {{219--225}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Application of the max-min fairness principle in telecommunication network design}},
url = {{http://dx.doi.org/10.1109/NGI.2005.1431669}},
doi = {{10.1109/NGI.2005.1431669}},
year = {{2005}},
}