A column generation algorithm for network routing subject to max-min fair flow allocation

The max-min fairness (MMF) is a paradigm which has attracted a growing attention in communication networks, particularly with the bandwidth allocation problems in multicommodity flow networks. Roughly speaking, it amounts to imposing that the bandwidths should be allocated so that a further attempt to increase the allocation of the bandwidth of any user would necessarily decrease the allocation of the bandwidth of another user receiving smaller or equal allocation. To the best of our knowledge, up to now this paradigm has only been considered as a routing objective. Since the congestion control mechanism used in TCP layer provides a bandwidth allocation which is well approximated by the MMF bandwidth allocation, we consider the MMF as a protocol requirement rather than a routing objective. We address the problem where, given a network with link capacities and a set of communications to route, we must select a single path for each communication so as to maximize a network utility function subject to MMF constraints. We develop a column generation algorithm, proposing the decomposition model, column selection and trimming methods. We test our algorithms on many realistic instances with different numbers of commodities in order to evaluate their performances. The results indicate that the column generation algorithm is able to find feasible solutions with reasonable gaps for the large instances where the exact method cannot find any feasible solution. When comparing with results of restricted MIP (where a fixed amount of paths are generated randomly for each commodity and the commodity is restricted to use them), column generation algorithm gives better results. We also show that the paths in the best feasible integer solution are quite different than the paths in the linear solution.

Il max-min fairness (MMF) è un paradigma che ha ricevuto una crescente attenzione nelle reti di comunicazione, in particolare, nel caso di problemi di allocazione della banda in flussi multicommodity su reti. Sulla base delle nostre conoscenze, tuttavia, questo paradigma è stato considerato come un obiettivo di routing: la banda dovrebbe essere allocata in modo tale che un ulteriore tentativo di aumentare l'allocazione di qualsiasi flusso renderebbe necessario il decremento di allocazione di flusso con minore o uguale allocazione. Poichè i meccanismi di controllo della congestione usati nel layer TCP forniscono una allocazione di banda che è ben approssimata dall'allocazione di banda proposta da MMF, si è considerato l'MMF come un requisito del protocolo di comunicazione invece che come un obiettivo di routing. In questa tesi, consideriamo il problema che consiste, data una rete con archi (con una capacità sugli archi) e un insieme di comunicazioni da instradare, nel selezionare un percorso unico per ogni comunicazione in modo da massimizzare la funzione di utilità dell'operatore soggetta a vincoli MMF. Sviluppiamo un algoritmo di 'column generation', proponendo un modello di decomposizione, e metodi di selezione di colonne e trimming. Testiamo questo algoritmo su casi realistici con un numero vario di origini e destinazioni per valutarne le efficenta. I risultati indicano che l'algoritmo è in grado di trovare soluzioni ammissibili con discostamenti ragionevoli per grandi istanze dove metodi esatti non riescono. Nel confronto con i risultati di MIP ristretto, dove i percorsi sono generati casualmente, l'algoritmo fornisce migliori risultati rispetto a quelli ottenuti risolveldo un modello MIP basato su un numero di ristretto di cammini. Mostriamo anche che i percorsi nella migliore soluzione intera possibile sono diversi dai percorsi nella soluzione lineare.