Differences between revisions 6 and 8 (spanning 2 versions)
Revision 6 as of 2015-03-04 16:21:07
Size: 23657
Editor: lukisi
Comment:
Revision 8 as of 2015-03-09 17:57:04
Size: 30252
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:
<<TableOfContents(4)>>
Line 50: Line 52:
Il nodo ''n'' chiede a ''v'' un nuovo ETP completo. Con le informazioni in questo ETP il nodo ''n'' aggiorna la sua mappa. ''n'' prepara tutti i percorsi della sua mappa che hanno subito una variazione e li mette in un set ''P''. Se ''P'' risulta non vuoto il nodo ''n'' mette ''P'' e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini tranne ''v''. Il nodo ''n'' chiede a ''v'' un nuovo ETP completo.

La richiesta di un ETP potrebbe venire rifiutata da ''v'' perché non è ancora maturo. In questo caso ''n'' rinuncia all'aggiornamento, confidando che sarà lo stesso nodo ''v'', una volta divenuto maturo, ad iniziare un flood di ETP verso ognuno dei suoi vicini.

Altrimenti, con le informazioni in questo ETP il nodo ''n'' aggiorna la sua mappa. ''n'' prepara tutti i percorsi della sua mappa che hanno subito una variazione e li mette in un set ''P''. Se si tratta di un percorso nuovo o cambiato basta memorizzare in ''P'' il percorso con i valori correnti. Se si tratta di un percorso rimosso dalla mappa lo si memorizza nella lista ''P'' con costo ''dead''.

Inoltre il nodo ''n'' aggiorna tutte le informazioni relative ai suoi g-nodi, cioè fingerprint e numero di nodi interni, sulla base delle conoscenze aggiornate nella sua mappa. Controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se ''P'' risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, il nodo ''n'' mette ''P'' e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini tranne ''v''.
Line 54: Line 64:
La richiesta di un ETP potrebbe venire rifiutata da ''v'' perché non è ancora maturo. In questo caso ''n'' rinuncia all'aggiornamento, confidando che sarà lo stesso nodo ''v'', una volta divenuto maturo, ad iniziare un flood di ETP verso ognuno dei suoi vicini.
Line 58: Line 66:
Il nodo ''n'' 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 ''n'' aggiorna la sua mappa. ''n'' prepara il set ''P'' con tutti i percorsi della sua mappa che hanno subito una variazione. Se ''P'' risulta vuoto il nodo ''n'' non fa nient'altro. Altrimenti mette ''P'' e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini. Il nodo ''n'' 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 ''n'' aggiorna la sua mappa. ''n'' prepara il set ''P'' con tutti i percorsi della sua mappa che hanno subito una variazione.

Inoltre il nodo ''n'' aggiorna tutte le informazioni relative ai suoi g-nodi e controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se ''P'' risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, il nodo ''n'' mette ''P'' e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini.
Line 62: Line 74:
''n'' si comporta come per il caso di cambio di costo dell'arco. Il nodo ''n'' rimuove dalla sua mappa tutti i percorsi che iniziavano con l'arco rimosso e li scrive nel set ''P'' con costo = ''dead''. Poi ''n'' si comporta come per il caso di cambio di costo dell'arco.
Line 76: Line 88:
Con le informazioni dell'ETP il nodo ''n'' aggiorna la sua mappa.

Per ogni modifica che apporta alla sua mappa il nodo ''n'' memorizza questa modifica in una lista ''P''. Se si tratta di un percorso nuovo o cambiato basta memorizzare i nuovi valori. Se si tratta di un percorso rimosso dalla mappa lo si memorizza nella lista ''P'' con costo ''dead''.

Se ''P'' ≠ ∅, ''n'' produce un ETP con ''P'', la lista di hop attraversati dall'ETP ricevuto da ''v'' più l'ID di ''n''. Il nuovo ETP viene inviato in broadcast a tutti i vicini tranne ''v''.
Con le informazioni dell'ETP il nodo ''n'' aggiorna la sua mappa. ''n'' prepara il set ''P'' con tutti i percorsi della sua mappa che hanno subito una variazione.

Inoltre il nodo ''n'' aggiorna tutte le informazioni relative ai suoi g-nodi e controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se ''P'' risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, ''n'' produce un ETP con ''P'', la lista di hop attraversati dall'ETP ricevuto da ''v'' più l'ID di ''n''. Il nuovo ETP viene inviato in broadcast a tutti i vicini tranne ''v''.
Line 84: Line 96:
Questo evento di fittizia variazione del grafo è aggiunto come misura di sicurezza. Se un vicino ha perso qualche informazione interessante questa è una occasione per rivederla. Questo evento di fittizia variazione del grafo è aggiunto come misura di ridondanza. Se un vicino ha perso qualche informazione interessante questa è una occasione per rivederla.
Line 151: Line 163:
=== Processazione dei dati in un ETP ricevuto ===
Sia ''m'' un ETP che il nodo ''n'' riceve dal nodo ''v''.
== Processazione di un set di ETP ==
Il seguente algoritmo per processare un set di ETP viene eseguito dal nodo ''n'' in queste possibili circostanze:

 * Il nodo ''n'' è appena entrato in una rete e quindi ha chiesto un ETP a tutti i suoi vicini.
 * Il nodo ''n'' ha rilevato un nuovo arco ''a'' verso un vicino ''v'' e quindi ha chiesto un ETP a ''v''.
 * Il nodo ''n'' ha rilevato il cambio di costo in un arco ''a_changed'' e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso tra gli argomenti di questo algoritmo ho anche l'arco ''a_changed'' che ha avuto una variazione.
 * Il nodo ''n'' ha rilevato la rimozione di un arco ''a_removed'' e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso prima di iniziare questo algoritmo, il nodo ''n'' ha rimosso dalla sua mappa tutti i percorsi che sfruttavano l'arco ''a_removed''.
 * Il nodo ''n'' ha ricevuto un ETP inviato in broadcast da un suo vicino.

