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.

Max-min fair distribution of modular network flows on fixed paths

Author

  • Pål Nilsson
  • Michal Pioro

Summary, in English

In this paper a new aspect of the classical max-min fairness fixed-path problem is investigated. The considered (multi-criteria) optimization problem is almost identical to the continuous-flow problem, with the additional complicating assumption that flows must be integral. We show that such an extension makes the problem substantially more difficult (in fact NP-hard). Through comparison with the closely related continuous-flow problem, a number of properties for the solution of the extended problem are derived. An algorithm, based on sequential resolution of linear programs, that shows to be useful (produce optimal solutions) for many instances of the considered problem, is given. It follows that this algorithm can be made exact, through substituting the involved linear programs by mixed-integer programs.

Publishing year

2006

Language

English

Pages

916-927

Publication/Series

Networking 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. Proceedings / Lecture Notes in Computer Science

Volume

3976

Document type

Conference paper

Publisher

Springer

Topic

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

Keywords

  • network optimization
  • max-min fairness
  • modular flows

Conference name

5th International IFIP-TC6 Networking Conference

Conference date

2006-05-15 - 2006-05-19

Conference place

Coimbra, Portugal

Status

Published

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-34192-5