L’algoritmo di routing a stato di collegamento è quello attualmente più utilizzato. Internet usa un algoritmo di questo tipo chiamato OSPF (Open Shortest Path First).
Ogni router mantiene un database che descrive la topologia della rete e le distanze in base a varie metriche. Le informazioni per costruire il database vengono ottenute scambiando con tutti gli altri router della rete dei pacchetti (LSP – Link State Packets) che contengono informazioni sui router vicini.
Ogni router applica alle informazioni del database che descrivono la rete un algoritmo per la ricerca del percorso più breve verso le destinazioni; i risultati della ricerca sono usati per aggiornare la tabella di instradamento.
In pratica il router costruisce un pacchetto (LSP) con l’elenco dei vicini e la distanza da ogni vicino; il pacchetto contiene anche l’identità del mittente, un numero di sequenza, incrementato per ogni pacchetto spedito, e un tempo di vita. I pacchetti possono essere costruiti periodicamente o meglio quando si verifica un evento (un cambiamento nella rete).
Poi il router spedisce il pacchetto a tutti i router utilizzando il flooding; i router tengono traccia dell’ultimo numero di sequenza ricevuto da ogni router mittente; se arriva un pacchetto con numero di sequenza nuovo per quel mittente, il router lo memorizza nel database e lo ritrasmette in flooding; se arriva un pacchetto duplicato o vecchio lo scarta; il campo con il tempo di vita sui pacchetti viene periodicamente decrementato; quando arriva a zero il pacchetto viene scartato.
Quando un router ha ricevuto i pacchetti LSP da tutti gli altri router può costruire un grafo della rete in cui ogni nodo rappresenta un router e ogni arco una linea; lavorando sul grafo può calcolare il cammino minimo per ogni destinazione e creare la tabella di routing.
Il cammino minimo può essere calcolato in base al numero di salti, ma anche alla distanza in chilometri o alla velocità della linea; le informazioni relative a queste metriche sono associate agli archi del grafo (grafo pesato); la velocità di ogni linea può essere calcolata dinamicamente in base al ritardo medio di un pacchetto di test spedito periodicamente.
L’algoritmo più noto per la ricerca del cammino minimo (cioè di peso minimo) in un grafo orientato e pesato è l’algoritmo di Dijkstra.
