Modulo QSPN - Esplorazione della rete

TP - Tracer Packet

Un TP viene avviato da un nodo S, che ci scrive il suo ID e lo invia a tutti i suoi vicini. Un nodo che riceve il TP vi aggiunge il suo ID e poi lo inoltra a tutti i suoi vicini tranne quello da cui lo ha ricevuto.

Un nodo (N) che invia o inoltra un TP lo invia a più di un vicino, quindi invia in effetti un insieme di TP, detto bouquet di N. Il primo di questi TP a raggiungere un altro nodo M contiene la rotta più veloce che può usare M per raggiungere N (e qualsiasi altro nodo attraversato). Un nodo può ricevere più di una volta un TP proveniente da uno stesso flood, ma lo inoltra solo la prima volta. Quindi se un nodo S invia un TP, tutti i nodi scropriranno per ogni loro vicino la rotta migliore verso S.

ATP - Acyclic Tracer Packet

Un ATP è un TP che, quando un nodo lo riceve lo inoltra a tutti i suoi vicini tranne quello da cui lo riceve, anche se il flood era già passato da lì. Un ATP non viene inoltrato da un nodo N se l'ID di N era già presente in esso. Questo lo rende aciclico. Quindi se un nodo S invia un ATP tutti i nodi scopriranno tutte le possibili rotte verso S, senza rotte in loop.

CTP - Continuous Tracer Packet

Un CTP è un TP che, quando un nodo lo riceve lo inoltra sempre a tutti i suoi vicini tranne quello da cui lo riceve. Inoltre, se il nodo ricevente ha come unico vicino quello che glielo ha inoltrato allora svuota la lista di hops e lo inoltra di nuovo al nodo che glielo aveva inoltrato. Quindi un CTP non cessa mai di esplorare tutte le rotte della rete.

Information rule

La regola dell'informazione interessante può essere aggiunta alla decisione sull'inoltro di un generico TP (TP o ATP o CTP). Questa regola dice che un TP non va inoltrato se non contiene nessuna informazione interessante per il nodo. Ad esempio nel caso di rotte se tutte le rotte in esso presenti erano già note al nodo.

Nota: una rotta verso una destinazione D che riporta un fingerprint F(D) diverso da quello che conoscevo è sempre una informazione interessante.

ETP - Extended Tracer Packet

Un ETP è un ATP che contiene una porzione di mappa (un set di rotte). Ad esso si associa la regola dell'informazione interessante, considerando tutte le rotte contenute come parte dell'informazione. Quindi un nodo che riceve l'ETP lo inoltra (a tutti i vicini tranne il mittente) se l'ETP non ha fatto già un ciclo (non c'è già il suo ID) AND le rotte contenute (la porzione di mappa nell'ETP) apportano qualche aggiornamento alla mappa del nodo.

Esplorazione

Ci proponiamo ora di esaminare come si realizza l'esplorazione di una rete dinamica, ossia in un grafo che cambia nel tempo in termini di vertici o di archi o di costo degli archi.

Una rete è stabile se tutti i nodi hanno tutte le conoscenze di loro pertinenza. Lasciamo indefinito questo concetto di informazioni di pertinenza del nodo, facciamo qualche esempio di cosa può significare: conoscere tutte le rotte verso tutte le destinazioni; oppure tutte le migliori rotte per ogni gateway; oppure le migliori n rotte disgiunte.

Una rete inizia come singolo nodo. Quando inizia è quindi stabile e il nodo si considera maturo (vedi sotto).

Sia G una rete stabile. Consideriamo tutti i possibili eventi che cambiano il grafo e quindi rendono la rete non più stabile. Vediamo quali operazioni sono necessarie a farla ridiventare stabile.

Tali eventi, come si può vedere dall'elenco che segue, sono riconducibili alla nascita/variazione/morte di archi tra due nodi vicini. Questi eventi sono tutti notificati al modulo QSPN, come si è detto nei requisiti dell'analisi funzionale.

