Advanced

Application of the max-min fairness principle in telecommunication network design

Pioro, Michal LU ; Dzida, Mateusz; Tomaszewski, Artur; Zagozdzon, Michal; Kubilinskas, Eligijus LU ; Nilsson, Pål LU and Ogryczak, Wlodzimierz (2005) 1st Euro-NGI Conference on Next Generation Internet Networks In Next Generation Internet Networks, 2005 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
to be added
in
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
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
2008-02-11 15:14:26
date last changed
2016-10-13 04:49:14
@misc{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},
  isbn         = {0-7803-8900-X},
  keyword      = {to be added},
  language     = {eng},
  pages        = {219--225},
  publisher    = {ARRAY(0x8a2dc88)},
  series       = {Next Generation Internet Networks, 2005},
  title        = {Application of the max-min fairness principle in telecommunication network design},
  url          = {http://dx.doi.org/10.1109/NGI.2005.1431669},
  year         = {2005},
}