Modulo QSPN - Analisi Funzionale

Il modulo realizza lo scambio di ETP con i vicini del nodo per l'esplorazione della rete (vedi documento esplorazione). Il dialogo avviene soltanto fra nodi che hanno già costituito degli archi; il modulo ignora i messaggi ricevuti da un nodo con il quale non è stato costituito un arco. Questo comporta che il dialogo avviene solo fra nodi che appartengono alla stessa rete.

L'obiettivo è di mantenere per ogni destinazione dst fino a max_paths percorsi disgiunti (vedi documento percorsi disgiunti), che siano i più rapidi. Inoltre occorre mantenere per ogni destinazione dst e per ogni proprio vicino v, almeno 1 percorso, se esiste, indipendentemente dal valore di max_paths e dalle regole di disgiunzione, verso dst che non contiene v tra i suoi passaggi.

Struttura gerarchica della rete

La rete è strutturata gerarchicamente in levels livelli. Al livello 0 ogni singolo nodo della rete costituisce una entità a se stante. Al livello 1 un certo numero di singoli nodi sono raggruppati a costituire un gruppo (o cluster) che chiamiamo g-nodo di livello 1. Al livello 2 un certo numero di g-nodi di livello 1 costituisce un g-nodo di livello 2. E così via. Anche il singolo nodo a volte viene chiamato (impropriamente) un g-nodo di livello 0.

Nel livello più alto levels è presente un solo gruppo che costituisce tutta la rete.

Ogni g-nodo di livello l contiene un numero massimo fissato di g-nodi di livello l-1.

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

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

Questa strutturazione gerarchica è adottata per evitare che la mappa della rete che ogni nodo tiene in memoria diventi troppo grande.

Mappa gerarchica della rete

In ogni singolo nodo, il modulo QSPN ha il compito di costruire e tenere in memoria una mappa a topologia gerarchica della rete.

Per ogni livello della rete in tale mappa sono memorizzati tutti i g-nodi di quel livello (e il cui g-nodo di livello direttamente superiore coincide con il nostro) di cui il nodo conosce l'esistenza (e di conseguenza almeno un percorso). Per ognuno vanno memorizzati tutti i percorsi noti con le relative informazioni (che riassumeremo più sotto).

Affinché questa mappa gerarchica sia sufficiente al nodo per raggiungere ogni possibile destinazione, ogni g-nodo deve essere internamente connesso. E' compito del modulo QSPN scoprire e segnalare se un g-nodo di cui si conosce l'esistenza (e almeno 2 diversi percorsi) è divenuto disconnesso. Eventuali successive azioni volte a porre rimedio non sono di competenza del modulo.

A questo scopo ogni g-nodo ha anche un altro identificativo chiamato fingerprint. Vediamo come si genera un fingerprint e come viene "assegnato" ad un g-nodo.

Fingerprint

A livello 0, il fingerprint di un nodo è composto da un identificativo del nodo, univoco a livello di rete, e da una lista di valori che rappresentano l'anzianità ai vari livelli dal livello 0 al livello levels-1. L'anzianità a livello 0 indica quanto è vecchio il nodo rispetto agli altri nodi del suo stesso g-nodo di livello 1; a livello i indica quanto è vecchio il suo g-nodo di livello i rispetto agli altri g-nodi di livello i del suo stesso g-nodo di livello i+1. L'oggetto fingerprint del nodo viene passato al modulo QSPN dal suo utilizzatore; quindi come vengano generati o recuperati i dati in esso contenuti non è di pertinenza del modulo, e nemmeno in che modo sia implementato il confronto fra due valori di anzianità.

Il fingerprint di un g-nodo di livello 1 ha come identificativo l'identificativo del nodo più anziano in esso contenuto e i suoi stessi valori di anzianità dal livello 1 in su (valori che dovrebbero risultare gli stessi per tutti i nodi del g-nodo). Come vedremo subito, quando un nodo viene a conoscenza dell'esistenza di un altro nodo di livello 0 nel suo g-nodo di livello 1, cioè viene a conoscenza di un percorso per raggiungerlo, viene anche portato a conoscenza del fingerprint di quel nodo. Di conseguenza ogni nodo è in grado di computare il fingerprint del suo g-nodo di livello 1.