=== Pre-processazione dei percorsi in un ETP ricevuto ===
Sia ''m'' un ETP che il nodo ''n'' riceve dal nodo ''v'' attraverso l'arco ''a''.
Line 158: Line 179:
Infine ''n'' esamina il set di percorsi ''P'' contenuto in ''m'', ma deve renderli coerenti con i suoi g-nodi. Come avviene questo: Infine ''n'' esamina il set di percorsi ''P'' contenuto in ''m'', ma deve renderli coerenti con i suoi g-nodi. Ecco come realizza questo:
Line 164: Line 185:
 * Per tutti i percorsi del set ''P'', ''n'' somma al costo del percorso il costo dell'arco con ''v''.  * Per tutti i percorsi ''p'' del set ''P'', che sono istanze di !EtpPath, il nodo ''n'' crea una istanza di !NodePath ''q'' associando al percorso ''p'' l'arco ''a''. Mette ''q'' in un set globale che chiamiamo ''Q''.
Line 167: Line 188:
Nel corso del documento abbiamo più volte usato diciture quali ''"n aggiorna la sua mappa"'' oppure ''"i percorsi nella mappa di n che hanno subito variazioni"''. Qui descriviamo meglio come avvengono questi passaggi.

Il nodo ''n'' quando riceve e processa un ETP si trova con un set di percorsi nuovi che chiamiamo ''P''. Indichiamo con ''M'' l'insieme dei percorsi che già prima il nodo ''n'' conosceva, cioè la sua mappa.

 * Il nodo ''n'' prepara una lista ''P'', inizialmente vuota, di percorsi che andranno segnalati ai vicini a cui si inoltrerà l'ETP.
 * Il nodo ''n'' raggruppa i percorsi contenuti in ''P'' per destinazione. Per ogni destinazione ''d'':
  * Sia ''P~-,,d,,-~'' l'insieme dei percorsi nuovi verso ''d''.
Quando abbiamo descritto la gestione degli eventi che portano a variazioni nel grafo della rete, abbiamo più volte usato diciture quali ''"n aggiorna la sua mappa"'' oppure ''"mette in P i percorsi che nella sua mappa hanno subito variazioni"''. Qui descriviamo meglio come avvengono questi passaggi.

Il nodo ''n'', dopo aver processato il set di ETP ricevuti, si trova infine con un set di percorsi nuovi che chiamiamo ''Q''. Indichiamo con ''M'' l'insieme dei percorsi che già prima il nodo ''n'' conosceva, cioè la sua mappa.

 * Il nodo ''n'' prepara una lista ''P'', inizialmente vuota, di percorsi che andranno segnalati ai vicini a cui si inoltrerà l'ETP.
 * Il nodo ''n'' prepara una lista ''B'', inizialmente vuota, di destinazioni per le quali alla fine intende iniziare un nuovo flood. Questo per la regola di primo rilevamento di split.
 * Il nodo ''n'' raggruppa i percorsi contenuti in ''Q
'' per destinazione. Per ogni destinazione ''d'':
  * Sia ''Q~-,,d,,-~'' l'insieme dei percorsi nuovi verso ''d''.
Line 175: Line 197:
  * Il nodo ''n'' prepara una lista ''F'' ’ con tutti i fingerprint distinti che conosceva per il g-nodo ''d''.
Line 177: Line 200:
  * Se ''M~-,,d,,-~'' = ∅ ed esiste un percorso ''p'' ∈ ''P~-,,d,,-~'' tale che ''p''.cost ≠ ''dead'':
   * il nodo ''n'' ha appena individuato una nuova destinazione prima ignota.
  * Il nodo ''n'' prepara una lista ''S~-,,d,,-~'', inizialmente vuota, di segnali da emettere.
Line 180: Line 202:
   * il nodo ''n'' controlla se esiste un ''p''’’ ∈ ''P~-,,d,,-~'' che abbia la stessa sequenza di passi. Se esiste:    * Il nodo ''n'' controlla se esiste un ''p''’’ ∈ ''Q~-,,d,,-~'' che abbia la stessa sequenza di passi. Questo confronto fra ''p''’ e ''p''’’, che sono entrambi istanze di !NodePath, avviene con il metodo ''hops_are_equal'' che tiene conto anche dell'arco verso il vicino. Se esiste:
Line 183: Line 205:
     * ''p''’’ viene scartato da ''P~-,,d,,-~''.      * ''p''’’ viene scartato da ''Q~-,,d,,-~''.
Line 187: Line 209:
     * ''p''’’ viene scartato da ''P~-,,d,,-~''.      * ''p''’’ viene scartato da ''Q~-,,d,,-~''.
Line 189: Line 211:
     * Se ''p''’.arc.i_qspn_equals(''a_changed''):
      * ''p''’ viene aggiunto a ''V~-,,d,,-~''.
Line 191: Line 215:
  * Tutti i percorsi rimasti in  ''P~-,,d,,-~'' vengono aggiunti a ''O~-,,d,,-~''.
  * Poi il nodo ''n'' ordina ''O~-,,d,,-~'' in base al costo crescente. Esegue su questa lista l'algoritmo descritto nel documento [[Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti|percorsi disgiunti]] per scartare quelli non sufficientemente disgiunti e tenere solo i ''max_paths'' più rapidi. Nel fare questo deve tener conto del requisito di mantenere per la destinazione ''d'' e per ogni proprio vicino ''v'', almeno 1 percorso, se esiste, indipendentemente dal valore di ''max_paths'' e dalle regole di disgiunzione, verso ''d'' che non contiene ''v'' tra i suoi passaggi. Alla fine in ''O~-,,d,,-~'' non possono rimanere percorsi con costo = ''dead''.
  * Infine il nodo ''n'' sulla base del contenuto delle liste di appoggio prima descritte (''O~-,,d,,-~'', ''M~-,,d,,-~'' e ''V~-,,d,,-~'') popola la lista ''P'' che andrà a comporre l'ETP che sarà inoltrato ai vicini. Questo avviene così:
   * Se ''p''’.arc.i_qspn_equals(''a_changed''):
     * ''p''’ viene aggiunto a ''V~-,,d,,-~''.
  *
