On efficient max-min fair routing algorithms

Michal Pioro, Pål Nilsson, Eligijus Kubilinskas, Gabor Fodor

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

25 Citations (SciVal)

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
Original languageEnglish
Title of host publicationProceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003
PublisherIEEE - Institute of Electrical and Electronics Engineers Inc.
Pages365-372
ISBN (Print)0-7695-1961-X
DOIs
Publication statusPublished - 2003
EventInternational Symposium on Computers and Communications ISCC 2003 - Kemer-Antalya, Turkey
Duration: 2003 Jun 302003 Jul 3

Conference

ConferenceInternational Symposium on Computers and Communications ISCC 2003
Country/TerritoryTurkey
CityKemer-Antalya
Period2003/06/302003/07/03

Subject classification (UKÄ)

  • Communication Systems
  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • maxmin fair routing algorithms
  • source-destination pair
  • optimization problem
  • network utilization
  • elastic traffic
  • maxmin fairness constraints
  • multipath routing
  • bandwidth allocation

Fingerprint

Dive into the research topics of 'On efficient max-min fair routing algorithms'. Together they form a unique fingerprint.

Cite this