Il fingerprint di un g-nodo di livello i ha come identificativo l'identificativo del g-nodo di livello i-1 più anziano in esso contenuto e i suoi stessi valori di anzianità dal livello i in su (valori che dovrebbero risultare gli stessi per tutti i g-nodi di livello i-1 del g-nodo). Anche a livello i abbiamo che quando un nodo viene a conoscenza dell'esistenza di un altro g-nodo di livello i-1 nel suo g-nodo di livello i, cioè viene a conoscenza di un percorso per raggiungerlo, viene anche portato a conoscenza del fingerprint di quel g-nodo. Di conseguenza ogni nodo è in grado di computare il fingerprint del suo g-nodo di livello i.

Proseguendo così si ottiene che il fingerprint a livello levels non ha valori di anzianità ma solo un identificativo. Questo è l'identificativo della rete.

Questo meccanismo di costruzione del fingerprint di un g-nodo a partire da quelli dei g-nodi in esso contenuti (sulla base della conoscenza del nodo corrente) fa in modo che al variare della rete ogni nodo rilevi immediatamente il verificarsi dello split di un g-nodo (o dell'intera rete). Con questo termine indichiamo che il g-nodo non è più internamente connesso, ma si sono formate 2 o più isole.

Vediamo con un esempio come avviene questo rilevamento.

Sia g un g-nodo di livello 1; sia f il nodo più anziano in esso. Siano v e w due border-nodi appartenenti al g-nodo g di livello 1; il termine border-nodo di g indica un nodo appartenente a g che ha almeno un vicino che non appartiene a g. Sia x il vicino di v esterno a g; sia y il vicino di w esterno a g; supponiamo che entrambi siano appartenenti allo stesso g-nodo a di livello 2 in cui si trova anche tutto il g-nodo g.

I nodi v e w sono entrambi a conoscenza di alcuni percorsi per raggiungere f. Quindi entrambi hanno calcolato il fingerprint del g-nodo g ottenendo come identificativo lo stesso di f. Supponiamo che g diventi disconnesso, per esempio per via della rimozione di un arco; che si siano formate due isole; che v ed f si trovino nella prima isola; che w si trovi nella seconda isola. Quando w scopre di non avere più alcun percorso verso f lo considera morto, e ricalcola il fingerprint del g-nodo g ottenendo come identificativo quello di un altro nodo h. Per via di questa variazione il nodo w trasmette un ETP al nodo y. Supponiamo ora che il g-nodo a sia ancora internamente connesso. Quindi esiste un percorso che collega x ad y senza passare per g. Allora l'ETP ricevuto da y si propagherà e raggiungerà x. Ora x sarà a conoscenza di 2 percorsi verso la destinazione g che hanno informazioni diverse riguardo il fingerprint di g. Se questa situazione rimarrà tale per un certo tempo, allora x avrà rilevato lo split del g-nodo g.

Si intuisce che questo meccanismo si ripresenta in maniera analoga qualsiasi sia il livello del g-nodo che diventa disconnesso, basta che il g-nodo di livello superiore sia ancora connesso. Se invece lo split avviene sul livello più alto, cioè se si divide su tutta la rete, quello che si ottiene è che le 2 isole diventano reti distinte con identificativi di rete distinti. Per entrambe le situazioni, come detto in precedenza, il compito del modulo QSPN è solo quello di permetterne il rilevamento, non quello di porre rimedio.

Elementi memorizzati nella mappa

Riassumendo, per ogni g-nodo nella topologia gerarchica del nodo corrente, la mappa mantiene queste informazioni:

• livello (lvl) e identificativo all'interno di quel livello (pos : numero da 0 a gsize(lvl) - 1). Il modulo QSPN lo rappresenta con una istanza della classe HCoord.

• tutti i percorsi che il nodo sa di poter usare per raggiungere quel g-nodo. Il modulo li rappresenta con istanze della classe NodePath. Per ogni percorso vanno mantenute queste informazioni:

  • l'arco verso il gateway;
  • tutti gli hops del percorso espressi come istanze di HCoord;
  • il costo del percorso;
  • il fingerprint del g-nodo destinazione come riportato da questo percorso;
  • il numero di nodi stimati all'interno del g-nodo destinazione come riportato da questo percorso.

Nota: da spostare nei dettagli tecnici

• Se per un g-nodo g vengono rilevate due percorsi 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 g. Il modulo lo segnala con un evento.

• Il tempo di tolleranza è direttamente proporzionale alla somma delle latenze associate ai due percorsi che differiscono; ma il modulo QSPN non ha questa informazione in quanto il costo associato ad un percorso non sappiamo se sia espresso in latenza, in larghezza di banda o in altra metrica; quindi il calcolo di tale tempo di tolleranza va demandato all'utilizzatore del modulo il quale fornisce una callback. Per dare il massimo del supporto a questa callback vengono passate le istanze di IQspnNodePath che rappresentano i percorsi discordi. Da queste la callback potrà estrapolare i costi e sommarli se si tratta in effetti di latenze. Altrimenti la callback potrà leggere la destinazione e confrontarla con il proprio indirizzo per risalire al livello del g-nodo comune, chiedere allo stesso modulo QSPN la stima dei nodi all'interno di tale livello e finalmente proporre un tempo di tolleranza sulla base di questo dato.
• I percorsi che riportano il fingerprint con minore anzianità sono mantenuti nella mappa del modulo e trasmessi tramite ETP, ma soltanto quelli con il fingerprint più anziano sono segnalati all'esterno del modulo. Inoltre, per non perdere informazioni cruciali, quando si viene a conoscenza di un percorso che riporta un fingerprint diverso da tutti gli altri percorsi per la stessa destinazione, non si considera la regola del numero massimo di percorsi e dei percorsi disgiunti.

Nota: da spostare nei dettagli tecnici

• Per un g-nodo g di livello l possono venire rilevati diversi percorsi che differiscono per il "numero di nodi nel g-nodo" e questa situazione si può mantenere stabile. Questo non indica che il g-nodo g sia splittato, infatti le variazioni nel numero di nodi possono venire ignorate se il cambiamento non è massiccio (per evitare eccessivo traffico). In questi casi il nodo prende per buono il numero di nodi come riportato dal percorso più veloce. Userà questa informazione per calcolare il numero di nodi (stimato) all'interno del suo g-nodo di livello l+1.

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 (levels);

• per ogni livello l, numero di posizioni in quel livello (gsize(l));

Dati questi parametri, un indirizzo di nodo è composto da un identificativo per ogni livello da levels-1 a 0. Invece, un indirizzo di g-nodo di livello l è composto da un identificativo per ogni livello da levels-1 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.

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

Nota: spostare nei dettagli tecnici. 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

• Indirizzo Netsukuku del proprio nodo.
• Numero massimo di percorsi per destinazione da memorizzare.

• Massimo rapporto di hops comuni nella verifica di disgiunzione (vedi documento percorsi disgiunti).

• Archi che esistono tra il nodo e i suoi vicini.
• Durante le sue operazioni, il modulo viene informato alla costituzione di un nuovo arco; alla rimozione di un arco; al cambio di costo di un arco.

• Nota: spostare nei dettagli tecnici. Allo stesso tempo questo modulo può segnalare che rimuove un arco perché non funziona, di modo che l'utilizzatore del modulo lo viene a sapere e può prendere misure in merito (ad esempio chiedere al modulo Neighborhood di rimuoverlo); questa segnalazione il modulo QSPN la fa con un segnale.

• Il suo fingerprint come nodo (istanza di IQspnFingerprint).

• Nota: spostare nei dettagli tecnici. Fino alla ricezione degli ETP dei vicini il nodo non è 'maturo' e pertanto non produce ETP. Una volta ricevuti gli ETP il nodo è in grado di calcolare il fingerprint di tutti i g-nodi di cui è parte; si tratta di un array di l+1 istanze di IQspnFingerprint. In seguito tale array per intero sarà passato in ogni messaggio ETP in broadcast.

• Oggetto per calcolare il lasso temporale di tolleranza prima di segnalare il rilevamento di split di un g-nodo.
• Factory per creare uno "stub" per invocare metodi remoti nei vicini.
• Factory per la produzione di istanze di una classe serializzabile ETP.

Deliverables

• Emette un segnale per:
  • fallito hook nella rete.
  • il modulo è ora maturo.
  • rimosso un arco, perché non funzionava.
  • nuovo g-nodo nella mappa, rimosso g-nodo dalla mappa.
  • nuovo percorso, percorso cambiato o percorso rimosso per un certo g-nodo.
  • cambio nel fingerprint di uno dei miei g-nodi.
  • cambio nel numero di nodi interni ad uno dei miei g-nodi.
  • rilevamento di un g-nodo splittato.
• Fornisce metodi per:
  • Chiedere se il nodo è maturo nella rete. Restituisce un booleano.

  • Relativamente ad un g-nodo a cui il nodo non appartiene, vale a dire dato un HCoord, ottenere tutti i percorsi a disposizione per raggiungerlo, con i relativi costi. Restituisce una lista di IQspnNodePath. Se il nodo non è maturo lancia eccezione QspnNotMatureError.

  • Relativamente ad uno dei g-nodi a cui appartiene il nodo, vale a dire dato un livello da 0 a l compresi, ottenere:

    • il fingerprint del g-nodo. Restituisce un IQspnFingerprint. Se il nodo non è maturo lancia eccezione QspnNotMatureError.

    • una stima del numero di nodi al suo interno. Restituisce un intero. Se il nodo non è maturo lancia eccezione QspnNotMatureError.

Classi e interfacce

La classe HCoord è nota a questo modulo. Una sua istanza contiene le coordinate gerarchiche di un g-nodo nella mappa del nodo: livello e identificativo nel livello.

Con tali coordinate e l'istanza di IQspnMyNaddr del proprio nodo si può ottenere una istanza di IQspnPartialNaddr che rappresenta il g-nodo.

In vari casi è necessario rappresentare una serie di hops percorsi da un TP, oppure un percorso noto verso una destinazione. Questa serie di hop la chiamiamo TP-List. Si tratta di una lista di HCoord. Include in testa la coordinata che rappresenta il vicino che usiamo come gateway e in coda la coordinata che rappresenta la destinazione.

Una TP-List è sempre in termini di g-nodi che hanno il g-nodo superiore in comune con questo nodo.

Non viene definita una classe per contenere questa informazione: si usa una lista di HCoord.

L'oggetto che rappresenta i percorsi scritti in un ETP (Npath) non è del tutto noto a questo modulo, che conosce la sua interfaccia IQspnPath. Una istanza di IQspnPath rappresenta un percorso e contiene i dati che sono scritti in un ETP. L'interfaccia ci consente di leggere:

• la TP-list (lista di hops) che costituisce questo percorso;
• il costo del percorso dal nostro vicino fino alla destinazione (escluso il costo dell'arco dal nodo al vicino). E' una istanza dell'interfaccia IQspnREM;
• il fingerprint del g-nodo come riportato da questo percorso. E' una istanza dell'interfaccia IQspnFingerprint;
• il numero di nodi nel g-nodo come riportato da questo percorso.

La classe NodePath è nota a questo modulo. Una sua istanza rappresenta un percorso da questo nodo alla destinazione comprensivo dell'arco dal nodo al vicino che ha pubblicizzato il percorso. Contiene:

• l'arco da usare come primo hop (istanza dell'interfaccia IQspnArc)
• il percorso come è stato pubblicizzato dal vicino attraverso questo arco (istanza della interfaccia IQspnPath)

Il percorso fornito dal metodo pubblico del modulo non è necessariamente l'oggetto usato internamente, cioè NodePath. L'interfaccia nota all'esterno del modulo (IQspnNodePath) 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.

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; il metodo 'i_qspn_get_address_by_coord' restituisce un IQspnPartialNaddr che quindi è anche un IQspnNaddr.
  • dato un IQspnNaddr (nodo o g-nodo) ottenere il HCoord riferito al g-nodo che lo contiene; come effetto collaterale ottengo anche il minimo livello comune; il metodo 'i_qspn_get_coord_by_address' prende come argomento un IQspnNaddr che accetta quindi anche un IQspnPartialNaddr.
• 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.

La stub factory è un oggetto di cui il modulo conosce l'interfaccia IQspnStubFactory. Tramite essa il modulo può:

• Creare uno stub per chiamare un metodo in broadcast su tutti i propri vicini (con callback per gli archi in cui il messaggio fallisce); il modulo può opzionalmente indicare un arco per ottenere uno stub che invia un messaggio destinato a tutti tranne che al nodo collegato tramite quell'arco.
• Creare uno stub per chiamare un metodo in modo reliable su un vicino tramite un dato arco.

Se per un g-nodo g vengono rilevati due percorsi (istanze di IQspnNodePath) 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 g.

Per valutare quanto deve attendere prima di segnalare lo split del g-nodo, al modulo viene fornito un oggetto dal suo utilizzatore, che implementa l'interfaccia IQspnThresholdCalculator. Tramite essa il modulo può:

• Calcolare, passando un paio di istanze di IQspnNodePath che rappresentano i percorsi discordi, il tempo di tolleranza che deve passare da quando si verifica il disallineamento per poter segnalare lo split del g-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:

• verificare se due archi sono identici (metodo 'i_qspn_equals');
• leggere l'indirizzo Netsukuku del vicino (metodo 'i_qspn_get_naddr');
• leggere il costo associato all'arco (metodo 'i_qspn_get_cost').

Il costo di un arco e il costo di un percorso sono rappresentati da istanze di una classe non del tutto nota a questo modulo. La sua interfaccia nota al modulo (IQspnREM) gli consente di:

• sommare il costo di un percorso a quello di un arco (metodo 'i_qspn_add_segment');
• comparare il costo di due percorsi, valutando quale sia il minore (metodo 'i_qspn_compare_to')

Il costo di un percorso, che viene pubblicizzato al modulo QSPN da un vicino, può essere un costo fittizio per indicare una certa situazione – come null per indicare che la destinazione è proprio il vicino, o dead per indicare che il percorso non è più funzionante. Invece il costo di un arco, che viene passato al modulo QSPN dal suo utilizzatore, è sempre un valore frutto di una reale misurazione. Infatti non ha alcun significato un arco verso me stesso, e un arco non funzionante viene semplicemente rimosso.

Il fingerprint di un g-nodo è un oggetto che il modulo non istanzia da solo; gli viene passato il suo fingerprint di nodo (a livello 0) e il modulo ne conosce l'interfaccia IQspnFingerprint. Il modulo inoltre richiede che tale oggetto sia serializzabile.

L'interfaccia IQspnFingerprint consente di:

• Confrontare due fingerprint per stabilire se sono identici (metodo 'i_qspn_equals').
• ?? Leggere il livello del g-nodo a cui appartiene (proprietà 'i_qspn_level').
• Confrontare due fingerprint discordi riferiti allo stesso g-nodo e decidere quale sia più anziano (metodo 'i_qspn_elder').

• Sul fingerprint del proprio g-nodo g di livello i, dati i fingerprint di tutti gli altri g-nodi conosciuti di livello i dentro il mio g-nodo h di livello i+1, ottenere l'istanza di fingerprint del g-nodo h (metodo 'i_qspn_construct').

Un ETP è un oggetto serializzabile che il modulo QSPN deve poter produrre. Si veda il relativo documento.