Tutti i percorsi rimasti in ''Q~-,,d,,-~'' vengono aggiunti a ''O~-,,d,,-~''.
  * Poi il nodo ''n'' ordina ''O~-,,d,,-~'' in base al costo crescente. Esegue su questa lista l'algoritmo descritto nel documento [[Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti|percorsi disgiunti]] per scartare quelli non sufficientemente disgiunti e tenere solo i ''max_paths'' più rapidi. Nel fare questo deve tener conto del requisito di mantenere per la destinazione ''d'' e per ogni proprio vicino ''v'', almeno 1 percorso, se esiste, indipendentemente dal valore di ''max_paths'' e dalle regole di disgiunzione, verso ''d'' che non contiene ''v'' tra i suoi passaggi. Ed anche del requisito di mantenere per la destinazione ''d'' almeno 1 percorso per ogni diverso fingerprint di ''d'' che gli viene segnalato. Alla fine in ''O~-,,d,,-~'' non possono rimanere percorsi con costo = ''dead''.
  * Infine il nodo ''n'' sulla base del contenuto delle liste di appoggio prima descritte (''O~-,,d,,-~'', ''M~-,,d,,-~'' e ''V~-,,d,,-~'') popola la lista ''P'' che andrà a comporre l'ETP che sarà inoltrato ai vicini e allo stesso tempo compone il set ''S~-,,d,,-~'' dei segnali da emettere per questa destinazione. Illustriamo l'algoritmo di questa operazione, tenendo conto che i confronti tra istanze di !NodePath anche qui vanno fatti con il metodo ''hops_are_equal'':
Line 196: Line 222:
     * Metti ''p'' in ''P''’.      * Metti ''p'' in ''P''.
     * Prepara un segnale di ''path_added'' e aggiungilo al set ''S~-,,d,,-~''.
Line 201: Line 228:
     * Metti ''p2'' in ''P''’.      * Metti ''p2'' in ''P''.
     * Prepara un segnale di ''path_removed'' e aggiungilo al set ''S~-,,d,,-~''.
Line 204: Line 232:
      * Metti ''p'' in ''P''’.
  * Il nodo ''n'' sostituisce ''O~-,,d,,-~'' al vecchio ''M~-,,d,,-~''. Cioè rimuove da ''M'' tutti i percorsi verso ''d'' e vi aggiunge tutti i percorsi che ora sono in ''O~-,,d,,-~''.

Ora la mappa di ''n'' è aggiornata. Inoltre abbiamo in ''P''’ l'elenco dei percorsi nella mappa di ''n'' che hanno subito variazioni.
      * Metti ''p'' in ''P''.
      * Prepara un segnale di ''path_changed'' e aggiungilo al set ''S~-,,d,,-~''.
  * Il nodo ''n'' sostituisce ''O~-,,d,,-~'' al vecchio ''M~-,,d,,-~''. Cioè:
   * Se ''M~-,,d,,-~'' = ∅ e ''O~-,,d,,-~'' ≠ ∅, allora inserisce in testa al set ''S~-,,d,,-~'' il segnale ''destination_added''.
   * Se ''M~-,,d,,-~'' ≠ ∅ e ''O~-,,d,,-~'' = ∅, allora aggiunge in coda al set ''S~-,,d,,-~'' il segnale ''destination_removed''.
   * Rimuove da ''M'' tutti i percorsi verso ''d'' e vi aggiunge tutti i percorsi che ora sono in ''O~-,,d,,-~''.
   * Emette tutti i segnali che sono in ''S~-,,d,,-~''.
  * Il nodo ''n'' prepara una lista ''F'' ’’ con tutti i fingerprint distinti che conosce adesso per il g-nodo ''d''.
  * Valuta dal confronto tra ''F'' ’ ed ''F'' ’’ se è necessario iniziare un nuovo flood di ETP con i percorsi per ''d'' per la regola di primo rilevamento di split. Cioè:
   * Se ''F'' ’’.size > 1:
    * Per ogni ''fp'' ∈ ''F'' ’’:
     * Se ''fp'' ∉ ''F'' ’:
      * Metti ''d'' in ''B''.
      * Esci dal ciclo.

Ora la mappa di ''n'' è aggiornata. Inoltre abbiamo in ''P'' l'elenco dei percorsi nella mappa di ''n'' che hanno subito variazioni.

Infine abbiamo in ''B'' tutte le destinazioni per cui si ritiene necessario inviare un nuovo flood. Quindi:

 * Se ''B'' ≠ ∅:
  * Il nodo ''n'' prepara un nuovo ETP con tutti i percorsi che conosce verso le destinazioni ''d'' ∈ ''B''. Lo invia a tutti i suoi vicini.

=== Variazioni nei propri g-nodi ===
Dopo aver completato un aggiornamento della propria mappa, il nodo ''n'' aggiorna anche le informazioni relative ai propri g-nodi, cioè fingerprint e numero di nodi all'interno. Se ci sono state variazioni ''n'' se ne accorge e questo è importante per decidere se l'ETP ricevuto va inoltrato ai suoi vicini.

