Sartomiki.net

Principio di funzionamento
Il protocollo "Link State" si basa sul principio opposto rispetto al "distance vector". Il prerequisito affinchè il link state funzioni è che i router nel momento della connessione alla rete siano in grado di conoscere a quali router sono collegati. Una volta che un router si accorge di essere collegato con i suoi vicini, esso manda in broadcast un pacchetto con all'interno la lista dei router a cui esso è collegato direttamente e il relativo costo. Essendo un pacchetto in broadcast, esso viene mandato anche ai router non collegati direttamente. Questo algoritmo crea una mappa ad archi pesati della rete in tutti i nodi (al contrario del distance vector, in cui nessun router aveva la mappa). A questo punto è necessario un algoritmo per trovare un next hop per i pacchetti.
Nel distance vector ogni nodo dice tutto ciò che sa della rete ai suoi vicini, nel Link State ogni nodo dice ciò che sa dei suoi vicini a tutti.

Componenti dell'algoritmo di Link State
Perchè questo algoritmo funzioni sono necessari molti aggiustamenti e molti componenti accessori:
-Hello Protocol, che permetta ai vicini di sapere quali router siano collegati direttamente.Il pacchetto di hello deve avere una periodicità elevata.
-Link State Packet, un pacchetto che permette di trasmettere a tutti la mappa dei vicini. Rispetto ai pacchetti distance vector, la propagazione è molto più veloce, in quanto i router non devono rielaborare la mappa. Ne consegue che la convergenza dell'algoritmo è più veloce.
-Link State Database, una memoria in cui sono immagazzinati tutti i nodi e gli archi.
-Flooding, un componente che permette di fare un broadcast controllato su tutta la rete. L'algoritmo usato è il Selective Flooding classico ed è usato solo per i pacchetti Link State.
-Dijkstra, algoritmo che trova il percorso migliore per ogni destinazione. In più garantisce una buona distribuzione del traffico. La complessità è data da L*lg(L) con L=numero di link. Per Bellman-Ford (algoritmo del distance vector) ha una complessità N*L con N=numero di nodi e circa uguale al numero di L. Ne segue che la complessità di Dijkstra è solitamente inferiore.
-Bringing up Adjacencies, componente che permette il riallineamento delle adiacenze. Esso è fondamentale nel momento in cui si connettono due reti separate: in questo caso, infatti, non solo è necessario che i due router che fanno da ponte si riconoscano, ma è necessario che tutti i router delle due reti mandino i link state a tutti i router della nuova rete più grande. Genericamente questo si realizza mediante un algoritmo di riallineamento: quando si riceve un pacchetto di hello da un router che non si conosceva in precedenza significa che si ha una nuova adiacenza (si realizza uno scambio dati punto-punto con quel router). A questo punto si chiede all'altro router quali sono i link state della rete ad esso collegati e si mandano in broadcast a tutta la rete di partenza. Un tipo di ottimizzazione si può avere richiedendo solo i link state che non si hanno.

Generazione dei Link State
I link state vengono generati solo quando il router rileva una variazione nella topologia locale. Un variazione si ha quando si riconosce un nuovo vicini, cambia un costo di un vicino o si perde la connettività. Nella realtà, però, si ha una generazione periodica dei link state in modo da garantire una certa affidabilità

Reti reali e Link State.
Il problema principale del Link State è l'implementazione su rete reale, che non risulta molto semplice. Un altro problema da affrontare è la complessità crescente con il crescere del numero di adiacenze. Infatti Dijkstra risulta più lento, la fase di riallineamento complessa e il numero di pacchetti link state esplode. Un "trucco" utilizzato è quello di separare i link di host e i link di router, in quanto gli host non contribuiscono al routing. Per questo motivo si associa agli host un unico nodo (net). Il problema non è del tutto risolto, ad esempio quando si hanno tanti collegamenti tra router (caso frequente nelle reti broadcast ATM virtuali). Per risolvere questo secondo problema si usa lo pseudo nodo (o designed router), nel senso che è eletto un master della LAN. In questo modo tutti i router della LAN hanno un'adiacenza con lo pseudo-nodo e nessuna relazione con tutti gli altri router della rete. In questo modo si trasforma una rete a topologia completa in una a stella. Questa topologia rimane a livello virtuale (nel senso che poi in realtà i pacchetti dati faranno il percorso diretto, la topologia a stella è usata solo dai pacchetti di routing), Questo metodo di per sè è poco affidabile, ma per renderlo più sicuro si costruisce parallelamente anche un back-up, in modo da non avere problemi nel caso in cui lo pseudo-nodo si rompa.

Vantaggi del Link State
Il Link State:
-ha una convergenza rapida, in quanto i pacchetti si propagano molto più velocemente.
-tendenzialmente non genera loop, e se si creano sono facilmente identificabili.
-è semplice fare il debug, in quanto tutti i nodi hanno la stessa mappa.
-è molto scalabile rispetto al distance vector, anche se è meglio non avere domini maggiori di 200 unità.

Convergenza per distance vector e link state
L'algoritmo link state permette di avere una convergenza più rapida rispetto al distance vector, in quanto le informazioni si propagano più velocemente.
Il distance vector, infatti, presenta due fonti di ritardo:
-quella dovuta al tempo necessario a propagare il pacchetto di distance vector.
-quella dovuta all'elaborazione del nuovo distance vector.
Nell'algoritmo link state questo seconda fonte di ritardo non è presente, in quanto, una volta che un router ha letto un pacchetto in uscita, esso può essere direttamente inoltrato senza che esso necessiti di alcun tipo di elaborazione.
La maggior velocità di convergenza del distance vector si può anche rintracciare nel fatto che per questo algoritmo la fase di conoscenza dei vicini e quella di annuncio della propria presenza ai vicini sono separate. Infatti è presente, ad esempio, un pacchetto di hello. Tra l'altro l'hello packet è molto piccolo e quindi si può inviare ad intervalli regolari molto piccoli e questo consente di rilevare molto prima errori di connessione. Il distance vector non ha tutti questi vantaggi, infatti, ad esempio in RIP, l'intervallo di advertisement è di 30s, mentre quello di time out di 180s. Questi tempi lunghi di aggiornamento sono dovuti al fatto che i distance vector sono dei pacchetti "pesanti", che, se aumentati, andrebbero a togliere troppa banda ai dati.
Un altro vantaggio dell'algoritmo di link state è l'estrema facilità di debug, in quanto dal dump ottenuto da un qualunque router della rete, si riesce a capire quale sarà il percorso di ogni pacchetto su tutta la rete.
Il link state è quindi utilizzato in reti molto grosse, che non variano molto nel tempo, in quanto ogni volta che ci sono variazioni si entra in transitori. Ci sono comunque dei limiti fisici a delle reti così organizzate, in quanto troppi pacchetti di routing su una stessa rete finirebbero per congestionarla. Il massimo numero di router per una rete link state è 200.