Metodi euristici per l'ottimizzazione di flussi TCP/IP soggetti a vincoli di equità

Il presente lavoro riguarda il problema che si pone un operatore di rete quando deve decidere il piano d'instradamento da adottare, per soddsifare al meglio tutte le richieste di servizi di tipo best-effort. Tali richieste sono definite unicamente dalle coppie origine-destinazione, poiché la domanda non è nota a priori. Si tratta di un problema bilivello in cui l'operatore di rete (al primo livello) sceglie un cammino per ogni coppia sorgente-destinazione con l'obbiettivo di massimizzare il throughput complessivo della rete, mentre il meccanismo di controllo della congestione dei protocolli di trasporto (al secondo livello) provvede ad allocare i flussi secondo il principio di equità MMF ("max min fairness"). Vista la notevole complessità del problema e l'elevato onere computazionale richiesto dai metodi di risoluzione esatti, sono stati sviluppati diversi algorimti euristici: dalla più semplice ricerca greedy randomizzata, al più articolato metodo GRASP ("greedy randomized adaptive search procedure") con "path-relinking". Le prove computazionali condotte evidenziano che l'algoritmo GRASP con "path-relinking" sia in grado di produrre delle soluzioni di qualità media molto buona in tempi ragionevoli.