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.

(2013). On single-path network routing subject to max-min fair flow allocation [journal article - articolo]. In ELECTRONIC NOTES IN DISCRETE MATHEMATICS. Retrieved from http://hdl.handle.net/10446/229356

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

Coniglio, Stefano;
2013

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.
articolo
Amaldi, Edoardo; Coniglio, Stefano; Gianoli, Luca G.; Ileri, Can Umut
(2013). On single-path network routing subject to max-min fair flow allocation [journal article - articolo]. In ELECTRONIC NOTES IN DISCRETE MATHEMATICS. Retrieved from http://hdl.handle.net/10446/229356
File allegato/i alla scheda:
File Dimensione del file Formato  
2013-INOC.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 178.37 kB
Formato Adobe PDF
178.37 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229356
Citazioni
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact