PARTE I- TECNICHE DI OTTIMIZZAZIONE: ROUTING E REROUTING LSP
5.4 Ottimizzazione del routing online-dinamico
5.4.1 Uno schema generale per il routing dinamico
5.2.4.1 Meccanismi di preemption
I meccanismi di preemption costituiscono una delle maggiori peculiarità dell’explicite
routing supportato dal MPLS-Traffic Engineering: essi consento nodi porre termine alle trasmissioni che avvengono su particolari LSP, forzando nell’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.[44]
La preemption si basa sull’utilizzo di due scale di priorità comprendenti ciascuna otto livelli, dallo 0 al 7, con 0 valore di massima priorità. Ad ogni LSP viene associata una coppia di valori (s,h): s rappresenta la setup priority, cioè la priorità dell’LSP nell’acquisire risorse a scapito di altri LSP, mentre h rappresenta la holding priority, cioè l’importanza di conservare intatto l’LSP.
Il meccanismo base su cui è fondata la preemption è molto semplice: ogni richiesta di definizione di un nuovo LSP ha il potere di provocare l’abbattimento di un qualunque LSP già presente sulla rete e caratterizzato da una holding priority inferiore alla setup priority del nuovo LSP. Si ricorda che, rappresentando priorità maggiori con valori di classe minori, ciò corrisponde a chiedere che il valore di setup sia minore di quello di holding:
LSPnewpuò abbattere LSPold ⇔ sLSPnew < hLSPold
Sebbene un LSP possa essere associato ad una coppia (s,h) con s≠h viene comunque richiesto che si abbia s≥ h, cioè che la holding priority sia superiore e quindi numericamente inferiore a quella di setup. Ciò viene imposto per evitare che un LSP instaurato con successo sia abbattuto da una richiesta immediatamente successiva di uguale setup priority. All’interno di questa trattazione si assumerà comunque, senza perdita di generalità, che ogni LSP sia caratterizzato da setup e holding priority di uguale valore e si potrà quindi utilizzare un singolo parametro di priorità s per caratterizzare ogni LSP.
L’introduzione dei meccanismi di preemption ha effetti anche sulla definizione dei constraint predicate, poiché, per verificare se un link ha sufficiente banda per soddisfare una richiesta, non si dovrà considerare più la sola banda non utilizzata, ma anche quella che può eventualmente essere liberata abbattendo LSP. Si rende quindi necessaria l’introduzione di un nuovo parametropreempt , che specifica, per ogni arco eσ e∈Edel grafo, la banda totale che può essere liberata mediante preemption operata da un LSP di priorità σ . La priorità di un LSP è pari al quarto elemento della quadrupla (sk,tk,Bk,Dk,σk) che si può usare per individuare una commodity k(si ricorda che i primi due elementi s ,k tk individuano i nodi origine e destinazione dell’LSP da definire e Bkè la banda richiesta).
La relazione matematica che definisce la banda preemptable in un arco e per la classe di priorità σ è:
∑
< ∧ ∈ ∈ = σ σ σ k p e P p p e f preempt : (5.33) Se si introduce un parametro res σe indicante la banda dell’arco e complessivamenteutilizzata da LSP di priorità σ che contengono l’arco, il constraint predicate per una
∑
< ≤ + k e k e B b res σ σ σ (5.34)equivalente a verificare se la somma della banda resσe e utilizzata da LSP non abbattibili e di quella Bkrichiesta risulta inferiore o uguale alla capacità di banda dell’arco. Rispetto al constraint predicate utilizzato in uno scenario senza preeemption, ciò che cambia è che la banda utilizzata da altri LSP non è più totalmente intoccabile, ma può essere liberata abbattendo LSP di minore importanza rispetto alla corrente richiesta di instaurazione: gli LSP caratterizzati da valori di priorità maggiori e quindi meno importanti è come se non esistessero e non vengono considerati nella verifica della disponibilità di banda.
Conseguenza dell’adozione dei meccanismi di preemption è il sorgere di un nuovo problema: secondo quali criteri e modalità selezionare degli LSP da abbattere al fine di liberare banda? Il successivo paragrafo è dedicato a dare una risposta a questa domanda, mostrando come trattare il problema e risolverlo tramite una semplice ma efficace euristica.
Quando non vi è sufficiente disponibilità di risorse ed arriva ad un ingress router una richiesta per il set up di un nuovo LSP la tecnica della preemption potrebbe consentire il soddisfacimento della richiesta, assicurando che i flussi di traffico con maggiore priorità siano serviti nel modo più efficiente possibile. Se per eseguire la preemption di un LSP si considerasse solamente la sua la priorità purché la banda offerta sia maggiore o uguale a quella richiesta, si potrebbe verificare un spreco della banda. Per esempio ipotizziamo che in un ingress router arrivi una richiesta da parte di un LSP L1 con priorità 1 e banda pari a 50 Mbit/s
e che vi siano un LSP L2 con priorità 5 caratterizzato da una banda di 100Mbit/s, e un altro L3
con priorità 4 ma banda 55 Mbit/s, se scegliessimo in base alla priorità la nostra scelta sarebbe L2 con uno spreco di banda di 50 Mbit/s. Inoltre un solo LSP potrebbe non essere sufficiente a
soddisfare la richiesta di banda, in questo caso la preemption potrebbe essere applicata a più LSP. Il numero di questi LSP dovrebbe essere il minimo possibile per limitare al massimo il rerouting ed i costi di segnalazione.
Nell’ottica dell’ottimizzazione della rete che si intende realizzare, risulta particolarmente importante la scelta, non solo, di quali LSP rimpiazzare, ma anche, di dove questi LSP rimpiazzati verranno reinstradati.
La Figura 10 mostra un esempio di LSP preemption con rerouting: l’LSP BLU viene abbattuto per lasciare risorse al LSP ROSSO e viene reinstradato lungo un percorso subottimo.
Figura 10 Esempio di preemption con rerouting di LSP
Il rerouting degli LSP in seguito alla preemption risulta in definitiva applicabile alle esigenze del servizio, ed è in grado di garantire l’affidabilità, fintanto che sulla rete è presente un path sul quale è possibile instradare il LSP a banda garantita.