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

Politecnico di Torino

I Facoltà di Ingegneria

Corso di Laurea in Matematica per le Scienze dell’Ingegneria

Tesi di Laurea

Ottimizzazione topologica di reti

di tipo Internet Protocol con il

metodo del Local Branching

Relatore:

prof. Roberto Tadei Candidato:

Flavio Cimolin

Dicembre 2003

Indice

1 Introduzione 2

2 Il problema in esame 4

2.1 Descrizione del problema . . . . . . . . . . . . . . . . . . . . . 4

2.2 Modello di programmazione lineare . . . . . . . . . . . . . . . 6

2.3 Implementazione del modello in Xpress Mosel . . . . . . . . . 9

3 Metodi per la Programmazione Lineare Misto-Intera 12

3.1 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2 Euristiche basate su ricerca locale . . . . . . . . . . . . . . . . 14

3.3 Local Branching . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Implementazione del metodo e analisi dei risultati 24

4.1 Implementazione del metodo . . . . . . . . . . . . . . . . . . 24

4.1.1 Perché il local branching . . . . . . . . . . . . . . . . . 24

4.1.2 Soluzione iniziale . . . . . . . . . . . . . . . . . . . . . 25

4.1.3 Tagli di local branching . . . . . . . . . . . . . . . . . . 25

4.1.4 Tempo limite . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.5 Imposizione di un Upper Bound . . . . . . . . . . . . . 27

4.1.6 Struttura dell’algoritmo . . . . . . . . . . . . . . . . . . 27

4.1.7 Xpress IVE . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2 Istanze analizzate . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3 Risultati ottenuti . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 Analisi dei risultati . . . . . . . . . . . . . . . . . . . . . . . 35

5 Conclusioni e sviluppi futuri 40

Bibliografia 41

A Listato del programma in Mosel IVE 43

B Esempio di Istanza 55

Capitolo 1: Introduzione

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, cioè 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 espansione di 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 ampiamente 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.

Capitolo 2: Il problema in esame

2.1 Descrizione del problema

Il problema che andremo ad affrontare si può descrivere sinteticamente nel modo seguente:

Dato un insieme di nodi collegati tra loro da una serie di archi (ciascuno dei quali con un determinato costo di instradamento), e dato un insieme di richieste fra coppie di nodi, determinare la topologia di costo minimo e l’allocazione della banda che permetta di instradare tutti i flussi nel modo ottimale.

Andiamo ora a vedere più in dettaglio le varie componenti del problema.

Possiamo anzitutto pensare l’insieme dei nodi (che chiameremo in seguito N) come a città in una data regione, collegate fra di loro da strade. Una strada fra due città vicine corrisponde ad un arco fra una coppia di nodi. Non necessariamente, dunque, fra ogni coppia di nodi esiste un arco attivabile.

Nella formulazione matematica del modello, al fine di ridurre il numero di variabili utilizzate, conviene distinguere fra arco senza direzione fra il nodo i ed il nodo j (che indicheremo con {i, j} e chiameremo spigolo) ed arco direzionale fra il nodo i ed il nodo j (che indicheremo con (i, j) e chiameremo arco vero e proprio). Per questa descrizione iniziale del problema confonderemo ancora archi con spigoli, evidenziando le differenze laddove necessario.

Su ogni via che congiunga una città con un’altra è possibile installare uno o più link. Un link è un cavo in fibra ottica che porta con sé una certa banda fissata (non necessariamente uguale su tutti gli archi della rete). Per come è costituito fisicamente, un link installato su un arco fornisce una capacità costante uguale in entrambe le direzioni, e il traffico che circola in un verso non influenza quello che circola nel verso opposto. Per ogni arco (bidirezionale, cioè per ogni spigolo) viene dunque assegnata la capacità dei link che vi si possono installare (chiameremo tali valori q{ij}) ed il relativo costo unitario (che chiameremo c{ij}).

Figura 2.1: Esempio di grafo per il problema

Per ogni arco potenziale sono inoltre definiti dei pesi amministrativi (nel modello saranno chiamati wij) e, questa volta, non necessariamente tali costi sono simmetrici nelle due direzioni, cioè è possibile che un arco abbia un costo se percorso in un verso, ed un altro costo differente se percorso in senso inverso. È importante notare che questi “costi di instradamento” non sono delle vere e proprie spese che vadano ridotte al minimo, ma devono piuttosto essere considerati come dei pesi, attraverso i quali il gestore della rete cerca di far fluire il traffico su certi archi piuttosto che su altri, al fine di ottimizzare alcuni parametri di QoS (Quality of Service). L’operazione di calibrazione dei pesi viene però effettuata in fase di simulazione, e di conseguenza nell’ambito del problema in esame ci limitiamo a considerare questi valori come dei dati del problema stesso, che rientreranno nel nostro modello in qualità di pesi per il calcolo dei cammini minimi.