Il nodo ''n'' procede così:

 * Sia ''my_fingerprints[i]'' il valore che ''n'' conosce attualmente come fingerprint del suo g-nodo di livello ''i''.
 * Sia ''my_nodes_inside[i]'' il valore che ''n'' conosce attualmente come numero di nodi interni al suo g-nodo di livello ''i''.
 * ''changes_in_my_gnodes'' = False.
 * Per ogni livello ''i'' da 1 a ''l'':
  * ''FP'' = nuovo set vuoto.
  * ''NN'' = 0.
  * Per ogni destinazione ''d'' di livello ''i-1'' nella mia mappa:
   * ''fp~-,,d,,-~'' = null.
   * Per ogni !NodePath ''p'' in ''d'':
    * ''fp~-,,d,p,,-~'' = fingerprint di ''d'' come riportato da ''p''.
    * Se ''fp~-,,d,,-~'' = null:
     * ''fp~-,,d,,-~'' = ''fp~-,,d,p,,-~'' .
    * Altrimenti:
     * Se ''fp~-,,d,,-~'' ≠ ''fp~-,,d,p,,-~'' :
      * Se ''fp~-,,d,,-~'' è meno anziano di ''fp~-,,d,p,,-~'' :
       * ''fp~-,,d,,-~'' = ''fp~-,,d,p,,-~'' .
   * Aggiungi ''fp~-,,d,,-~'' al set ''FP''.
   * Sia ''p'' la !NodePath più veloce verso ''d''.
   * ''nn~-,,d,,-~'' = numero nodi interni a ''d'' come riportato da ''p''.
   * Somma ''nn~-,,d,,-~'' a ''NN''.
  * ''new_fp'' = ''my_fingerprints[i-1]'' .i_qspn_construct( ''FP'' ).
  * Se ''new_fp'' ≠ ''my_fingerprints[i]'':
   * ''my_fingerprints[i]'' = ''new_fp''.
   * ''changes_in_my_gnodes'' = True.
   * Emetti segnale ''changed_fp'' a livello ''i''.
  * ''new_nn'' = ''my_nodes_inside[i-1]'' + ''NN''.
  * Se ''new_nn'' ≠ ''my_nodes_inside[i]'':
   * ''my_nodes_inside[i]'' = ''new_nn''.
   * ''changes_in_my_gnodes'' = True.
   * Emetti segnale ''changed_nodes_inside'' a livello ''i''.

Ora abbiamo in ''changes_in_my_gnodes'' se sono state apportate variazioni alle informazioni relative ai g-nodi di ''n''.

Modulo QSPN - Esplorazione della rete

Concetti e termini

Questa prima parte non descrive quali messaggi vengano effettivamente passati da un nodo all'altro.

In questa prima parte esaminiamo i concetti generali e introduciamo alcuni termini, per avere una idea di quali considerazioni abbiano portato alla scelta dell'effettiva implementazione che sarà descritta più sotto.

TP - Tracer Packet

Un TP flood viene avviato da un nodo s. Per farlo s genera un TP, ci scrive il suo ID e lo invia a tutti i suoi vicini. Un nodo n che riceve il TP vi aggiunge il suo ID e il costo dell'arco attraverso il quale lo ha ricevuto e poi lo inoltra a tutti i suoi vicini tranne quello da cui lo ha ricevuto.

Quando un nodo invia un TP (questo vale sia per il nodo s che inizia il flood sia per il generico nodo n che lo inoltra) lo invia a più di un vicino, quindi invia in effetti un insieme di TP. Quando questi TP raggiungono un altro nodo v possono quindi aver compiuto percorsi diversi; grazie al loro contenuto il nodo v sa valutare per ogni percorso il suo costo, sommando i costi di ogni singolo arco attraversato.

Un nodo v può ricevere più di una volta un TP proveniente da uno stesso flood, ma lo inoltra solo se il percorso contenuto risulta essere il percorso con costo minore da v ad s. Quindi se un nodo s inizia un TP flood, tutti i nodi scropriranno per ogni loro vicino il percorso 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 inizia un ATP flood tutti i nodi scopriranno tutti i possibili percorsi verso s, senza cicli.

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 ID e lo inoltra di nuovo al nodo che glielo aveva inoltrato. Quindi un CTP non cessa mai di esplorare tutti i percorsi della rete.

Interesting 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 percorsi se tutti i percorsi in esso presenti erano già noti al nodo.

ETP - Extended Tracer Packet

Un ETP è un ATP che contiene una porzione di una mappa, cioè un set P di percorsi. Ad esso si associa la regola dell'informazione interessante, considerando tutti i percorsi contenuti come parte dell'informazione. Quindi un nodo n 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à l'ID di n) AND i percorsi contenuti in P hanno apportato qualche aggiornamento alla mappa di n.

Implementazione dell'esplorazione

Si descrive ora come viene implementata l'esplorazione di una rete. Affrontiamo subito il problema della dinamicità della rete, cioè operiamo in un grafo che cambia nel tempo in termini di vertici o di archi o di costo degli archi. Si noti invece che in questo capitolo non introduciamo subito l'aspetto della struttura gerarchica che viene imposta sugli indirizzi della rete per ridurre la quantità di informazioni memorizzate in ogni singolo nodo. Le implicazioni di questa strutturazione verranno descritte nel capitolo successivo.

Rete completamente esplorata

Una rete si dice completamente esplorata, per brevità diciamo esplorata, se tutti i nodi hanno tutte le conoscenze di loro pertinenza. L'obiettivo che ci siamo prefissati è descritto nel dettaglio nel documento di analisi funzionale: in sintesi, ogni nodo deve avere per ogni destinazione un numero di percorsi rapidi e tra loro disgiunti. I dettagli sulle informazioni per ogni percorso verranno man mano esplicitati in questo documento. In seguito nel documento indicheremo questo insieme di conoscenze di un nodo con il termine mappa di n.

