Protocolli e architetture di instradamento/Open Shortest Path First

L'Open Shortest Path First (OSPF) è un protocollo di instradamento intra-dominio basato sull'algoritmo Link State (LS). Le prime due versioni sono utilizzate con IPv4, mentre la versione 3 è pensata per IPv6.

Il principale vantaggio di OSPF rispetto agli altri protocolli di instradamento intra-dominio è la scalabilità (fino a qualche centinaio di router):

• algoritmo LS: la conoscenza della topologia della rete permette una maggiore stabilità rispetto ai protocolli basati sull'algoritmo Distance Vector;
• instradamento gerarchico: OSPF suggerisce di non avere più di 200 router in una singola area:
  • le informazioni di instradamento sulle altre aree possono essere sommarizzate;
  • i cambiamenti delle rotte in un'area non perturbano le altre aree.

Aree

Esempio di rete OSPF.

OSPF definisce la propria terminologia, che non è sempre allineata a quella degli altri protocolli:

Autonomous System (AS)

un dominio sotto il controllo di una singola entità dal punto di vista amministrativo (ad es. GARR)

Autonomous System OSPF

un dominio sotto il controllo di una singola entità dal punto di vista tecnico (cioè di configurazione degli apparati), e gestito da una singola istanza di protocollo OSPF

Autonomous System boundary router (ASBR)

un router di frontiera posto tra l'AS OSPF (tipicamente l'area 0) e un dominio di instradamento esterno (EGP, oppure IGP se l'AS OSPF convive all'interno dell'AS stesso insieme ad altri domini di instradamento con protocolli IGP anche differenti)

area edge

uno dei sotto-domini gerarchici in cui è suddiviso un AS OSPF, composto da una rete fisicamente contigua: ogni router interno può comunicare con qualsiasi altro router nella stessa area senza dover uscire dall'area stessa

area 0

l'area di backbone, non necessariamente fisicamente contigua ( #Aree partizionate), attraverso la quale deve passare tutto il traffico tra un'area edge e l'altra o tra un'area edge e l'esterno dell'AS OSPF:

• no collo di bottiglia: i link non devono essere sottodimensionati
• robusta: non deve diventare un'area partizionata

area border router (ABR)

un router di frontiera posto tra l'area 0 e un'area edge

Vista della rete dall'area 1.

Ogni router conosce perfettamente la topologia dell'area a cui appartiene, ma la topologia precisa delle altre aree non è nota: il router può conoscere la lista delle destinazioni raggiungibili al di fuori della sua area, che possono venire sommarizzate o sostituite da una rotta di default.

Il database di un router interno contiene tre tipi di record:

• Link State: sono generati dagli altri router interni all'area e contengono le rotte interne all'area, incluse le informazioni sulla topologia, che non vengono mai sommarizzate.
  Un ABR conosce i Link State di entrambe le aree che connette: ha più database, uno per ogni area, che danno origine naturalmente a una singola tabella di instradamento;
• Summary/External Record: contengono le rotte esterne all'area, escluse le informazioni sulla topologia (solo indirizzo di rete + netmask), che possono essere sommarizzate:
  • Summary Record: sono generati dall'ABR e contengono le rotte esterne in altre aree dello stesso AS OSPF (compresa l'area 0);
  • External Record: sono generati dall'ASBR e contengono le rotte esterne al di fuori dell'AS OSPF.

I router nell'area 0 sono solitamente configurati al fine di aggregare gli indirizzi di rete, così da propagare i riassunti delle reti da un'area all'altra. Tuttavia l'aggregazione deve essere specificata manualmente dall'operatore, al fine di non avere problemi con la sommarizzazione di rete.

Aree stub

Un'area edge normale, oltre a conoscere i dettagli sulla topologia di tutte le rotte interne all'area stessa, importa tutte le rotte esterne dall'area 0 senza alcuna ulteriore aggregazione.

Un'area è stub quando alcune rotte esterne sono sostituite da una singola rotta di default per ridurre le informazioni di instradamento importate dall'esterno:

