Modulo QSPN - Analisi Funzionale

Il modulo realizza lo scambio di messaggi con i vicini del nodo al fine di esplorare la rete. Tali messaggi sono chiamati ETP, acronimo di Extended Tracer Packet. In questo documento non illustriamo nel dettaglio come sono fatti questi messaggi. Rimandiamo per questo al documento esplorazione ma consigliamo di leggerlo solo dopo aver letto il presente documento. Per ora basta considerare che ogni nodo usa questi messaggi per comunicare ai suoi vicini le informazioni riguardanti i percorsi della rete che sono a lui noti.

L'obiettivo di ogni nodo n è di reperire e mantenere per ogni destinazione dst fino a max_paths percorsi disgiunti, che siano i percorsi con costo minore. Inoltre n vuole 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. Infine n vuole mantenere per ogni destinazione dst almeno 1 percorso per ogni diverso fingerprint di dst che gli viene segnalato (questo concetto sarà chiarito in seguito).

Il concetto di costo di un percorso può essere implementato con una qualsiasi metrica. Si può ad esempio usare la latenza di un messaggio che attraversa questo percorso. Oppure la larghezza di banda, cioè la quantità di informazioni per unità di tempo che possono attraversare questo percorso. E' sufficiente che siano implementate queste operazioni:

• La somma del costo di due segmenti di un percorso. Questo è necessario poiché il costo di un percorso è dato dalla somma del costo di tutti gli archi che lo costituiscono.
• Il confronto del costo di due percorsi verso la stessa destinazione. Questo è necessario per individuare i percorsi con costo minore.

Per una prima lettura di questo documento si consiglia di identificare il termine "costo" con il concetto di latenza di un messaggio che attraversa il percorso.

Vicini del nodo

Il modulo QSPN nel nodo n considera vicino di n un nodo v se è a conoscenza di uno o più archi che collegano n a v. La conoscenza degli archi a disposizione del nodo n viene passata al modulo come requisito.

Per ogni arco di cui il modulo QSPN viene portato a conoscenza, esso genera un identificativo che possa essere considerato univoco. Si adotta un numero random in uno spazio sufficientemente grande. Questo identificativo dell'arco andrà a far parte, come vedremo in seguito, delle proprietà di un percorso, che lo rendono distinguibile da un altro. L'identificativo dell'arco è un concetto interno al modulo QSPN, di cui l'utilizzatore non si deve occupare.

La trasmissione di messaggi ETP e la loro ricezione sono subordinate agli archi noti al modulo. Un nodo trasmette ETP soltanto tramite gli archi che conosce (oppure in broadcast). Analogamente, un nodo accetta un ETP solo se proviene da un vicino tramite un arco che conosce. Questo fatto comporta il seguente problema.

Siano n e v due nodi vicini. Il nodo n si avvede per primo della presenza di v e lo contatta per formare un arco (questo avviene al di fuori del modulo QSPN). Il nodo v conferma. Di seguito entrambi avviano una prima misurazione del costo dell'arco. Soltanto a misurazione avvenuta il modulo QSPN viene informato della presenza di un arco. Sia n il nodo che per primo completa la misurazione. Il modulo QSPN del nodo n riceve la notifica di un nuovo arco e cerca di contattare il nodo v per richiedere un ETP. Il nodo v non ha ancora completato la misurazione, quindi il modulo QSPN del nodo v non trova l'arco nella sua lista.

Questo problema rende necessario che quando il modulo QSPN in un nodo v riceve una richiesta da un vicino e non trova l'arco relativo nella sua lista, prima aspetti un certo tempo e verifichi di nuovo la presenza dell'arco. Dopo questa attesa, che chiamiamo tempo di rilevamento dell'arco, se l'arco risulta ancora sconosciuto, il modulo potrà ignorare la richiesta o rifiutarla con una eccezione. La durata di questa attesa deve essere passata al modulo QSPN dal suo utilizzatore, in quanto è esso a conoscere i dettagli dell'iter di misurazione del costo dell'arco.