Una rete inizia come singolo nodo. Quando inizia è quindi esplorata e il nodo si considera maturo (questa definizione verrà chiarificata sotto).

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

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 hooked: Sia n un nodo appena entrato nella rete G grazie ad un set di archi verso nodi vicini.

Il nodo n si considera non maturo. In questo stato se n 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".

n chiede a tutti i suoi vicini un nuovo ETP completo; vedremo fra poco come viene preparato un ETP completo. Se un vicino v rifiuta perché non è ancora maturo, n lo ignora, confidando che sarà lo stesso nodo v, una volta divenuto maturo, ad iniziare un flood di ETP verso ognuno dei suoi vicini. Può succedere come caso estremo che n non riceve nessun ETP: in questo caso n non è entrato in G; la procedura di hook nella rete è da considerarsi fallita e occorrerà riprovare da capo.

Con la somma delle informazioni da tutti gli ETP ricevuti, il nodo n aggiorna la sua mappa.

Da questo momento n è maturo. Il nodo n prepara un nuovo ETP completo e lo invia in broadcast a tutti i vicini. n processa gli eventi accodati.

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

Il nodo n chiede a v un nuovo ETP completo.

La richiesta di un ETP potrebbe venire rifiutata da v perché non è ancora maturo. In questo caso n rinuncia all'aggiornamento, confidando che sarà lo stesso nodo v, una volta divenuto maturo, ad iniziare un flood di ETP verso ognuno dei suoi vicini.

Altrimenti, con le informazioni in questo ETP il nodo n aggiorna la sua mappa. n prepara tutti i percorsi della sua mappa che hanno subito una variazione e li mette in un set P. Se si tratta di un percorso nuovo o cambiato basta memorizzare in P il percorso con i valori correnti. Se si tratta di un percorso rimosso dalla mappa lo si memorizza nella lista P con costo dead.

Inoltre il nodo n aggiorna tutte le informazioni relative ai suoi g-nodi, cioè fingerprint e numero di nodi interni, sulla base delle conoscenze aggiornate nella sua mappa. Controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se P risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, il nodo n mette P e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini tranne v.

Poi n prepara un nuovo ETP completo e lo invia a v.

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

Il nodo n 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 n aggiorna la sua mappa. n prepara il set P con tutti i percorsi della sua mappa che hanno subito una variazione.

Inoltre il nodo n aggiorna tutte le informazioni relative ai suoi g-nodi e controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se P risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, il nodo n mette P e il suo ID in un nuovo ETP. Invia l'ETP in broadcast a tutti i vicini.

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

Il nodo n rimuove dalla sua mappa tutti i percorsi che iniziavano con l'arco rimosso e li scrive nel set P con costo = dead. Poi n si comporta come per il caso di cambio di costo dell'arco.

Preparazione di un nuovo ETP completo: Quando un nodo n prepara un nuovo ETP completo, il suo contenuto dipende se lo sta preparando per tutti i suoi vicini o per un vicino in particolare.

Se il destinatario è un nodo particolare v, il nodo n prepara in P tutti i percorsi della sua mappa che non contengono v, né come gateway né come hop né come destinazione. n mette P e il suo ID in un ETP e lo invia solo a v.

Se l'ETP va inviato a tutti i vicini, il nodo n prepara in P tutti i percorsi della sua mappa. n mette P e il suo ID in un ETP e lo invia a tutti i vicini.

In entrambi i casi, il set P potrebbe risultare vuoto, ma l'ETP viene comunque prodotto e inviato, perché l'ETP contiene il percorso intrinseco verso lo stesso nodo n.

Evento etp-received: Quando un nodo n riceve un ETP da un vicino v.

Con le informazioni dell'ETP il nodo n aggiorna la sua mappa. n prepara il set P con tutti i percorsi della sua mappa che hanno subito una variazione.

Inoltre il nodo n aggiorna tutte le informazioni relative ai suoi g-nodi e controlla se tali informazioni sono effettivamente cambiate rispetto a prima.

Se P risulta non vuoto, oppure se sono state apportate variazioni alle informazioni relative ai propri g-nodi, n produce un ETP con P, la lista di hop attraversati dall'ETP ricevuto da v più l'ID di n. Il nuovo ETP viene inviato in broadcast a tutti i vicini tranne v.

Evento periodical-update: Sia il nodo n ∈ G. Sono passati 10 minuti dal momento in cui n è diventato maturo in G oppure dal precedente evento periodical-update.

Questo evento di fittizia variazione del grafo è aggiunto come misura di ridondanza. Se un vicino ha perso qualche informazione interessante questa è una occasione per rivederla.

Il nodo n prepara un nuovo ETP completo e lo invia in broadcast a tutti i vicini.


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

Struttura gerarchica degli indirizzi

In questo capitolo prendiamo in esame il fatto che ogni singolo nodo mantiene informazioni sulla rete che sono limitate ad una visione gerarchica. Quindi anche quando le trasmette esse hanno questo limite. Vedremo cosa questo comporta in termini di informazioni che devono essere trasmesse in ogni ETP in aggiunta al set di percorsi che abbiamo prima introdotto. Essendo questo l'ultimo aspetto affrontato, descriveremo di seguito nel dettaglio come è fatto un messaggio di ETP.

Rappresentazione gerarchica degli ID

Abbiamo detto che un messaggio di ETP contiene, oltre alla lista di ID dei nodi che ha percorso, anche un set P di percorsi; ognuno dei percorsi è a sua volta una lista di ID di nodi tra loro connessi fino ad una certo nodo destinazione. Aggiungiamo ora che ogni ID può in effetti rappresentare o un singolo nodo oppure un g-nodo, diciamo genericamente un g-nodo di livello i da 0 a l-1. Anche la destinazione di ognuno dei percorsi nel set P è un g-nodo.