In Figura 2.1 è rappresentato un esempio di grafo relativo al problema in esame, sul quale sono anche riportati i dati di una particolare istanza costruita in modo da essere il più possibile somigliante ad un caso reale (il file di dati contenente le matrici come vengono lette dal programma è visibile in Appendice B). I nodi sono allora costituiti da 6 città, e sono collegati da una struttura di 10 archi potenziali. Sugli archi sono indicati in carattere grande i valori c{ij} corrispondenti al costo di installazione di un link (e sono proporzionali alla distanza reale fra le città), e più in piccolo i valori q relativi alle capacità dei link da installare. Inoltre i pesi wij sono stati rappresentati con delle freccette, dato che corrispondono al costo di attraversamento di un arco in una specifica direzione.

Il costo effettivo della rete così strutturata, che si vorrà appunto andare a minimizzare, è dato allora dalla somma dei costi di ogni singolo link installato. Per farlo, sarà necessario scegliere su quali archi installare dei link e quanti installarne. Per questo parleremo inizialmente solo di archi potenziali, che diventeranno archi effettivi della rete solo una volta che vi sia stato installato almeno un link.

L’insieme delle richieste (che indicheremo in seguito con K) è costituito da terne contenenti un nodo di origine (ok), uno di destinazione (dk), ed una capacità del flusso in questione (pk). La topologia che verrà stabilita, oltre a dover naturalmente garantire che tutti i flussi possano giungere a destinazione, deve soddisfare alcuni principi generali che andremo ora a descrivere, e che devono essere tenuti in considerazione all’interno del modello. Anzitutto la strategia di instradamento che consideriamo è costituita dall’Open Shortest Path First protocol (OSPF), consistente nella richiesta che ciascun pacchetto di dati debba essere instradato su uno dei cammini minimi fra il nodo di origine ed il nodo di destinazione (cammino minimo calcolato in base ai costi wij degli archi della topologia che devono essere percorsi). Dato che ogni richiesta rappresenta un flusso costituito da molti pacchetti di dati, ciascun cammino minimo verrà utilizzato. In particolare, una approssimazione comunemente accettata è data dall’Equal Commodity Multi-flow principle (ECM): ogni flusso che giunge in un nodo in cui vi siano più (di uno) archi uscenti appartenenti a cammini minimi dal nodo stesso alla destinazione, viene suddiviso uniformemente su ognuno di essi. È infatti possibile che per arrivare dal nodo di origine ō al nodo di destinazione d ci siano vari percorsi alternativi tutti con lo stesso costo (minimo possibile). Allora la regola ECM impone che il flusso p̄ venga suddiviso in parti uguali su ognuno di questi possibili cammini minimi.

2.2 Modello di programmazione lineare

Riportiamo di seguito il modello di PLMI del problema sopra descritto, come presentato in [2]. Consideriamo anzitutto i seguenti insiemi di base:

• N: insieme dei nodi
• K: insieme delle richieste
• E: insieme degli spigoli potenziali
• A: insieme degli archi potenziali

Utilizzeremo la notazione {i, j} per indicare uno spigolo (senza direzione) fra il nodo i ∈ N ed il nodo j ∈ N, e la notazione (i, j) per indicare un arco (direzionale) fra il nodo i ∈ N ed il nodo j ∈ N.

Per rendere più agevole la scrittura del problema faremo uso inoltre delle seguenti notazioni:

• ok ∈ N: nodo origine della richiesta k
• dk ∈ N: nodo destinazione della richiesta k
• DK = {v ∈ N: ∃k ∈ K, v = dk} ⊂ N: insieme dei nodi che sono destinazione di qualche richiesta
• Od = {v ∈ N: ∃k ∈ K, v = ok ∧ dk = d} ⊂ N: nodi che sono origine di una richiesta che ha come nodo di destinazione d
• kod = {k ∈ K: ok = o, dk = d} ⊂ K: richieste che hanno come origine il nodo o e come destinazione il nodo d

Definiamo ora le costanti fondamentali del problema:

• c{ij}: costo di installazione di un link sullo spigolo {i, j} ∈ E
• q{ij}: capacità di un link installato sullo spigolo {i, j} ∈ E
• wij: peso di instradamento per l’arco (i, j) ∈ A
• pk: capacità della richiesta k ∈ K

Sia inoltre definita per ogni nodo d ∈ D la costante MKd somma delle richieste dirette al nodo d:

M_d = ∑ p_od

o∈O_d

Per ogni spigolo {i, j} ∈ E definiamo poi la costante M{ij} che indichi il numero massimo di link installabili sullo spigolo {i, j}.

Consideriamo infine due costanti MΩ sufficientemente grande ed ε sufficientemente piccola, relative alla ricerca dei cammini minimi. MΩ è posta uguale alla somma degli n − 1 archi più lunghi della rete (dove n è il numero di nodi), mentre ε è posta uguale a 1. Questi valori sono rispettivamente un upper bound ed un lower bound della massima e della minima distanza tra due nodi della rete.

