OSPF, Open Shortest Path First, è un protocollo di routing di tipo Link State, così classificato in quanto  trasferisce le informazioni di routing a tutti i router della rete. Appartiene inoltre alla classe dei protocolli IGP (Interior Gateway Protocol), per il fatto di operare all’interno di uno stesso Autonomous System (AS).

Permette l’IP subnetting, l’aggregazione delle rotte (route summarization) e la tecnica VLSM, variable-Lenght Subnet Mask. C’è da evidenziare che l’aggregazione delle rotte non viene effettuata in maniera predefinita: la funzione deve essere abilitata manualmente dall’amministratore.

Le principali differenze tra gli algoritmi Link State, come OSPF, e quelli Distance Vector, come RIP, sono costituite dal fatto che i Link State informano tutti i router della rete sulla completa topologia e sui ritardi, richiedendo così un tempo minore per convergere ad una soluzione stabile, mentre i Distance Vector inviano l’intera tabella di routing ai soli router vicini e non conoscono l'intero percorso verso una destinazione.

I router OSPF stabiliscono e mantengono un rapporto di relazione con i vicini, tecnicamente detto adjacency (adiacenza o contiguità). Dopo l’inizializzazione o a seguito di qualche cambiamento nel routing, un router con OSPF attivo genera degli annunci, detti LSA (Link State Advertisement), contenenti informazioni topologiche sulla rete. Tramite un processo detto di flooding, gli annunci vengono scambiati con tutti i router della rete. Non appena un router riceve gli LSA, crea un Link-State Database su cui applica l'algoritmo SPF (Shortest Path First) di Dijkstra per creare un albero della topologia di rete, o più semplicemente una mappa della rete. Ogni router crea un Link-State Database e costruisce il proprio albero SPF a partire dalle stesse informazioni link-state; tuttavia ognuno genera una propria vista della topologia di rete, diversa da quella creata sugli altri router.

Inizialmente, ogni router identifica se stesso come radice dell’albero; poi, a partire da questa root, l’algoritmo identifica il percorso più breve per ogni destinazione, con il relativo costo.

Schematizzando, ciascun router con OSPF deve:

• scoprire l'indirizzo di ogni router vicino;
• misurare il costo necessario per raggiungere ciascun router vicino;
• inviare un messaggio a tutti i router diffondendo le informazioni acquisite;
• calcolare, in locale, il cammino minimo verso ogni altro router utilizzando l’algoritmo SPF sviluppato da Dijkstra.

Scoperta dei vicini

Per conoscere l'intera topologia di una rete, ogni router invia un pacchetto Hello su tutte le connessioni point-to-point disponibili e riceve come risposta, dai router direttamente connessi, il loro identificativo, detto Router ID. Il tempo che trascorre tra l'invio di due pacchetti Hello è regolato dal campo Hello Interval, di default 10" su reti Ethernet e sui link seriali punto-punto, 30" sulle reti Multiaccess come Frame Relay. Il tempo massimo in cui un router attende l'Hello Packet è regolato dal campo Dead Interval, di default 40" su reti Ethernet e sui link seriali punto-punto, 120" sulle reti Multiaccess come Frame Relay, quindi valori quadrupli rispetto all'Hello Interval. Per calcolare il costo di connessione con i router vicini, è utilizzato un pacchetto Echo con cui si misura il tempo necessario ad ottenere risposta.

Prima di raggiungere la “perfetta” conoscenza dei vicini, detta neighbor adjacency, il router passa attraverso vari cambiamenti di stato:

• Init - In questo stato il router ha ricevuto un primo Hello Packet dal vicino; restituisce quindi un pacchetto ACK contenente l'ID di quel vicino, un numero di serie e la lista dei vicini conosciuti (ciascuno con la stima di costo associata).
• 2-Way – si raggiunge lo stato 2-way quando il router vede il proprio ID all’interno del pacchetto Hello ricevuto.  A questo punto il router decide se stabilire un rapporto di relazione (adjacency) con il vicino.
• Exstart – I router stabiliscono una relazione master-slave e scelgono un numero di sequenza iniziale per formare l’adiacenza. Tra due router, quello con l’ID maggiore diventa master e fa partire lo stato di Exchange.
• Exchange – I router scambiano i pacchetti DBD (Database Descriptor), che contengono le intestazioni degli annunci link-state (LSA).  I pacchetti DBD hanno un numero di sequenza che può essere incrementato solo dal router master.
• Loading – In base alle informazioni fornite dai pacchetti DBD, i router inviano richieste link-state per avere informazioni specifiche. I vicini forniscono queste informazioni con aggiornamenti link-state (update packets).
• Full – Tutti i router hanno scambiato gli LSA ed i loro database sono sincronizzati. Lo stato di Full è quello ritenuto normale per un router OSPF. Se un router è bloccato in un altro stato, vuol dire che c’è un problema.

Lo stato di full, e quindi la neighbor adjacency tra due router, è possibile solo se si verificano tutte le condizioni seguenti:

• I router hanno ID diversi;
• l'Hello Interval è lo stesso (di default 10" su reti Ethernet e sui link seriali punto-punto, 30" sulle reti Multiaccess come Frame Relay);
• il Dead Interrval è lo stesso (tempo massimo in secondi in cui si attende l'Hello Packet, valore quadruplo rispetto all'Hello Interval)
• l'Area di appartenenza è la stessa (tipicamente Area 0);
• la rete è la stessa (ossia i router comunicano a livello IP e concordano sulla subnet mask)

Elezione dei Designated Router

Nei collegamenti punto-punto, a parte le condizioni elencate, non vi sono problemi per stabilire adiacenze, poiché per definizione sul link possono essere presenti solo due router. Al contrario, in una rete multiaccess, ovvero in un segmento di rete dove sono collegati più router, un router può raggiungere lo stato di full solo con un router designato (DR, Designated Router) o un router di backup designato (BDR, Backup Designated Router). Lo scopo di avere un router designato DR ed un router di backup BDR è quello di ridurre il numero di aggiornamenti trasmessi, il flusso di traffico non necessario ed il sovraccarico di elaborazione; i router possono accettare aggiornamenti solo dal DR. In ogni segmento di rete vi possono essere un solo DR ed un solo BDR. Tutti gli altri router assumono il ruolo di DROther (altro dal DR) e devono avere una connessione con il DR e il BDR. Quando un link non funziona, il router con tale informazione invia l’aggiornamento al DR utilizzando l’indirizzo multicast 224.0.0.6; a sua volta il DR è incaricato di distribuire il cambiamento a tutti gli altri router OSPF, sempre in multi cast, ma all’indirizzo 224.0.0.5. Oltre a ridurre il numero di aggiornamenti inviati attraverso la rete, questo processo assicura che tutti i router ricevano le stesse informazioni nello stesso momento e da una singola fonte. Il DR mantiene il suo ruolo sino ad un eventuale fallimento: se il DR fallisce, il BDR prende il suo posto, e verrà eletto un nuovo BDR. Il DR può fallire perché il processo OSPF si arresta o riparte, o perché la sua interfaccia LAN diventa “down”.

All'interno della rete, il router con l'ID più alto viene eletto DR, il secondo più alto viene eletto BDR. Il router ID non è altro che un indirizzo IP, scelto in questo modo:

• impostandolo tramite comando (router-ID command) sul router;
• se nessun valore è impostato manualmente dall’amministratore, viene utilizzato il più alto indirizzo IP configurato sulle interfacce di loopback;
• se nessuna interfaccia di loopback è configurata, viene utilizzato il più alto indirizzo IP sulle interfacce fisiche attive.

Nell’esempio qui sotto possiamo vedere quali sono i router-ID di ogni apparato e , per ogni segmento di rete, qual è il designated router (DR):

Nel caso in cui l’amministratore di rete lo desideri, può forzare l’elezione del DR e del BDR configurando la priorità di ciascun router. In maniera predefinita, i router OSPF hanno una priorità con valore 1; se la priorità viene cambiata, il router con la priorità più alta vince l’elezione indipendentemente dal router-ID. Il massimo valore di priorità è 255; un valore pari a 0 significa che il router non partecipa all’elezione.

Metrica

OSPF calcola il costo della metrica basandosi sulla larghezza di banda e la velocità di un collegamento specifico. L'equazione utilizzata per calcolare il costo di un collegamento OSPF è:

Costo = 100.000.000 / larghezza di banda del link in bps

I risultati di quest’equazione, applicata ai vari tipi di collegamento, sono mostrati in tabella:

Utilizzando questa equazione si presenta un problema con le velocità di connessione superiori a 100 Mbps, come Fast Ethernet e Gigabit Ethernet. Entrambi questi due link hanno valore di 1; per compensare questo problema (dovuto all’età del protocollo), sui router si può configurare manualmente il valore di costo dell’interfaccia.

Aree OSPF

Una rete con protocollo OSPF attivo viene inizialmente identificata come AREA 0. Nel caso di espansione della rete, possono essere create altre aree adiacenti all’area 0, con valori compresi nell'intervallo 0-4294967295. Il massimo numero di router presenti in un’area è 50.

OSPF ha una gerarchia su 2 livelli:

• Area 0, spesso chiamata backbone area, è presente al livello superiore
• Le altre aree sono al livello inferiore, dipendenti dall’area 0, a cui sono direttamente connesse.

Un gruppo di aree genera un sistema autonomo OSPF (OSPF Autonomous System). L'instradamento dei pacchetti effettuato da OSPF non è circoscritto ai router appartenenti ad una certa area, ma è da intendersi esteso a tutto l'Autonomous System.

La divisione in aree fa si che se all’interno di un’area si verifica un cambiamento nella topologia di rete, solo i router all’interno di quell’area riceveranno gli LSA ed applicheranno l’algoritmo SPF. Un router che permette il collegamento di un’area specifica all’AREA 0 è chiamato Area Border Router (ABR). Un router che permette il collegamento di un’area ad un’altra rete con protocollo di routing diverso da OSPF, ad esempio EIGRP, è chiamato Autonomous System Border Router (ASBR).