|
|
|
Vi sono almeno 4 motivi per i quali un protocollo link state e' preferibile rispetto ad un protocollo distance vector. In dettaglio :
Analizziamo in dettaglio queste ragioni : Come menzionato in precedenza, i protocolli distance vector eseguono un calcolo distribuito utilizzando l'algoritmo di Bellman-Ford. Il numero di step richiesti con quest' algoritmo e' proporzionale al numero dei nodi nella rete; nel caso peggiore, questo e' uguale al numero di hops del percorso piu' lungo. Viceversa, l'algoritmo link state prevede due fasi :
Qualcuno potrebbe obiettare che la procedura di "triggered updates" non richiede, in pratica, molti piu' messaggi di quanti ne richieda l'algoritmo di flooding, ma questo e' vero solo nel caso favorevole di un singolo aggiornamento sufficiente a correggere la tabella di routing. RIP, ad esempio, richiede che gli aggiornamenti vengano spaziati da un intervallo di tempo variabile da 1 a 5 secondi e questo tempo e' molto piu' grande di quello richiesto ad un router per calcolare l'intera tabella di routing di una rete di 200 nodi. Ancora piu' importanza riveste la proprieta' "loopless". Immediatamente dopo il flooding ed il calcolo, tutte le route della rete sono equilibrate, nessun loop intermedio, nessun conteggio all'infinito e considerando solo le distruttive conseguenze dei loop intermedi, e' sufficiente questa singola proprieta' a far preferire OSPF a RIP.
Abbiamo gia' visto come i protocolli distance vector non supportino metriche molto raffinate. Se il costo dei link e' molto variabile o se il costo dei link migliori diventa di ordini di grandezza di minor valore rispetto a quelli dei link piu' lenti, c'e' il rischio di attendere tempi lunghi, quando il conteggio all'infinito diventa necessario. Questo rischio non esiste con i protocolli link state. Poiche' il calcolo del percorso piu' breve viene eseguito conoscendo completamente la tipologia, si possono utilizzare arbitrariamente precise metriche senza rallentare la convergenza. Infatti, la precisione del calcolo rende possibile il supporto di numerose metriche in parallelo. Definire una "best route" e' arbitrario, ma tutti concorderanno su 4 punti :
In realta', tipologie differenti hanno differenti caratteristiche; un tipico esempio e' il link satellitare che e' generalmente meno costoso di un link terrestre a pari velocita', ma piu' lento. Trattare metriche differenti con un algoritmo link state richiede :
Consideriamo ad esempio che, per ciascun link si documentino la sua velocita', il suo ritardo, il costo per bit ed un indicatore di affidabilita'. Quindi e' possibile calcolare questi valori per qualsiasi dato percorso. La velocita' sara' quella del link piu' limitato nel percorso; il ritardo ed il costo saranno la somma dei ritardi e dei costi dei link; l'affidabilita' sara' una combinazione delle affidabilita' dei link.
Si verifica spesso, su reti complesse, che esistano numerose routes "quasi equivalenti" verso una destinazione. Riprendiamo la rete nell'esempio precedente:
Possiamo osservare che i percorsi da A ad E tramite i nodi B e D hanno la stessa lunghezza e questo vale anche per i percorsi da D a B attraverso i nodi A ed E. Analizzando il protocollo RIP, la scelta del percorso era stata di tipo random, in quanto vi era una sola next-hop entry nella tabella di routing. Questa semplice decisione ha un grosso difetto: invece di utilizzare tutta la capacita' disponibile , ne usa solo la meta'. Analizzando matematicamente il problema, si puo' provare che la suddivisione del traffico su 2 percorsi differenti e' piu' efficiente, genera minori ritardi, intuibile in quanto la banda disponibile e' maggiore e riduce le variazioni dei ritardi sull'arrivo dei pacchetti. Inoltre, suddividere il traffico si dimostra un'ottima scelta anche per un inconveniente meno ovvio: se si sceglie un unico percorso e questo diventa indisponibile, tutto il traffico verra' reinstradato su un percorso alternativo, aumentando il rischio d congestione. Questo fenomeno fu osservato agli inizi di Arpanet, la cui topologia includeva 2 aree principali alle coste Est e Ovest, collegati tramite 2 percorsi diretti al Nord e al Sud del paese. Poche modifiche alla topologia potrebbero causare maggiori scambi di tratte e instabilita' della rete. Al contrario, se il traffico viene frazionato su numerosi percorsi, solo una parte di questo dovra' essere reinstradato a seguito di un guasto su un link e tutto l'insieme sara' molto piu' scorrevole. Una semplice modifica dell'algoritmo SPF permette di rilevare tutti quei percorsi di costo uguale e, in particolare, questa viene utilizzata in OSPF, la cui specifica prevede che il traffico debba essere suddiviso equamente tra tutti i percorsi a costo uguale (procedura equal cost multi-path). Suddividere il traffico tra numerosi percorsi puo' tuttavia anche avere effetti dannosi, specialmente nel caso di connessioni TCP. I vari percorsi possono anche avere metriche equivalenti, ma i pacchetti instradati su percorsi separati potranno incontrare differenti condizioni di accodamento e, di conseguenza, potranno soffrire di differenti ritardi e potrebbero arrivare non in ordine. TCP reagisce al disordine ritrasmettendo i pacchetti, con un conseguente rallentamento dell'intera performance. Il classico rimedio a questo problema e' di suddividere il traffico tra i percorsi in modo tale che una data connessione TCP sia sempre instradata su un singolo percorso. Molti routers calcoleranno un codice hash, H, dagli indirizzi sorgente e destinazione del pacchetto e dai numeri di porta e quindi suddivideranno il traffico basandosi sui valori di tali codici. Ad esempio, essi potranno inviare tutto il traffico il cui codice hash e' minore o uguale ad H1, sul primo percorso e tutto quello che e' maggiore di H1 sul secondo. Nel caso vi siano piu' di 2 percorsi, i routers possono utliizzare un set di valori, H1, H2 etc. al fine di suddividere il traffico sui vari percorsi. Gli "equal cost multi-path" sono quindi un miglioramento rispetto al routing "single path" ma non sono certo la soluzione finale al problema dell'ottimizzazione del traffico ossia a come meglio bilanciare il traffico tra i vari percorsi. Questo e' un vecchio problema, per il quale sono state proposte piu' soluzioni sin dagli anni '70. Un tipico approccio e' di aumentare l'informazione nel database di routing con l'indicazione sul carico dei vari links e quindi combinare l'indicazione nella metrica usata per calcolare i percorsi piu' brevi. L'idea e' di creare un loop all'indietro che lavori nel seguente modo :  I
routers ricevono i nuovi "link state records" che indicano il carico
dei percorsi e calcolano quelli piu' brevi.
Il problema e' che ogni loop oscilla tra 2 estremi. Se il loop e' troppo lento, non si otterra' un buon miglioramento e se, al contario, il loop e' troppo veloce, cioe' il carico viene misurato e diffuso molto rapidamente, si osserveranno delle oscillazioni dovute ai rapidi reinstradamenti da un percorso carico ad uno vuoto. Una prima soluzione a questo problema e' di tenere in conto la lunghezza ed il carico del percorso e di utilizzare solo l'indicazione del carico come un modo per suddividere il traffico tra i percorsi selezionati, cosi' che solo una parte del traffico venga reinstradata da un percorso ad un altro. La miglior soluzione richiede che un sistema centrale esamini tutti i possibili percorsi della rete; in pratica si puo' ottenere una buona approssimazione della soluzione, anche solo mantenendo alcuni dei percorsi, tipicamente da 4 a 6 tra ogni coppia sorgente - destinazione. Il problema puo' essere risolto attraverso la programmazione lineare, nel seguente modo:
Questo algoritmo puo' essere distribuito. La soluzione classica e' di assegnare un "prezzo" a ciascuno dei link. Il prezzo riflette la derivata prima della funzione di costo del link, per il traffico sottoposto. I vari nodi utilizzano il prezzo come una guida per il loro assegnamento di traffico ai differenti percorsi. La convergenza si ottiene quando il prezzo di tutti i link saturati nella rete e' uguale. In tutti i casi, l'ottimizzazione del traffico sulla rete e' ancora oggi campo di ricerca. L'implementazione di OSPF per risolvere la suddivisione del carico e' denominata "Optimized Multi Path".
Nei nostri semplici esempi, abbiamo sempre considerato problemi di routes interne ma, le connessioni Internet prevedono reti generalmente connesse attraverso uno o piu gateway esterni con una o piu' reti di transito, raggiungendo milioni di host in qualsiasi parte del mondo. Quando si ha un solo gateway verso il mondo esterno, l'approccio e' semplice: e' solo necessario prevedere una route di default verso quel gateway. Entrambi i protocolli distance vector e link state possono supportare questo. Ma, quando si deve scegliere tra molti gateway, la soluzione "route di default" non si adatta bene. Essa induce a scegliere il gateway esterno piu' vicino, anche se magari un altro ne avrebbe piu' efficientemente trasportato i dati verso la propria destinazione. L'alternativa e' quella di calcolare routes specifiche per tutte le destinazioni, o almeno per quelle piu' frequentemente utilizzate. Questo viene effettuato in modo differente dai protocolli distance vector e link state. Nel primo caso, si sommera' un'entry per destinazione, nel secondo caso si entrera' nel database che OSPF chiama "gateway link state records". Questo porta l'algoritmo di link state alle migliori prestazioni, dovute alle metriche piu' precise e alla semplicita' dei calcoli.
|
