Differences between revisions 4 and 5
Revision 4 as of 2014-11-26 10:19:24
Size: 9502
Editor: lukisi
Comment:
Revision 5 as of 2014-11-27 09:44:49
Size: 9683
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:
Il modulo realizza lo scambio di ETP con i vicini del nodo per l'esplorazione della rete (vedi documento [[Netsukuku/docs/ModuloQSPN/EsplorazioneRete|esplorazione]]).
Line 3: Line 4:
Il modulo realizza lo scambio di ETP con i vicini del nodo per l'esplorazione della rete
(vedi documento esplorazione).

L'obiettivo è di mantenere per ogni destinazione fino a ''n'' percorsi disgiunti,
che siano i più rapidi (vedi documento rotte disgiunte).
L'obiettivo è di mantenere per ogni destinazione fino a ''n'' percorsi disgiunti, che siano i più rapidi (vedi documento [[Netsukuku/docs/ModuloQSPN/RotteDisgiunte|rotte disgiunte]]).
Line 10: Line 7:
La rete è strutturata gerarchicamente in ''l'' livelli. Il livello 0 rappresenta il singolo nodo. Nel livello più alto ''l'' è presente un solo gruppo che costituisce tutta la rete.
Line 11: Line 9:
La rete è strutturata gerarchicamente in ''l'' livelli. Il livello 0 rappresenta
il singolo nodo. Nel livello più alto ''l'' è presente un solo gruppo che
costituisce tutta la rete.
Ogni gruppo di livello ''i'' contiene un numero massimo fissato di gruppi di livello ''i-1''.
Line 15: Line 11:
Ogni gruppo di livello ''i'' contiene un numero massimo fissato di gruppi di
livello ''i-1''.
Il numero massimo di elementi di un gruppo è detto ''gsize''. Ogni livello da ''0'' a ''l-1'' può avere un valore ''gsize'' diverso. Chiamiamo ''gsize(i)'' il numero massimo di elementi in un gruppo di livello ''i+1''.
Line 18: Line 13:
Il numero massimo di elementi di un gruppo è detto ''gsize''. Ogni livello da
''0'' a ''l-1'' può avere un valore ''gsize'' diverso. Chiamiamo ''gsize(i)'' il
numero massimo di elementi in un gruppo di livello ''i+1''.
Ogni gruppo di livello ''i'' ha un identificativo che lo individua univocamente all'interno del suo gruppo di livello ''i+1''. Tale identificativo è un numero intero da ''0'' a ''gsize(i) - 1''.
Line 22: Line 15:
Ogni gruppo di livello ''i'' ha un identificativo che lo individua univocamente
all'interno del suo gruppo di livello ''i+1''. Tale identificativo è un numero
intero da ''0'' a ''gsize(i) - 1''.

