PARTE I- TECNICHE DI OTTIMIZZAZIONE: ROUTING E REROUTING LSP
4.2 Stato dell’arte
La definizione dei percorsi associati agli LSP, e in generale il problema del routing, è un elemento molto importante soprattutto in relazione all’utilizzazione delle risorse di rete e la distribuzione del carico sulla rete. I protocolli di routing usati tradizionalmente nell’architettura IP, come il Minimum Hop Algorithm o l’Open Shortest Path First (OSPF) [33], sono conectionless e non permettono il bilanciamento del carico.
MPLS supera i limiti dell’architettura tradizionale supportando un nuovo tipo di routing, detto Constraint-based Routing (CBR), in cui l’instradamento del traffico è fatto lungo percorsi a costo minimo, rispettando contemporaneamente determinati vincoli (constraint) sullo sfruttamento delle risorse di rete. Un esempio di vincolo potrebbe essere quello di trovare un percorso con una certa minima capacità disponibile in ogni link, oppure evitare o includere un determinato link nel percorso. Soltanto un nodo di ingresso può determinare un percorso secondo il CBR, poiché i nodi interni non sono a conoscenza dei vincoli da rispettare. Siamo quindi in presenza di un meccanismo di explicit routing (o source routing).
Il protocollo più semplice ispirato al routing basato su vincoli è il Constraint Shortest Path First (CSPF) [34]che risolve i problemi relativi al bilanciamento del carico includendo un costo che tiene conto della corrente utilizzazione delle capacità dei link, ma come l’OSPF non possiede sufficienti elementi per supportare il TE in condizioni di traffico pesante [35]. Questa tecnica deve spesso essere supportata da metodologie di admission contol per migliorare le prestazioni.
Uno dei primi algoritmi di explicit routing più evoluti in ambito MPLS è il Minimum Interference Routing Algorithm (MIRA) [36]che usando la conoscenza della coppia ingress- egress cerca di prevenire i bottleneck e ridurre il numero di richieste degli LSP rifiutate, selezionando percorsi che massimizzano la minima capacità disponibile tra la coppia di ingress-egress. Questa tecnica risulta, però, molto onerosa computazionalmente, gli autori della [37] ne hanno presentato una variante più performante chiamata Least Interference Optimization Algorithm (LIOA) che ottimizza il routing cercando di minimizzare l’interferenza misurata, in questo caso, come numero di flussi che attraversa quel link. L’algoritmo associa a ogni link una funzione costo che tiene conto del numero di flussi trasportati sul link e della differenza tra il massimo della banda riservabile è il totale della banda riservata dagli LSP attivi su quel link.
Un altro lavoro basato sul concetto di minima interferenza e computazionalmente meno pesante del MIRA è stato presentato nel [38]. L’algoritmo proposto consta di due fasi, nella prima, il preprocessamento, si sfruttano le informazioni del traffic profile per risolvere un multicommodity flow problem (MCFP) e preallocare la banda sui link relativamente a
instradata usando un shortest path algorithm. Un altro algoritmo che fa uso del MCFP è proposto nel [39], dove si cerca di soddisfare una nuova richiesta per la quale non si hanno risorse libere sufficienti, reinstradando un LSP instaurato precedentemente. È un algoritmo abbastanza semplice che non produce una riottimizzazione globale della configurazione degli LSP sulla rete, ma si limita a ridefinire il path per due LSP, quello della nuova richiesta e uno tra quelli precedentemente instradati, senza fare nessuna distinzione tra gli LSP, che potrebbero avere priorità differenti.
Secondo il [28] si può individuare una funzione di costo che tiene conto dell’evoluzione di un sistema che si trova in uno stato s (caratterizzato da un certo numero di LSP definiti e una certa capacità disponibile), che incorre in un certo evento e (es. richiesta di banda ) il quale comporta una decisione da prendere a (setup o ridimensione dell’LSP che provoca una variazione della capacità del sistema, o nessuna azione) tale funzione è data dalla somma di tre contributi:
- Wsign(S,a) costo di segnalazione di setup o di ridimensionamento degli LSP, per
aggiornare i router;
- Wb(S,a) costo dovuto alla banda;
- Wsw(S,a) costo dovuto allo switching del traffico;
La funzione è: W(S,a)= Wsign(S,a)+ Wb(S,a)+ Wsw(S,a)
in tale funzione Wsign(S,a) dipende linearmente dal numero di salti del percorso fisico su cui
l’LSP è reinstradato, inoltre, avrà una componente costante aggiuntiva dovuta alla notifica della variazione della capacità disponibile nella linea. Questo approccio avvalora ulteriormente la scelta dei parametri che stiamo considerando nel nostro metodo di ottimizzazione.
Come è stato evidenziato precedentemente nell’architettura DS-TE si può far uso della preemption. I meccanismi di preemption costituiscono una delle maggiori peculiarità dell’explicite routing supportato dal MPLS-Traffic Engineering, essi consento ai nodi di porre termine alle trasmissioni che avvengono su particolari LSP, forzandone l’abbattimento. La conseguenza è che viene liberata banda preziosa utilizzabile per instaurare un nuovo LSP associato ad una richiesta che altrimenti non sarebbe potuta essere soddisfatta per insufficiente disponibilità di banda.
L’impiego della preemption genera delle interruzioni di servizio se non si provvede in qualche modo al rerouting degli LSP preempted che, a sua volta, produce un aumento del traffico di segnalazione, inoltre, si potrebbero verificare degli sprechi di banda se la scelta degli LSP da abbattere non è oculata. Per ottimizzare la scelta di quali LSP abbattere e ridurre il rerouting, un interessantissimo lavoro è stato presentato in [27]. Gli autori propongono un algoritmo che ottimizza, su un determinato link, la scelta degli LSP da abbattere sulla base di tre criteri: minimizzazione della priorità degli LSP abbattuti, minimizzazione del numero di questi LSP e minimizzare la banda preempted. Nella seconda parte viene proposto un'altra tecnica con la quale cerca di liberare risorse riducendo il rate degli LSP aventi priorità più bassa. La riduzione del rate non comporta dei costi di segnalazioni aggiuntivi in quanto
potrebbe essere usato lo stesso protocollo di segnalazione dei refresh degli LSP, in ogni caso l’onere di tale segnalazione sarebbe notevolmente inferiore rispetto a quello necessario all’abbattimento, il reinstradamento e il set up per un nuovo LSP. La determinazione del percorso associato agli LSP non è affrontato ma demandato ai protocolli tradizionali, così come non si affronta il problema del reistradamento degli LSP preempted.
Questa ultima tecnica fa parte delle tecniche basate su un approccio decentralizzato in cui ogni nodo del percorso è responsabile di applicare l’algoritmo di preemption sugli LSP.
L’approccio opposto è quello centralizzato in cui una entità manager che possiede tutte le informazione relative agli LSP attivi e lo stato di tutti i link della rete decide quale o quali LSP abbattere per soddisfare la nuova richiesta.
Entrambi gli approcci possiedono i loro vantaggi e svantaggi. L’approccio centralizzato offre un ottimizzazione globale a scapito, però, di un onere computazionale molto maggiore dovuto soprattutto all’aggiornamento delle informazioni sugli LSP e sui link, infatti, risulta più adatto alla gestione di una situazione statica della rete dove non vi sono repentini cambiamenti. In una rete dinamica, in cui gli LSP vengono stabiliti e demoliti molto frequentemente, l’approccio decentralizzato, nonostante non fornisca soluzioni ottime, offre maggiori benefici e risulta più semplice da implementare.
Il presente lavoro parte dall’analisi dello stato dell’arte e dalle peculiarità dell’architettura di rete per arrivare alla definizione di un framework completo in grado di ottimizzare non solo il processo di routing di un nuovo LSP su una rete carica ma anche il processo di preemption e di rerouting degli LSP abbattuti.