La procedura di propagazione.

Introduzione

I Link State Advertisement (LSA) sono propagati tramite un pacchetto Link State Update che puo' contenere piu' di un annuncio, ognuno pero' propagato un solo hop in avanti. Viceversa per garantire la affidabilita' del processo di propagazione e' bene che gli acknowledgment siano ritrasmessi uno alla volta (sebbene possano essere parimenti raggruppati) in un pacchetto di tipo Link State Acknowledgement. Uno degli elementi tipici del processo di propagazione e' anche la Retrasmission List che, in ogni router, tiene conto dei LSA ricevuti che ancora non abbiano avuto acknowledgement. Ogni interfaccia avra' quindi una determinata lista di ritrasmissione opportunamente settata tenendo conto della velocita' di tale interfaccia.
L'algoritmo di ritrasmissione inizia con la ricezione di un pacchetto di tipo Link State Update. La struttura gerarchica di incapsulazione del protocollo OSPF garantisce tutti i controlli di consistenza. Quindi quando artiva un pacchetto di tipo Link State Update:

Si deduce il vicino dall'inbtestazione OSPF del pacchetto.
Si controlla se lo stato di questo vicino e' Exchange. Se non lo e' il pacchetto viene gettato.

Osserveremo nel seguito la stretta dipendenza dell'algoritmo dagli stati Exchange e Loading.

Ricezione del pacchetto Link State Update.

Per ogni LSA presente:

Validazione del checksum LSA. Se invalido passare al prossimo LSA.
Esame del campo Type dell'LSA, se sconosciuto passare al prossimo LSA.
Se un LSA e' del tipo External e ci si trova in una Stub Area, passare al prossimo LSA.
Se il campo Age ha il valore MaxAge e non ci sono istanze dell'LSA nel Database Topologico del Router allora:

Acknowledge al vicino tramite apposito pacchetto.
Ripulisci tutte le richieste della stessa istanza
Se lo stato del vicino e' Exchange o Loading allora installa tale LSA nel Database Topologico altrimenti eliminalo.
Esamina il prossimo LSA.

Altrimenti, trova l'istanza di questo LSA nel Database. Se e' assente o e' piu' recente.

Se c'e' ed e' vecchia MinLsInterval secondi rispetto ad ora, passa al prossimo (senza acknowledgment)
altrimenti propagalo in un sottoinsieme delle interfaccie, detto Sottinsieme delle Interfaccie Eleggibili. Esse sono scelte in base al tipo di LSA: se e' di tipo External allora dobbiamo escludere quelle interfaccie del router che fanno parte di una Stub Area o di un Link Virtuale. Altrimenti sono da considerarsi eleggibili tutte le interfaccie attaccate all'area di cui proviene il LSA.
rimuovi la copia dell'LSA da tutte le Retrasmission List dei vicini.
installa la nuova istanza al posto della vecchia(non prima che siano passati MinLSInterval secondi) acknowledgment al vicino.

Allora se vi e' una istanza nelle Request List del vicino vi e' stato un errore. Restart del router con segnalazione dell'evento BadLsRequest al vicino e rimozione del pacchetto.
Se l'eta' e' maggiore della corrente

Se sta nelle Retrasmission List deve essere rimosso (acknowledgment implicito)
Acknowledgment al vicino.

Se e' piu' recente la copia nel Database c'e' stato un errore passa al prossimo LSA.

Quale LSA e' piu' nuovo?
Si stabilisce quale LSA e' piu' nuovo:

Se ha un LS Sequence number maggiore.
Se ha una checksum intera (valutata come numero intero)
se ha Age=MaxAge.
nel caso la differenza sia MaxAgeDiff, se ha un LS Sequence Number minore.

Reinstallazione di un LSA nel DataBase.

Se si reinstalla un LSA si deve verificare il contenuto del LSA. Se tale contenuto e' uguale non si devono riaggiornare le Routing Tables e i link ai router. Questo vale a maggior ragione per LSA di tipo External o Summary.

Sincronismo tra i databases.