(vedi documento "Documents/livelli e bits")
(vedi documento [[../LivelliBits|livelli e bits]])
Line 29: Line 18:
Line 32: Line 20:
Per ogni livello della rete in tale mappa sono memorizzati tutti i g-nodi di quel
livello di cui il nodo conosce l'esistenza (e di conseguenza almeno una rotta).
Per ogni livello della rete in tale mappa sono memorizzati tutti i g-nodi di quel livello di cui il nodo conosce l'esistenza (e di conseguenza almeno una rotta).
Line 36: Line 23:
Line 38: Line 26:
  * l'arco da usare come primo hop (istanza dell'interfaccia IQspnArc)
   * tutti i successivi hop del percorso in termini di g-nodi che hanno il g-nodo superiore in comune con questo nodo (istanze di HCoord)
   * il costo della path dal primo hop alla destinazione (escluso il costo dell'arco dal nodo al primo hop)
   * il fingerprint del g-nodo come riportato da questa path;
   * il numero di nodi nel g-nodo come riportato da questa path.
  * l'arco da usare come primo hop (istanza dell'interfaccia IQspnArc)
  * tutti i successivi hop del percorso in termini di g-nodi che hanno il g-nodo superiore in comune con questo nodo (istanze di HCoord)
  * il costo della path dal primo hop alla destinazione (escluso il costo dell'arco dal nodo al primo hop)
  * il fingerprint del g-nodo come riportato da questa path;
  * il numero di nodi nel g-nodo come riportato da questa path.
Line 44: Line 32:
Se per un g-nodo vengono rilevate due path che differiscono per il loro
fingerprint e se questa situazione si mantiene per un certo lasso di tempo,
questo è sintomo dello split del g-nodo in questione. Il modulo lo segnala con
un evento. <<BR>>
Il tempo di tolleranza è direttamente proporzionale alla somma dei costi
associati alle due path che differiscono. Ma essendo l'oggetto costo non del
tutto noto al modulo qspn, viene fornita una callback al modulo per tradurre
questo costo somma in un lasso temporale.
Se per un g-nodo vengono rilevate due path che differiscono per il loro fingerprint e se questa situazione si mantiene per un certo lasso di tempo, questo è sintomo dello split del g-nodo in questione. Il modulo lo segnala con un evento. <<BR>> Il tempo di tolleranza è direttamente proporzionale alla somma dei costi associati alle due path che differiscono. Ma essendo l'oggetto costo non del tutto noto al modulo qspn, viene fornita una callback al modulo per tradurre questo costo somma in un lasso temporale.
Line 54: Line 35:
Il Netsukuku address è l'indirizzo di una risorsa all'interno della rete, ad esempio un nodo o un g-nodo. Devono essere noti i parametri della topologia gerarchica della rete:
Line 55: Line 37:
Il Netsukuku address è l'indirizzo di una risorsa all'interno della rete, ad
esempio un nodo o un g-nodo. Devono essere noti i parametri della topologia
gerarchica della rete:
Line 61: Line 40:
Dati questi parametri, un indirizzo di nodo è composto da un identificativo
per ogni livello da ''levels'' a ''0''. <<BR>>
Invece, un indirizzo di g-nodo di livello ''l'' è composto da un identificativo
per ogni livello da ''levels'' a ''l''.
Dati questi parametri, un indirizzo di nodo è composto da un identificativo per ogni livello da ''levels'' a ''0''. <<BR>> Invece, un indirizzo di g-nodo di livello ''l'' è composto da un identificativo per ogni livello da ''levels'' a ''l''.
Line 66: Line 42:
Per convenienza, diciamo che i parametri della topologia fanno parte
dell'indirizzo.
Per convenienza, diciamo che i parametri della topologia fanno parte dell'indirizzo.
Line 69: Line 44:
Per rappresentare gli indirizzi di nodi e g-nodi definiamo
la classe Naddr. Gli indirizzi di g-nodi li chiamiamo
!PartialNaddr anche se la classe che li istanzia è la stessa.
Per rappresentare gli indirizzi di nodi e g-nodi definiamo la classe Naddr. Gli indirizzi di g-nodi li chiamiamo !PartialNaddr anche se la classe che li istanzia è la stessa.
Line 73: Line 46:
Un nodo conosce, per requisito, il suo indirizzo e da questo può costruire gli
indirizzi che rappresentano ognuno dei g-nodi di cui fa parte.
Un nodo conosce, per requisito, il suo indirizzo e da questo può costruire gli indirizzi che rappresentano ognuno dei g-nodi di cui fa parte.
Line 76: Line 48:
Un nodo può venire a conoscenza di Naddr e !PartialNaddr di qualsiasi punto della
topologia, cioè che non hanno necessariamente in comune il livello direttamente
superiore con uno dei g-nodi di cui il nodo è membro.
Un nodo può venire a conoscenza di Naddr e !PartialNaddr di qualsiasi punto della topologia, cioè che non hanno necessariamente in comune il livello direttamente superiore con uno dei g-nodi di cui il nodo è membro.
Line 80: Line 50:
Nel caso però, in cui un Naddr o !PartialNaddr abbia il suo livello direttamente
superiore in comune con il nodo corrente, tale indirizzo può essere espresso
sotto forma di HCoord (coordinate gerarchiche).
Nel caso però, in cui un Naddr o !PartialNaddr abbia il suo livello direttamente superiore in comune con il nodo corrente, tale indirizzo può essere espresso sotto forma di HCoord (coordinate gerarchiche).
Line 84: Line 52:
Per questo l'interfaccia del proprio indirizzo è distinta dalla interfaccia di
un comune Naddr o !PartialNaddr, perché solo partendo dal proprio indirizzo per
il nodo corrente ha senso fare operazioni che coinvolgano le HCoord.
Per questo l'interfaccia del proprio indirizzo è distinta dalla interfaccia di un comune Naddr o !PartialNaddr, perché solo partendo dal proprio indirizzo per il nodo corrente ha senso fare operazioni che coinvolgano le HCoord.

<<Anchor(requisiti)>>
Line 99: Line 67:
Line 101: Line 68:
  * nuovo g-nodo, rimosso g-nodo.
  * nuova path, path cambiata o path rimossa per un certo g-nodo.
   * rilevamento di un g-nodo splittato.
  * nuovo g-nodo, rimosso g-nodo.
  * nuova path, path cambiata o path rimossa per un certo g-nodo.
  * rilevamento di un g-nodo splittato.
Line 105: Line 72:
  * relativamente ad un g-nodo tutte le path a disposizione per raggiungerlo, con i relativi costi. La path fornita dal metodo pubblico del modulo non è necessariamente l'oggetto usato internamente. L'interfaccia nota all'esterno del modulo (IQspnPath) consente di:
     * leggere la destinazione come IQspnPartialNaddr
     * leggere l'arco come IQspnArc
     * leggere gli hops successivi come IQspnPartialNaddr
     * leggere il costo
     * leggere il numero di nodi
  * relativamente ad un g-nodo tutte le path a disposizione per raggiungerlo, con i relativi costi. La path fornita dal metodo pubblico del modulo non è necessariamente l'oggetto usato internamente. L'interfaccia nota all'esterno del modulo (IQspnPath) consente di:
   * leggere la destinazione come IQspnPartialNaddr
   * leggere l'arco come IQspnArc
   * leggere gli hops successivi come IQspnPartialNaddr
   * leggere il costo
   * leggere il numero di nodi
Line 113: Line 80:
L'identificativo del proprio nodo, come anche l'identificativo di ogni vicino, è un oggetto il cui contenuto non è del tutto noto al modulo qspn. L'interfaccia di questo oggetto nota al modulo (IQspnNodeData) gli consente di:
Line 114: Line 82:
L'identificativo del proprio nodo, come anche l'identificativo di ogni vicino,
è un oggetto il cui contenuto non è del tutto noto al modulo qspn.
L'interfaccia di questo oggetto nota al modulo (IQspnNodeData) gli consente di:
Line 119: Line 84:
 * leggere il Naddr (Netsukuku address) del nodo; l'oggetto Naddr non è del tutto noto a questo modulo, che ne conosce l'interfaccia IQspnMyNaddr;  * leggere il Naddr (Netsukuku address) del nodo; l'oggetto Naddr non è del tutto noto a questo modulo, che ne conosce l'interfaccia IQspnNaddr;
 * leggere il Naddr del nodo come proprio; da usare solo sull'identificativo del proprio nodo; ottiene l'interfaccia IQspn
MyNaddr;
Line 121: Line 87:
  * verificare se due netid si riferiscono alla stessa rete (metodo is_same_network)
   * ...
  * verificare se due netid si riferiscono alla stessa rete (metodo is_same_network)
  * ...
Line 125: Line 91:
L'oggetto che rappresenta gli indirizzi (Naddr) non è del tutto noto a questo modulo, che conosce alcune sue interfacce a seconda dell'uso che può farne.
Line 126: Line 93:
L'oggetto che rappresenta gli indirizzi (Naddr) non è del tutto noto a questo modulo, che
conosce alcune sue interfacce a seconda dell'uso che può farne.

Per il proprio indirizzo il nodo conosce l'interfaccia IQspnMyNaddr, per gli indirizzi
di altri nodi conosce l'interfaccia IQspnNaddr, per gli indirizzi di g-nodi conosce
l'interfaccia IQspnPartialNaddr.
Per il proprio indirizzo il nodo conosce l'interfaccia IQspnMyNaddr, per gli indirizzi di altri nodi conosce l'interfaccia IQspnNaddr, per gli indirizzi di g-nodi conosce l'interfaccia IQspnPartialNaddr.
Line 134: Line 96:
Line 135: Line 98:
  * leggere levels e gsize(l) della rete;
   * leggere pos(l) di questo indirizzo;
  * leggere levels e gsize(l) della rete;
  * leggere pos(l) di questo indirizzo;
Line 138: Line 101:
  * dato un HCoord ottenere il IQspnPartialNaddr (nodo o g-nodo) riferito;
   * dato un IQspnPartialNaddr (nodo o g-nodo) ottenere il HCoord riferito al g-nodo che lo contiene; come
  
effetto collaterale ottengo anche il minimo livello comune;
  * dato un HCoord ottenere il IQspnPartialNaddr (nodo o g-nodo) riferito;
  * dato un IQspnPartialNaddr (nodo o g-nodo) ottenere il HCoord riferito al g-nodo che lo contiene; come effetto collaterale ottengo anche il minimo livello comune;
Line 142: Line 104:
  * leggere il livello del g-nodo; può essere 0 se questa istanza potrebbe rappresentare sia un g-nodo sia un nodo.   * leggere il livello del g-nodo; può essere 0 se questa istanza potrebbe rappresentare sia un g-nodo sia un nodo.
Line 145: Line 107:
Un arco è un oggetto il cui contenuto non è del tutto noto al modulo qspn. L'interfaccia di questo oggetto nota al modulo (IQspnArc) gli consente di:
Line 146: Line 109:
Un arco è un oggetto il cui contenuto non è del tutto noto al modulo qspn. L'interfaccia
di questo oggetto nota al modulo (IQspnArc) gli consente di:
Line 152: Line 113:
Il costo di un arco (come il costo di una path) è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnREM) gli consente di:
Line 153: Line 115:
Il costo di un arco (come il costo di una path) è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnREM) gli consente di:
Line 158: Line 119:
Il fingerprint di un g-nodo è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnFingerprint) gli consente di:
Line 159: Line 121:
Il fingerprint di un g-nodo è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnFingerprint) gli consente di:
Line 162: Line 123:
Il fingerprint a livello 0 è il guid del proprio nodo. Il fingerprint a livello
levels è l'identificativo della rete.

