Advanced

On efficient max-min fair routing algorithms

Pioro, Michal LU ; Nilsson, Pål LU ; Kubilinskas, Eligijus LU and Fodor, Gabor (2003) International Symposium on Computers and Communications ISCC 2003 In Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003 p.365-372
Abstract
In the paper, we consider the problem of routing and bandwidth allocation in networks that support elastic traffic. We assume that the bandwidth demand between each source-destination (S-D) pair is specified in terms of a minimum and maximum value, and a set of flows between each S-D pair is allowed to realize these demands. (We say that a set of flows realizes the demand associated with an S-D pair, if the sum of the bandwidths allocated to these flows is greater than the minimum value assumed for the demand of that S-D pair). In this setting, we show that routing and bandwidth allocation can be formulated as an optimization problem, where network utilization is to be maximized under capacity and the widely used max-min fairness... (More)
In the paper, we consider the problem of routing and bandwidth allocation in networks that support elastic traffic. We assume that the bandwidth demand between each source-destination (S-D) pair is specified in terms of a minimum and maximum value, and a set of flows between each S-D pair is allowed to realize these demands. (We say that a set of flows realizes the demand associated with an S-D pair, if the sum of the bandwidths allocated to these flows is greater than the minimum value assumed for the demand of that S-D pair). In this setting, we show that routing and bandwidth allocation can be formulated as an optimization problem, where network utilization is to be maximized under capacity and the widely used max-min fairness constraints. We describe three different algorithms to solve variants of this problem. The most important one, an efficient, original algorithm assuming multipath routing is studied in detail and illustrated with a numerical example (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
maxmin fair routing algorithms, source-destination pair, optimization problem, network utilization, elastic traffic, maxmin fairness constraints, multipath routing, bandwidth allocation
in
Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003
pages
365 - 372
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
International Symposium on Computers and Communications ISCC 2003
external identifiers
  • WOS:000184416200054
  • Scopus:84859771854
ISBN
0-7695-1961-X
DOI
10.1109/ISCC.2003.1214147
language
English
LU publication?
yes
id
7a0c0cbd-8f35-44e0-a1bc-11fff3f7a671 (old id 612742)
date added to LUP
2007-11-30 15:56:10
date last changed
2016-10-13 04:46:56
@misc{7a0c0cbd-8f35-44e0-a1bc-11fff3f7a671,
  abstract     = {In the paper, we consider the problem of routing and bandwidth allocation in networks that support elastic traffic. We assume that the bandwidth demand between each source-destination (S-D) pair is specified in terms of a minimum and maximum value, and a set of flows between each S-D pair is allowed to realize these demands. (We say that a set of flows realizes the demand associated with an S-D pair, if the sum of the bandwidths allocated to these flows is greater than the minimum value assumed for the demand of that S-D pair). In this setting, we show that routing and bandwidth allocation can be formulated as an optimization problem, where network utilization is to be maximized under capacity and the widely used max-min fairness constraints. We describe three different algorithms to solve variants of this problem. The most important one, an efficient, original algorithm assuming multipath routing is studied in detail and illustrated with a numerical example},
  author       = {Pioro, Michal and Nilsson, Pål and Kubilinskas, Eligijus and Fodor, Gabor},
  isbn         = {0-7695-1961-X},
  keyword      = {maxmin fair routing algorithms,source-destination pair,optimization problem,network utilization,elastic traffic,maxmin fairness constraints,multipath routing,bandwidth allocation},
  language     = {eng},
  pages        = {365--372},
  publisher    = {ARRAY(0x9d80a30)},
  series       = {Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003},
  title        = {On efficient max-min fair routing algorithms},
  url          = {http://dx.doi.org/10.1109/ISCC.2003.1214147},
  year         = {2003},
}