Struttura gerarchica della rete

L'assegnazione degli indirizzi ai nodi della rete avviene sulla base di una struttura gerarchica imposta alla rete. Tale gerarchia è composta da un numero fisso di livelli: l.

Al livello 0 ci sono i singoli nodi. Ogni nodo da solo costituisce un vertice.

Al livello 1 i singoli nodi sono raggruppati a costituire gruppi (o cluster) che chiamiamo g-nodi di livello 1. Un g-nodo di livello 1 può essere costituito anche da un solo nodo, oppure da più nodi fino ad un numero massimo fissato. Ogni g-nodo di livello 1 può essere considerato come un singolo vertice.

Al livello 2 i g-nodi di livello 1 sono raggruppati a costituire g-nodi di livello 2. Un g-nodo di livello 2 può essere costituito anche da un solo g-nodo di livello 1, oppure da più g-nodi fino ad un numero massimo fissato. Ogni g-nodo di livello 2 può essere considerato come un singolo vertice. Si noti che i singoli nodi che fanno parte di un g-nodo di livello 1 che fa parte a sua volta di un g-nodo di livello 2, ognuno di questi singoli nodi fa parte allo stesso tempo anche del g-nodo di livello 2.

E così via. Nel livello più alto l è presente un solo gruppo che costituisce tutta la rete.

Anche il singolo nodo a volte viene chiamato (impropriamente) un g-nodo di livello 0.

Come detto, ogni g-nodo di qualsiasi livello i può essere considerato come se fosse un unico vertice. Si forma cioè per ogni livello i una sorta di partizionamento del grafo che costituisce l'intera rete.

Abbiamo detto che ogni g-nodo di livello i+1 contiene un numero massimo fissato di g-nodi di livello i. Il numero massimo di elementi di un g-nodo è detto gsize. Ogni livello da 0 a l-1 può avere un valore gsize diverso. Chiamiamo gsize(i) il numero massimo di g-nodi di livello i in un g-nodo di livello i+1.

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

L'indirizzo del singolo nodo va ad essere composto mettendo in sequenza gli identificativi di tutti i g-nodi a cui esso appartiene, a partire da quello di livello l-1 fino a quello di livello 0. Si noti che ogni singolo nodo, dal momento che conosce il proprio indirizzo, sa di far parte di un preciso g-nodo di livello 1, di un preciso g-nodo di livello 2, e così via, fino al livello più alto.

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 i della rete, da 0 a l-1, un nodo n deve memorizzare in tale mappa tutti i g-nodi di livello i appartenenti al suo stesso g-nodo di livello i+1 di cui n conosce l'esistenza, cioè conosce almeno un percorso per raggiungerli. Per ognuno vanno memorizzati tutti i percorsi noti e per ogni percorso alcune informazioni che elencheremo più sotto.

Ad esempio, sia il nodo n con indirizzo n_l-1·...·n₁·n₀. Vale a dire che n ha identificativo n₀ all'interno del suo g-nodo di livello 1, il quale ha identificativo n₁ all'interno del suo g-nodo di livello 2, ... fino a n_l-1. Per il livello 0 il nodo n dovrà memorizzare nella mappa tutti i nodi (detti g-nodi di livello 0) che conosce che appartengono al g-nodo di livello 1 n₁. Il nodo n non memorizzerà nella sua mappa n₀ perché è esso stesso. Per il livello 1 il nodo n dovrà memorizzare nella mappa tutti i g-nodi di livello 1 che conosce che appartengono al g-nodo di livello 2 n₂ come se fossero singoli vertici. Il nodo n non memorizzerà n₁ come un singolo vertice perché di esso ha già memorizzato tutti i vertici di cui è composto. Per il livello 2 il nodo n dovrà memorizzare nella mappa tutti i g-nodi di livello 2 che conosce che appartengono al g-nodo di livello 3 n₃ come se fossero singoli vertici. Il nodo n non memorizzerà n₂ come un singolo vertice perché di esso ha già memorizzato tutti i vertici di cui è composto. E così via fino a memorizzare come fossero singoli vertici anche tutti i g-nodi di livello l-1 che conosce, tranne n_l-1.

