Differences between revisions 3 and 5 (spanning 2 versions)
Revision 3 as of 2014-12-02 19:01:28
Size: 10767
Editor: lukisi
Comment:
Revision 5 as of 2014-12-12 18:49:09
Size: 13214
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 60: Line 60:
<<Anchor(EtpRicevuto)>>
Line 66: Line 68:
  * La destinazione era nota, ma questa rotta contiene degli hop intermedi diversi dalle rotte già note.   * La destinazione era nota, ma questa rotta si differenzia rispetto alle altre rotte verso la stessa destinazione per gli hop intermedi.
Line 68: Line 70:
 * Una rotta viene rimossa. Può accadere perché nelle rotte scritte nell'ETP vedo una rotta (che avevo già nella mia mappa) con costo DeadREM: significa che un arco nella path è venuto a mancare. Oppure può accadere perché altre rotte verso la stessa destinazione sono state scoperte con costo inferiore e questa è diventata non disgiunta o oltre il numero massimo di rotte da memorizzare (vedi documento [[Netsukuku/ita/docs/ModuloQSPN/RotteDisgiunte|rotte disgiunte]]).
Line 73: Line 76:
'''''Evento periodical-update''''': Sia il nodo A ∈ G. Sono passati 10 minuti dal momento in cui A è diventato maturo in G oppure dal precedente evento periodical-update.

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.

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