• area stub: mantiene i Summary Record, ma rimuove gli External Record;
• area totally stubby: rimuove sia i Summary Record sia gli External Record, lasciando solo i Link State e la singola rotta di default verso l'uscita;
• area not-so-stubby: è simile all'area stub, ma può iniettare in altre aree le rotte esterne all'AS OSPF (senza importarle nell'area).

Le aree stub sono attivate su esplicita configurazione del gestore della rete:

• area stub: area xx stub
• area totally stubby: area xx stub no summary
• area not-so-stubby: area xx nssa

Sebbene OSPF non impedisca di avere un'area stub con più di un ABR, ha più senso configurare un'area stub quando è connessa all'area 0 tramite un solo ABR: non è necessario propagare le rotte esterne perché c'è un solo percorso che connette l'area al resto della rete, mentre le rotte esterne sono utili solo se esiste più di un router egress.

Virtual Link

Il Virtual Link è una sorta di "tunnel" tra due router, di cui almeno uno appartenente all'area 0, che logicamente appartiene all'area 0, ma fisicamente è composto da una sequenza di link all'interno di un'area edge. Lo scopo è far credere a OSPF che quei due router siano collegati da un link fittizio in area 0.

L'attivazione del Virtual Link richiede solo l'area da attraversare (una sola) e i Router ID dei due router coinvolti, non gli indirizzi IP delle loro interfacce: OSPF deriverà automaticamente gli indirizzi IP corretti. I messaggi di instradamento OSPF sono incapsulati in pacchetti unicast IP che attraversano il link → per avere un tunnel bidirezionale, occorre configurare il Virtual Link su entrambi i router alle estremità.

Aree partizionate

• 
  Partizionamento di un'area edge.
• 
  Partizionamento dell'area 0.

Il problema delle aree partizionate è gestito in OSPF differentemente a seconda del tipo di area:

• area edge: l'ABR non sommarizza le informazioni su tutte le reti presenti nell'area edge, ma annuncia solo le reti che è in grado di raggiungere → i pacchetti verso la partizione verranno inviati solo agli ABR per cui esiste un percorso interno per giungere a destinazione;
• area 0: OSPF non è in grado di risolvere automaticamente i problemi di aree partizionate nel backbone (viene scelto sempre l'ABR più vicino come punto di uscita), ma in alcuni casi l'operatore può attivare manualmente tra due ABR un Virtual Link che fisicamente passa attraverso un'area edge: quando un pacchetto arriva a un ABR, rientra nell'area andando all'ABR all'altra estremità del tunnel per poi finalmente entrare nell'area 0 → l'area 0 deve sempre essere logicamente contigua, ma non necessariamente lo è fisicamente.

Estensione dell'area di backbone

Un link tra due router appartenenti ad aree edge differenti normalmente non può essere usato: il traffico da un'area all'altra infatti deve passare sempre attraverso l'area 0.

Grazie al Virtual Link è possibile portare nel backbone un router di un'area edge che è collegato direttamente a un solo router di backbone: quel router interno diventa un ABR di accesso all'area 0, e quindi tutti i link ad esso collegati possono essere usati per il traffico.

Metriche e costi

OSPF supporta più di una metrica simultaneamente su un singolo link: il percorso migliore può essere, a seconda dei pacchetti, ad esempio:

• il percorso più breve;
• il percorso con la migliore capacità di banda;
• il percorso con il minore ritardo.

OSPF consente di definire le metriche a seconda del campo "Type of Service" (ToS) del pacchetto IP → in teoria, sono possibili 64 tipi di servizio e quindi 64 alberi di instradamento diversi, ma in pratica questa funzione è quasi inutilizzata perché il carico di elaborazione richiesto dall'algoritmo LS su ogni router sarebbe duplicato per ogni ToS.

OSPF adotta il multipath routing a costi equivalenti. A differenza di IGRP, OSPF non definisce un modo non ambiguo per calcolare il costo di un link: il costo è assegnato dal produttore dell'apparato di rete → ogni produttore ha i propri valori predefiniti, creando possibili inconsistenze in reti multi-vendor → è meglio personalizzare i valori di costo sui link più importanti (su entrambe le estremità).

Router ID

Ogni router OSPF è identificato univocamente da un Router ID, che è usato come "nome" dei router nei pacchetti OSPF (ad es. come sorgente nell'intestazione OSPF).

OSPF non specifica come deve essere determinato il Router ID, ma si limita a specificare che deve essere un identificativo univoco lungo 32 bit. Sugli apparati Cisco, i Router ID possono essere ottenuti in due modi:

• manualmente: l'amministratore di rete configura esplicitamente il valore del Router ID (in IPv4 tipicamente non si fa, mentre in IPv6 è obbligatorio: B6. Instradamento IPv6#OSPFv3;
• automaticamente: un algoritmo ricava il Router ID dagli indirizzi IPv4 del router:
  • se c'è almeno un'interfaccia di loopback, il Router ID è uguale all'indirizzo più grande tra quelli delle interfacce di loopback: le interfacce di loopback non dipendono dallo stato delle interfacce fisiche e sono così più stabili;
  • se non c'è alcuna interfaccia di loopback, il Router ID è uguale all'indirizzo più grande tra quelli delle interfacce di rete OSPF.

LSA

Il Link State Advertisement (LSA) è la struttura dati, contenuta nei pacchetti di Link State Update, che contiene le informazioni di instradamento OSPF:

1. Router LSA: descrive un'adiacenza tramite un link punto-punto;
2. Network LSA: elenca i router collegati a una rete di transito, ed è generato dal router designato della rete di transito;
3. Network Summary LSA: contiene le rotte esterne in altre aree dello stesso AS OSPF (Summary Record), ed è generato da un ABR;
4. ASBR Summary LSA: comunica la posizione dell'ASBR se esso non si trova nell'area 0 ma in un'area edge.
5. AS External LSA: contiene le rotte esterne al di fuori dell'AS OSPF (External Record), ed è generato da un ASBR.

Router LSA

• Le adiacenze viste dal router R1.
• 
  Router singolo.
• 
  Router link.
• 
  Network link.

OSPF definisce due tipi di link:

• router link (predefinito): in presenza di un link punto-punto tra due router (ad es. interfaccia seriale), ciascuno dei router lo vede suddiviso logicamente in due link punto-punto:
  • una connessione punto-punto con il router adiacente, identificato dal suo Router ID;
  • una connessione punto-punto con la rete IP adiacente, chiamata rete stub, cioè quella a cui appartiene l'interfaccia di rete del router.
    Se l'interfaccia di un router è attiva ma non è collegata ad alcun altro router, solo la connessione con la rete stub è presente (figura router singolo);
• network link (figura network link): in presenza di una rete broadcast (ad es. Ethernet), chiamata rete di transito, ciascuno dei due o più router ad essa collegati la vede logicamente come una connessione punto-punto con la rete di transito adiacente.

I Router LSA possono descrivere diversi tipi di adiacenze tramite link punto-punto:

1. adiacenza con un router: è generato da ciascuno dei due router adiacenti tra loro;
2. adiacenza con una rete di transito: è generato da ciascuno dei router adiacenti alla rete di transito (compreso il router designato);
3. adiacenza con una rete stub: è generato dal router la cui interfaccia è adiacente alla rete stub;
4. adiacenza con un Virtual Link: è generato da ciascuno dei router alle estremità del Virtual Link.

Pacchetti OSPF

Tutti i pacchetti OSPF vengono incapsulati direttamente in IP (Protocol Type = 89), senza l'ausilio di un protocollo di trasporto intermedio.

Un'intestazione OSPF, uguale per tutti i pacchetti, specifica il tipo del pacchetto OSPF trasportato:

• tipo 1: Hello
• tipo 2: Database Description
• tipo 3: Link State Request
• tipo 4: Link State Update
• tipo 5: Link State Acknowledgement

Protocollo di hello

Il protocollo di hello effettua il rilevamento dei guasti senza affidarsi al livello fisico.

I pacchetti Hello vengono inviati ogni HelloInterval (predefinito = 10 s), e l'adiacenza è considerata scomparsa e non viene più annunciata:

• appena il guasto è rilevato a livello fisico;
• dopo un certo numero di pacchetti Hello persi (RouterDeadInterval predefinito = 40 s, equivalente a 4 pacchetti Hello), se il guasto non può essere rilevato a livello fisico.

L'LSA tuttavia rimane nel database OSPF, e se non rinnovato scade dopo un tempo pari al MaxAge (predefinito = 1 ora).

Il Router ID è calcolato all'avvio del processo OSPF, e non viene modificato anche se vengono modificati gli indirizzi IP sul router → il router potrebbe apparire con un Router ID diverso al riavvio del processo OSPF (ad es. in seguito a un guasto o a un'interruzione dell'alimentazione) → nella topologia calcolata dall'algoritmo LS rimane un nodo non più esistente, fino a quando non scade il relativo LSA.

Protocollo di exchange

Il protocollo di exchange è usato per effettuare il riallineamento delle adiacenze, cioè per sincronizzare il database di due router quando diventano adiacenti.

Il riallineamento delle adiacenze viene svolto solo quando necessario, cioè quando un router ha delle informazioni non aggiornate nel suo database. La verifica della necessità di un aggiornamento del database viene fatta:

• in seguito a un cambiamento nella rete (ad es. in fase di avvio del sistema o quando diventa attivo un nuovo link);
• a ogni scadenza del timer LSA Refresh (predefinito = 30 minuti), per rinfrescare l'age degli LSA ancora validi prima che scadano.

Durante il riallineamento delle adiacenze, vengono scambiati solo gli LSA vecchi o mancanti:

1. Database Description: il router master invia la lista dei numeri di sequenza di tutti gli LSA nel suo database;
2. Link State Request: il router slave invia la lista dei numeri di sequenza relativi agli LSA vecchi o mancanti nel suo database;
3. Link State Update: il router master invia gli LSA richiesti, e il pacchetto Link State Update viene propagato in selective flooding;
4. Link State Acknowledgement: il router slave conferma la ricezione del Link State Update.