Ottimizzazione topologica di reti di tipo Internet Protocol con il metodo del Local Branching

Laurea in matematica per le scienze dell'ingegneria 

 

Il lavoro di tesi nasce nel contesto della progettazione di reti ottiche di telecomunicazioni di tipo IP (Internet Protocol). Il problema di Network Design consiste essenzialmente nell’ottimizzare la topologia di una rete, ciè nel determinare l’installazione di cavi tra coppie di nodi della rete che minimizzi il costo complessivo e che consenta di soddisfare un insieme di richieste di traffico.
Lo sviluppo di reti di telecomunicazioni di tipo IP è attualmente un problema di grande interesse, in connessione con la corrente e continua espansionedi Internet, nel numero di utenti utilizzatori e di servizi offerti.
Il futuro non può che prevedere sempre maggiori richieste da parte degli utenti, e dunque sarà importante progettare reti sicure e veloci, oltre che in grado di fornire servizi sempre più all’avanguardia.
La strategia di instradamento più utilizzata nelle reti IP è quella OSPF (Open Shortest Path First), secondo la quale ogni pacchetto di dati viene instradato su uno dei cammini minimi fra il nodo di partenza e quello di destinazione, e conseguentemente ogni flusso, costituito da tanti pacchetti di dati, viene suddiviso in parti uguali su tutti i cammini minimi possibili.
La formalizzazione matematica in un modello di Programmazione Lineare Misto-Intera di problemi di Network Design è stata affrontata ampliamente in un precedente lavoro di tesi [5], in cui tra l’altro si è tenuto conto anche della possibilità di studiare reti robuste, ovvero in grado di resistere ad eventuali malfunzionamenti di alcuni archi. In questa tesi si è considerato un modello relativamente più semplice, ma ciononostante sempre di notevole complessità computazionale, ed in particolare si è tentato l’approccio risolutivo con un metodo che si colloca in posizione intermedia fra il Branch and Bound esatto ed i metodi euristici. Si tratta del metodo del Local Branching, descritto ampiamente in [1], che consiste in una successione di soft variable fixing: non vengono scelte manualmente le variabili da fissare, ma è l’algoritmo stesso che decide quali sia più conveniente mantenere costanti e quali invece far variare.
Questo tecnica può essere implementata in Programmazione Lineare grazie all’inserimento di un particolare tipo di taglio, detto taglio di Local Branching, in grado di ridurre ad un piccolo sottoinsieme del politopo originale lo spazio di ricerca delle soluzioni.
Il metodo che ne deriva, pur essendo in linea di principio esatto, si comporta essenzialmente come una meta-euristica, e dunque è in grado di trovare in tempi brevi soluzioni molto prossime all’ottimo, ma senza poterne garantire l’ottimalità. Si propone allora in questa tesi un confronto tra questo metodo innovativo ed il più tradizionale Branch and Bound applicato al problema in esame.
I risultati rispecchiano la grande complessità del problema, che può essere risolto con queste tecniche solo per istanze di 6, 7 nodi, ancora troppo lontane da istanze reali, che dovrebbero tenere in conto almeno 15, 20 nodi. Il Local Branching, opportunamente settato, può però risultare nettamente migliore del Branch and Bound classico, soprattutto quando la ricerca è volta a determinare la migliore soluzione possibile in tempi brevi.

 

 

 

Scarica la tesi

http://www.matematicamente.it//tesi/Cimolin-Ottimizzazione_topologica_reti.pdf

Scarica la presentazione PowerPoint

http://www.matematicamente.it//tesi/Cimolin-Ottimizzazione.ppt

 

Commenti

commenti