On single-path network routing subject to max-min fair flow allocation

Edoardo Amaldi, Stefano Coniglio, Luca G. Gianoli, Can Umut Ileri

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

Abstract

Fair allocation of flows in multicommodity networks has been attracting a growing attention. In Max-Min Fair (MMF) flow allocation, not only the flow of the commodity with the smallest allocation is maximized but also, in turn, the second smallest, the third smallest, and so on. Since the MMF paradigm allows to approximate the TCP flow allocation when the routing paths are given and the flows are elastic, we address the network routing problem where, given a graph with arc capacities and a set of origin-destination pairs with unknown demands, we must route each commodity over a single path so as to maximize the throughput, subject to the constraint that the flows are allocated according to the MMF principle. After discussing two properties of the problem, we describe a column generation based heuristic and report some computational results.

Original languageEnglish
Pages (from-to)543-550
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume41
DOIs
Publication statusPublished - 9 Jul 2013
Externally publishedYes

Keywords

  • Column generation
  • Integer programming
  • Max-min fairness
  • Network routing

Fingerprint Dive into the research topics of 'On single-path network routing subject to max-min fair flow allocation'. Together they form a unique fingerprint.

  • Cite this