Affinché questa mappa gerarchica sia sufficiente al nodo per raggiungere ogni singolo nodo esistente nella rete, 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 l-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. Questi valori dal livello 1 in su risultano gli stessi per tutti i nodi del g-nodo di livello 1; questa proprietà è assicurata con una modalità che non è di pertinenza del modulo QSPN, come è stato implicitamente detto prima. 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 risultano 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 l 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.

Il nodo che rileva questa situazione, nel nostro esempio x, è un border-nodo dell'isola che contiene il nodo più anziano. Invece noi vogliamo che sia l'altra isola (o le altre isole) ad essere avvertita. Occorre quindi che si generi il flood di un nuovo ETP che porti questa informazione indietro al nodo y. Aggiungiamo quindi una regola che chiamiamo regola di primo rilevamento di split : quando un nodo n vede un percorso p1 verso un g-nodo g con un fingerprint fp1, se prima n non conosceva fp1 e se conosceva g attraverso un diverso percorso p2 con un diverso fingerprint fp2, allora n produce un nuovo ETP con tutti i percorsi verso g e lo invia a tutti i suoi vicini.

Alla fine anche il nodo y verrà a conoscenza di 2 (o più) percorsi verso la destinazione g che hanno informazioni diverse riguardo il fingerprint di g. Se questa situazione rimarrà tale per un certo tempo, allora y avrà rilevato lo split del g-nodo g. Siccome y ha fra i suoi diretti vicini un border-nodo di un'isola di g con un fingerprint diverso da quello più anziano, la segnalazione di questo rilevamento da parte del modulo QSPN potrà fare in modo che l'isola scollegata (non la più anziana) venga avvertita.

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 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. In particolare nel caso di split di un g-nodo, è necessario che lo rilevi almeno un nodo diretto vicino di un border-nodo dell'isola (o delle isole) che non contiene il nodo più anziano.

Nota 1: Per questo è importante che un nodo sempre mantenga e trasmetta per ogni destinazione d almeno un percorso per ogni diverso fingerprint di d che gli viene segnalato attraverso gli ETP ricevuti. Ma soltanto i percorsi con il fingerprint più anziano, per ogni destinazione d, vengono restituiti all'esterno del modulo con il metodo get_paths_to ( d ) .

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 i passi del percorso espressi come istanze di HCoord;
  • tutti gli identificativi degli archi che collegano un passo al successivo, compreso l'identificativo dell'arco verso il gateway;
  • 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.
• Si consideri che due percorsi di cui il nodo viene a conoscenza sono dal nodo considerati distinti se e solo se non riportano le stesse sequenze di passi e di archi.

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

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

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

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

Requisiti

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

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

• Tempo di rilevamento degli archi.
• 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.
• Il suo fingerprint come nodo (istanza di IQspnFingerprint).
• 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.

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. Metodo List<IQspnNodePath> get_paths_to. 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

L'oggetto che rappresenta gli indirizzi 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 i parametri della topologia della rete, cioè l e gsize(i) con i da 0 a l-1;

  • leggere pos(i) di questo indirizzo, con i da 0 a l-1.

• 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 massimo distinto g-nodo che lo contiene, distinto rispetto al nostro nodo; 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 classe HCoord è nota a questo modulo. E' una classe serializzabile, cioè le cui istanze sono adatte al passaggio di dati a metodi remoti. 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.

I passi che costituiscono un percorso noto verso una destinazione sono rappresentati da una doppia sequenza di k elementi:

• hops : sequenza di k istanze di HCoord.

• 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].

E' inclusa in testa la coordinata che rappresenta il vicino che usiamo come gateway (o meglio il suo massimo distinto g-nodo rispetto a noi) e in coda la coordinata che rappresenta la destinazione.

