The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

On efficient max-min fair routing algorithms

På svenska

Author

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

Summary, in English

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

Publishing year

2003

Language

English

Pages

365-372

Publication/Series

Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003

Document type

Conference paper

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • 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

Conference name

International Symposium on Computers and Communications ISCC 2003

Conference date

2003-06-30 - 2003-07-03

Conference place

Kemer-Antalya, Turkey

Status

Published

ISBN/ISSN/Other

  • ISBN: 0-7695-1961-X