Differences between revisions 12 and 22 (spanning 10 versions)
Revision 12 as of 2015-04-08 12:38:21
Size: 24501
Editor: lukisi
Comment:
Revision 22 as of 2016-07-28 08:52:21
Size: 101
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
= Modulo QSPN - Esplorazione della rete =
<<TableOfContents(4)>>

== 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, un identificativo univoco dell'arco ''α'' attraverso il quale lo ha ricevuto e il costo dell'arco ''c ( α )'' 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 [[Netsukuku/ita/docs/ModuloQSPN/AnalisiFunzionale#requisiti|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''.

<<Anchor(EtpRicevuto)>>

'''''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 già detto che un generico TP contiene la lista degli ID dei nodi che ha percorso, e per ognuno di questi nodi contiene anche l'identificativo dell'arco attraverso il quale il nodo seguente ha ricevuto il TP. Un percorso non è altro che questa lista letta al contrario.

Abbiamo già detto, inoltre, che un messaggio di ETP contiene, oltre alla lista di ID dei nodi e archi che ha percorso, anche un set ''P'' di percorsi; ognuno dei percorsi è a sua volta una lista di ID di nodi e archi fino ad un 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 percorso ''p'' è composto di due sequenze di ''k'' elementi:

 * ''p.hops'' : sequenza di k g-nodi.
 * ''p.arcs'' : sequenza di k identificativi di arco, dove arcs[0] indica l'arco che congiunge il nodo corrente a hops[0], e arcs[j] indica l'arco che congiunge hops[j-1] a hops[j].

Ogni g-nodo in queste liste è espresso in forma di coordinate gerarchiche che sono valide per il nodo che ha prodotto l'oggetto ETP. Gli identificativi degli archi in queste liste sono gli effettivi archi che collegano un border-nodo del g-nodo precedente ad un border-nodo del g-nodo successivo.

=== 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 ''v~-,,l-1,,-~·...·v~-,,1,,-~·v~-,,0,,-~''. Vale a dire che ''v'' ha identificativo ''v~-,,0,,-~'' all'interno del suo g-nodo di livello 1, il quale ha identificativo ''v~-,,1,,-~'' all'interno del suo g-nodo di livello 2, ... fino al suo g-nodo di livello ''l-1'' che ha identificativo ''v~-,,l-1,,-~'' all'interno dell'unico g-nodo di livello ''l'' che costituisce l'intera rete.

Il nodo ''n'' ha indirizzo ''n~-,,l-1,,-~·...·n~-,,1,,-~·n~-,,0,,-~'' con analogo significato.

Sia ''i'', con ''i'' < ''l'', il più grande intero tale che ''v~-,,i,,-~'' ≠ ''n~-,,i,,-~'', 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 ''v~-,,i+1,,-~'' = ''n~-,,i+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 ''v~-,,i,,-~'', 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 ''n~-,,i,,-~'', 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.

<<Anchor(GroupingRule)>>

=== Definizione di grouping rule ===
Sia ''m'' un ETP che il nodo ''n'' riceve dal nodo ''v''. Sia ''lst'' una lista di hop contenuta in ''m'', vale a dire o la lista che rappresenta un percorso ''p'' ∈ ''P'' oppure la lista di hop percorsi dallo stesso ETP ''m''.

Definiamo la ''grouping rule'' come l'elaborazione che il nodo ''n'' deve fare su ''lst'' 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 ''i'' ≤ ''l'' il livello del minino comune g-nodo tra ''n'' e ''v''.

Se ''i'' = 1, cioè se il minimo comune g-nodo tra ''n'' e ''v'' è ''v~-,,1,,-~'', 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'' considera validi tutti gli hop della lista; inoltre vi aggiunge in testa l'hop composto dal massimo distinto g-nodo di ''v'' per ''n'' - che sarà del tipo (0, v~-,,0,,-~) - e dall'arco tramite il quale ''n'' ha ricevuto l'ETP.

Se invece ''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'' rimuoverà tutti gli hop iniziali che rappresentano un g-nodo di livello inferiore ad ''i-1''; di seguito vi aggiunge in testa l'hop composto dal massimo distinto g-nodo di ''v'' per ''n'' e dall'arco tramite il quale ''n'' ha ricevuto l'ETP.

Bisogna aggiungere, in questa seconda situazione, che la rimozione degli hop iniziali che rappresentano un g-nodo di livello inferiore ad ''i-1'' può portare al completo svuotamento di ''lst''. Se si verifica questo caso, bisogna distinguere se ''lst'' è un percorso ''p'' ∈ ''P'' oppure è la lista di hop percorsi da ''m''. Si consideri che un percorso verso una destinazione interna ad un g-nodo ''g'' non è interessante per il nodo ''n'' ∉ ''g''. Invece un ETP originato in ''g'' può essere che porti variazioni a percorsi che escono da ''g'', quindi può essere nel complesso interessante per il nodo ''n'' ∉ ''g''.

Se non resta alcun elemento in ''lst'', dove ''lst'' è un percorso ''p'' ∈ ''P'', allora l'intera lista viene scartata.

Se non resta alcun elemento in ''lst'', dove ''lst'' è la lista di hop percorsi da ''m'', allora la lista viene sostituita con una lista contenente solo l'hop composto dal massimo distinto g-nodo di ''v'' per ''n'' e dall'arco tramite il quale ''n'' ha ricevuto l'ETP.

<<Anchor(AcyclicRule)>>

=== 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.

Se la regola non è soddisfatta, cioè se il percorso è ciclico, bisogna di nuovo distinguere se ''lst'' è un percorso ''p'' ∈ ''P'' oppure è la lista di hop percorsi da ''m''. Se si tratta di un percorso ''p'' ∈ ''P'' tale percorso viene scartato. Se si tratta della lista di hop percorsi da ''m'' allora l'intero ETP viene ignorato.

=== Contenuto e forma di un messaggio ETP ===
Un messaggio ETP ''m'' inviato da un nodo ''v'' deve contenere:

 * L'indirizzo del nodo ''v'', come elenco ''v~-,,l-1,,-~·...·v~-,,1,,-~·v~-,,0,,-~''.
 * La lista dei g-nodi percorsi dall'ETP sotto forma di due sequenze:
  * hops: sequenza di k g-nodi sotto forma di coordinate gerarchiche valide per il nodo ''v''.
  * arcs: sequenza di k identificativi di arco, dove arcs[0] indica l'arco che congiunge il nodo v a hops[0], e arcs[j] indica l'arco che congiunge hops[j-1] a hops[j].
 * Un set di percorsi ''P'' che il nodo ''v'' intende comunicare ai suoi vicini. Per ogni percorso ''p'' ∈ ''P'':
  * La lista dei g-nodi del percorso ''p''; questa comprende il g-nodo destinazione ''d''; anche questa lista è espressa come due sequenze:
   * p.hops: sequenza di k~-,,p,,-~ g-nodi sotto forma di coordinate gerarchiche valide per il nodo ''v''.
   * p.arcs: sequenza di k~-,,p,,-~ identificativi di arco, dove arcs[0] indica l'arco che congiunge il nodo v a hops[0], e arcs[j] indica l'arco che congiunge hops[j-1] a hops[j].
  * 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''.

==== Informazioni aggiuntive riguardo gli archi ====
Quando un ETP abbandona un g-nodo ''g'' di livello ''i'' esso deve perdere tutte le informazioni interne al g-nodo ''g''. Infatti ogni nodo ''n'' che lo riceverà in seguito con ''n'' ∉ ''g'', considera tutti i nodi interni a ''g'' come raggruppati in un unico vertice. Ogni percorso noto a ''n'', che tocca il vertice ''g'', avrà come successivo hop un altro vertice ''h'', di livello ''i'' o maggiore. Il passaggio da ''g'' ad ''h'' avviene attraverso un arco che è un arco realizzato da uno dei border-nodi di ''g''.

Come fa il nodo ''n'' a distinguere i diversi possibili percorsi che toccano in sequenza i vertici ''g'' ed ''h''? Il nodo ''n'' può distinguere tanti diversi percorsi che toccano prima ''g'' e poi ''h'' quanti sono gli archi che congiungono border-nodi di ''g'' a border-nodi di ''h''. Se però un percorso ''p1'' e un percorso ''p2'' sono composti da hops diversi internamente al g-nodo ''g'' per raggiungere uno stesso arco ''α'' che collega il g-nodo ''g'' al g-nodo ''h'', allora i 2 percorsi ''p1'' e ''p2'' sono indistinguibili per il nodo ''n''.

Di conseguenza, il nodo ''n'' ∉ ''g'' è interessato a ricevere informazioni su percorsi che toccano ''g'' e poi escono da ''g'' attraverso l'arco ''α'' solo se si tratta del miglior percorso (con costo minore) che esce da ''g'' attraverso l'arco ''α''. Quindi il messaggio ''m'' prodotto da ''v'' deve contenere anche:

 * Per ogni percorso ''p'' ∈ ''P'':
  * Per ogni livello ''i'' da 1 a ''l-1'':
   * Un booleano che dice se ''p'' è interessante per il nodo ''n'' ∉ ''v,,i,,''.

La valorizzazione di questo booleano procede così:

 * Per ogni percorso ''p'' ∈ ''P'':
  * Per ogni livello ''i'' da 1 a ''l-1'':
   * Se la destinazione di ''p'' ha livello maggiore o uguale a ''i'', cioè p.hops.last().lvl ≥ i:
    * Sia ''j'' il più piccolo valore tale che p.hops[j].lvl ≥ i.
    * Il booleano vale True se e solo se è questo il miglior percorso da ''v'' verso p.hops[j] tramite p.arcs[j].
   * Altrimenti:
    * Il booleano vale False. Infatti il percorso ''p'' verrà comunque scartato da ''n'' per la grouping rule.

==== Informazioni aggiuntive riguardo la destinazione ====
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 ''v~-,,i,,-~''. 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 ''v~-,,i,,-~'' e il numero di nodi all'interno di ''v~-,,i,,-~''. 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'' prodotto da ''v'' deve contenere anche:

 * Per ogni livello ''i'' da 0 a ''l-1'':
  * Il fingerprint del g-nodo ''v~-,,i,,-~''.
  * Il numero di nodi stimato all'interno del g-nodo ''v~-,,i,,-~''.
[[https://github.com/lukisi/documentation/blob/master/ita/ModuloQspn/EsplorazioneRete.md|Redirect]]

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