La sequenza hops è sempre in termini di g-nodi che hanno il g-nodo superiore in comune con il nodo corrente.

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

I passi che costituiscono il percorso fatto da un ETP sono rappresentati da una singola sequenza di istanze di HCoord.

Per questa informazione si usa una lista di HCoord.

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 assume che sia un oggetto serializzabile.

L'interfaccia IQspnFingerprint consente di:

• Confrontare due fingerprint per stabilire se sono identici (metodo 'i_qspn_equals').
• 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').

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 (IQspnCost) 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 funzionamento di questo comparatore è il seguente. Un oggetto IQspnCost indica una misura del costo di un percorso. Quindi dato il costo a e il costo b si dice che a > b se inviare un messaggio per il tramite di a è più "oneroso" che inviarlo per il tramite di b. Si traduce questa formula con a .i_qspn_compare_to ( b ) > 0 . Analogamente per gli altri operatori di confronto ( = , < , ≤ , ≥ , ≠ ).

• Confrontare due costi (riferiti allo stesso percorso) per valutare se c'è stata una variazione significativa (metodo 'i_qspn_important_variation').

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.

Quindi l'interfaccia IQspnCost consente anche di:

• Vedere se il valore è null (metodo 'i_qspn_is_null').

• Vedere se il valore è dead (metodo 'i_qspn_is_dead').

Un'altra caratteristica importante di questi due costi fittizzi (null e dead) è che essi rappresentano il minimo assoluto e il massimo assoluto. Come tali, essi possono essere sommati o confrontati con qualsiasi altro costo indipendentemente dalla metrica a cui si riferisce (latenza, larghezza di banda, ecc.). Infatti, sia c_n la costante costo null, sia c_d la costante costo dead e sia w un costo che rappresenta una effettiva misurazione di una qualsiasi metrica. Abbiamo queste proprietà:

• c_n = c_n

• c_n < w

• c_n < c_d

• w < c_d

• c_d = c_d

• c_n + c_n = c_n

• c_n + w = w

• c_n + c_d = c_d

• c_d + w = c_d

• c_d + c_d = c_d

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').
• Verificare se un metodo remoto avviato dalla libreria ZCD su richiesta di un vicino è stato ricevuto tramite questo arco (metodo 'i_qspn_comes_from').

Un ETP è una istanza della classe EtpMessage che è interna al modulo. Essa è serializzabile. Un ETP contiene:

• L'indirizzo del nodo n che produce l'ETP. E' una istanza di IQspnNaddr. Il modulo assume che sia anche un oggetto serializzabile. Proprietà IQspnNaddr node_address.

• La lista di fingerprint per i g-nodi di n ai livelli da 0 a l-1. E' una lista di istanze di IQspnFingerprint. Il modulo assume che ognuna sia anche un oggetto serializzabile. Proprietà List<IQspnFingerprint> fingerprints.

• La lista del numero approssimativo di nodi all'interno dei g-nodi di n ai livelli da 0 a l-1. E' una lista di interi. Proprietà List<int> nodes_inside.

• La lista dei g-nodi attraversati da questo ETP. Proprietà List<HCoord> hops.

• La lista P dei percorsi. Ogni percorso p ∈ P è una istanza di EtpPath, descritta sotto. Proprietà List<EtpPath> p_list.

Un percorso p scritto nella lista P di un ETP è una istanza della classe EtpPath che è interna al modulo. Essa è serializzabile. Contiene:

• La lista dei g-nodi e relativi archi che costituiscono il percorso p fino al g-nodo destinazione d. Quando si riceve un ETP questa lista non comprende il nostro vicino, cioè il nodo n che ha prodotto l'ETP; ma dopo aver eseguito la Grouping Rule (descritta nel documento esplorazione) conterrà anche n e in tale stato verrà memorizzato nella mappa dentro un oggetto NodePath. Si compone delle due proprietà List<HCoord> hops e List<int> arcs.

• Il costo di p da n a d. E' una istanza dell'interfaccia IQspnCost. Il modulo assume che sia anche un oggetto serializzabile. Proprietà IQspnCost cost.