Ogni g-nodo in queste liste (sia la destinazione che i passi del percorso) è espresso in forma di coordinate gerarchiche che sono valide per il nodo che ha prodotto l'oggetto ETP.

Informazioni aggiuntive sulla destinazione

Aggiungiamo inoltre che ogni percorso del set P contiene alcune informazioni aggiuntive riguardo il g-nodo che è la sua destinazione. Contiene il suo fingerprint e il numero di nodi stimati nel suo interno.

Minimo comune g-nodo e massimo distinto g-nodo

Introduciamo due definizioni che ci saranno utili nel resto del capitolo. Siano due nodi distinti n e v.

Il nodo v ha indirizzo vl-1·...·v1·v0. Vale a dire che v ha identificativo v0 all'interno del suo g-nodo di livello 1, il quale ha identificativo v1 all'interno del suo g-nodo di livello 2, ... fino al suo g-nodo di livello l-1 che ha identificativo vl-1 all'interno dell'unico g-nodo di livello l che costituisce l'intera rete.

Il nodo n ha indirizzo nl-1·...·n1·n0 con analogo significato.

Sia i, con i < l, il più grande intero tale che vini, cioè il livello più alto a cui v ed n non appartengono allo stesso g-nodo.

Definiamo minimo comune g-nodo tra v e n il g-nodo vi+1 = ni+1, cioè il più piccolo g-nodo che contiene sia n sia v. Potrebbe trattarsi del g-nodo a livello l che costituisce l'intera rete. Siccome si tratta di uno dei g-nodi di n e anche uno dei g-nodi di v, per entrambi i nodi questo può essere rappresentato semplicemente con l'intero i+1.

Definiamo massimo distinto g-nodo di v per n il g-nodo vi, cioè il più grande g-nodo che contiene v ma non contiene n. Per il nodo n questo può essere rappresentato come coordinata gerarchica a livello i. Invece per il nodo v può essere rappresentato semplicemente con l'intero i.

Simmetricamente abbiamo che il massimo distinto g-nodo di n per v è il g-nodo ni, cioè il più grande g-nodo che contiene n ma non contiene v.

Percorso a livelli crescenti

Si consideri che un ETP è un ATP, cioè è aciclico. Quando il nodo n riceve dal nodo v un ETP m che contiene già il suo ID nella lista del percorso seguito, subito n ignora l'ETP m. Bisogna considerare che in questa frase con il termine ID di n si intende l'identificativo del massimo distinto g-nodo di n per v.

Come conseguenza del fatto che non possono essere mantenuti o trasmessi percorsi ciclici a nessun livello della gerarchia, le liste di hop percorsi sono sempre in una forma in cui i livelli salgono man mano che si avanza. Infatti nel momento in cui un ATP esce da un g-nodo non può più rientrarvi. Ad esempio potrei avere il percorso (0, 2) - (0, 5) - (1, 3) - (1, 7) - (2, 2) - (4, 2) - (4, 3) - (5, 3) - (5, 6). In questa rappresentazione delle coordinate il primo numero indica il livello e il secondo l'identificativo.

Definizione di grouping rule

Sia m un ETP che il nodo n riceve dal nodo v. Definiamo la grouping rule come l'elaborazione che il nodo n deve fare su una lista di hop contenuta in m affinché tale lista, dapprima coerente con i g-nodi a cui appartiene v nei vari livelli, diventi coerente con i g-nodi a cui appartiene n.

Sia i con il il livello del minino comune g-nodo tra n e v. Se i > 1 questo significa che il nodo v e il nodo n sono bordernodi di g-nodi diversi, cioè che le informazioni del percorso interno al g-nodo di v distinto dal g-nodo di n non sono interessanti per n. Quindi n potrà rimuovere tutti gli hop iniziali che hanno livello inferiore ad i-1. Poi in testa va aggiunto l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di v.

Se invece il minimo comune g-nodo tra n e v è v1, cioè n e v sono nello stesso g-nodo di livello 1, allora tutti gli indirizzi che sono nella mappa gerarchica di v possono essere nella mappa gerarchica di n. Quindi n non rimuove nessun hop nella lista, ma solo vi aggiunge in testa l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di v, che sarà del tipo (0, v0).

Definizione di acyclic rule

Sia lst una lista di hop coerente con i g-nodi a cui appartiene v. Definiamo la acyclic rule come l'elaborazione che permette al nodo v di stabilire se in lst è presente l'identificativo di uno dei suoi g-nodi, cioè se questo percorso è ciclico a qualsiasi livello della gerarchia.

L'implementazione è banale. Va effettuata su tutti i livelli. Il nodo v sa di aver ricevuto questo percorso dal nodo n, quindi, avendo calcolato i il livello del minimo comune g-nodo tra n e v, potrebbe limitarsi a verificare il livello i-1, poiché in teoria il nodo n ha già rimosso i percorsi con cicli nei livelli superiori. Comunque il nodo v non si fida di questo e verifica tutti i livelli da i-1 in su. Quelli inferiori a i-1 sono stati rimossi dalla grouping rule.

Contenuto e forma di un messaggio ETP

Un messaggio ETP m inviato da un nodo v contiene:

  • L'indirizzo del nodo v, come elenco vl-1·...·v1·v0.

  • La lista dei g-nodi percorsi dall'ETP sotto forma di coordinate gerarchiche valide per il nodo v.

  • Un set di percorsi P che il nodo v intende comunicare ai suoi vicini. Per ogni percorso pP:

    • La lista dei g-nodi del percorso p; questa comprende il g-nodo destinazione d; ogni g-nodo è espresso sotto forma di coordinate gerarchiche valide per il nodo v.

    • Il fingerprint del g-nodo d come riportato dal percorso p.

    • Il numero di nodi stimato nel g-nodo d come riportato dal percorso p.

    • Il costo totale del percorso da v a d.