Passiamo ora a definire le variabili del problema:

• y{ij}, ∀{i, j} ∈ E: variabile binaria della topologia, vale 1 se {i, j} appartiene alla topologia, vale 0 altrimenti
• x{ij}, ∀{i, j} ∈ E: variabile intera che indica il numero di links da installare sullo spigolo {i, j}
• ydij, ∀(i, j) ∈ A, ∀d ∈ D: variabile binaria, vale 1 se l’arco (i, j) è su almeno uno dei cammini minimi da un qualunque nodo in Od verso il nodo d, 0 altrimenti
• fdij, ∀(i, j) ∈ A, ∀d ∈ D: variabile reale che indica l’ammontare totale dei flussi diretti al nodo d che passano attraverso l’arco (i, j)
• πdi, ∀i ∈ N, ∀d ∈ D: variabile reale che indica il costo del cammino minimo dal nodo i al nodo d

Consideriamo a questo punto la seguente funzione obiettivo:

min ∑ c{ij} x{ij} (2.1)

{i,j}∈E

Andiamo ora a descrivere una per una le varie classi di vincoli:

Vincoli di capacità: ∑ fdij ≤ q{ij}x{ij} ∀(i, j) ∈ A (2.2)

d∈D

Vincoli di conservazione del flusso:

∑ fdij − ∑ fdji = pk se i ∈ Od

j∈N/(i,j)∈A j∈N/(j,i)∈A

∑ fdji − ∑ fdij = MKd se i = d ∀d ∈ D, ∀i ∈ N

j∈N/(j,i)∈A j∈N/(i,j)∈A

∑ fdij − ∑ fdji = 0 altrimenti (2.3)

j∈N/(i,j)∈A j∈N/(j,i)∈A

Vincoli di equa suddivisione dei flussi secondo la regola OSPF-ECM:

fdij ≤ fdil + MΩ(2 − y^d_il − y^d_ij) ∀d ∈ D, ∀(i, j) ∈ A, ∀(i, l) ∈ A (2.4)

fdij ≤ M^d_K y^d_ij ∀d ∈ D, ∀(i, j) ∈ A (2.5)

Vincoli per il calcolo dei cammini minimi:

πdi − πdj ≤ wij + ε(ydij − 1) + MΩ(1 − ydji) + (ε − wji − wij)ydji (2.6)

∀(i, j) ∈ A, ∀d ∈ D

Vincoli relativi agli archi aperti:

ydij + ydji ≤ y{ij} ∀d ∈ D, ∀{i, j} ∈ E (2.7)

Vincoli di rafforzamento del modello (sono già presenti implicitamente all’interno dei precedenti, ma la loro aggiunta permette di escludere alcune soluzioni non intere e quindi non ammissibili nello spazio delle soluzioni):

x{ij} ≤ M{ij} y{ij} ∀{i, j} ∈ E (2.8)

y{ij} ≤ x{ij} ∀(i, j) ∈ E (2.9)

Riepiloghiamo infine i domini delle variabili:

y{ij} ∈ {0, 1} ∀{i, j} ∈ E

x{ij} ∈ ℕ ∀{i, j} ∈ E

ydij ∈ {0, 1} ∀d ∈ D, ∀(i, j) ∈ A

fdij ∈ ℝ ∀d ∈ D, ∀(i, j) ∈ A

πdi ∈ ℝ ∀d ∈ D, ∀i ∈ N

2.3 Implementazione del modello in Xpress Mosel

L’implementazione in linguaggio Mosel ha dovuto necessariamente tenere conto di una serie di accorgimenti che andremo a descrivere.

Anzitutto, vista la grande mole di dati relativi ad un’istanza del problema (descrizione della topologia della rete, costi di instradamento, costi dei links, richieste), è stato necessario creare un file di dati apposito per ogni istanza su cui applicare il modello. Ad esempio, un file di dati del tipo “istanza 6n 20r.dat” contiene i dati relativi ad un’istanza da 6 nodi e 20 richieste. Il file di dati viene letto dal programma in fase di inizializzazione in modo da acquisire tutte le costanti necessarie. Per un esempio effettivo di file di istanza, vedere l’Appendice B.

Per come è stato formulato il modello, esso presenta casi in cui formalmente sarebbe necessario costruire array di insiemi, cosa che non è possibile effettuare in automatico con i comandi del linguaggio Mosel. È stato dunque necessario aggirare il problema costruendo per ognuno di questi array una matrice strutturata da usare in sostituzione dell’insieme che si voleva descrivere. Per vedere come si è risolto il problema nei vari casi specifici, si rimanda all’Appendice A, ove è riportato il listato del programma con i relativi commenti esplicativi. L’utilizzo di matrici opportunamente strutturate in luogo di insiemi è stato effettuato principalmente per gli insiemi O e kod.