• Il fingerprint del g-nodo d come riportato da questo percorso. E' una istanza dell'interfaccia IQspnFingerprint. Il modulo assume che sia anche un oggetto serializzabile. Proprietà IQspnFingerprint fingerprint.

• Il numero di nodi nel g-nodo d come riportato da questo percorso. Proprietà int nodes_inside.

• Una lista di l booleani il cui elemento i-esimo (da 0 a l-1) dice se va ignorato questo percorso dai nodi che non appartengono al g-nodo di livello i del nodo n che ha prodotto l'ETP. In realtà per i = 0 il valore è sempre false ma per semplicità teniamo anche questo valore. Proprietà List<bool> ignore_outside.

La classe NodePath è interna al 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 per raggiungere il vicino gateway. Proprietà IQspnArc arc .

• Il percorso come è stato pubblicizzato dal vicino attraverso questo arco. Proprietà EtpPath path .

Il percorso fornito dal metodo pubblico get_paths_to del modulo non ha le stesse informazioni usate internamente al modulo e presenti nella classe NodePath. Si usa un'altra classe, RetPath. Anche questa è una classe interna al modulo. La sua interfaccia nota all'esterno del modulo (IQspnNodePath) consente di:

• Leggere l'arco come IQspnArc.
• Leggere i passi successivi, fino alla destinazione compresa, come IQspnHop (vedi sotto).
• Leggere il costo come IQspnCost.
• Leggere il numero di nodi stimati all'interno del g-nodo destinazione.

L'oggetto che rappresenta un passo dentro un IQspnNodePath è una istanza della della classe RetHop. Tale classe è interna al modulo. La sua interfaccia nota all'esterno del modulo (IQspnHop) consente di:

• Leggere l'identificativo dell'arco (un intero) che permette di raggiungere questo passo.
• Leggere l'indirizzo del passo come IQspnPartialNaddr.

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 in millisecondi che deve passare da quando si verifica il disallineamento per poter segnalare lo split del g-nodo (metodo 'i_qspn_calculate_threshold').

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. 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.
• Le chiamate a metodi remoti fatte con questo stub procedono in modo asincrono: l'invio del messaggio procederà in una nuova tasklet, mentre il metodo non fornirà alcuna risposta al chiamante. Il modulo può fornire un oggetto (istanza di IQspnMissingArcHandler, descritta sotto) in cui un determinato metodo (callback) verrà richiamato dopo un certo tempo se per qualcuno degli archi noti al modulo non si avrà ricevuto un messaggio di ACK dal vicino collegato. Questo controllo viene fatto sugli archi che sono esistenti al momento dell'invio AND sono ancora presenti alla scadenza del timeout. Il metodo callback viene chiamato una volta per ogni arco che fallisce e avrà quell'arco come argomento, così che il chiamante possa prendere un provvedimento, ad esempio tentando un messaggio con protocollo reliable.
• Creare uno stub per chiamare un metodo in modo reliable su un vicino tramite un dato arco.
• Le chiamate a metodi remoti fatte con questo stub procedono in modo sincrono: l'invio del messaggio avviene nella stessa tasklet, e il metodo fornirà una risposta al chiamante, che può segnalare la corretta ricezione del messaggio o un errore. E' possibile dichiarare di voler attendere la processazione del messaggio o soltanto la sua ricezione. In ogni caso se non si verifica una eccezione RPCError si è certi che il messaggio è stato ricevuto. In caso contrario il modulo considera l'arco non funzionante; di norma gestisce questo evento con la rimozione dell'arco dalla sua lista e la segnalazione tramite il segnale.

Il gestore per gli archi che non segnalano la ricezione di un messaggio in broadcast è una istanza di una classe interna al modulo, che implementa l'interfaccia IQspnMissingArcHandler. Tramite essa:

• Al modulo viene segnalato un arco da cui non si è ricevuta la notifica di ricezione del messaggio (metodo 'i_qspn_missing').