----
Line 77: Line 87:
==== Lettura delle informazioni in un ETP ====
Sia il nodo A ∈ G che riceve un ETP.
== Lettura delle informazioni in un ETP ==
==== Liste di hop percorsi ====
Un ETP contiene alcune liste di hop percorsi: una lista indica il percorso che ha seguito l'ETP da quando è stato generato a quando ci ha raggiunto; inoltre per ogni path contenuta come informazione dentro l'ETP, una lista indica il contenuto stesso della path.
Line 80: Line 91:
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. In entrambi i casi queste liste sono espresse in forma di coordinate gerarchiche che sono valide per il nodo che ha prodotto l'oggetto ETP.
Line 82: Line 93:
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: Come conseguenza del fatto che non possono essere rilevate rotte cicliche 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 la path (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.
Line 84: Line 95:
 * Un ETP arriva ad A da un certo suo vicino N interno ad un g-nodo N~-^1^-~ a sua volta interno a N~-^2^-~ ... 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~-^0^-~ a N~-^l^-~ il fingerprint e il numero di nodi interni. ==== Definizione di grouping rule ====
Pensiamo ora ad un ETP che viene trasmesso da un nodo N ad un suo vicino A. Definiamo la grouping rule come l'elaborazione che il nodo A deve fare su una lista di hop contenuta nell'ETP affinché tale lista, dapprima coerente con i g-nodi a cui appartiene N nei vari livelli, diventi coerente con i g-nodi a cui appartiene A.

Il nodo N è all'interno di un g-nodo N~-^1^-~ a sua volta all'interno di N~-^2^-~, e così via fino a N~-^l^-~.

Il nodo A ha in comune con N (almeno N~-^l^-~) fino ad un certo g-nodo N~-^i^-~. Se ''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''. Poi in testa va aggiunto l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N.

Se invece il minimo comune g-nodo tra A e N è N~-^1^-~, 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 nella lista, ma solo vi aggiunge in testa l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N, che sarà del tipo (0, x).

==== Interpretazione dei dati nell'ETP ====
Sia ''m'' un ETP che il nodo A riceve.

A esamina la lista di hop percorsi da ''m''. 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 ''m'' era già passato per il mio nodo (o cluster) lo ignoro del tutto.

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

 * ''m'' arriva ad A da un certo suo vicino N interno ad un g-nodo N~-^1^-~ a sua volta interno a N~-^2^-~ ... 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. L'ETP ''m'', oltre alle rotte così come sono viste da N, contiene per i g-nodi da N~-^0^-~ a N~-^l^-~ il fingerprint e il numero di nodi interni.
Line 86: Line 113:
 * 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~-^i^-~ 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~-^1^-~, 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^-~.
 * Per ogni rotta nel set R ora la destinazione è espressa come coordinata gerarchica valida per il nodo A; il nodo A esegue la Grouping Rule sulla lista di hop intermedi di ogni singola rotta.
 * Il nodo A rimuove dal set R le rotte che contengono nella lista di hop intermedi il suo identificativo a livello ''i''. Questa situazione dovrebbe in teoria essere possibile solo per ''i'' = livello del minimo comune g-nodo tra il nodo A e il vicino N. Questa è la Acyclic Rule.
 * Il nodo A aggiunge al set R la rotta verso N~-^i-1^-~ con costo NullREM e fingerprint e numero di nodi così come riportati in ''m'' per N~-^i-1^-~.
 * Per tutte le rotte del set R al costo della path viene sommato il costo dell'arco con N.

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 si differenzia rispetto alle altre rotte verso la stessa destinazione per gli hop intermedi.
  • 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.
  • Una rotta viene rimossa. Può accadere perché nelle rotte scritte nell'ETP vedo una rotta (che avevo già nella mia mappa) con costo DeadREM: significa che un arco nella path è venuto a mancare. Oppure può accadere perché altre rotte verso la stessa destinazione sono state scoperte con costo inferiore e questa è diventata non disgiunta o oltre il numero massimo di rotte da memorizzare (vedi documento rotte disgiunte).

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.

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

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.

Il nodo A 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 stabile.

Lettura delle informazioni in un ETP

Liste di hop percorsi

Un ETP contiene alcune liste di hop percorsi: una lista indica il percorso che ha seguito l'ETP da quando è stato generato a quando ci ha raggiunto; inoltre per ogni path contenuta come informazione dentro l'ETP, una lista indica il contenuto stesso della path.

In entrambi i casi queste liste sono espresse in forma di coordinate gerarchiche che sono valide per il nodo che ha prodotto l'oggetto ETP.

Come conseguenza del fatto che non possono essere rilevate rotte cicliche 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 la path (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

Pensiamo ora ad un ETP che viene trasmesso da un nodo N ad un suo vicino A. Definiamo la grouping rule come l'elaborazione che il nodo A deve fare su una lista di hop contenuta nell'ETP affinché tale lista, dapprima coerente con i g-nodi a cui appartiene N nei vari livelli, diventi coerente con i g-nodi a cui appartiene A.

Il nodo N è all'interno di un g-nodo N1 a sua volta all'interno di N2, e così via fino a Nl.

Il nodo A ha in comune con N (almeno Nl) fino ad un certo g-nodo Ni. Se 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. Poi in testa va aggiunto l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N.

Se invece il minimo comune g-nodo tra A e N è N1, 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 nella lista, ma solo vi aggiunge in testa l'hop ottenuto come rappresentazione in coordinate gerarchiche dell'indirizzo di N, che sarà del tipo (0, x).

Interpretazione dei dati nell'ETP

Sia m un ETP che il nodo A riceve.

A esamina la lista di hop percorsi da m. 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 m era già passato per il mio nodo (o cluster) lo ignoro del tutto.

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

  • m arriva ad A da un certo suo vicino N interno ad un g-nodo N1 a sua volta interno a N2 ... Nl. 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. L'ETP m, oltre alle rotte così come sono viste da N, contiene per i g-nodi da N0 a Nl il fingerprint e il numero di nodi interni.

  • Il nodo A ha in comune con N (almeno Nl) fino ad un certo g-nodo Ni. 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; il nodo A esegue la Grouping Rule sulla lista di hop intermedi di ogni singola rotta.
  • Il nodo A rimuove dal set R le rotte che contengono nella lista di hop intermedi il suo identificativo a livello i. Questa situazione dovrebbe in teoria essere possibile solo per i = livello del minimo comune g-nodo tra il nodo A e il vicino N. Questa è la Acyclic Rule.

  • Il nodo A aggiunge al set R la rotta verso Ni-1 con costo NullREM e fingerprint e numero di nodi così come riportati in m per Ni-1.

  • Per tutte le rotte del set R al costo della path viene sommato il costo dell'arco con N.

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