Il fingerprint a livello 0 è il guid del proprio nodo. Il fingerprint a livello levels è l'identificativo della rete.

Modulo QSPN - Analisi Funzionale

Il modulo realizza lo scambio di ETP con i vicini del nodo per l'esplorazione della rete (vedi documento esplorazione).

L'obiettivo è di mantenere per ogni destinazione fino a n percorsi disgiunti, che siano i più rapidi (vedi documento rotte disgiunte).

Struttura gerarchica della rete

La rete è strutturata gerarchicamente in l livelli. Il livello 0 rappresenta il singolo nodo. Nel livello più alto l è presente un solo gruppo che costituisce tutta la rete.

Ogni gruppo di livello i contiene un numero massimo fissato di gruppi di livello i-1.

Il numero massimo di elementi di un gruppo è detto gsize. Ogni livello da 0 a l-1 può avere un valore gsize diverso. Chiamiamo gsize(i) il numero massimo di elementi in un gruppo di livello i+1.

Ogni gruppo di livello i ha un identificativo che lo individua univocamente all'interno del suo gruppo di livello i+1. Tale identificativo è un numero intero da 0 a gsize(i) - 1.

(vedi documento livelli e bits)

Mappa gerarchica della rete

Il modulo genera e mantiene una mappa a topologia gerarchica della rete.

