• Netsukuku
• ita
• docs
• ModuloQSPN
• AnalisiFunzionale

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 n percorsi disgiunti, che siano i più rapidi (vedi documento rotte disgiunte). Inoltre occorre mantenere per ogni destinazione dst e per ogni proprio vicino v, 1 percorso, se esiste, verso dst che non contiene v tra i suoi passaggi.

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 (e il cui g-nodo di livello direttamente superiore coincide con il nostro) 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 della classe HCoord.

• tutti i percorsi che il nodo sa di poter percorrere per raggiungere quel g-nodo. Il modulo li rappresenta con istanze della classe NodePath.

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.
Le path che riportano il fingerprint con minore anzianità sono mantenute nella mappa del modulo e trasmesse tramite ETP, ma soltanto quelle con il fingerprint più anziano sono segnalate all'esterno del modulo. Inoltre, per non perdere informazioni cruciali, quando si viene a conoscenza di una path che riporta un fingerprint diverso da tutte le altre path per la stessa destinazione, non si considera la regola del numero massimo di path e delle path disgiunte.

Per un g-nodo G di livello l possono venire rilevate diverse path 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 dalla rotta 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;
• 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

• Indirizzo Netsukuku del proprio nodo.
• Numero massimo di percorsi per destinazione da memorizzare e ratio massimo di hops comuni.

• Archi che esistono tra il nodo e i suoi vicini; per ogni arco si conosce l'indirizzo Netsukuku del vicino e il costo associato all'arco.
  Il modulo viene informato alla costituzione di un nuovo arco; alla rimozione di un arco; al cambio di costo di un arco. Allo stesso tempo questo modulo può segnalare che rimuove un arco perché non funziona, di modo che chi lo aveva fornito (modulo Neighborhood) lo sappia e lo rimuova dalla sua lista; questo lo fa con un segnale.
  Se all'inizio delle operazioni non ci sono archi significa che il nodo sta generando una nuova rete, quindi il modulo si considera da subito maturo. Se invece ci sono degli archi il modulo si considera non maturo e chiede ai vicini di comunicargli le loro mappe con un ETP completo. Se riceve uno o più ETP li elabora e poi si considera maturo. Infine, se all'inizio ci sono degli archi ma nessuna delle richieste di un ETP ritorna con successo allora il modulo emette il segnale 'fallito hook' affinché il nodo consideri fallito l'ingresso nella rete e riprovi da capo.

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

• Callback per ottenere da un arco l'oggetto per la chiamata di un metodo remoto sul nodo collegato. Gli archi che il modulo riceve sono istanze di IQspnArc ma anche istanze di INeighborhoodArc. Così da poterli usare sui metodi esposti dal modulo Neighborhood attraverso l'interfaccia INeighborhoodArcToStub.
• 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.
• 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 (per segnalare che non funzionava)
  • nuovo g-nodo, rimosso g-nodo.
  • nuova path, path cambiata o path rimossa 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 on demand:
  • dice se il nodo è maturo nella rete.

  • relativamente ad un g-nodo a cui il nodo non appartiene, vale a dire dato un HCoord, tutte le path a disposizione per raggiungerlo, con i relativi costi. Se il nodo non è maturo lancia eccezione QspnNotMatureError. La path fornita 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

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

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

    • una stima del numero di nodi al suo interno. 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 una rotta nota 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 le path scritte in un ETP (Npath) non è del tutto noto a questo modulo, che conosce la sua interfaccia IQspnPath. Una istanza di IQspnPath rappresenta una path e contiene i dati che sono scritti in un ETP. L'interfaccia ci consente di leggere:

• la TP-list (lista di hops) che costituisce questa path;
• il costo della path 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 questa path. E' una istanza dell'interfaccia IQspnFingerprint;
• il numero di nodi nel g-nodo come riportato da questa path.

La classe NodePath è nota a questo modulo. Una sua istanza rappresenta una path da questo nodo alla destinazione comprensiva dell'arco dal nodo al vicino che ha pubblicizzato la destinazione. Contiene:

• l'arco da usare come primo hop (istanza dell'interfaccia IQspnArc)
• la path come è stata pubblicizzata dal vicino attraverso questo arco (istanza della interfaccia IQspnPath)

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.

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 (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 (metodo 'i_qspn_add_segment');
• comparare il costo di due path, valutando quale sia il minore (metodo 'i_qspn_compare_to');

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.

Fondamentalmente il fingerprint di nodo (a livello 0) è composto da un identificativo del nodo e da una lista di valori che rappresentano l'anzianità ai vari livelli. L'identificativo è generato dal nodo come random in modo che sia presumibilmente univoco a livello di rete. 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. Questi valori sono comunicati al nodo dal Coordinator del g-nodo in cui fa hook quando entra nella rete.

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

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

Il fingerprint a livello levels è 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 conosca immediatamente come comportarsi davanti a scenari cruciali come lo split di un g-nodo o lo split dell'intera rete in due reti distinte (che dopo devono avere identificativi diversi).

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').
• leggere il livello del g-nodo a cui appartiene (proprietà 'i_qspn_level').

• dati i fingerprint di tutti i g-nodi di livello i-1 contenuti in un g-nodo G di livello i, ottenere l'istanza di fingerprint del g-nodo G (metodo 'i_qspn_construct').

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