Si consideri il nodo n vicino di v che riceve questo messaggio m tramite un suo arco. Oltre al set di percorsi P contenuto in m, il nodo n intrinsecamente riceve un percorso verso il massimo distinto g-nodo di v per n. Sia i il livello di questo g-nodo, indichiamo questo g-nodo con vi. Il nodo n vorrà memorizzare nella sua mappa questo percorso e dovrà quindi essere informato sulle informazioni aggiuntive di cui abbiamo parlato in precedenza, cioè il fingerprint di vi e il numero di nodi all'interno di vi. Siccome il nodo v quando trasmette l'ETP m non conosce il livello i (poiché il messaggio m potrebbe essere inviato in broadcast e raggiungere diversi vicini) allora v dovrà aggiungere ad m queste informazioni per tutti i g-nodi a cui appartiene ad ogni livello. Quindi il messaggio m contiene anche:

  • Per ogni livello i da 0 a l-1:

    • Il fingerprint del g-nodo vi.

    • Il numero di nodi stimato all'interno del g-nodo vi.

Processazione di un set di ETP

Il seguente algoritmo per processare un set di ETP viene eseguito dal nodo n in queste possibili circostanze:

  • Il nodo n è appena entrato in una rete e quindi ha chiesto un ETP a tutti i suoi vicini.

  • Il nodo n ha rilevato un nuovo arco a verso un vicino v e quindi ha chiesto un ETP a v.

  • Il nodo n ha rilevato il cambio di costo in un arco a_changed e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso tra gli argomenti di questo algoritmo ho anche l'arco a_changed che ha avuto una variazione.

  • Il nodo n ha rilevato la rimozione di un arco a_removed e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso prima di iniziare questo algoritmo, il nodo n ha rimosso dalla sua mappa tutti i percorsi che sfruttavano l'arco a_removed.

  • Il nodo n ha ricevuto un ETP inviato in broadcast da un suo vicino.

Pre-processazione dei percorsi in un ETP ricevuto

Sia m un ETP che il nodo n riceve dal nodo v attraverso l'arco a.

Il nodo n calcola il livello i del minimo comune g-nodo tra n e v.

Il nodo n esamina la lista di hop percorsi da m. Per prima cosa esegue la Grouping Rule su tale lista per renderla coerente con i g-nodi a cui n appartiene. Poi esegue la Acyclic Rule sulla lista, e se vede che m era già passato per il mio nodo (o g-nodo) lo ignora del tutto.

Infine n esamina il set di percorsi P contenuto in m, ma deve renderli coerenti con i suoi g-nodi. Ecco come realizza questo:

  • Il nodo n elimina dal set P tutti i percorsi che hanno una destinazione di livello inferiore a i-1.

  • Per ogni percorso p rimasto in P il nodo n esegue la Grouping Rule.

  • Per ogni percorso p in P il nodo n esegue la Acyclic Rule e se vede che il percorso ha fatto un ciclo lo rimuove da P.

  • Il nodo n aggiunge a P il percorso verso vi-1. con costo null e fingerprint e numero di nodi così come riportati in m.

  • Per tutti i percorsi p del set P, che sono istanze di EtpPath, il nodo n crea una istanza di NodePath q associando al percorso p l'arco a. Mette q in un set globale che chiamiamo Q.

Variazioni nella mappa di n

Quando abbiamo descritto la gestione degli eventi che portano a variazioni nel grafo della rete, abbiamo più volte usato diciture quali "n aggiorna la sua mappa" oppure "mette in P i percorsi che nella sua mappa hanno subito variazioni". Qui descriviamo meglio come avvengono questi passaggi.