Evento added-link: Sia il nodo A ∈ G. A rileva la nascita di un nuovo arco con un vicino B ∈ G.

Il nodo A chiede a B un nuovo ETP completo (vedi sotto). La richiesta può venire rifiutata perché B non è ancora maturo; in questo caso A aspetta un po' e riprova. Con le informazioni in questo ETP il nodo A aggiorna la sua mappa. A prepara tutte le rotte della sua mappa che hanno subito una variazione e le mette in un set R. Mette R e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini tranne B. Poi A prepara un nuovo ETP completo e lo invia a B.

Evento changed-link: Sia il nodo A ∈ G con un arco verso B. A rileva che l'arco verso B cambia il suo costo.

Il nodo A chiede a tutti i suoi vicini un nuovo ETP completo. Con la somma delle informazioni da tutti questi ETP e i costi dei link ai suoi vicini (di cui uno è cambiato), il nodo A aggiorna la sua mappa. A prepara il set R con tutte le rotte della sua mappa che hanno subito una variazione. Mette R e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini.

Evento removed-link: Sia il nodo A ∈ G con un arco verso B. A rileva che l'arco viene rimosso.

A si comporta come per il caso di cambio di costo dell'arco.

Evento hooked: Sia A un nodo appena entrato nella rete G grazie ad un set di archi verso nodi vicini.

Il nodo A si considera non maturo. In questo stato se A riceve la notifica di eventi — di modifica dei suoi archi e/o ricezione di ETP — li accoda per processarli in seguito. Inoltre se riceve la richiesta di produrre un ETP la rifiuta "perché non maturo".

A chiede a tutti i suoi vicini un nuovo ETP completo. Se un vicino rifiuta perché non è ancora maturo, A lo rimuove dai suoi archi così da interrogarlo nuovamente dopo. Può succedere come caso estremo che A rimuove così tutti i suoi archi: in questo caso non è entrato in G; riproverà più tardi.

Con la somma delle informazioni da tutti gli ETP ricevuti, il nodo A aggiorna la sua mappa. Poi A prepara un nuovo ETP completo e lo invia in broadcast a tutti i vicini.

Da questo momento A è maturo. A processa gli eventi accodati.

Evento requested-etp: Quando un nodo A riceve da un vicino B la richiesta di un nuovo ETP completo.

A considera B come il g-nodo di più alto livello a cui appartiene il nodo B ma non appartiene il nodo A.

A prepara in R tutte le rotte della sua mappa che non contengono B, né come gateway né come hop né come destinazione. A mette in un ETP R e il suo ID e lo invia solo a B.

Evento etp-received: Quando un nodo A riceve un ETP da un vicino B.

Con le informazioni dell'ETP il nodo A aggiorna la sua mappa. Elenchiamo le possibili variazioni alla mappa:

Per ogni modifica che apporta alla sua mappa il nodo A memorizza questa modifica in una lista R. Se si tratta di una rotta nuova o cambiata basta memorizzare i nuovi valori. Se si tratta di una rotta rimossa dalla mappa la si memorizza nella lista R con costo DeadREM.

Se R ≠ ∅, A produce un ETP con R, la lista di hop attraversati dall'ETP ricevuto da B più l'ID di A. Il nuovo ETP viene inviato in broadcast a tutti i vicini tranne B.

Quando tutti gli ETP finiscono il loro ciclo di vita la rete è di nuovo stabile.

Lettura delle informazioni in un ETP

Sia il nodo A ∈ G che riceve un ETP.

A esamina la lista di hop percorsi dall'ETP. Per prima cosa esegue la grouping rule su tale lista per renderla coerente con i cluster a cui il nodo A appartiene. Poi esegue la acyclic rule sulla lista, cioè se l'ETP era già passato per il mio nodo (o cluster) lo ignoro del tutto.

Infine A esamina il set di rotte R contenuto nell'ETP, ma deve renderle coerenti con i cluster a cui il nodo A appartiene. Come avviene questo: