Design and Optimisation of a Novel Composite-Star TDM/WDM Network Architecture: the Petaweb

(Fig.1.8). Si ha dunque una sovrapposizione di stelle aventi al centro un nodo di commu-
tazione, detto anche nodo cuore, e alle estremita` dei nodi di accesso. In tal modo il traffico
fra due nodi di accesso avviene sempre e solo con un solo salto (hop) e ogni cammino ottico
viene commutato da un solo nodo cuore.
Un insieme di richieste di connessioni caratterizza una matrice di traffico fra i nodi
d’accesso elettronici, i quali introducono nella rete di trasporto traffico statico di tipo
aggregato. Il traffico proveniente dalla rete di accesso e` smaltito tramite un insieme di
cammini ottici di capacita` discreta che sono commutati dai nodi cuore. Ogni nodo cuore e`
costituito da uno o piu` piani di commutazione, ognuno dei quali (Fig.1.9) e` costituito da
un numero di commutatori spaziali uguale al numero di lunghezze d’onde per fibra (che
consideriamo uguale per tutte le fibre). Ogni commutatore spaziale tratta canali relativi
alla stessa lunghezza d’onda. In base al numero di piani di commutazione, si considerano
tre tipi di nodi cuore: un nodo cuore con 1, 2 o 4 piani di commutazione e` di tipo 1, 2 o
3. La connessione ottica fra un nodo di accesso e un nodo cuore e` quindi costituita da un
numero di fibre uguale al numero di piani di commutazione del nodo cuore (Fig.1.10), in
modo tale che i canali di una fibra sono demultiplessati da un unico piano di commutazione.
E´ quindi evidente la semplificazione garantita da tale schema di commutazione ad un solo
hop.
Per operare la divisione temporale del canale di una lunghezza d’onda si propone (par.
1.2.2) la sostituzione dei piani di commutazione descritti in Vickers et al. [11] con i com-
mutatori ottici a divisione temporale proposti in Huang et al. [26]; questi ultimi hanno
una struttura compatibile con quella descritta e effettuano la commutazione a livello di
time-slot nel dominio ottico senza alcun’operazione di buffering.
Ogni nodo di accesso definisce un sito di rete, e ogni sito di rete diviene sito di commu-
tazione se un nodo cuore vi e` installato. Piu` nodi cuori possono essere installati in un sito e
quindi il tronco ottico di linea fra un nodo di accesso e un sito di commutazione e` formato
da uno o piu` collegamenti ottici unidirezionali in numero pari, per direzione, al numero di
nodi cuore del sito di commutazione; il numero di fibre totali del tronco di linea e` quindi
pari, per direzione, al numero totale di piani di commutazione del sito.
Studi su PetaWeb
Concepita come una rete di trasporto ottico di prossima generazione, PetaWeb e` stata
oggetto di sperimentazioni e di analisi delle prestazioni. Blouin et al. [12] hanno emulato
una struttura di rete PetaWeb, Blouin and Beshai [14] hanno proposto un particolare
algoritmo di instradamento per aumentare le prestazioni, Sterbenz et al. [15] hanno studiato
l’interconessione di IP con PetaWeb in diversi scenari. Blouin et al. [13] hanno comparato
IV
la struttura PetaWeb alle tradizionali reti ottiche a maglia; hanno concluso che anche se
l’implementazione di una rete PetaWeb richiede un’importante quantita` di fibra ottica (circa
il 17% in piu` che in una rete multihop) e implica un piu` importante ritardo di propagazione,
le semplificazioni nelle procedure di instradamento e commutazione e la semplice estensione
della rete sono fattori molto importanti. Dopotutto gli autori concludono che la diminuzione
progressiva del costo della fibra e` incoraggiante. In questa tesi si mostra come il costo della
fibre adottando una particolare topologia puo` essere tenuto al di sotto del 70% del costo
totale della rete.
Reinert e Sanso` [21] [22] [23], sono stati i primi ad affrontare il design di una rete ottica
di tipo PetaWeb con traffico statico. I loro metodi e formulazioni hanno ispirato il lavoro
di questa tesi; tuttavia, avendo gli autori considerato una divisione temporale continua
del canale e non avendo affrontato in maniera rigorosa la gestione dell’instradamento nella
rete, la modellizzazione proposta e` carente e parziale; alcuna emulazione dei loro risultati
e` infatti possibile, cos`ı come alcun assegnamento delle risorse e analisi delle prestazioni e`
effettuabile.
In questa tesi si affronta di nuovo il design di una rete di tipo PetaWeb definendo
rigorosamente il modello di rete, l’approvvigionamento (provisiong) dei cammini ottici e
il loro instradamento (cap.3). Si pone un problema di design che viene risolto sia nella
sua parte di allocazione delle risorse che nell’assegnamento delle stesse (cap.4-5). Si for-
nisce una realistica metodologia di gestione dei cammini ottici che facilita ulteriormente
l’instradamento e la commutazione in una struttura di tipo PetaWeb. Al fine di diminuire
i tempi di ottenimento della soluzione si descrive come modificare un’euristica esistente per
la risoluzione di parte del problema di design (cap.6-7). Si aggiunge poi al modello una
strategia di protezione e si mostra come cio` migliora i risultati in termini di affidabilita`
(cap.8-9). Infine si fornisce una procedura di aggiornamento ottimo di una rete PetaWeb
esistente, precedentemente ottimizzata, e sottoposta a un incremento di traffico e di nodi
di accesso (cap.10-11). Un’ultima analisi dimostra la convenienza dell’uso del TDM/WDM
(cap.12).
Modello di rete
Il traffico delle richieste di connessione dei nodi di accesso e` di tipo statico ed e` estratto da
delle matrici di traffico fornite in due tipi: A per traffico proveniente da dati industriali, B
per traffico determinato secondo un modello gravitazionale (par.3.1). Lungo la tesi vengono
considerati principalmente quattro modelli di rete con 10 e 34 nodi di accesso: 10A, 10B,
34A e 34B (Appendix A). Ogni richiesta di connessione e` nell’ordine del Tb/s, mentre il
volume di traffico globale e` nell’ordine del Pb/s.
V
Il progetto della rete consiste nella minimizzazione del costo totale, determinato come
somma del costo degli apparati di commutazione, del costo della fibra e di un costo attribuito
al ritardo di propagazione dei cammini ottici (par.3.2).
Il modello di rete fornisce quindi un insieme di richieste di connessioni fra i nodi di
accesso da accomodare in cammini ottici. Coerentemente con i recenti standard ITU-T
[1] [2], definiamo una gerarchia a tre livelli di servizio per i cammini ottici sfruttando la
partizione temporale del canale di una lunghezza d’onda (Fig.3.2). Il cammino ottico viene
chiamato ts-lightpath (TLP). La prima classe di servizio, indicata con TLP-1 (3.1), utilizza
un time slot ed ha una capacita` di trasporto di 0.625 Gb/s. La seconda classe di servizio,
indicata con TLP-2 (3.2), utilizza un intero canale di una lunghezza d’onda e ha quindi
una capacita` di trasporto di 10 Gb/s. La terza, indicata con TLP-3 (3.3), utilizza invece
un’intera fibra, quindi 16 canali, ed ha una capacita` di 160 Gb/s. In tal modo le operazioni
di commutazione sono ulteriormente semplificate perche´ un TLP-2 puo` essere commutato
senza dover effettuare l’allineamento dei time-slots, e un TLP-3 puo` essere commutato
semplicemente interconnettendo una fibra in ingresso al nodo cuore e una fibra in uscita.
Una richiesta di connessione fra due nodi di accesso e` servita al meglio utilizzando il minor
numero di cammini ottici che garantiscono una buon’approssimazione del traffico richiesto
(par.3.3).
L’ottimizzazione della rete consiste quindi nel dimensionare efficacemente la rete, de-
terminando dove installare i nodi cuore, la loro dimensione (tipo), quali TLP ogni nodo
cuore deve commutare e quali risorse devono essere assegnate ad ogni TLP. Nel modello di
ottimizzazione si deve tenere conto di vincoli di capacita` (par.3.4.1) e di vincoli di coerenza
(par.3.4.2). I primi considerano la limitata capacita` di trasporto dei collegamenti ottici, la
limitata capacita` di commutazione dei nodi cuore in base al loro tipo, e la limitata capacita`
di trasmissione dei nodi d’accesso elettronici. I vincoli di coerenza impongono che tutti
i TLP relativi ad una stessa connessione siano trasportati lungo gli stessi tronchi ottici
di linea, che tutti i time-slot di uno stesso TLP siano multiplessati contiguamente e sul
medesimo collegamento ottico (commutati dallo stesso nodo cuore).
Problema di design
Il problema di design di un’architettura di rete di tipo PetaWeb con il modello di rete
descritto e` chiamato RFWTAA (Route, Fibre, Wavelength, Time-slot Allocation and As-
signment), ed e` diviso nei due sottoproblemi:
RFA Route and Fibre Allocation (par.4.2)
Questo sottoproblema riguarda l’allocazione ottima delle risorse dati l’insieme dei
cammini ottici generati per servire il volume di traffico richiesto, e i siti possibili per i
VI
nodi cuore. Restituisce il numero, il tipo e la localizzazione dei nodi cuori con i TLP
loro assegnati. Vengono cos`ı definiti i percorsi (Route) di un hop dei TLP assegnando
loro due collegamenti ottici: uno fra il nodo d’accesso d’origine e il nodo cuore, e uno
fra il nodo cuore e il nodo d’accesso di destinazione.
WTA Wavelength and Time-slot Assignment (par.4.3)
Riguarda l’assegnamento delle lunghezze d’onda e dei time-slot ai cammini ottici,
ognuno dei quali e` gia` stato univocamente assegnato a due collegamenti ottici.
Il sotto-problema RFA e` un problema matematico che non e` stato classificato formal-
mente. Presenta, tuttavia, alcune similitudini col Problema di Localizzazione dei Fornitori
a Capacita` Limitata [77]. Per la sua risoluzione viene proposta una formulazione matem-
atica di programmazione lineare a numeri interi espressa dalle (4.10)-(4.18): l’obiettivo da
minimizzare (4.10) e` il costo totale della rete espresso come somma del costo di tutti i nodi
cuori attivi, di tutte le fibre connesse a tali nodi cuore e del costo assunto dal ritardo di
propagazione di tutti i TLPs; (4.12) impone che un TLP puo` essere commutato da un solo
nodo cuore; (4.13) esprime il legame fra le due variabili; (4.14), (4.15) e (4.16) impongono i
vincoli sulle capacita` dei nodi d’accesso e dei collegamenti ottici; (4.17) e (4.18) impongono
la binarieta` delle variabili.
Il sotto-problema WTA e` invece di complessita` minore; per risolverlo viene descritto
un algoritmo lineare di risoluzione che procede in modo sistematico all’assegnamento delle
fibre, delle lunghezze d’onda e dei time-slot dei collegamenti ottici attivati, rispettando i
vincoli del modello di rete. Il diagramma di flusso dell’algoritmo di risoluzione del problema
WTA e` riportato in Fig.4.4.
Con questa tesi si propone anche l’adozione di una topologia quasi-regolare estratta da
quella regolare ottimizzata (par.4.4). Infatti, grazie al rigoroso modello di rete, si puo` ora
avere un controllo diretto sulla rete ottimizzata conoscendo esattamente quali lunghezze
d’onda e quali time-slot non saranno assegnati ad alcun ts-lightpath. Analizzando tutti i
collegamenti di rete attivi nella topologia regolare ottimizzata, e ricordando che un collega-
mento di rete fra un nodo d’accesso e un nodo cuore e` costituito da 1, 2 o 4 fibre ottiche,
si va a controllare se vi sono delle fibre che effettivamente saranno inutilizzate. In caso
affermativo, si disattivano e il loro costo e quello delle porte di connessione al nodo cuore
vengono sottratti dal costo totale. Se tutte le fibre di un collegamento ottico risultano
inutilizzate, l’intero collegamento ottico viene disattivato; similmente, se tutti i collega-
menti ottici lungo un tronco di linea risultano inutilizzati, l’intero tronco di linea verra`
disattivato. L’estrazione della topologia quasi-regolare e` effettuata a monte dell’algoritmo
WTA e non ne modifica il comportamento. La nuova topologia proposta e` stata chiamata
quasi-regolare, e non irregolare, perche´ con essa la regolarita` rimane preservata e ancora
VII
raggiungibile tramite integrazioni successive.
Risultati
Nel capitolo 5 sono riportati i risultati dettagliati ottenuti risolvendo il problema di de-
sign con l’ottimizzazione ILP (4.10)-(4.18), risolta attraverso CPLEX, e l’algoritmo WTA
(Fig.4.4). Sono stati considerati i modelli di rete 10A, 10B, 34A e 34B.
I risultati dell’allocazione delle risorse (par. 5.5) mostrano come il costo della fibra si
attesti sempre intorno all’80% del costo totale. Il costo dei nodi cuore e` dell’11% circa per
reti a 10 nodi, e del 5% circa per reti a 34 nodi (Tab.5.6). La distribuzione dei nodi delle
reti ottimizzate e` mostrata in Fig.5.5 e Fig.5.6, mentre le topologie regolare e quasi-regolare
per i modelli 10A e 10B sono illustrate in Fig.5.7 e Fig.5.8. In quest’ultime figure si nota
come e quanti tronchi di linea, collegamenti ottici e fibre vengono disattivati assumendo la
topologia quasi-regolare; cos`ı facendo il costo della rete diminuisce di circa il 60%; il peso
del costo della fibra passa infatti al 60%-73% e, conseguentemente, aumenta di dieci punti
percentuali il peso del costo del ritardo di propagazione (Tab.5.7).
Riguardo all’utilizzazione della rete, questa e` relativamente bassa se si assume la topolo-
gia regolare (intorno al 20%), mentre migliora fino al 50% con l’adozione di una topologia
quasi-regolare. Certo un’utilizzazione migliore della rete sarebbe auspicabile, ma la pre-
senza di una buona quantita` di capacita` di trasporto ancora disponibile e` un benefico effetto
dell’adozione della multiplazione temporale nei sistemi WDM. La capacita` rimasta disponi-
bile potra`, infatti, essere sfruttata per adottare strategie di ripristino dei cammini ottici,
nonche´ per aggiornare la rete con nuovi carichi di traffico e per offrire servizi di allocazione
dinamica di banda.
L’osservazione dei risultati dell’assegnamento delle risorse (par. 5.6) permette di com-
prendere come effettivamente l’instradamento viene effettuato in una architettura di tipo
PetaWeb, e come i time-slot e le lunghezze d’onda sono assegnati ai cammini ottici (Fig.5.12).
Euristica
I risultati ottenuti tramite l’approccio descritto nel capitolo 4 sono ottimali; tuttavia il
tempo di esecuzione degli algoritmi di risoluzione cresce in modo esponenziale all’aumentare
delle dimensioni della rete, cos`ı come si e` verificato per le reti a 34 nodi d’accesso. Dovendo
ottimizzare anche reti fino a 130 nodi, e` stato necessario sviluppare un metodo euristico
per il design di una rete PetaWeb in modo sub-ottimale.
Il capitolo 6 e` dedicato alla descrizione di un metodo euristico, ispirato ad un lavoro
precedente [23], a sua volta ispirato ad una euristica ad accoppiamento ripetuto ideata
VIII
da Ro¨nnqvist [76] [77] per risolvere il problema di localizzazione dei fornitori a capacita`
limitata. Abbiamo effettuato le modifiche utili a rendere tal euristica adatta al nostro
modello di rete.
L’euristica consiste in una successione di problemi di accoppiamento. S’introducono
diverse entita`: un Kit (par.6.1.1) comprende un nodo cuore e l’insieme dei suoi TLP, ed
e` realizzabile se non degenera nel solo nodo cuore o nell’insieme dei TLP; un Packing
(par.6.1.2) e` un’unione di Kit, realizzabili o meno, degeneri o meno. Un Packing e` definito
da tre insiemi:
L1 : insieme dei nodi cuori attivi, i.e. che non commutano alcun TLP; puo` essere visto
come un insieme di Kit degeneri nel proprio nodo cuore.
L2 : insieme di TLP non assegnati ad alcun nodo cuore; puo` essere visto come un insieme
di Kit degeneri nel proprio insieme di TLP.
L3 : insiemi di nodi cuore con i relativi TLP assegnati, i.e. un insieme di Kit realizzabili.
Un Packing e` detto realizzabile se non contiene Kit degeneri nel proprio insieme di TLP, i.e.
se L2 = . Il Packing definisce quindi lo stato della rete progettata che varia con le varie
iterazioni dell’euristica. E’ quindi sottoposto a cambiamenti, e gli elementi dei suoi insiemi
si accoppiano in modo tale da far diminuire una funzione di costo lui associata. Il costo di
un Packing (6.2) e` definito come la somma del costo dei nodi cuore attivi, delle fibre a loro
connessi, del ritardo di propagazione assunto dai TLP e di un costo, alto, attribuito a quei
TLP in L2 non ancora assegnati ad alcun Kit.
Nel paragrafo 6.2 e` ripresa la classica formulazione del problema dell’accoppiamento.
Nell’euristica ogni iterazione e` caratterizzata da un Packing iniziale e da un Packing finale.
L’obiettivo e` di modificare gli insiemi del Packing iniziale per diminuire il suo costo e
quindi il costo della rete progettata. Gli insiemi sono modificati attraverso una serie di
accoppiamenti fra gli elementi degli insiemi L1, L2 e L3. Ogni elemento di questi insiemi si
accoppia con un solo altro elemento; se l’accoppiamento e` riflessivo, lo status dell’elemento
non cambia.
Per ogni possibile accoppiamento si determina il costo, e tutti i costi vengono mem-
orizzati in un’apposita matrice (par.6.3.1). Il problema di risoluzione dell’accoppiamento
consiste quindi nell’estrarre dalla matrice dei costi un vettore indicante la serie di ac-
coppiamenti fra gli insiemi del Packing meno costosa. Tale problema e` risolto attraverso
l’algoritmo di Jonker and Volgenant [78], che estrae un vettore contenente una soluzione
asimmetrica, e attraverso l’algoritmo di Forbes [79], che estrae dalla soluzione asimmetrica
una soluzione simmetrica cancellando i cicli pari e dispari (par.6.3.2).
In Fig.6.4 e` riportato il diagramma dell’euristica. Si parte da un Packing non realizz-
abile, con L1 e L3 vuoti e L2 pieno. Ad ogni iterazione si costruisce la matrice dei costi e
IX
si risolve il problema dell’accoppiamento. Si sfrutta la soluzione per creare i nuovi insiemi
L′1, L′2 e L′3 dell’iterazione successiva. Quando il costo del Packing non diminuisce per tre
iterazioni successive e L2 e` vuoto, si esce e si controlla se e` possibile un’agglomerazione fra
nodi cuori di tipo 1 o 2; infatti due nodi cuore di tipo 1 o 2 possono essere rimpiazzati
da un solo nodo cuore di tipo 2 o 3, rispettivamente, avente un costo minore. Se viene
effettuata un’agglomerazione si ricomincia, altrimenti si esce dall’euristica. Un ultimo con-
trollo verifica se e` rispettata la capacita` dei nodi d’accesso, e in caso negativo si procede
alla disattivazione di un numero adeguato di piani di commutazione.
Risultati con l’euristica
Nel capitolo 7 sono riportati dettagliatamente i risultati della risoluzione del problema
di design ottenuti attraverso l’uso dell’euristica. L’euristica e` stata implementata in C++
riscrivendo interamente e modificando il codice esistente perche´ inadeguato al nuovo modello
di rete (Fig.7.1).
I risultati ottenuti tramite l’euristica per i modelli 10A, 10B 34A e 34B sono mostrati
in Tab.7.1 e Tab.7.2 per, rispettivamente, una topologia regolare e una quasi-regolare.
Comparando i risultati con quelli mostrati nel capitolo 5, si puo` notare che le soluzioni per
le reti a 10 nodi d’accesso sono esattamente le stesse, ma con l’importante differenza che
queste sono stati ottenuti in qualche secondo piuttosto che in qualche minuto. I tempi sono
enormemente diminuiti anche per le soluzioni dei modelli a 34 nodi: in tal caso gli obiettivi
sono leggermente diversi, ma la differenza con gli obiettivi ottenuti tramite l’approccio
ottimo e` al massimo dello 0.1%, quindi decisamente trascurabile.
Dunque, l’uso dell’euristica e` molto benefico e consigliabile per l’ottimizzazione di reti
con un gran numero di nodi d’accesso. In tal modo si sono potute ottenere, infatti, le
soluzioni per i modelli 40B, 50B, etc., fino a 130B (par.7.3). Grazie ai bassi tempi di es-
ecuzioni dell’euristica, sono state anche condotte delle simulazioni utilizzando altri tipi di
traffico (par.7.4). Queste ultime hanno dimostrato che con distribuzioni di tipo uniforme,
a parita` di volume di traffico, il costo della rete ottimizzata aumenta, pur aumentando
l’utilizzazione della capacita` di trasporto. Invece, mantenendo la stessa distribuzione in-
iziale, ma aumentando il volume di traffico di un fattore moltiplicativo, il costo della rete
non cresce in modo proporzionale all’aumento di traffico ed, infatti, l’utilizzazione della rete
raggiunge livelli prossimi all’80% con una topologia quasi-regolare. Cio` evidenzia la facile
scalabilita` di una struttura di rete di tipo PetaWeb che e` in grado di supportare con costi
competitivi volumi di traffico dell’ordine del Pb/s.
X
Strategia di protezione
Due situazioni particolari pongono problemi d’affidabilita` in una rete PetaWeb ottimizzata
con i metodi descritti. Una rete con una topologia come quelle mostrata in Fig.5.7b presenta
diversi nodi di accesso connessi alla rete di trasporto attraverso un solo tronco di linea. In
caso di rottura di quest’ultimo, tali nodi rimarrebbero del tutto isolati dalla rete anche
nel caso si adottassero delle procedure di ripristino del collegamento; infatti, il nodo di
accesso non disporrebbe di connessioni alternative dove instradare il flusso di ripristino
dei cammini ottici. Una situazione analoga si potrebbe verificare nel caso in cui la rete
ottimizzata presenti tutti i nodi cuori installati nello stesso sito di commutazione; tale
configurazione e` verosimile soprattutto per reti con un basso numero di nodi.
Nel capitolo 8 si affronta, per la prima volta, l’ottimizzazione di una rete di tipo PetaWeb
adottando una strategia di protezione del cammino ottico. Si e` scelta una strategia di
tipo Dedicated Path Protection (DPP), nella modalita` 1+1, perche´ e` l’unica che garan-
tisce l’assenza di una fase di segnalazione, in caso di rottura di un collegamento, che causi
l’interruzione del flusso ottico; cio` e` indispensabile per reti di tipo PetaWeb date le alte fre-
quenze di trasmissione. Aggiungere una strategia DPP al modello di rete significa prevedere
che per ogni TLP effettivo ne sia riservato anche uno di protezione, e che i due TLP siano
trasmessi su dei tronchi di linea diversi. Inoltre si e` aggiunta la facolta` di allocare per i TLP
di protezione un percorso piu` lungo rispetto a quello del TLP effettivo, garantendo quindi
a quest’ultimo un minor ritardo di propagazione. Il nodo di accesso di destinazione, in caso
di danno ad uno dei tronchi di linea a lui connessi, ricoverera` il flusso dati di protezione
proveniente da un altro tronco di linea senza interrompere la trasmissione.
L’introduzione della strategia DPP interviene nella sola formulazione di risoluzione
del problema RFA; infatti e` quest’ultima che si occupa di scegliere l’instradamento ot-
timo dei cammini ottici. L’algoritmo WTA non viene quindi modificato. La soluzione
per l’allocazione ottima delle risorse e` ottenuta sfruttando la formulazione di program-
mazione lineare (8.1)-(8.9). Nella funzione obiettivo (8.1) i termini relativi al costo dei
nodi cuore e delle fibre non cambiano rispetto a (4.10); per quanto riguarda il costo del
ritardo di propagazione, quello relativo ai TLP di protezione e` scalato per garantire il per-
corso migliore ai TLP effettivi. Il vincolo (8.2) impone che ogni TLP effettivo e il proprio
TLP di protezione siano trasportati su dei tronchi di linea diversi, il che equivale a imporre
che siano commutati in dei siti di commutazione diversi. Gli altri vincoli sono simili a quelli
della formulazione senza DPP, ma estesi anche ai TLP di protezione.
Per poter aggiungere la strategia di protezione all’euristica si interviene sui costi di
accoppiamento. Si vuole evitare il sorgere di violazioni, dove con violazione si intende la
commutazione di un TLP e del proprio TLP di protezione nello stesso sito. Per poter
XI
far cio`, si effettuano degli interventi a priori e degli interventi a posteriori. Coi primi si
imposta ad infinito il costo di quei accoppiamento che causerebbero una violazione. Suc-
cessivamente, gli interventi a posteriori vanno a controllare se nella soluzione simmetrica
restituita dall’algoritmo di Forbes sono state introdotte delle violazioni o se sono presenti
delle violazioni non interrompibili a priori (par.8.3). Con tali accorgimenti, l’euristica ad ac-
coppiamento ripetuto e` riutilizzabile anche per l’allocazione delle risorse in caso di adozione
di una strategia DPP.
Risultati con protezione DPP
I risultati ottenuti applicando la strategia di protezione al modello di rete sono riportati
nel capitolo 9. I risultati dell’allocazione delle risorse (Tab.9.1 e Tab.9.2) mostrano che al
raddoppio della capacita` di trasporto allocata non corrisponde il raddoppio del costo della
rete. Infatti, laddove conveniente, si e` utilizzata meglio la capacita` disponibile sui collega-
menti ottici rispetto al caso senza protezione, e cio` si riflette in una maggiore utilizzazione
della rete. Ovviamente la complessita` della formulazione ILP con protezione e` maggiore
rispetto alla precedente, e conseguentemente il tempo di esecuzione e` aumentato.
In Fig.9.3 e Fig.9.4 sono riportate la topologia regolare e quella quasi-regolare per i
modelli 10A e 10B. Diversamente che in Fig.5.7b, la rete ottimizzata a topologia quasi-
regolare e` ora affidabile: ogni nodo d’accesso e` collegato ad almeno due siti di commutazione
e in caso di danno ad un tronco di linea tutti i cammini ottici possono essere ricoverati dai
cammini ottici di protezione che sono trasportati su tronchi di linea disgiunti.
I risultati ottenuti con l’euristica sono riportati nel paragrafo 9.2. L’introduzione del
vincolo di protezione ha reso la dinamica dell’euristica meno ”naturale”, e cio` causa il
raggiungimento di una soluzione non ottimale, seppur ancor valida; l’obiettivo e` sempre
al di sotto del 13% dell’obiettivo raggiunto tramite il metodo ottimale. Tuttavia l’uso
dell’euristica rimane ancora indispensabile per configurare le soglie superiori dell’obiettivo
in CPLEX; cio` velocizza notevolmente il raggiungimento della soluzione con l’approccio
ottimo. Inoltre l’euristica, data l’attuale potenza di calcolo, rimane uno strumento indis-
pensabile per poter ottenere delle soluzioni accettabili per reti con un gran numero di nodi
(par.9.2.2).
L’osservazione dei risultati dell’algoritmo WTA, al paragrafo 9.3, permette di apprezzare
come i cammini ottici effettivi e di protezione sono instradati su tronchi di linea disgiunti, e
come le lunghezze d’onda e i time-slot sono assegnati con tale configurazione. Si puo` anche
notare come ai cammini ottici di protezione mostrati sia stato assegnato un percorso piu`
lungo rispetto a quell’ottimale assunto dai corrispondenti cammini ottici effettivi.
XII
Aggiornamento della rete
I risultati hanno quindi mostrato come una architettura di tipo PetaWeb puo` essere piani-
ficata in modo ottimale e affidabile; l’ottimizzazione garantisce il ripristino di ogni connes-
sione in caso di danno limitato ad un tronco di linea. Ancora una gran capacita` di trasporto
e` disponibile nella rete ottimizzata, circa il 50% nel caso di topologia quasi-regolare. Tale
capacita` puo` essere sfruttata attraverso aggiornamenti successivi della rete, e la procedura
di aggiornamento avra` un costo piu` o meno importante in base alla topologia della rete
esistente.
Nel capitolo 10 si affronta il problema dell’aggiornamento di una rete PetaWeb esistente
precedentemente ottimizzata. L’aggiornamento di una rete con un tipo di topologia (rego-
lare o quasi-regolare) produce una rete con lo stesso tipo di topologia. Si assume, per ovvie
ragioni, che l’instradamento dei cammini ottici gia` instaurati non venga modificato, e si
mantiene la strategia di protezione gia` definita. Inoltre si esclude dalla modellizzazione la
rimozione di equipaggiamenti gia` installati perche´ sarebbe inverosimile per reti ottiche di
estensione nazionale come PetaWeb. Il valore dei costi puo` cambiare; infatti si effettua una
valutazione della rete esistente secondo i costi attuali. L’incremento nel volume di traffico
genera nuovi TLP che devono essere trasportati nella rete pre-esistente. L’aggiornamento
consiste quindi nel sovradimensionare una rete esistente per poter accomodare un volume
di traffico maggiore e per annettere, eventualmente, nuovi nodi di accesso. Questo sovradi-
mensionamento puo` contemplare l’integrazione di collegamenti ottici esistenti con nuove
fibre (per una topologia quasi-regolare), e l’installazione di nuovi nodi cuore e collegamenti
ottici.
Anche il problema di aggiornamento e` suddiviso nelle due fasi di allocazione e di asseg-
namento delle risorse. L’algoritmo WTA non cambia, mentre la formulazione matematica
per l’allocazione e` ispirata a quelle gia` descritte. Nell’affrontare l’aggiornamento di una
rete PetaWeb ottimizzata si devono considerare il caso delle due topologie possibili: re-
golare e quasi-regolare. Nel paragrafo 10.2.1 si fornisce una formulazione unificata per
l’aggiornamento di una rete ottimizzata (10.5)-(10.14), dove il tipo di tipologia influenza il
valore di alcuni parametri (10.1)-(10.4). Tali parametri definiscono lo stato attuale della
rete e riguardano il costo equivalente degli apparati gia` installati (fibre e nodi cuore), e la ca-
pacita` di trasporto gia` utilizzata per ogni collegamento ottico. In tal modo l’aggiornamento
di una rete con topologia regolare avverra` ad un costo minore perche´ una gran quantita` di
fibre sara` gia` installata; nell’aggiornamento di una rete a topologia quasi-regolare, invece,
nella scelta per l’instradamento dei nuovi cammini ottici si terra` conto dei maggiori costi
per l’installazione di alcune fibre, precedentemente non installate perche´ sarebbero state
inutilizzate, per integrare o creare ex-novo dei collegamenti ottici previsti nella struttura
XIII
regolare.
Risultati dell’aggiornamento
Nel capitolo 11 si mostrano i risultati dell’aggiornamento in tre diversi scenari: aumento del
volume di traffico esistente del 40%, aumento del 200%, annessione di nuovi nodi d’accesso
con aumento del traffico esistente del 40%. Nel primo caso si nota che l’aggiornamento ha
causato l’apertura di 4 nuovi piani di commutazione nella rete oltre che lo sfruttamento della
capacita` gia` disponibile; l’utilizzazione della rete aumenta e conseguentemente diminuisce il
peso costo della fibra. Nel secondo caso l’aumento del 200% interessa tutti i nodi d’accesso
tranne quello di uno che gia` richiedeva un volume di traffico molto alto; si nota cos`ı che
pur avendo triplicato il traffico di quasi tutte le connessioni fra i nodi d’accesso, il costo
d’aggiornamento di una topologia regolare e` minore che nel primo caso; il costo di una
topologia quasi-regolare e` invece simile perche´, pur aumentando il numero dei piani di
commutazione, solo le fibre utili vengono effettivamente attivate.
Nel primo caso i piani di commutazione erano stati attivati per il solo traffico di New
York e la maggior parte delle nuove fibre da installare con la topologia regolare assumono un
alto costo, oltre che essere inutilizzate. Infatti, nel secondo caso alcun nuovo piano di com-
mutazione viene attivato con l’aggiornamento e viene solamente sfruttata la capacita` resa
disponibile dalla rete pre-esistente. E l’utilizzazione della rete aumenta significativamente.
Nel caso in cui oltre all’aumento del traffico esistente del 40% si aggiungono nuovi
nodi d’accesso, con nuove richieste di connessione, si apprezza come i nuovi nodi vengono
integrati alla rete. La rete aggiornata resta affidabile e robusta in caso di danno ad un
tronco di linea e i nuovi nodi vengono collegati attraverso almeno due percorsi ottici diversi.
L’aggiornamento e` in tal caso meno costoso di circa il 50% se riguarda una topologa quasi-
regolare. Nella Fig.11.4 si puo` osservare come una parte della rete esistente viene modificata
in seguito all’aggiornamento con nuovi nodi d’accesso, e come i cammini ottici delle nuove
richieste di connessioni vengono assegnati alle lunghezze d’onda e ai time-slot sia lungo
i collegamenti ottici disponibili nella rete pre-ottimizzata, sia lungo i nuovi collegamenti
installati per poter connettere i nuovi nodi d’accesso
Conclusioni
In questa tesi abbiamo, per la prima volta, affrontato rigorosamente e esaustivamente il
problema di dimensionamento e assegnamento ottimo delle risorse di una struttura di rete
ottica di tipo PetaWeb. La rete ottimizzata tramite i metodi proposti e` affidabile, garantisce
il servizio anche in caso di rottura dei collegamenti ottici; e` robusta, supporta bene alti
carichi di traffico; e` facilmente espandibile, perche´ grazie all’adozione della multiplazione
XIV
TDM/WDM molta capacita` di trasporto e` resa disponibile e l’aggiornamento della rete puo`
avvenire con costi limitati e con semplici operazioni di integrazione agli apparati esistenti.
Abbiamo inoltre dimostrato come l’uso del TDM e` utile nelle reti WDM, e in particolare
nelle reti PetaWeb, garantendo un risparmio nel costo finale fra il 10% e il 15%.
Una novita` del nostro lavoro e` la definizione di diverse classi di servizio con scelte
che semplificano ancor piu` le operazioni di commutazione in un’architettura di rete di
tipo PetaWeb. Il prossimo passo nell’esplorazione di questa nuova struttura di rete e` la
realizzazione di un simulatore che analizzi le prestazioni in diversi casi di studio.
Proponendo una topologia quasi-regolare, abbiamo limitato il costo della fibra a meno
del 70% per una rete progettata ex-novo con i modelli di traffico assegnatoci. Infatti, l’alta
lunghezza di fibra richiesta da un’architettura PetaWeb puo` essere un fattore decisivo nella
sua affermazione. Dalle analisi dei risultati emerge che l’adozione di una topologia rego-
lare e` consigliabile per reti di trasporto con aggiornamento continuo del volume di traffico.
Infatti, l’aggiornamento di una topologia quasi-regolare e` piu` costoso, a meno che non si
aggiungano nuovi nodi; tuttavia la sua adozione garantisce un costo piu` basso e piu` com-
petitivo che potrebbe rendere un’architettura di rete di tipo PetaWeb interessante per il
mercato; laddove gli apparati di trasporto e di commutazione sono facilmente integrabili
tramite aggiornamenti successivi, l’adozione di una topologia quasi-regolare e` molto con-
sigliabile. Un possibile ambito di ricerca potrebbe avere come oggetto lo sviluppo di una
metodologia di aggiornamento col vincolo che alcun nuovo equipaggamento possa essere
installato; in tal modo un operatore di rete potrebbe preferire l’installazione di una rete
PetaWeb a topologia quasi-regolare aggiornabile con questo strumento finche` non vengono
aggiunto dei nuovi nodi.
Un possibile ulteriore lavoro sull’argomento potrebbe essere l’introduzione di classi di
servizio con diversi livelli di affidabilita`, in base al grado di protezione offerto, e di qualita`,
in base al ritardo di propagazione subito. Un altro successivo studio potrebbe riguardare
l’offerta di cammini ottici dinamici, di traffico on-demand, con connessioni di durata lim-
itata su una rete PetaWeb gia` ottimizzata; cio` puo` avvenire sfruttando la capacita` di
trasporto in essa inutilizzata, come passo intermedio verso il progetto di reti ottiche a
commutazione automatica (ASON) ora oggetto di studi e standardizzazione.
XV
Abstract
Because of its tremendous potential, the optical networking is well admitted as a good
candidate for the next generation high-capacity communication networks. The attraction
of optical technologies grows with the development of the wavelength division multiplexing
and agile photonic switching. Photonic switching is advantageous because it significantly
reduces power consumption and facilitates switching analogue signals. On the other hand,
the heterogeneity of networks such as the Internet, their versatility and also their increasing
need in networking optical resources, raise multiple optimisation challenges. The problems
are usually difficult to solve and concern the setting up and the engineering of network
equipments.
This thesis presents the work related to the design and optimisation of a novel high
capacity network structure. Such a structure, called the PetaWeb, has a total capacity
of several petabits per second (1015 bit/s). It is composed of an optical agile core that
produces high capacity connections between the edge nodes of a network. The PetaWeb
is based on an innovative composite-star structure that presents many advantages. In this
work we assume the use of the TDM (Time Division Multiplexing) in addition to WDM
(Wavelength Division Multiplexing).
The thesis aims at proposing methods for the design of a PetaWeb network structure
with static traffic and under many conditions. Firstly, we deal with the network model for
this peculiar time-slotted wavelength-routed network: switching cores’ structure, switching
schemes and routing strategy. The network serves the connection requests through light-
paths of different classes. Routing issues and constraints are analysed in order to interface
the PetaWeb to the access network. Given a virtual topology defined by a set of edge nodes
and their connection requests, the design problem is to find how to switch lightpaths and
where to place switching equipment to plan the network of minimum cost.
We call the design problem RFWTAA (Route, Fiber, Wavelength, Time-slot Allocation
and Assignment) and we divide it into two subproblems: the resources allocation problem,
shortly called RFA (Route and Fiber Allocation), and the resources assignment problem,
XVII
called WTA (Wavelength and Time-slot Assignment). The first determines the lightpaths
routes and the equipments locations; the second proceeds, with linear complexity, to the
assignment of wavelengths and time-slots.
From the regular composite-star topology given by the RFA solution, a quasi-regular topol-
ogy is extracted in the beginning of the WTA part of the problem; such quasi-regular topol-
ogy improves the utilization of the available capacity and the total network cost. Passing
through further network upgrades a quasi-regular topology will be modified towards a reg-
ular topology.
We explain similarities and differences between the RFA problem and the classical lo-
cation problem. Then we propose two mathematical formulations for the RFA problem
resolution: an Integer Linear Programming (ILP) formulation is based on the minimization
of a cost function subjected to many constraints; a second formulation considers a dedi-
cated path protection strategy in the network model. The ILP formulations give rise to
an extremely hard combinatorial problem; thus, we introduce simplifications to make the
problem tractable.
The solution of the RFWTAA problem contains the network components geographical
location and the lightpaths’ switching schemes. In terms of computational complexity, the
resolution time is high for the both mathematical formulations. It is even harder to find
an optimal solution when edge nodes are numerous and the traffic matrix is dense. To be
able to solve the problem for large instances, we propose the use of an original repeated
matching heuristic satisfying the network model constraints. Its results show that the
solution is almost the same than the one found by integer linear programming, but with a
resolution time significantly reduced.
Then we tackle the upgrade problem. We furnish an ILP formulation for the upgrade of
an existing PetaWeb network having a regular topology or a quasi-regular topology. You
can so appreciate how the idle capacity left available by previous optimisations can be
exploited augmenting the network utilization.
Finally we compare the results with the case in which the TDM is not used; the benefits
in the network cost are important, between the 10% and the 15%.
XVIII