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:

• Una nuova rotta verso una destinazione. Questa a sua volta può essere divisa in due casi:
  • La destinazione era sconosciuta finora.
  • La destinazione era nota, ma questa rotta contiene degli hop intermedi diversi dalle rotte già note.
• Una rotta già nota cambia. Può cambiare il suo costo, il fingerprint riportato, il numero di nodi interni riportato. Se si tratta di un cambio di fingerprint la modifica viene apportata. Se il fingerprint non cambia, allora si valuta se almeno una delle altre variazioni supera una data soglia (ad esempio il 30% del costo o il 10% del numero di nodi) per decidere se apportare la modifica nella propria 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:

• Un ETP arriva ad A da un certo suo vicino N interno ad un g-nodo N¹ a sua volta interno a N² ... N^l. Questo ETP è prodotto da N anche se N lo sta inoltrando, cioè potrebbe essere stato originato da un altro nodo in conseguenza di variazioni nei suoi link. Questo ETP, oltre alle rotte così come sono viste da N, contiene per i g-nodi da N⁰ a N^l il fingerprint e il numero di nodi interni.

• Il nodo A ha in comune con N (almeno N^l) fino ad un certo g-nodo Nⁱ. Il nodo A elimina dal set R tutte le rotte che, come sono viste da N, si riferiscono a destinazioni di livello inferiore a i-1. Si tratta infatti di rotte interne ad un g-nodo a cui N appartiene ma A non appartiene. Il nodo A considera invece tutte le altre rotte del set R.

• Per ogni rotta nel set R ora la destinazione è espressa come coordinata gerarchica valida per il nodo A; ma gli hop intermedi vanno corretti:
  • Gli hop intermedi verso una generica destinazione (lD, pD), cioè verso il g-nodo di livello lD e identificativo pD, come conseguenza del fatto che non possono essere rilevate rotte cicliche a nessun livello della gerarchia, sono sempre in una forma in cui i livelli salgono man mano che si avanza. Ad esempio verso (5, 6) potrei avere la path (0, 2) - (0, 5) - (1, 3) - (1, 7) - (2, 2) - (4, 2) - (4, 3) - (5, 3) - (5, 6).

  • Quando un ETP prodotto da N viene trasmesso ad A, se il minimo g-nodo comune è Nⁱ con i>1 questo significa che N ed A sono bordernodi di g-nodi diversi, cioè che le informazioni del percorso interno al g-nodo di N distinto dal g-nodo di A non sono interessanti per A. Quindi A potrà rimuovere tutti gli hop iniziali che hanno livello inferiore ad i-1 e sostituirli con il solo hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N.

  • Se invece il minimo comune g-nodo tra A e N è N¹, cioè A ed N sono nello stesso g-nodo di livello 1, allora tutti gli indirizzi che sono nella mappa gerarchica di N possono essere nella mappa gerarchica di A. Quindi A non rimuove nessun hop in nessuna delle rotte contenute nell'ETP, ma solo vi aggiunge in testa l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N.

• Il nodo A aggiunge al set R la rotta verso N^i-1 con costo uguale all'arco verso N e fingerprint e numero di nodi così come riportati nell'ETP per N^i-1.