Occore un sincronismo tra i Database associati alle interfaccie eleggibili. Dunque, per ogni interfaccia eleggibile si effettua questo algoritmo, che tiene conto se c'e' una alta probabilita' che un vicino abbia gia' ricevuto un LSA. (Comunque per sicurezza e affidabilita' tale LSA viene reinserito nelle retrasmission list del vicino.)
Per ogni interfaccia eleggibile:

per ogni vicino vengono eseguiti i controlli:

se il vicino e' in uno stato Exchange non partecipa alla propagazione, passa al prossimo vicino.
se lo stato del vicino e' Exchange o Loading, esamina la sua request list. Se esiste tale istanza del LSA controlla il database e cancella dalla request list questa istanza del LSA. Comunque avviene l'inserimento nelle retrasmission list del vicino, come detto prima.

se tale istanza non esiste nelle retrasmission list dei vicini, ovviamente non viene propagato e si passa alla prossima interfaccia eleggibile.
Se e' stato gia' ricevuta tale istanza dal Router Designato o dal Router Designato di Backup si passa alla prossima interfaccia eleggibile.
Se l'interfaccia e' in stato backup ( o il router ricevente e' esso stesso un router designato di backup) allora si passa alla prossima interfaccia eleggibile, e si propaga l'annuncio solo quando il router diventa Designato.
Se per caso si arriva in questo punto, propaga l'annuuncio.

Propagazione.

Si manda a questo punto un pacchetto di tipo Link State Update, incrementando l'Age dell'LSA di InfTransDelay secondi. Su reti broadcast viene fatto il multicast a tutti i router, altrimenti in unicast, router per router.

LSA originati dal mittente.

Questo avviene quando:

il campo Advertising Router = ID del mittente
il campo LinkStateID = IP number di una interfaccia del mittente.

Rimozione degli LSA dalla retrasmission list.

Cio' accade quando:

Non esiste piu' una route verso l'esterno (caso di un LSA di tipo Summary o External)
Se e' un LSA di tipo Network e il router non e' piu' quello designato.
Se per caso il campo LinkStateID = IP number di una interfaccia del mittente, ma l'AdvertisingRouter ha una ID diversa dalla propria, in questo caso c'e' stata una riconfigurazione degli ID del router e l'LSA, e la rimozione avviene per Aging prematuro, come vedremo dopo.

Processo di Acknowledgment.

L'accettazione di un LSA puo' essere di 2 tipi

Ritardata: permette il raggrupamento e con essa la conferma da parte di tutti i vicini con un solo pacchetto, ad un ritardo fissato e non troppo grande (per evitare accavallamenti).
Diretto: in risposta ad un duplicato e per forza in unicast.

La ripropagazione avviene quando l' LSA arrivato e' piu' recente di quello che si trova nel DataBase (Acknowledge ritardato o meno a seconda se non e' o se e'un Router Designato di Backup), oppure quando e' un duplicato o ha Age=MaxAge (con acknowledge diretto solo nel caso in cui non si consideri un acknowledge implicito). Ovviamente si procedera' diversamente nel caso di reti unicast, come per la propagazione normale.

Aging e Aging Prematuro.

Il processo di aging aumenta il campo Age del LSA di InfTransDelay secondi. Ora se il pacchetto ha Age=MAxAge esso deve essere ignorato, semplicemente perche' nel processo di propagazione esso sara' rimosso, e non sara' ulteriormente usato nel calcolo delle routing table. Inoltre il campo LSACheckSUM dovra' essere controllato ogni CheckAge secondi. Se si verifica un errore a questo punto si riavvia il router. L'Aging Prematuro viene usato per eliminare artificiosamente un LSA. Questo solo quando

l' LSA non e' piu' contenuto in nessuna delle retrasmission list dei vicini.
Nessun Router e' nello stato Exchange o Loading. Settando il campo Age al valore 0x7ffffff (MaxAge) si ottiene l'invecchiamento prematuro, utile quando una route di tipo External e' irraggiungibile, o quando l' LSA e' generato dal mittente.

Link Virtuali.

Un link virtuale e' configurato come un Link Point-to-Point di tipo unnumbered, che unisce due Router di Frontiera dell'Area. Il Backbone avra' dunque i suoi LSA che passano per il Link Virtuali, e nel protocollo Hello si calcoleranno anche le adiacenze virtuali. Il costo e la transitabilita' sono desunti facendo il calcolo del round trip di un pacchetto fatto transitare ai due estremi del Link Virtuale. Analogamente gli IP numbers degli estremi sono desunti dal campo Link Data nel LSA del mittente. Ovviamente LSA di tipo External non sono abilitati alla propagazione lungo il link, perfino nei tratti intra-area.