Per ogni livello della rete in tale mappa sono memorizzati tutti i g-nodi di quel livello di cui il nodo conosce l'esistenza (e di conseguenza almeno una rotta).

Per ogni g-nodo la mappa mantiene queste informazioni:

  • livello (level) e identificativo all'interno di quel livello (pos : numero da 0 a gsize(level) - 1). Il modulo qspn lo rappresenta con una istanza dell'oggetto HCoord.
    (Con tali coordinate e l'istanza di IQspnMyNaddr del proprio identificativo (IQspnNodeData) si può ottenere una istanza di IQspnPartialNaddr che rappresenta il g-nodo)

  • tutti i percorsi (paths) che il nodo sa di poter percorrere per raggiungere quel g-nodo.
    La classe Path (nota a questo modulo) contiene queste informazioni:

    • l'arco da usare come primo hop (istanza dell'interfaccia IQspnArc)
    • tutti i successivi hop del percorso in termini di g-nodi che hanno il g-nodo superiore in comune con questo nodo (istanze di HCoord)
    • il costo della path dal primo hop alla destinazione (escluso il costo dell'arco dal nodo al primo hop)
    • il fingerprint del g-nodo come riportato da questa path;
    • il numero di nodi nel g-nodo come riportato da questa path.

Se per un g-nodo vengono rilevate due path che differiscono per il loro fingerprint e se questa situazione si mantiene per un certo lasso di tempo, questo è sintomo dello split del g-nodo in questione. Il modulo lo segnala con un evento.
Il tempo di tolleranza è direttamente proporzionale alla somma dei costi associati alle due path che differiscono. Ma essendo l'oggetto costo non del tutto noto al modulo qspn, viene fornita una callback al modulo per tradurre questo costo somma in un lasso temporale.

Netsukuku Address

Il Netsukuku address è l'indirizzo di una risorsa all'interno della rete, ad esempio un nodo o un g-nodo. Devono essere noti i parametri della topologia gerarchica della rete:

  • numero di livelli in cui la rete è suddivisa;
  • per ogni livello l, numero di posizioni in quel livello;

Dati questi parametri, un indirizzo di nodo è composto da un identificativo per ogni livello da levels a 0.
Invece, un indirizzo di g-nodo di livello l è composto da un identificativo per ogni livello da levels a l.

Per convenienza, diciamo che i parametri della topologia fanno parte dell'indirizzo.

Per rappresentare gli indirizzi di nodi e g-nodi definiamo la classe Naddr. Gli indirizzi di g-nodi li chiamiamo PartialNaddr anche se la classe che li istanzia è la stessa.

Un nodo conosce, per requisito, il suo indirizzo e da questo può costruire gli indirizzi che rappresentano ognuno dei g-nodi di cui fa parte.

Un nodo può venire a conoscenza di Naddr e PartialNaddr di qualsiasi punto della topologia, cioè che non hanno necessariamente in comune il livello direttamente superiore con uno dei g-nodi di cui il nodo è membro.

Nel caso però, in cui un Naddr o PartialNaddr abbia il suo livello direttamente superiore in comune con il nodo corrente, tale indirizzo può essere espresso sotto forma di HCoord (coordinate gerarchiche).

Per questo l'interfaccia del proprio indirizzo è distinta dalla interfaccia di un comune Naddr o PartialNaddr, perché solo partendo dal proprio indirizzo per il nodo corrente ha senso fare operazioni che coinvolgano le HCoord.

Requisiti

  • Identificativo del proprio nodo.
  • Numero massimo di percorsi per destinazione da memorizzare e ratio massimo di disgiunzione.
  • Archi che esistono tra il nodo e i suoi vicini; per ogni arco si conosce l'identificativo del vicino e il costo associato all'arco.
    Viene informato alla costituzione di un nuovo arco; alla rimozione di un arco; al cambio di costo di un arco.

  • Il suo fingerprint come nodo e il fingerprint di tutti i g-nodi di cui è parte; si tratta di un array di levels+1 istanze di IQspnFingerprint; tale array per intero sarà passato in ogni messaggio ETP in broadcast; il modulo verrà notificato se tale array subisce mutazioni.
  • Callback per ottenere da un arco l'oggetto per la chiamata di un metodo remoto sul nodo collegato.
  • Callback per ottenere l'oggetto per l'invio di un messaggio broadcast a tutti i propri vicini (con callback per gli archi in cui il messaggio fallisce)
  • Callback analoga per inviare il messaggio broadcast a tutti i vicini tranne quello collegato ad un dato arco.
  • Callback per ottenere dalla somma dei costi di due path discordi (sul fingerprint del g-nodo) il lasso temporale di tolleranza prima di emettere il segnale di split.

Deliverables

  • Emette un segnale per:
    • nuovo g-nodo, rimosso g-nodo.
    • nuova path, path cambiata o path rimossa per un certo g-nodo.
    • rilevamento di un g-nodo splittato.
  • Fornisce on demand:
    • relativamente ad un g-nodo tutte le path a disposizione per raggiungerlo, con i relativi costi. La path fornita dal metodo pubblico del modulo non è necessariamente l'oggetto usato internamente. L'interfaccia nota all'esterno del modulo (IQspnPath) consente di:
      • leggere la destinazione come IQspnPartialNaddr
      • leggere l'arco come IQspnArc
      • leggere gli hops successivi come IQspnPartialNaddr
      • leggere il costo
      • leggere il numero di nodi

Classi e interfacce

L'identificativo del proprio nodo, come anche l'identificativo di ogni vicino, è un oggetto il cui contenuto non è del tutto noto al modulo qspn. L'interfaccia di questo oggetto nota al modulo (IQspnNodeData) gli consente di:

  • verificare se due identificativi sono identici (metodo 'equals').
  • verificare se due identificativi appartengono alla stessa rete (metodo is_on_same_network)
  • leggere il Naddr (Netsukuku address) del nodo; l'oggetto Naddr non è del tutto noto a questo modulo, che ne conosce l'interfaccia IQspnNaddr;
  • leggere il Naddr del nodo come proprio; da usare solo sull'identificativo del proprio nodo; ottiene l'interfaccia IQspnMyNaddr;
  • leggere il netid della rete; il modulo non conosce del tutto questo oggetto, l'interfaccia che il modulo conosce (IQspnNetworkID) gli consente di:
    • verificare se due netid si riferiscono alla stessa rete (metodo is_same_network)
    • ...


L'oggetto che rappresenta gli indirizzi (Naddr) non è del tutto noto a questo modulo, che conosce alcune sue interfacce a seconda dell'uso che può farne.

Per il proprio indirizzo il nodo conosce l'interfaccia IQspnMyNaddr, per gli indirizzi di altri nodi conosce l'interfaccia IQspnNaddr, per gli indirizzi di g-nodi conosce l'interfaccia IQspnPartialNaddr.

Questi i metodi delle interfacce note al modulo:

  • IQspnNaddr
    • leggere levels e gsize(l) della rete;
    • leggere pos(l) di questo indirizzo;
  • IQspnMyNaddr (che richiede IQspnNaddr)
    • dato un HCoord ottenere il IQspnPartialNaddr (nodo o g-nodo) riferito;
    • dato un IQspnPartialNaddr (nodo o g-nodo) ottenere il HCoord riferito al g-nodo che lo contiene; come effetto collaterale ottengo anche il minimo livello comune;
  • IQspnPartialNaddr (che richiede IQspnNaddr)
    • leggere il livello del g-nodo; può essere 0 se questa istanza potrebbe rappresentare sia un g-nodo sia un nodo.


Un arco è un oggetto il cui contenuto non è del tutto noto al modulo qspn. L'interfaccia di questo oggetto nota al modulo (IQspnArc) gli consente di:

  • leggere l'identificativo del vicino;
  • leggere il costo associato all'arco.


Il costo di un arco (come il costo di una path) è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnREM) gli consente di:

  • sommare il costo di una path a quello di un arco;
  • comparare il costo di due path, valutando quale sia il minore;


Il fingerprint di un g-nodo è un oggetto non del tutto noto a questo modulo. La sua interfaccia nota al modulo (IQspnFingerprint) gli consente di:

  • confrontare due fingerprint per stabilire se sono equivalenti. Il confronto si basa su una parte del fingerprint che è un identificativo univoco (ad esempio un guid) e che è lo stesso guid del nodo più anziano all'interno del g-nodo.
  • dati due fingerprint diversi, stabilire quale sia il più anziano.

Il fingerprint a livello 0 è il guid del proprio nodo. Il fingerprint a livello levels è l'identificativo della rete.

Netsukuku/ita/docs/ModuloQSPN/AnalisiFunzionale (last edited 2016-07-28 08:51:31 by lukisi)