Un protocollo di routing Link State (routing basato sullo stato del collegamento), è un tipo di algoritmo in cui la topologia dell'intera rete e tutti i costi dei collegamenti sono noti.

In un protocollo link state ogni nodo della rete acquisisce informazioni sullo stato dei collegamenti adiacenti ed inoltra queste informazioni a tutti gli altri nodi della rete tramite un Pacchetto Link State trasmesso tramite un algoritmo di link state broadcast.

Quando un nodo riceve un Pacchetto Link State confronta il numero di sequenza del pacchetto con quello dell'ultimo pacchetto ricevuto da quel nodo:

• se il numero di sequenza indica che il pacchetto è più recente di quello memorizzato, il nuovo pacchetto viene memorizzato e inoltrato a tutti i nodi collegati, eccetto quello da cui è stato ricevuto;

• se il numero di sequenza è invariato il pacchetto viene scartato;

• se il numero di sequenza indica che il pacchetto ricevuto è meno recente di quello memorizzato, quest'ultimo viene trasmesso al nodo mittente.

Ogni nodo memorizza i pacchetti ricevuti e costruisce una mappa completa e aggiornata della rete: il Link State Database, ottenendo così gli stessi risultati.

Ogni nodo esegue in maniera indipendente un algoritmo, generalmente una variante dell' Algoritmo di Dijkstra, per determinare il cammino minimo per raggiungere ogni nodo della rete ponendosi come radice dell'albero dei cammini minimi.

Al termine della elaborazione per ogni nodo di destinazione abbiamo il suo predecessore lungo il cammino a costo minimo dal nodo radice.

È possibile costruire la tabella di routing di un nodo memorizzando per ciascuna destinazione il nodo successivo sul cammino a costo minimo.

Vantaggi e svantaggi

L'utilizzo di un algoritmo di routing Link State presenta diversi vantaggi:

• può gestire reti composte da un gran numero di nodi;

• converge rapidamente al cammino minimo;

• difficilmente genera cammini ciclici;

• è facile da comprendere poiché ogni nodo ha la mappa della rete;

Il principale svantaggio di un algoritmo Link State è la complessità di realizzazione, anche dovuta alla notevole capacità di memoria ed elaborazione richiesti.