Algoritmi di instradamento: Link State Packet.
L'algoritmo link state packet assume che ogni router disponga della mappa completa della rete su cui calcolare gli instradamenti ottimali utilizzando l'algoritmo di Dijkstra o Shortest Path First (SPF). La mappa della rete non è scritta nei router dal sistema di gestione (sarebbe impraticabile per reti grandi), ma è costruita direttamente dai router tramite l'utilizzo di Link State Packet (LSP).
Ogni router, tramite protocolli di neighbor greetings, apprende quali nodi sono a lui adiacenti e lo comunica agli altri router inviando un LSP che descrive tali adiacenze. La figura riporta un esempio di rete e del relativo LSP inviato dal router R1. Si noti che il LSP non contiene una entry per il router R4 in quanto non adiacente a R1.
 | |
| Adiacente | Costo |
| A | 4 |
| B | 4 |
| C | 4 |
| r1 | 0 |
| R2 | 3 |
| R3 | 5 |
LSP inviato dal router R1 |
|
I Link State Packet sono trasmessi in selective flooding a tutti i router della rete, secondo una modalità dettagliata nel seguito. Ogni router contiene un LSP database in cui memorizza il LSP più recente generato da ogni router.
Il LSP database è una rappresentazione del grafo della rete data come matrice delle adiacenze. Si osservi che per definizione il LSP database deve essere esattamente lo stesso su tutti i router della rete. La figura seguente riporta un ipotetico grafo di rete, i cui vertici sono i nodi della rete (Sistemi Terminali o router) e i cui archi sono le linee con i costi associati, e il relativo LSP database.
Il LSP database, rappresentando la mappa della rete con i costi associati, è l'informazione necessaria e sufficiente affinchè un router possa calcolare le sue tabelle di instradamento. Si noti la differenza con il distance vector: in quel caso i router cooperano direttamente per calcolare le tabelle di instradamento, qui i router cooperano per mantenere aggiornata la mappa della rete, poi ogni router calcola la propria tabella di instradamento in modo autonomo.
Il calcolo delle tabelle equivale al calcolo dello spanning tree di tipo Shortest Path First e si effettua con l'algoritmo di Dijkstra.
| Grafo della rete | Link State Packet data Base | |||
 |
Dest | Adiacenze | ||
| A | B - 2 | |||
| B | A - 2 | D - 3 | E - 2 | |
| C | D - 1 | |||
| D | B - 3 | C - 1 | G - 1 | |
| E | B - 2 | F - 5 | G - 2 | |
| F | E - 5 | H - 4 | ||
| G | D - 1 | E - 2 | H - 1 | |
| H | F - 4 | G - 1 | ||
Ogni nodo ha a disposizione il grafo pesato della rete ed assegna a tutti gli altri nodi un'etichetta che rappresenta il costo massimo per la raggiungibilità del nodo in esame; l'algoritmo di calcolo modifica tali etichette cercando di minimizzarle e di renderle permanenti.
Le strutture dati coinvolte sono:
l'insieme V dei vertici del grafo (i nodi della rete);
il costo C [i, j ] della connessione diretta da i a j (assunto infinito se tale connessione non esiste);
il costo D[i] del cammino dal vertice 1 (assunto come radice dell'albero degli instradamenti, è cioè il nodo che sta effettuando il calcolo della tabella) al vertice i.
L'algoritmo inizializza D[i]=C[1, i] e poi iterativamente cerca di minimizzare D[i], mantenendo un insieme S in cui memorizza quali vertici hanno già un valore definitivo (non ulteriormente riducibile).
Il nodo B, dopo aver applicato l'algoritmo di Dijkstra al grafo della rete, ottiene il seguente albero:
| Albero visto da B | Tabella di instradamento di B | |
 |
Dest. | Next hop |
| A | A | |
| C | D | |
| D | D | |
| E | E | |
| F | E | |
| G | E | |
| H | E | |
Il nodo F, dopo aver applicato l'algoritmo di Dijkstra al grafo della rete, ottiene il seguente albero:
| Albero visto da F | Tabella di instradamento di B | |
 |
Dest. | Next hop |
| A | E | |
| B | E | |
| C | H | |
| D | H | |
| E | E | |
| G | H | |
| H | H | |
Architettura di un router LSP
L’unità di ricezione di un router può ricevere 3 tipi di pacchetti:
un pacchetto dati in transito verso altre destinazioni; l’unità di inoltro consulta il forwarding database usando come chiave l'indirizzo di destinazione e determina il nuovo instradamento, cioè su quale linea ritrasmettere il pacchetto;
un pacchetto dati destinato al router; (pacchetto di gestione o management) viene passato ai protocolli di livello superiore;
un LSP o un pacchetto di neighbor greetings; il router verifica se si tratta di un nuovo nodo adiacente o di un nodo già noto. Nel secondo caso non fa nulla, nel primo caso genera un LSP per informare dell'esistenza del nuovo nodo tutti gli alrti router, in modo che il nuovo nodo diventi raggiungibile da qualsiasi punto della rete.
Un Link State Packet contiene, oltre alle informazioni di adiacenza già descritte, anche un checksum, un lifetime e un numero di sequenza che serve per distinguere, da parte di un router che riceve più LSP, quelli generati dallo stesso router.
Un router che riceve un LSP lo ritrasmette in flooding solo se esso ha modificato il LSP database del router stesso (selective flooding).
All'atto del ricevimento di un LSP un router compie le seguenti azioni:
Se non ha mai ricevuto un LSP da quel mittente o se il numero di sequenza dell’LSP è maggiore di quello dell’LSP proveniente dalla stessa sorgente e memorizzato nell’LSP database, allora memorizza il pacchetto nell’LSP database e lo ritrasmette in flooding su tutte le linee eccetto quella da cui l'ha ricevuto;
Se l’LSP ricevuto ha lo stesso numero di sequenza di quello posseduto, allora non occorre fare nulla poichè lo stesso pacchetto era già stato precedentemente trasmesso in flooding;
Se l’LSP è più vecchio di quello posseduto, cioè è obsoleto, allora il router ricevente trasmette l’LSP aggiornato al router mittente.
Questo meccanismo serve a fare in modo che gli LSP database di tutti i router si mantengano perfettamente allineati e coerenti, condizione indispensabile per un corretto instradamento.