Il nodo n, dopo aver processato il set di ETP ricevuti, si trova infine con un set di percorsi nuovi che chiamiamo Q. Indichiamo con M l'insieme dei percorsi che già prima il nodo n conosceva, cioè la sua mappa.

  • Il nodo n prepara una lista P, inizialmente vuota, di percorsi che andranno segnalati ai vicini a cui si inoltrerà l'ETP.

  • Il nodo n prepara una lista B, inizialmente vuota, di destinazioni per le quali alla fine intende iniziare un nuovo flood. Questo per la regola di primo rilevamento di split.

  • Il nodo n raggruppa i percorsi contenuti in Q per destinazione. Per ogni destinazione d:

    • Sia Qd l'insieme dei percorsi nuovi verso d.

    • Sia Md l'insieme dei percorsi precedentemente noti verso d.

    • Il nodo n prepara una lista F ’ con tutti i fingerprint distinti che conosceva per il g-nodo d.

    • Il nodo n prepara una lista Od, inizialmente vuota, di percorsi verso d che sono correnti e andranno ordinati.

    • Il nodo n prepara una lista Vd, inizialmente vuota, di percorsi verso d che hanno subito una variazione.

    • Il nodo n prepara una lista Sd, inizialmente vuota, di segnali da emettere.

    • Per ogni p’ ∈ Md:

      • Il nodo n controlla se esiste un p’’ ∈ Qd che abbia la stessa sequenza di passi. Questo confronto fra p’ e p’’, che sono entrambi istanze di NodePath, avviene con il metodo hops_are_equal che tiene conto anche dell'arco verso il vicino. Se esiste:

        • Siamo di fronte a un aggiornamento sulle informazioni relative ad un percorso che era già noto. 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. Infatti se la modifica è non cruciale e non rilevante si preferisce ignorarla per ridurre il traffico di rete.
        • Se l'aggiornamento è giudicato rilevante:
          • p’’ viene scartato da Qd.

          • p’’ viene aggiunto a Od.

          • p’’ viene aggiunto a Vd.

        • Altrimenti:
          • p’’ viene scartato da Qd.

          • p’ viene aggiunto a Od.

          • Se p’.arc.i_qspn_equals(a_changed):

            • p’ viene aggiunto a Vd.

      • Altrimenti:
        • p’ viene aggiunto a Od.

        • Se p’.arc.i_qspn_equals(a_changed):

          • p’ viene aggiunto a Vd.

    • Tutti i percorsi rimasti in Qd vengono aggiunti a Od.

    • Poi il nodo n ordina Od in base al costo crescente. Esegue su questa lista l'algoritmo descritto nel documento percorsi disgiunti per scartare quelli non sufficientemente disgiunti e tenere solo i max_paths più rapidi. Nel fare questo deve tener conto del requisito di mantenere per la destinazione d e per ogni proprio vicino v, almeno 1 percorso, se esiste, indipendentemente dal valore di max_paths e dalle regole di disgiunzione, verso d che non contiene v tra i suoi passaggi. Ed anche del requisito di mantenere per la destinazione d almeno 1 percorso per ogni diverso fingerprint di d che gli viene segnalato. Alla fine in Od non possono rimanere percorsi con costo = dead.

    • Infine il nodo n sulla base del contenuto delle liste di appoggio prima descritte (Od, Md e Vd) popola la lista P che andrà a comporre l'ETP che sarà inoltrato ai vicini e allo stesso tempo compone il set Sd dei segnali da emettere per questa destinazione. Illustriamo l'algoritmo di questa operazione, tenendo conto che i confronti tra istanze di NodePath anche qui vanno fatti con il metodo hops_are_equal:

      • Per ogni pOd:

        • Se pMd:

          • Metti p in P.

          • Prepara un segnale di path_added e aggiungilo al set Sd.

      • Per ogni pMd:

        • Se pOd:

          • p2 = copia di p.

          • p2.cost = dead.

          • Metti p2 in P.

          • Prepara un segnale di path_removed e aggiungilo al set Sd.

        • Altrimenti:
          • Se pVd:

            • Metti p in P.

            • Prepara un segnale di path_changed e aggiungilo al set Sd.

    • Il nodo n sostituisce Od al vecchio Md. Cioè:

      • Se Md = ∅ e Od ≠ ∅, allora inserisce in testa al set Sd il segnale destination_added.

      • Se Md ≠ ∅ e Od = ∅, allora aggiunge in coda al set Sd il segnale destination_removed.

      • Rimuove da M tutti i percorsi verso d e vi aggiunge tutti i percorsi che ora sono in Od.

      • Emette tutti i segnali che sono in Sd.

    • Il nodo n prepara una lista F ’’ con tutti i fingerprint distinti che conosce adesso per il g-nodo d.

    • Valuta dal confronto tra F ’ ed F ’’ se è necessario iniziare un nuovo flood di ETP con i percorsi per d per la regola di primo rilevamento di split. Cioè:

      • Se F ’’.size > 1:

        • Per ogni fpF ’’:

          • Se fpF ’:

            • Metti d in B.

            • Esci dal ciclo.

Ora la mappa di n è aggiornata. Inoltre abbiamo in P l'elenco dei percorsi nella mappa di n che hanno subito variazioni.

Infine abbiamo in B tutte le destinazioni per cui si ritiene necessario inviare un nuovo flood. Quindi:

  • Se B ≠ ∅:

    • Il nodo n prepara un nuovo ETP con tutti i percorsi che conosce verso le destinazioni dB. Lo invia a tutti i suoi vicini.

Variazioni nei propri g-nodi

Dopo aver completato un aggiornamento della propria mappa, il nodo n aggiorna anche le informazioni relative ai propri g-nodi, cioè fingerprint e numero di nodi all'interno. Se ci sono state variazioni n se ne accorge e questo è importante per decidere se l'ETP ricevuto va inoltrato ai suoi vicini.

Il nodo n procede così:

  • Sia my_fingerprints[i] il valore che n conosce attualmente come fingerprint del suo g-nodo di livello i.

  • Sia my_nodes_inside[i] il valore che n conosce attualmente come numero di nodi interni al suo g-nodo di livello i.

  • changes_in_my_gnodes = False.

  • Per ogni livello i da 1 a l:

    • FP = nuovo set vuoto.

    • NN = 0.

    • Per ogni destinazione d di livello i-1 nella mia mappa:

      • fpd = null.

      • Per ogni NodePath p in d:

        • fpd,p = fingerprint di d come riportato da p.

        • Se fpd = null:

          • fpd = fpd,p .

        • Altrimenti:
          • Se fpdfpd,p :

            • Se fpd è meno anziano di fpd,p :

              • fpd = fpd,p .

      • Aggiungi fpd al set FP.

      • Sia p la NodePath più veloce verso d.

      • nnd = numero nodi interni a d come riportato da p.

      • Somma nnd a NN.

    • new_fp = my_fingerprints[i-1] .i_qspn_construct( FP ).

    • Se new_fpmy_fingerprints[i]:

      • my_fingerprints[i] = new_fp.

      • changes_in_my_gnodes = True.

      • Emetti segnale changed_fp a livello i.

    • new_nn = my_nodes_inside[i-1] + NN.

    • Se new_nnmy_nodes_inside[i]:

      • my_nodes_inside[i] = new_nn.

      • changes_in_my_gnodes = True.

      • Emetti segnale changed_nodes_inside a livello i.

Ora abbiamo in changes_in_my_gnodes se sono state apportate variazioni alle informazioni relative ai g-nodi di n.

Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete (last edited 2016-07-28 08:52:21 by lukisi)