Modelli e metodi di ottimizzazione per l'instradamento di flussi soggetto a vincoli di equità di suddivisione della banda

Questa tesi di Ricerca Operativa riguarda l'instradamento di comunicazioni su reti di telecomunicazione soggetto a meccanismi automatici di allocazione della banda (e.g. Transfer Control Protocol -- TCP). Il problema affrontato è quello dell'operatore di rete che, volendo massimizzare una funzione di utilità del servizio proporzionale alla quantità totale di traffico instradato, deve determinare i cammini per ogni coppia di origine-destinazione. Si suppone che, scelti dall'operatore i cammini, nelle reti IP (Internet Protocol) il meccanismo automatico di allocazione della banda sia ben approssimato dal cosiddetto principio di Max-Min Fairness (MMF). Viene così proposto un modello di Programmazione Lineare Misto-Intera (PLMI) che mira a massimizzare la sommatoria dei flussi assegnati, includendo il rispetto del principio di Max-Min Fairness sotto forma di vincoli. Questo approccio è diverso da quello classico adottato in letteratura, dove il raggiungimento di una soluzione Max-Min Fair viene considerato come obiettivo dell'ottimizzazione, piuttosto che come vincolo da rispettare. Successivamente viene analizzato il problema della formazione di sotto-cicli nelle soluzioni. Sono quindi definiti e confrontati diversi insiemi di vincoli per la rimozione dei sotto-cicli, proponendo tre diverse formulazioni estese ed un approccio iterativo di disuguaglianze valide (piani di taglio) nel contesto di un algoritmo di Branch-and-Cut. Si definisce poi un insieme di vincoli da aggiungere alla formulazione nel tentativo di rafforzarla. Vengono proposti vincoli alternativi per il bilanciamento del flusso e per il raggiungimento della Max-Min Fairness. Infine, vengono presentati dei metodi euristici basati su un algoritmo esatto di assegnazione equa del flusso, chiamato ``waterfilling''. L'intento è di ridurre gli elevati tempi di risoluzione causati dalla notevole complessità del modello, fornendo soluzioni di buona qualità utilizzate nel contesto di un algoritmo di Branch-and-Bound.