Open Shortest Path First (OSPF) è uno dei più popolari algoritmi di routing appartenenti alla famiglia
degli Interior Gateway Protocol (IGP), ovvero un algoritmo ideato per il routing interno all'Autonomous System (AS).
OSPF è link state, il che significa che ogni router della rete scambia informazioni di routing con tutti gli altri per permette a ciascun router di costruire l'intera topologia di rete, per poi eseguire l'algoritmo di Dijkstra e calcolare il percorso con il costo minore per raggiungere la destinazione.
In particolare ogni router distribuisce informazioni riguardo al suo stato locale (ad esempio interfacce utilizzabili, costo di ogni interfaccia e chi sono i propri vicini)
agli altri router usando i Link State Advertisement (LSA), cioè informazioni contenute nei messaggi Link State Update.
Ogni router riceve questi messaggi e costruisce un database che descrive tutta la topologia dell'AS.
Una volta costruito il database, ogni router calcola la propria tabella di routing eseguendo l'algoritmo di Dijkstra che calcola i cammini a costo minimo. Quindi, il database contiene: le destinazioni
propagate dagli altri router, un next hop e un interfaccia di uscita per ogni destinazione.
Quando la topologia cambia a causa di guasti o per l'aggiunta di nuovi router, vengono propagati nuovi LSA; ogni router ricalcola la topologia di rete e poi ricalcola i cammini minimi.
A differenza di altri algoritmi di routing, OSPF non utilizza protocolli di trasporto come TCP o UDP, ma utilizza direttamente i datagrammi IP adottando il "protocollo numero 89". Un altra caratteristica
fondamentale di OSPF è la divisione in zone, cioè suddividere la rete in più sottoreti indipendenti tra loro.
Ogni pacchetto OSPF ha un header formato da campi che permettono l'autenticazione, il controllo degli errori, la gestione delle zone, la versione del protocollo e un campo "tipo" che indica uno dei
seguenti possibili messaggi:
- Hello: Questo tipo di messaggio permette a ogni router di scoprire i router adiacenti, cioè i router vicini. Inoltre, permette lo scambio di parametri fondamentali riguardo l'uso di OSPF nell'AS. Ogni router invia i messaggi hello ai propri vicini a intervalli regolari; se un router non riceve gli hello da un vicino per un certo periodo di tempo, assume che il vicino sia offline.
- Database Description: Questi messaggi contengono la descrizione della topologia dell'AS e permettono la sincronizzazione del Link State Database (LSDB).
- Link State Request: Questi messaggi permettono di richiedere dei records specifici o una porzione dell'LSDB di un router vicino.
- Link State Update: Messaggi di questo tipo contengono informazioni riguardo lo stato dei link salvati nel LSDB. Possono essere mandati in risposta a un messaggio Link State Request oppure periodicamente per aggiornare lo stato del LSDB.
- Link State Acknowledgement: Questi messaggi servono a comunicare la corretta ricezione dei messaggi Link State Update.