Struttura di una Routing Table

Introduzione

Le routing tables contengono tutte le informazioni necessarie per inoltrare gli "IP data packet" verso una delle possibili destinazioni raggiungibili. Ogni entry nella tabella di routing descrive l'insieme dei path migliori per arrivare a na particolare destinazione. OSPF prevede anche l'esistenza di una DEFAULT ROUTE, che verrà usata nel caso in cui non ci sia un'entry specifica per una data destinazione. Per ogni router esiste una sola tabella di routing Il primo insieme di campi descrive le entries della tabella di routing riguardanti la destinazione. I campi sono:

Destination Type

La destination puo' essere di tre tipi. Solo il tipo Network è attualmente usato quando si gestisce un IP data traffic. Gli altri tipi si usano solo nei passi intermedi per la costruzione della tabella di routing.

Network

E' un range di indirizzi IP raggiungibili dall'IP data traffic.

Area border router

Sono routers che sono connessi a piu' aree. Questi routers generano i summary link advertisements che si useranno per calcolare le inter-area routes

AS boundary router

Sono routers che generano gli AS external link advertisement che verranno usati per il calcolo delle external routes

Destination ID

E' l'identificativo della destinazione. Per i Network corrisponde al loro IP associato per gli altri tipi invece corrispondera' all'ID del relativo router

Optional Capabilities

Quando la destinazione e' un router questo campo indica le OSPF capabilities supportate dal router di destinazione. Attualmente due sono le Optional Capabilities accettate

1. l'abilità di gestire route basate su IP-TOS
2. l'abilità di processare gli AS external link

Per la stessa destinazione ci possono essere piu' entries nella tabella di routing dipendenti dai valori dei campi :

Type of Service

Può esserci una insieme separato di routes per ogni IP-TOS

Area

Questo campo indica l'area da cui il link state information e' stato mandato.

Il resto delle entries della tabella di routing descrivono l'nsieme dei paths per la destinazione. E sono :

Path-Type

Ci sono 4 possibili tipi di paths elencati in ordine di preferenza:

1. intra-area , path interni ad un area
2. inter-area path tra aree diverse
3. type 1 external path tra AS differenti
4. type 2 external path tra AS differenti

Cost

Descrive il costo necessario per raggiungere la destinazione. Per il type 2 external path invece descrive il costo del path interno all'AS.

Type 2 cost

Valido solo type 2 external path. indica il costo esterno all' AS

Link State Origin

Questo campo indica il link state advertisement che referenzia direttamente la destinazione. (Questo campo non e' usato dal protocollo OSPF)

Next Hop

E' l'ID del prossimo router da attreversare per raggiungere la destinazione Advertising router Valido solo per destinazioni esterne alle aree. Indica il l'ID del router di frontiera che ha propagato i summary link o gli AS external link che hanno portato alla costruzione della route corrente

Routing Table LookUp

Quando un IP data packet e' ricevuto, un router OSPF cerca nella tabella di routing il path migliore per mandare il pacchetto verso la destinazione. Quest'entry nella tabella di routing provvede a dare due informazioni

1. l'interfaccia di uscita
2. il next hop

Il processo di look-up e' formato da vari passi e permette di trovare tra tutte le entries della routing table la migliore.
I passi sono :

1. Seleziona dalla routing table le entry che permettono di arrivare alla destinazione desiderata.
2. Riduci l'insieme scegliendo il type di path migliore (e.s. intra-path verranno verranno scelti sempre prima degli inter-path perche' sono path interni all'area, e così via )
3. Riduci l'insieme scegliendo le routes nella routing table che hanno un range piu' specifico ( e.s. 128.185.1.0 e' migliore di 128.185.0.0) La default route e' la meno specifica.
4. Riduci scegliendo il routing che rispetta il TOS se nessun routing ha lo stesso TOS si sceglie quello con TOS 0

Calcolo di una Routing Table

Il processo di calcolo di una routing table puo' essere schematizzato nei seguenti passi:

1. La tabella di routing corrente viene invalidata e ne verrà costruita una nuova da zero. La vecchia tabella di routing verra salvata in modo da identificare i cambiamenti.
2. Le intra-area routes sono calcolate tramite lo Shortest-Path-Tree (SPF). In particolare verranno calcolate tutte le tabelle di routing la cui Destinatyon Type e' Area Border Router. Questo passo si suddivide in 2 sottopassi
1. L'albero verrà costruito considerando solo quei links tra routers e transit network.
2. Gli stub verranno aggiunti come foglie dell'albero.
3. Le inter-area routes sono calcolate tramite l'esame dei summary link advertisements
4. Vengono esaminati i summary link advertisement dei routers che connettono una o piu' aree
5. Routes per destinazioni esterne sono calcolate esaminando gli AS external link advertisement.

Calcolo dello SPF per un'area

Ogni router calcolera' l' SPF usando se stesso come radice dell'albero La formazione dello SPF e' fatto in due passi :

1. Vengono considerati solo i link tra routers e transit network
2. Le foglie vengono aggiunte considerando i link agli stub network

Il primo passo della procedura lavorerà sui transit-vertex a ogni vertice sono associati i seguenti dati :

Vertex ID:

E' un numero a 32 bit che identifica il vertice. Per un router corrisponde al Router ID. Per un network corrisponde all'IP del router designato per quel network.

Link State Advertisement

Ogni transit-vertex ha associato un link state advertisement.

List of next hops

La lista dei prossimi hops per lo shortest path dalla root a questo vertice.

Distance from root

Il costo dalla root al vertice corrente.

Per il calcolo dello SPF verrà applicato l'algoritmo di Dijkstra. Dopo aver creata una lista dei vertici,verranno cercati i path dalla root a questi vertici ma non necessariamente i path piu' corti. Comunque il path del vertice candidato piu' vicino alla root e' garantito essere il piu' corto. Questo vertice e' aggiunto all' SPT e rimosso dalla lista dei candidati e i suoi vertici adiacenti sono esaminati per possibili aggiunte o modifiche alla lista dei candidati. L'algoritmo si reitera e terminera' quando la lista dei vertici e' vuota.
Il passo successivo sara' quello di aggiungere le stub network all' SPF. In quesso passo tutti i vertici "router" saranno di nuovo esaminati. Ogni stub network link che compare negli advertisement verra' esaminato e verranno eseguiti i seguenti passi :

1. Calcolo della distanza dello stub network dalla radice.
2. Aggiornamento delle entries nella routing table delle stub network e calcolo dell'insieme dei next hops per raggiungere quella stub network.

Calcolo delle inter-area routes

Le inter-area routes sono calcolate esaminando i summary link advertisement. I passi sono i seguenti per ogni summary link advertisement:

1. Se il costo specificato dall'advertisement e' LSInfinity o LS Age e' uguale a MaxAge allora esamina il prossimo advertisement.
2. Se l'advertisement e' stato originato da se stesso esamina il prossimo advertisement
3. Se il summary link advertisement e' gia presente come routes intra-area allora l'advertisemnt verra scartato.
4. Altrimenti chiamata N la destinazione descritta dall'advertisement e BR il router che lo ha generato questo advertisement descrive l'inter-area path per la destinazione N, dove il costo e' la distanza fino a BR piu' il costo specificato dall'advertisement.
5. La routing table viene aggiornata solo se le vecchie entries erano di costo maggiore oppure di type 1 external o type 2 external.

Esame dei summary link delle transit area

Questo passo viene fatto solo da gli Area Border Router connessi a una o piu transit area. Questo passo serve a cercare paths migliori rispetto a quelli precedenti. I passi sono i seguenti:

1. Se il costo specificato dall'advertisement e' LSInfinity o LS Age e' uguale a MaxAge allora esamina il prossimo advertisement.
2. Se l'advertisement e' stato originato da se stesso esamina il prossimo advertisement
3. Esaminiamo la routing table per l'entry N.Se non esiste o non e' di tipo intra-area o inter-area o l'area associata con l'entry della routing table non e' di tipo backbone allora esamina il prossimo.
4. Esamina le routing table entry per l'advertising router BR associanto con l'area A. Il costo fino a N sara uguale alla somma del costo che c'e' nell'entry di BR riferito all'area A piu' il costo dell' advertisement.
5. Aggiornare la routing table se il costo e' minore.

Calcolo dell'AS external routes.

Le AS external routes routes sono calcolate esaminando gli AS external link advertisement. I passi sono i seguenti per ogni summary AS external link advertisement:

1. Se il costo specificato dall'advertisement e' LSInfinity o LS Age e' uguale a MaxAge allora esamina il prossimo advertisement.
2. Se l'advertisement e' stato originato da se stesso esamina il prossimo advertisement
3. Chiamata N la destinazione descritta dall'advertisemnt N. Esaminiamo le routing table entry per l'AS boundary router. Questo advertisement descrive l'AS external Path fino alla destinazione N
4. Esamina le routing table entry per la destinazione N. Se non esistono entry per N allora inastalla l'AS external path per N
5. Se il path e' presente ma non e' di tipo type 1 o type 2 non fare nulla.
6. Altrimenti compara i costi e se conveniente aggiorna la tabella di routing.