Modulo QSPN - Dettagli Tecnici

Il presente documento assume che siano stati letti il documento di Analisi Funzionale e quelli in esso indicati (Esplorazione della rete e Percorsi disgiunti).

Terminologia

Diamo un significato ad alcuni termini che useremo frequentemente nel resto del documento.

Invece di dire "l'utilizzatore del modulo QSPN" in ottica di uso generico, nel resto del documento ci riferiremo direttamente al "demone ntkd" per brevità.

C'è una relazione di equivalenza tra il termine "identità del nodo" e una istanza della classe QspnManager. A volte ci riferiremo ad una istanza di QspnManager, sottintendendo che questa si riferisce ad una specifica identità che vive in un nodo.

Per una dettagliata analisi del concetto di identità e delle sue caratteristiche rimandiamo al documento di trattazione del modulo Identities. Nel documento Identities viene introdotto il concetto di identità principale. Qui evidenziamo che tale identità detiene l'indirizzo che nella trattazione del presente modulo abbiamo indicato con il termine indirizzo definitivo.

A volte parleremo di nodo indicando con questo termine l'intera macchina fisica. O meglio il sistema su cui è in esecuzione il processo demone ntkd. Dobbiamo tenere presente che al suo interno possono vivere diverse identità. Ma nella trattazione degli aspetti di esplorazione della rete ci siamo di norma riferiti con il termine nodo alla singola entità del grafo che detiene un certo Netsukuku address. Questa è appunto una singola identità. Analogamente, con il termine g-nodo ci siamo riferiti ad un cluster di nodi, cioè un insieme di singole identità. Quando ci riferiamo ad un g-nodo o meglio ai singoli nodi che lo compongono, dobbiamo avere presente che su una singola macchina possono esistere diverse identità e di esse una o più possono appartenere al dato g-nodo.

Per questo motivo, per non portare confusione, cercheremo di usare direttamente il termine "demone ntkd" o il termine sistema al posto di nodo quando vogliamo indicare nel suo insieme il sistema su cui è in esecuzione. Quando vogliamo indicare un singolo vertice del grafo cercheremo di usare la locuzione nodo del grafo o genericamente g-nodo.

Inizializzazione del modulo

Il modulo QSPN fa uso delle tasklet, un sistema di multithreading cooperativo.

Il modulo QSPN fa uso del framework ZCD, precisamente appoggiandosi ad una libreria intermedia prodotta con questo framework per formalizzare i metodi remoti usati nel demone ntkd.

Il modulo QSPN è un modulo di identità. In un singolo nodo il demone ntkd può creare diverse istanze della classe QspnManager, ognuna gestita da una sua identità. Alcune operazioni di inizializzazione del modulo sono fatte una sola volta, per questo usano metodi statici della classe QspnManager.

Il demone ntkd per prima cosa inizializza il modulo QSPN richiamando il metodo statico init di QspnManager.

Nel metodo init viene passata l'istanza di ITasklet per fornire l'implementazione del sistema di tasklet.

Inoltre vengono passati:

• Il numero massimo di percorsi per destinazione da memorizzare (int max_paths).

• Il massimo rapporto di hops comuni nella verifica di disgiunzione (float max_common_hops_ratio).

• Tempo di rilevamento degli archi in millisecondi (int arc_timeout).

• Il calcolatore del tempo di tolleranza (istanza di IQspnThresholdCalculator threshold_calculator).

Requisiti e Deliverable

Esaminiamo nel dettaglio i requisiti (forniti dal demone ntkd) e i deliverable del modulo QSPN in questi possibili scenari:

• Avvio come singolo nodo. Quando un nodo si avvia viene creata la sua identità principale ed essa forma da sola una "rete".

• Il demone ntkd crea una istanza di QspnManager specificando che si tratta di questo scenario. In questo caso al costruttore viene passato un indirizzo definitivo generato in modo del tutto arbitrario.

• Ingresso nella rete di un singolo nodo del grafo o di un g-nodo.

• Se si tratta di un singolo nodo del grafo allora il demone ntkd individua l'istanza di QspnManager che ad esso si riferisce.

• Se si tratta di un g-nodo allora il demone ntkd individua una o più istanze di QspnManager che si riferiscono a nodi del grafo appartenenti al dato g-nodo.

• Per ogni istanza di QspnManager individuata, il demone ntkd:

  • Crea una nuova istanza di QspnManager specificando che si tratta di questo scenario e indicando la precedente istanza. In questo caso al costruttore viene passato un nuovo indirizzo valido nella nuova rete. Tale indirizzo sarà analogo (definitivo o di connettività) a quello detenuto dalla precedente identità.

  • Dismette la precedente istanza di QspnManager.

• Migrazione (di un singolo nodo del grafo o di un g-nodo) da un g-nodo di livello i ad un altro g-nodo (sempre di livello i) il quale appartiene a g-nodi distinti da quelli del primo fino al livello j.

• Di nuovo, se si tratta di un singolo nodo del grafo allora il demone ntkd individua l'istanza di QspnManager che ad esso si riferisce.

• Se si tratta di un g-nodo allora il demone ntkd individua una o più istanze di QspnManager che si riferiscono a nodi del grafo appartenenti al dato g-nodo.

• Per ogni istanza di QspnManager individuata, il demone ntkd:

  • Crea una nuova istanza di QspnManager specificando che si tratta di questo scenario e indicando la precedente istanza. In questo caso al costruttore viene passato un nuovo indirizzo valido nel nuovo g-nodo. Tale indirizzo sarà analogo (definitivo o di connettività) a quello detenuto dalla precedente identità.

  • Modifica la precedente istanza di QspnManager che ora detiene un indirizzo di connettività ai livelli da i a j, modificando la componente al livello i - 1 del precedente indirizzo.

Avvio

Il demone ntkd nel sistema n produce in modo completamente arbitrario un indirizzo Netsukuku conforme ad una certa topologia di rete di l livelli. Sceglie un identificativo random per il suo fingerprint a livello 0, il quale avrà tutte le anzianità ai vari livelli a zero (nel senso che è il primo nodo, nel primo g-nodo a livello 1, ... nel primo g-nodo a livello l - 1, nella rete).

Il nodo del grafo non ha archi.

Quindi il demone ntkd nel sistema n istanzia il suo QspnManager passando al costruttore:

• Tipo di costruttore: creazione di una rete (QspnManager.create_net).

• Il proprio indirizzo Netsukuku (istanza di IQspnNaddr my_naddr).

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

• La stub factory per le comunicazioni con i vicini (istanza di IQspnStubFactory stub_factory).

La lista di istanze di IQspnArc my_arcs viene inizializzata vuota dal costruttore.

Una istanza di QspnManager costruita in questo modo esce immediatamente dalla fase di bootstrap. Quando una istanza di QspnManager esce dalla fase di bootstrap lo notifica con il segnale bootstrap_complete.

Abbiamo detto che la rete è composta dal solo nodo del grafo n. Se in seguito il sistema n decidesse di entrare in una diversa rete, allora farebbe come vedremo sotto una nuova istanza di QspnManager.

Se invece un altro sistema decide di entrare come nodo nel grafo della mia rete, allora il demone ntkd nel sistema n segnala le variazioni sugli archi alla sua istanza di QspnManager con questi metodi:

• arc_add (IQspnArc arc).

• arc_is_changed (IQspnArc changed_arc).

• arc_remove (IQspnArc removed_arc).

Quando il QspnManager memorizza i suoi archi, per ognuno genera un identificativo di arco, cioè un intero random in uno spazio grande. Memorizza in una lista gli archi, accertandosi che non ci siano archi ripetuti. Memorizza e gestisce inoltre un dizionario (HashMap) che associa identificativi e archi.

Inoltre il modulo non assume che anche il suo utilizzatore mantenga le istanze degli archi. Questo significa che il QspnManager per vedere se un arco è nella sua lista si basa sul metodo i_qspn_equals fornito dall'interfaccia IQspnArc. Sul metodo arc_is_changed sostituisce l'istanza corrente nella sua lista (e nel suo dizionario degli identificativi) con quella passata (non assumendo che si tratti della stessa istanza) e dovrà fare lo stesso cambio su tutte le istanze della classe NodePath.

Ingresso

Supponiamo che il g-nodo w (a cui appartiene il nodo del grafo n che vive nel nostro sistema) fa il suo ingresso in una rete G. In questa trattazione è incluso il caso in cui w equivale a n.

Per l'esattezza, dire che un g-nodo w fa ingresso in una rete G significa che prenota un posto in un g-nodo g ∈ G tale che:

• Il livello di g è maggiore del livello di w.

• Il g-nodo g non è saturo.

• Il g-nodo w ha almeno un arco diretto verso g.

A fronte di diversi g-nodi che potrebbero soddisfare questi requisiti, la strategia che si adotta per la scelta del g-nodo non è di competenza del modulo QSPN. Viene descritta nel documento del modulo Migrations. TODO: inserire.

Se si tratta di un singolo nodo del grafo n che vuole entrare nel g-nodo g ∈ G — deve trattarsi dell'identità principale del suo sistema — lo stesso nodo n chiede ad un suo diretto vicino in g, chiamiamolo g₀, i dati che servono all'ingresso. Questa richiesta da n a g₀ viene fatta con i metodi remoti di un modulo di identità. Per rispondere, g₀ inizia un dialogo con il Coordinator di g. Dopo che n ha ricevuto la risposta, il demone ntkd crea una nuova istanza di QspnManager basata sulla precedente n che detiene un indirizzo definitivo in g.

Se si tratta di un g-nodo w che contiene diversi nodi del grafo e che vuole entrare in blocco nel g-nodo g ∈ G, in qualche modo si è eletto un suo border-nodo n₀ — che deve essere l'identità principale del suo sistema — a chiedere ad un suo diretto vicino g₀ in g i dati che servono all'ingresso. Di nuovo, la richiesta da n₀ a g₀ viene fatta con i metodi remoti di un modulo di identità e, per rispondere, g₀ inizia un dialogo con il Coordinator di g. Poi n₀ genera un identificativo di migrazione migration_id e propaga questi dati a tutto il g-nodo w, anche qui attraverso chiamate a metodo remoto fatte con un modulo di identità. Infine n₀ riceve conferma che tutti i nodi del grafo appartenenti al g-nodo w sono stati portati a conoscenza dei dati e del migration_id. A questo punto n₀ propaga analogamente a tutto il g-nodo w l'ordine di completare la migrazione.

In questo secondo scenario dobbiamo esaminare cosa avviene in ogni sistema in cui vivono dei nodi del grafo che appartengono a w. In particolare in ogni sistema possono vivere una o più istanze di QspnManager (cioè nodi del grafo) che appartengono a w e quindi il demone ntkd farà alcune operazioni per ognuna di esse.

Per ogni istanza n di QspnManager che apparteneva a w il demone ntkd crea una nuova istanza di QspnManager basata sulla precedente n che detiene un indirizzo in g analogo (definitivo o di connettività) a quello che deteneva n in w.

In questo modo si produce di fatto un g-nodo w’ all'interno del g-nodo g ∈ G che è isomorfo al g-nodo w come esisteva prima.

Notiamo che ci può essere il caso di un sistema in cui una istanza n di QspnManager che detiene un indirizzo di connettività appartiene a w, mentre l'identità principale del sistema (cioè l'istanza di QspnManager che detiene l'indirizzo definitivo) non appartiene a w ma ad un diverso g-nodo della stessa rete. In questo caso se w entra in blocco in G mentre altri g-nodi della vecchia rete non lo hanno ancora fatto, il sistema in questione ha la sua identità principale in una rete distinta da G e una sua identità di connettività dentro G.

Creazione di una identità nella rete G e dismissione della precedente

I dati che ogni identità n riceve in relazione a questo ingresso nel g-nodo g di livello i in G sono:

• L'identificativo di migrazione migration_id. Si tratta di un identificativo univoco (un numero random) reso noto a tutti i partecipanti alla migrazione.

• L'indirizzo Netsukuku di g ∈ G e la sua anzianità e quella dei g-nodi superiori in G.

• La posizione riservata al nuovo g-nodo w’ in g al livello i - 1 e la sua anzianità.

Abbiamo già detto che tali informazioni giungono ad una precisa identità n che vive nel sistema. Il demone ntkd per ogni identità n crea una nuova identità n’.

Questa operazione di creazione di una nuova identità viene realizzata dal demone ntkd avvalendosi del modulo Identities. Rimandiamo al relativo documento se si vuole approfondire. Qui ricordiamo solo che l'operazione avviene in due fasi, con il metodo prepare_add_identity e il metodo add_identity. Questi metodi richiedono due dati: l'identificativo di migrazione migration_id e l'identità n da duplicare. Subito, quando riceve le informazioni suddette, il demone ntkd riguardo l'identità n esegue il primo metodo e ne comunica (come risposta al metodo remoto con cui ha ricevuto le informazioni) il completamento.

Dopo un certo tempo l'identità n riceve l'ordine di completare la migrazione. A questo punto il demone ntkd riguardo l'identità n esegue il secondo metodo e realizza così la creazione di n’. Così facendo gli archi-identità sono stati correttamente duplicati da n a n’.

Ora il demone ntkd procede con le successive operazioni usando le altre informazioni ricevute.

Il g-nodo g di livello i è quello che è stato trovato non saturo in G e dove è stato riservato un posto per il g-nodo w’, o il singolo nodo n’.

Naturalmente i è maggiore del livello k del g-nodo w (k vale 0 se l'ingresso è di un singolo nodo n).

A queste informazioni il demone ntkd aggiunge le altre che già aveva nella sua identità n dal livello 0 fino al livello k - 1. Cioè: il demone ntkd interroga l'istanza di QspnManager che gestisce l'identità n per avere il suo indirizzo Netsukuku e il suo fingerprint a livello 0. Il demone ntkd sa come estrarre dal fingerprint i valori delle anzianità fino al livello k - 1.

Il demone ntkd costruisce un indirizzo Netsukuku valido in g e il fingerprint a livello 0 per la nuova identità n’ in G. Per l'identificativo del fingerprint a livello 0, usa lo stesso che aveva prima. Per le posizioni dell'indirizzo Netsukuku:

• Per i livelli maggiori o uguali a i - 1 usa le posizioni che gli sono state comunicate ora.

• Per i livelli minori di i - 1 usa le posizioni che aveva l'indirizzo dell'identità n.

Per le anzianità del fingerprint:

• Per i livelli maggiori o uguali a i - 1 usa le anzianità che gli sono state comunicate ora.

• Per i livelli maggiori o uguali a k e minori di i - 1 usa zero (nel senso che è il primo g-nodo).

• Per i livelli minori di k usa le anzianità che erano dei g-nodi a cui apparteneva l'identità n.

Costruisce le istanze degli archi (IQspnArc) basandosi sugli archi-identità duplicati prima. Prepara una istanza di IQspnStubFactory.

Prima (Verifica: perché dovrebbe farlo prima?) di costruire la nuova istanza di QspnManager, il demone ntkd chiama il metodo destroy sull'istanza di QspnManager che gestisce l'identità n, per segnalare ai suoi diretti vicini esterni a w che sta uscendo dalla rete. Tale metodo esegue una chiamata broadcast a metodo remoto.

Il demone ntkd costruisce una istanza di QspnManager fornendo:

• Tipo di costruttore: ingresso nella rete (QspnManager.enter_net).

• Il proprio indirizzo Netsukuku (istanza di IQspnNaddr my_naddr).

• Il tipo dell'indirizzo: definitivo o di connettività ai livelli da i₀ a j₀.

• È lo stesso tipo di indirizzo che prima deteneva n.

• Gli archi che esistono tra il nodo e i suoi vicini (lista di istanze di IQspnArc my_arcs).

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

• La stub factory per le comunicazioni con i vicini (istanza di IQspnStubFactory stub_factory).

• Il livello k del g-nodo w che sta facendo il suo ingresso in G, 0 se era il singolo nodo n (intero hooking_gnode_level).

• Il manager precedente (istanza di QspnManager previous_identity). La nuova istanza di QspnManager copia da esso nella mappa i percorsi noti verso i g-nodi di livello inferiore a k (perché sono in w).

• Grazie a questi percorsi la nuova istanza calcola i fingerprint dal livello 1 al livello k (se k è maggiore di 0).

Una volta costruita la nuova istanza, il demone ntkd potrà dismettere la vecchia istanza, la quale adesso sicuramente non è la principale.

Una istanza di QspnManager costruita in questo modo entra in una fase di bootstrap al livello k. In seguito i border-nodi di w’ riceveranno degli ETP completi dai loro diretti vicini esterni a w’. Poi propagheranno le nuove conoscenze (cioè percorsi verso g-nodi esterni a w’) trasmettendo degli ETP ai nodi del grafo interni a w’. Alla fine ogni nodo del grafo (cioè ogni identità) riceve queste nuove conoscenze e può uscire dalla fase di bootstrap. Quando una istanza di QspnManager esce dalla fase di bootstrap lo notifica con il segnale bootstrap_complete.

Anche ad una istanza di QspnManager costruita in questo modo, il demone ntkd segnala le eventuali variazioni sugli archi con i metodi:

• arc_add (IQspnArc arc).

• arc_is_changed (IQspnArc changed_arc).

• arc_remove (IQspnArc removed_arc).

Migrazione

Supponiamo che il g-nodo w (a cui appartiene il nodo del grafo n che vive nel nostro sistema) migra da un g-nodo g di livello i ad un diverso g-nodo h (sempre di livello i) il quale appartiene a g-nodi distinti da quelli di g fino al livello j. In questa trattazione è incluso il caso in cui w equivale a n.

In qualche modo si è eletto un nodo n₀ in w — che deve essere l'identità principale del suo sistema — che ha un arco verso h a coordinare la migrazione. L'identità n₀ chiede ad un suo diretto vicino in h, chiamiamolo h₀, i dati che servono all'ingresso. Questa richiesta da n₀ a h₀ viene fatta con i metodi remoti di un modulo di identità. Per rispondere, h₀ inizia un dialogo con il Coordinator di h. Inoltre l'identità n₀ inizia un dialogo con il Coordinator di g per ottenere la prenotazione di un identificativo virtuale al livello i - 1 in g e la sua anzianità. Poi l'identità n₀ genera un identificativo di migrazione migration_id e propaga questi dati a tutto il g-nodo w, anche qui attraverso chiamate a metodo remoto fatte con un modulo di identità. Infine n₀ riceve conferma che tutti i nodi del grafo appartenenti al g-nodo w sono stati portati a conoscenza dei dati e del migration_id. A questo punto n₀ propaga analogamente a tutto il g-nodo w l'ordine di completare la migrazione.

Dobbiamo esaminare cosa avviene in ogni sistema in cui vivono dei nodi del grafo che appartengono a w. In particolare in ogni sistema possono vivere una o più istanze n di QspnManager (cioè nodi del grafo) che appartengono a w. Ogni identità n in w poteva detenere un indirizzo definitivo o uno di connettività in g-nodi interni a w.¹ Non sicuramente un indirizzo di connettività in g-nodi di livello superiore a w, in quanto il g-nodo w che migra (considerato nel suo insieme come singolo vertice nel grafo [G]_i) è sicuramente un g-nodo reale. Nel senso che il suo Netsukuku address, che è composto da identificativi dal livello i in su, non ha alcun componente virtuale.

Per ogni istanza n di QspnManager che apparteneva a w il demone ntkd crea una nuova istanza di QspnManager n’ basata su n che detiene un indirizzo in h analogo (definitivo o di connettività) a quello che deteneva n in w.

In questo modo si produce di fatto un g-nodo w’ all'interno del g-nodo h che è isomorfo al g-nodo w all'interno del g-nodo g.

Inoltre viene modificato l'indirizzo detenuto da n in uno di connettività ai livelli da i a j.

Nota 1: Quando diciamo che un nodo del grafo (o una identità) n, con n ∈ w, è di connettività in g-nodi interni a w intendiamo dire che l'indirizzo che n detiene è un indirizzo di connettività ai livelli da i a j, dove i è minore o uguale al livello di w. Non si fa alcuna assunzione invece sul valore j.

Creazione di una identità in h

I dati che ogni identità n riceve in relazione a questa migrazione da g in h sono:

• L'identificativo di migrazione migration_id. Si tratta di un identificativo univoco (un numero random) reso noto a tutti i partecipanti alla migrazione.

• L'indirizzo Netsukuku di h e la sua anzianità e quella dei suoi g-nodi superiori ai livelli da i a j.

• Un identificativo reale libero al livello i - 1 in h, oppure uno virtuale e la prenotazione di uno reale che verrà presto liberato.

• L'anzianità del nuovo g-nodo al livello i - 1 in h.

• Un identificativo virtuale al livello i - 1 in g, il primo libero.

• L'anzianità del nuovo identificativo in g.

Abbiamo già detto che tali informazioni giungono ad una precisa identità n che vive nel sistema. Il demone ntkd per ogni identità n crea una nuova identità n’.

Questa operazione di creazione di una nuova identità viene realizzata dal demone ntkd avvalendosi del modulo Identities, come esposto sopra. L'operazione avviene in due fasi, con il metodo prepare_add_identity e il metodo add_identity. Questi metodi richiedono due dati: l'identificativo di migrazione migration_id e l'identità n da duplicare. Subito, quando riceve le informazioni suddette, il demone ntkd riguardo l'identità n esegue il primo metodo e ne comunica (come risposta al metodo remoto con cui ha ricevuto le informazioni) il completamento.

Dopo un certo tempo l'identità n riceve l'ordine di completare la migrazione. A questo punto il demone ntkd riguardo l'identità n esegue il secondo metodo e realizza così la creazione di n’. Così facendo gli archi-identità sono stati correttamente duplicati da n a n’.

Ora il demone ntkd procede con le successive operazioni usando le altre informazioni ricevute.

Naturalmente i è maggiore del livello k del g-nodo w (k vale 0 se la migrazione è di un singolo nodo n).

A queste informazioni il demone ntkd aggiunge le altre che già aveva nella sua identità n dal livello 0 fino al livello k - 1. Cioè: il demone ntkd interroga l'istanza di QspnManager che gestisce l'identità n per avere il suo indirizzo Netsukuku e il suo fingerprint a livello 0. Il demone ntkd sa come estrarre dal fingerprint i valori delle anzianità fino al livello k - 1.

Il demone ntkd costruisce un indirizzo Netsukuku valido in h e il fingerprint a livello 0 per la nuova identità n’ in h. Per l'identificativo del fingerprint a livello 0, usa lo stesso che aveva prima. Per le posizioni dell'indirizzo Netsukuku:

• Per i livelli maggiori di j usa le posizioni che aveva l'indirizzo dell'identità n.

• Per i livelli maggiori o uguali a i - 1 e minori o uguali a j usa le posizioni che gli sono state comunicate ora.

• Per i livelli minori di i - 1 usa le posizioni che aveva l'indirizzo dell'identità n.

Per le anzianità del fingerprint:

• Per i livelli maggiori di j usa le anzianità che aveva l'indirizzo dell'identità n.

• Per i livelli maggiori o uguali a i - 1 e minori o uguali a j usa le anzianità che gli sono state comunicate ora.

• Per i livelli maggiori o uguali a k e minori di i - 1 usa zero (nel senso che è il primo g-nodo).

• Per i livelli minori di k usa le anzianità che erano dei g-nodi a cui apparteneva l'identità n.

Notiamo che il fatto di usare per la nuova identità di n lo stesso identificativo di fingerprint a livello 0 che si usava nella vecchia identità è necessario e non comporta alcun problema.

• È necessario perché risultino coerenti le informazioni acquisite con la vecchia identità riguardo i percorsi verso g-nodi interni a w. Questi verranno copiati nella nuova identità.

• Non comporta alcun problema riguardo l'assegnazione dell'identificativo di fingerprint ai g-nodi di livello maggiore di k. Infatti il g-nodo w in g avrà lo stesso identificativo di fingerprint del g-nodo isomorfo w’ in h. Ma il g-nodo w in g avrà ora una componente virtuale al livello i-1 e un valore di anzianità maggiore (significa che è meno anziano) degli altri g-nodi in g. Quindi è impossibile che il g-nodo g e il g-nodo h ottengano per questo un identificativo di fingerprint identico.

Costruisce le istanze degli archi (IQspnArc) basandosi sugli archi-identità duplicati prima. Prepara una istanza di IQspnStubFactory.

Costruisce una istanza di QspnManager fornendo:

• Tipo di costruttore: per migrazione (QspnManager.migration).

• Il proprio indirizzo Netsukuku (istanza di IQspnNaddr my_naddr).

• Il tipo dell'indirizzo: definitivo o di connettività ai livelli da i₀ a j₀.

• È lo stesso tipo di indirizzo che era prima deteneva n.

• Gli archi che esistono tra il nodo e i suoi vicini (lista di istanze di IQspnArc my_arcs).

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

• La stub factory per le comunicazioni con i vicini (istanza di IQspnStubFactory stub_factory).

• Il livello k del g-nodo w che sta facendo la migrazione, 0 se era il singolo nodo n (intero hooking_gnode_level).

• Il manager precedente (istanza di QspnManager previous_identity). La nuova istanza di QspnManager copia da esso nella mappa i percorsi noti verso i g-nodi di livello inferiore a k (perché sono in w).

• Grazie a questi percorsi la nuova istanza calcola i fingerprint dal livello 1 al livello k (se k è maggiore di 0).

• I livelli i e j della migrazione (interi migration_i e migration_j). TODO verificare se servono alla nuova istanza di QspnManager; forse basta che sono passati (come detto sotto) alla vecchia istanza quando viene modificata.

Una istanza di QspnManager costruita in questo modo entra in una fase di bootstrap al livello k. In seguito i border-nodi di w’ riceveranno degli ETP completi dai loro diretti vicini esterni a w’. Poi propagheranno le nuove conoscenze (cioè percorsi verso g-nodi esterni a w’) trasmettendo degli ETP ai nodi del grafo interni a w’. Alla fine ogni nodo del grafo (cioè ogni identità) riceve queste nuove conoscenze e può uscire dalla fase di bootstrap. Quando una istanza di QspnManager esce dalla fase di bootstrap lo notifica con il segnale bootstrap_complete.

Dopo che è uscita dalla fase di bootstrap, una istanza di QspnManager trasmette i suoi primi ETP ai diretti vicini. Dopo averli trasmessi, aspetta un certo tempo per accertarsi che i vicini abbiano avuto modo di processarli e poi emette il segnale presence_notified. Con questo segnala al suo utilizzatore che i suoi nodi diretti vicini sono a conoscenza dei percorsi che possono sfruttare attraverso tale nodo del grafo.

Questo fatto è particolarmente importante per una istanza di QspnManager costruita in questo modo. Infatti quando il demone ntkd riceve questo segnale dall'istanza n’ sa di poter chiedere alla istanza n (come vedremo sotto) di rimuovere gli archi esterni al livello j.

Anche ad una istanza di QspnManager costruita in questo modo, il demone ntkd segnala le eventuali variazioni sugli archi con i metodi:

• arc_add (IQspnArc arc).

• arc_is_changed (IQspnArc changed_arc).

• arc_remove (IQspnArc removed_arc).

Abbiamo detto che tra i dati di cui è in possesso l'identità n riguardanti questa migrazione c'è un identificativo reale libero al livello i - 1 in h, oppure uno virtuale e la prenotazione di uno reale che verrà presto liberato. Nel momento in cui l'identità n può trasformare l'identificativo virtuale al livello i - 1 in uno reale, il demone ntkd chiama su questa istanza di QspnManager il metodo make_real.

Modifica della precedente identità in g in una identità di connettività

Con i dati suddetti relativi alla migrazione il demone ntkd sull'istanza di QspnManager n chiama il metodo make_connectivity. Con questa chiamata segnala al modulo che questa diventa una identità di connettività. Gli argomenti passati sono:

• Il livello k del g-nodo w che ha migrato.

• I livelli i e j della migrazione.

• Il nuovo identificativo virtuale e la nuova anzianità al livello i - 1, cioè dentro g.

In seguito il demone ntkd sull'istanza di QspnManager n può chiamare questi metodi:

• remove_outer_arcs

• Chiede al modulo di rimuovere gli archi che collegano a g-nodi di livello maggiore di j.

• check_connectivity

• Il demone ntkd chiama questo metodo periodicamente sull'istanza di QspnManager n. Con esso chiede al modulo di controllare se la connettività interna dei g-nodi di livello da i a j è garantita anche senza il g-nodo w.

• Se il livello del g-nodo w è maggiore di 0, cioè se effettivamente era un g-nodo a migrare, vorremmo che fosse solo un singolo nodo in w a fare periodicamente queste operazioni di verifica. TODO investigare su come fare.

• Vorremmo evitare di fare questa operazione più volte per un g-nodo perché, lo ricordiamo, prima di chiamare check_connectivity sull'istanza n il demone ntkd deve ottenere un "lock" sui g-nodi interessati.

• Se la verifica ha esito positivo:

  • Se la migrazione era di un g-nodo w:

    • Il demone ntkd sull'istanza di QspnManager n chiama il metodo prepare_destroy: con esso chiede al modulo di propagare questa informazione agli altri nodi in w. Poi aspetta 10 secondi.

  • Il demone ntkd sull'istanza di QspnManager n chiama il metodo destroy: con esso chiede al modulo di segnalare ai suoi diretti vicini (esterni a w) che questa identità sta per essere distrutta.

  • Il demone ntkd dismette l'istanza di QspnManager n.

• prepare_destroy

• Chiede al modulo di istruire i suoi diretti vicini (interni a w) di attendere 10 secondi e poi scartare la loro identità. La comunicazione ai vicini avviene tramite il metodo remoto got_prepare_destroy della classe QspnManager.

• destroy

• Chiede al modulo di segnalare ai suoi diretti vicini (esterni a w) che l'identità chiamante sta per essere distrutta. La comunicazione ai vicini avviene tramite il metodo remoto got_destroy della classe QspnManager.

Ulteriori deliverable

Esaminiamo altri deliverable del modulo QSPN, che sono gli stessi per ogni tipo di identità e di modalità di costruzione del QspnManager.

Il modulo, attraverso il segnale arc_removed di QspnManager, notifica questi eventi:

• Una comunicazione attraverso un dato arco (ad esempio per richiedere al vicino un ETP completo) fatta con protocollo reliable fallisce (ad esempio per problemi al link). Per questo è stato rimosso l'arco dalla lista del QspnManager.

• Oppure la risposta alla richiesta di un ETP (fatta attraverso un dato arco) è un rifiuto perché il nostro nodo non risulta tra i suoi archi. Per questo è stato rimosso l'arco dalla lista del QspnManager.

Il modulo notifica l'inserimento di un nuovo g-nodo nella sua mappa attraverso il segnale destination_added di QspnManager e la rimozione di un g-nodo attraverso il segnale destination_removed di QspnManager.

Il modulo notifica l'inserimento di un nuovo percorso verso una destinazione attraverso il segnale path_added, la rimozione di un percorso attraverso il segnale path_removed e il cambio di qualche parametro in un percorso attraverso il segnale path_changed di QspnManager.

Il modulo notifica il cambio nel fingerprint di uno dei suoi g-nodi attraverso il segnale changed_fp di QspnManager.

Il modulo notifica un cambiamento significativo nel numero approssimato di nodi all'interno di uno dei suoi g-nodi attraverso il segnale changed_nodes_inside di QspnManager.

Il modulo notifica il rilevamento di uno split in un g-nodo di sua conoscenza attraverso il segnale gnode_splitted di QspnManager.

Il modulo permette di vedere se ha completato il suo bootstrap con il metodo is_bootstrap_complete di QspnManager.

Il modulo permette di ottenere la lista dei g-nodi nella sua mappa con il metodo get_known_destinations di QspnManager.

Il modulo permette di ottenere la lista di percorsi noti verso un certo g-nodo con il metodo get_paths_to di QspnManager.

Il modulo permette di leggere il fingerprint di uno dei suoi g-nodi con il metodo get_fingerprint di QspnManager.

Il modulo permette di leggere il numero approssimato di nodi all'interno di uno dei suoi g-nodi con il metodo get_nodes_inside di QspnManager.

Funzioni di appoggio

Alcune funzioni, definite e usate internamente al modulo, sono aggiunte alle classi così come sono state descritte nell'analisi funzionale. Le illustriamo ora perché nel seguito del documento sono riportati alcuni algoritmi che ne fanno uso.

Aggiunte alla classe NodePath:

• La proprietà dinamica cost : viene calcolata dinamicamente come somma dei costi di arc e path .

• La proprietà exposed : indica se per questo percorso un segnale di path_added era stato emesso e in seguito nessun segnale di path_removed. Questo flag serve a gestire correttamente i segnali che il modulo deve emettere quando diversi percorsi verso un g-nodo di livello maggiore di 0 indicano fingerprint diversi (potenziale split).

• Quando viene creata una istanza di NodePath la proprietà exposed è sempre inizializzata a False. Solo quando l'istanza viene messa nella mappa del nodo, allora può venire impostata a True.

• I metodi hops_arcs_equal_etppath( EtpPath p ) e hops_arcs_equal( NodePath np ) :

• Si ricorda che due percorsi sono distinti se usano un diverso gateway o lo raggiungono attraverso una diversa interfaccia di rete del nodo corrente; oppure se la sequenza di passi fino alla destinazione (compresa) non è identica sia come g-nodi sia come archi di uscita. Considerato che nei percorsi memorizzati nella mappa la sequenza di archi comprende anche l'identificativo dell'arco del nodo corrente che lo collega al gateway; considerato che un arco univocamente identifica anche il gateway che vi è collegato; si deduce che il test di uguaglianza di un percorso NodePath np nella mappa del nodo con un altro percorso si basa esclusivamente sulle liste np.path.hops e np.path.arcs .

• Si consideri inoltre che i confronti con altri percorsi ricevuti in un ETP (istanze di EtpPath ) vengono fatti dopo che la Grouping Rule è stata eseguita, quindi anche essi comprendono come primo elemento delle liste hops e arcs gli identificativi riferiti al passo dal nodo corrente al suo gateway.

• Il metodo hops_arcs_equal_etppath( EtpPath p ) : confronta questa istanza con il percorso p ricevuto in un ETP tramite l'arco arc di questa istanza.

• Il metodo hops_arcs_equal( NodePath np ) : confronta questa istanza con l'istanza np .

Produzione e trasmissione di ETP

La costruzione e il passaggio di ETP quando necessario ai propri vicini è realizzata dal modulo in autonomia, senza necessitare di interventi dal suo utilizzatore.

Per sapere a chi deve inviare gli ETP e da chi deve riceverli il modulo si basa sugli archi che gli sono stati passati.

Quando riceve un ETP se non riesce ad associarlo ad uno degli archi che conosce (si intende anche dopo aver atteso il tempo di rilevamento) allora lo ignora. Quando riceve una richiesta di ETP se non riesce ad associarla ad uno degli archi che conosce allora risponde con l'eccezione QspnNotAcceptedError.

Il modulo assume che i nodi collegati ai suoi archi appartengano alla sua stessa rete.

L'elaborazione degli ETP ricevuti dai miei vicini che appartengono alla mia stessa rete da come risultato l'aggiornamento della mia mappa; allo stesso tempo mi permette anche di capire quali informazioni saranno di interesse anche per gli altri miei vicini, quindi mi consente di costruire un messaggio che sia esaustivo e allo stesso tempo più piccolo possibile. Il dettaglio di come tale elaborazione avviene è descritto nel documento esplorazione.

Metodi remoti

L'implementazione della trasmissione di ETP ai vicini avviene con l'uso di due metodi remoti: get_full_etp e send_etp .

Il metodo get_full_etp viene chiamato dal nodo n sul vicino v quando vuole ottenere da v un ETP completo . Il documento di esplorazione descrive cosa si intende per ETP completo. Quando un nodo chiede espressamente un ETP ad un suo vicino (o a tutti i vicini uno alla volta) si tratta sempre di un ETP completo.

Il metodo send_etp viene usato dal nodo n quando vuole spontaneamente inviare un ETP ad un suo vicino o a più vicini in broadcast. In questo caso può trattarsi di un ETP completo oppure no. Per questo il metodo send_etp prevede un parametro booleano che dice se l'ETP è completo.

Produzione del primo ETP

Prendiamo in esame un nodo che ha appena costituito una nuova rete. Il modulo QSPN cioè non riceve nessun arco. La sua mappa è vuota. Vediamo cosa deve fare per costruire un nuovo ETP completo, presumibilmente perché un nuovo nodo ha appena fatto ingresso nella rete e gli chiede un ETP.

Innanzi tutto la sua mappa è vuota, quindi la lista dei percorsi P è vuota.

Ci sono due informazioni che vanno inserite nell'ETP e che sono rappresentate con classi che il modulo non conosce: il fingerprint dei suoi g-nodi ai vari livelli e il suo indirizzo di nodo.

Al modulo viene passato l'indirizzo del nodo come istanza dell'interfaccia IQspnMyNaddr, che a sua volta richiede l'interfaccia IQspnNaddr. Nell'ETP va inclusa una istanza di IQspnNaddr, quindi questa istanza va bene. Il modulo assume che l'istanza sia anche un oggetto serializzabile.

Al modulo viene passato il fingerprint del nodo a livello 0 come istanza dell'interfaccia IQspnFingerprint. Anche questa si assume che sia un oggetto serializzabile. Inoltre, tramite il metodo i_qspn_construct chiamato sull'istanza del fingerprint a livello 0 e passando un set vuoto (ci riferiamo sempre ad un nodo con la mappa ancora vuota), gli viene restituita un'altra istanza di IQspnFingerprint che è il fingerprint del suo g-nodo a livello 1. Anche questa si assume che sia un oggetto serializzabile. E così via.

La lista del numero approssimativo di nodi all'interno dei propri g-nodi ai vari livelli, per un nodo con la mappa ancora vuota è banalmente una lista con l volte il valore 1.

Nell'ETP vi è anche una lista di HCoord che rappresenta il percorso di questo ETP. Un nodo che produce un ETP nuovo vi mette una List<HCoord> vuota.

In conclusione il modulo è in grado di costruire una istanza della classe EtpMessage con i dati necessari. Si tratta di un oggetto serializzabile, che quindi può essere usato nelle chiamate (o risposte) a metodi remoti.

Processazione di un set di ETP

Gli algoritmi illustrati nei successivi paragrafi, volti a processare un set di ETP, vengono eseguiti dal nodo n in queste possibili circostanze:

• Il nodo n è appena entrato in una rete e quindi ha chiesto un ETP a tutti i suoi vicini.

• Il nodo n ha rilevato un nuovo arco a verso un vicino v e quindi ha chiesto un ETP a v.

• Il nodo n ha rilevato il cambio di costo in un arco a_changed e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso tra gli argomenti di questo algoritmo ho anche l'arco a_changed che ha avuto una variazione.

• Il nodo n ha rilevato la rimozione di un arco a_removed e quindi ha chiesto un ETP a tutti i suoi vicini. In questo caso prima di iniziare questo algoritmo, il nodo n ha rimosso dalla sua mappa tutti i percorsi che sfruttavano l'arco a_removed.

• Il nodo n ha ricevuto un ETP inviato in broadcast da un suo vicino.

Rielaborazione dei percorsi in ogni ETP ricevuto

Sia m un ETP che il nodo n riceve dal nodo v attraverso l'arco a.

Quando il modulo riceve una istanza di EtpMessage che gli viene trasmessa in una chiamata a metodo remoto, questa contiene le istanze degli oggetti che l'utilizzatore del modulo (nell'altro nodo) ha costruito e che il modulo continua a conoscere solo in quanto implementazioni delle interfacce a lui note. Inoltre riconoscendo l'arco a da cui ha ricevuto il messaggio può ottenere l'istanza di IQspnCost che rappresenta il suo costo. Anche questa si assume che sia un oggetto serializzabile. Infine, sempre avendo individuato l'arco a, ha individuato l'identificativo id ( a ) , che è un intero.

Il nodo n calcola il livello i del minimo comune g-nodo tra n e v.

Il nodo n esamina la lista di hop percorsi da m. Per prima cosa esegue la Grouping Rule su tale lista per renderla coerente con i g-nodi a cui n appartiene. Poi esegue la Acyclic Rule sulla lista, e se vede che m era già passato per il mio nodo (o g-nodo) lo ignora del tutto.

Infine n esamina il set di percorsi P contenuto in m, ma deve renderli coerenti con i suoi g-nodi. Ecco come realizza questo:

• 1) Il nodo n elimina dal set P tutti i percorsi che sono stati dichiarati da ignorare all'esterno di v_i-1.

• 2) Per ogni percorso p rimasto in P il nodo n esegue la Grouping Rule.

• 3) Per ogni percorso p in P il nodo n esegue la Acyclic Rule e se vede che il percorso ha fatto un ciclo lo rimuove da P.

• 4) Il nodo n aggiunge a P il percorso verso v_i-1 con costo null e fingerprint e numero di nodi così come riportati in m.

• 5) Solo se m è un ETP completo:

  • Il nodo n cerca in tutta la sua mappa i percorsi che partono dal gateway v attraverso l'arco a. Li mette in un set M_a .

  • Per ogni percorso np in M_a :

    • Cerca un percorso p in P tale che np .hops_arcs_equal_etppath( p ).

    • Se non esiste tale p:

      • Crea una copia np₀ di np con costo dead e la mette nel set Q . Per farlo, crea una nuova istanza di EtpPath p₀ copiando i valori di np’ e mettendo cost a dead. Non c'è bisogno di valorizzare ignore_outside . Poi crea una istanza di NodePath np₀ associando al percorso p₀ l'arco a .

• 6) Per tutti i percorsi p del set P, i quali sono istanze di EtpPath, il nodo n crea una istanza di NodePath q associando al percorso p l'arco a . Mette q nel set Q .

Spieghiamo il punto 4. La ricezione di un ETP comporta sempre l'acquisizione di qualche informazione sulla rete, quindi contribuisce a popolare la mappa di n. Infatti, anche quando la lista P nell'ETP m fosse vuota, l'ETP contiene intrinsecamente un percorso verso il massimo distinto g-nodo di v per n, che indichiamo con v_i-1. Per rappresentare questo percorso intrinseco, il modulo nel nodo n costruisce una istanza della classe EtpPath con questi dati:

• La sequenza hops è composta da un solo g-nodo che è v_i-1.

• La sequenza arcs è composta dal solo id ( a ) .

• Il costo del percorso è null. Esso rappresenta il costo da v ad v.

• Il fingerprint del g-nodo è il fingerprint indicato nell'ETP m al livello i - 1.

• Il numero di nodi nel g-nodo è il numero di nodi indicato nell'ETP m al livello i - 1.

Spieghiamo il punto 5. Siccome m è un ETP completo, tutti i percorsi che n può usare passando per v sono presenti in m.P . Quindi i vecchi percorsi che n conosceva e che non sono in m.P andranno rimossi dalla mappa di n .

Spieghiamo il punto 6. In tutte le istanze di EtpPath ricevute nell'ETP (più quella costruita come detto adesso per rappresentare il percorso intrinseco verso il g-nodo vicino) il costo del percorso rappresenta il costo da v alla destinazione. Invece il costo da n ad v è il costo dell'arco a. Questo dato è già memorizzato nell'oggetto arco che comunque il modulo deve mantenere associato al percorso, per questo nella mappa interna del nodo n ogni percorso è in realtà memorizzato come istanza della classe NodePath, la quale include l'istanza di EtpPath.

Variazioni nella mappa di n

Quando abbiamo descritto, nel documento esplorazione, la gestione degli eventi che portano a variazioni nel grafo della rete, abbiamo più volte usato diciture quali "n aggiorna la sua mappa" e "mette in P i percorsi che nella sua mappa hanno subito variazioni".

Qui riportiamo l'algoritmo che realizza queste macro-operazioni. Inoltre l'algoritmo riportato evita di occupare memoria con percorsi che non sono disgiunti da altri già noti, come richiesto nell'analisi funzionale. Infine si occupa di emettere i segnali di variazioni nella mappa del nodo (nuova destinazione, nuovo percorso, ...) e i segnali di g-nodi splittati.

Il rilevamento dello split di un g-nodo d si ha quando per raggiungere d vengono rilevati due percorsi che differiscono per il loro fingerprint e se questa situazione si mantiene per un certo lasso di tempo. Tale 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 attraverso l'istanza di IQspnThresholdCalculator. 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 minimo 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. Ricevuto questo tempo, il modulo si occupa di emettere alla sua scadenza il segnale gnode_splitted di QspnManager se la situazione si è mantenuta.

Algoritmo

Il nodo n, dopo aver rielaborato i percorsi nel set di ETP ricevuti, si trova infine con un set di percorsi nuovi che chiamiamo Q. Indichiamo con M l'insieme dei percorsi che già prima il nodo n conosceva, cioè la sua mappa.

• Il nodo n prepara, per ogni livello i da 0 a l - 1, un insieme Z_i con i g-nodi di livello i diretti vicini del suo g-nodo di livello i.

• Il nodo n prepara una lista P, inizialmente vuota, di percorsi che andranno segnalati ai vicini a cui si inoltrerà l'ETP.

• Il nodo n prepara una lista B, inizialmente vuota, di destinazioni per le quali alla fine intende iniziare un nuovo flood. Questo per la regola di primo rilevamento di split.

• Il nodo n raggruppa i percorsi contenuti in Q per destinazione.

• Ordina le destinazioni per fare in modo che siano elaborate per prime le destinazioni più interne (con livello più basso); inoltre, a parità di livello, siano elaborate per prime le destinazioni più vicine, cioè quelle per le quali il percorso più rapido ha un numero minore di hops in quel livello.
• Questo previo ordinamento fa in modo che almeno uno dei percorsi verso ogni destinazione sarà memorizzato con successo. Infatti, se quando il nodo elabora un percorso esso contiene un hop che ancora non è conosciuto dal nodo come possibile destinazione, tale percorso va scartato. Purtroppo questo non è sufficiente a rendere subito validi tutti i percorsi, ma lo saranno al prossimo ETP.

• Per ogni destinazione d:

  • Sia Q_d l'insieme dei percorsi nuovi verso d.

  • Sia M_d l'insieme dei percorsi precedentemente noti verso d.

  • Se d.lvl > 0:

    • Il nodo n prepara una lista F ’ con tutti i fingerprint distinti che conosceva per il g-nodo d.

  • Il nodo n prepara una lista O_d, inizialmente vuota, di percorsi verso d che sono correnti e andranno ordinati.

  • Il nodo n prepara una lista V_d, inizialmente vuota, di percorsi verso d che hanno subito una variazione.

  • Il nodo n prepara una lista S_d, inizialmente vuota, di segnali da emettere.

  • Per ogni p’ ∈ M_d :

    • Il nodo n controlla se esiste un p’’ ∈ Q_d che abbia la stessa sequenza di passi. Questo confronto fra p’ e p’’, che sono entrambi istanze di NodePath, avviene con il metodo hops_arcs_equal che tiene conto delle liste hops e arcs. Se esiste:

      • Siamo di fronte a un aggiornamento sulle informazioni relative ad un percorso che era già noto. 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. Infatti se la modifica è non cruciale e non rilevante si preferisce ignorarla per ridurre il traffico di rete.
      • Se l'aggiornamento è giudicato rilevante:

        • p’’ viene scartato da Q_d.

        • p’’ viene aggiunto a O_d.

        • p’’ viene aggiunto a V_d.

      • Altrimenti:

        • p’’ viene scartato da Q_d.

        • p’ viene aggiunto a O_d.

        • Se p’.arc.i_qspn_equals(a_changed):

          • p’ viene aggiunto a V_d.

    • Altrimenti:

      • p’ viene aggiunto a O_d.

      • Se p’.arc.i_qspn_equals(a_changed):

        • p’ viene aggiunto a V_d.

  • Tutti i percorsi rimasti in Q_d vengono aggiunti a O_d.

  • Poi il nodo n ordina O_d in base al costo crescente. Esegue su questa lista l'algoritmo descritto nel documento percorsi disgiunti per scartare quelli non sufficientemente disgiunti e tenere solo i max_paths più rapidi. Nel fare questo tiene conto dei requisiti che vincolano i percorsi che il nodo n può scartare: per questo avrà bisogno dei set Z_i e del set dei diretti vicini. Alla fine in O_d non possono rimanere percorsi con costo = dead.

  • Infine il nodo n sulla base del contenuto delle liste di appoggio prima descritte (O_d, M_d e V_d) crea nuove istanze di EtpPath per popolare la lista P che andrà a comporre l'ETP che sarà inoltrato ai vicini e allo stesso tempo compone il set S_d dei segnali da emettere per questa destinazione. Illustriamo l'algoritmo di questa operazione, tenendo conto che i confronti tra istanze di NodePath anche qui vanno fatti con il metodo hops_arcs_equal :

    • valid_fp_d = null.

    • Se d.lvl > 0:

      • Per ogni p ∈ O_d :

        • fp_d,p = fingerprint di d come riportato da p.

        • Se valid_fp_d = null:

          • valid_fp_d = fp_d,p.

        • Altrimenti Se valid_fp_d è meno anziano di fp_d,p :

          • valid_fp_d = fp_d,p.

    • Per ogni p ∈ O_d :

      • Se p ∉ M_d :

        • fp_d,p = fingerprint di d come riportato da p.

        • p2 = copia iniziale di p . Vedere sotto l'algoritmo di produzione di un percorso da inviare.

        • Metti p2 in P.

        • Se d.lvl = 0:

          • Prepara un segnale di path_added e aggiungilo al set S_d.

        • Altrimenti:

          • Se fp_d,p = valid_fp_d:

            • Prepara un segnale di path_added e aggiungilo al set S_d.

            • p.exposed = True.

          • Altrimenti:
            • Niente.

    • Per ogni p ∈ M_d :

      • fp_d,p = fingerprint di d come riportato da p.

      • Se p ∉ O_d :

        • p2 = copia iniziale di p.

        • p2.cost = dead.

        • Metti p2 in P.

        • Se d.lvl = 0:

          • Prepara un segnale di path_removed e aggiungilo al set S_d.

        • Altrimenti:

          • Se p.exposed :

            • Prepara un segnale di path_removed e aggiungilo al set S_d.

          • Altrimenti:
            • Niente.
      • Altrimenti:

        • Sia p1 l'istanza in O_d equivalente di p, che la sostituirà in M_d.

        • Se p ∈ V_d :

          • p2 = copia iniziale di p.

          • Metti p2 in P.

          • Se d.lvl = 0:

            • Prepara un segnale di path_changed e aggiungilo al set S_d.

          • Altrimenti:

            • Se p.exposed :

              • Se fp_d,p = valid_fp_d:

                • Prepara un segnale di path_changed e aggiungilo al set S_d.

                • p1.exposed = True.

              • Altrimenti:

                • Prepara un segnale di path_removed e aggiungilo al set S_d.

            • Altrimenti:

              • Se fp_d,p = valid_fp_d:

                • Prepara un segnale di path_added e aggiungilo al set S_d.

                • p1.exposed = True.

              • Altrimenti:
                • Niente.

  • Il nodo n sostituisce O_d al vecchio M_d. Cioè:

    • Se M_d = ∅ e O_d ≠ ∅, allora inserisce in testa al set S_d il segnale destination_added.

    • Se M_d ≠ ∅ e O_d = ∅, allora aggiunge in coda al set S_d il segnale destination_removed.

    • Rimuove da M tutti i percorsi verso d e vi aggiunge tutti i percorsi che ora sono in O_d.

    • Emette tutti i segnali che sono in S_d.

  • Se d.lvl > 0:

    • Il nodo n prepara una lista F ’’ con tutti i fingerprint distinti che conosce adesso per il g-nodo d.

    • Valuta dal confronto tra F ’ ed F ’’ se è necessario iniziare un nuovo flood di ETP con i percorsi per d per la regola di primo rilevamento di split. Cioè:

      • Se F ’’.size > 1:

        • Per ogni fp ∈ F ’’:

          • Se fp ∉ F ’:

            • Se d ∉ B :

              • Metti d in B.

            • Esci dal ciclo.

        • Sia fp_eldest il più anziano in F ’’.

        • Sia bp_eldest il miglior percorso verso d che riporta come fingerprint fp_eldest.

        • Rimuovi fp_eldest da F ’’.

        • Per ogni fp ∈ F ’’:

          • Sia bp il miglior percorso verso d che riporta come fingerprint fp.

          • Avvia in una nuova tasklet:

            • Sia una lista globale del modulo pending_gnode_split .

            • Se la coppia (fp_eldest , fp ) è presente in pending_gnode_split :

              • Esci.

            • Metti la coppia (fp_eldest , fp ) in pending_gnode_split .

            • Calcola il tempo di tolleranza prima della segnalazione dello split. Si calcola con il threshold_calculator passando le istanze bp_eldest e bp .

            • Aspetta il tempo di tolleranza.

            • Togli la coppia (fp_eldest , fp ) da pending_gnode_split .

            • Se per la destinazione d è ancora noto un percorso che riporta il fingerprint fp_eldest :

              • Per ogni arco a nei miei archi:

                • Se il vicino collegato tramite a appartiene a d :

                  • Se il percorso per d tramite a riporta il fingerprint fp :

                    • Emetti il segnale gnode_splitted indicando a, d ed fp .

• Ora la mappa di n è aggiornata.

• Il nodo n cicla la lista P per finalizzare le istanze dei percorsi che andranno segnalati ai vicini a cui si inoltrerà l'ETP. Vedere sotto l'algoritmo di produzione di un percorso da inviare.

Ora la mappa di n è aggiornata. Inoltre abbiamo in P l'elenco dei percorsi nella mappa di n che hanno subito variazioni.

Infine abbiamo in B tutte le destinazioni per cui si ritiene necessario inviare un nuovo flood. Quindi:

• Se B ≠ ∅:

  • Il nodo n prepara un nuovo ETP con tutti i percorsi che conosce verso le destinazioni d ∈ B. Lo invia a tutti i suoi vicini.

Variazioni nei propri g-nodi

Dopo aver completato un aggiornamento della propria mappa, il nodo n aggiorna anche le informazioni relative ai propri g-nodi, cioè fingerprint e numero di nodi all'interno. Se ci sono state variazioni n se ne accorge e questo è importante per decidere se l'ETP ricevuto va inoltrato ai suoi vicini.

Supponiamo che il nodo n riceve un percorso p verso la destinazione d che prima non conosceva. La destinazione d è un g-nodo di livello i all'interno del suo g-nodo di livello i + 1. Nel percorso p è anche indicato il fingerprint di d e il numero di nodi interni al g-nodo d. Il fingerprint di d va ora incluso nel set di fingerprint di g-nodi di livello i da passare al metodo 'i_qspn_construct' del fingerprint del g-nodo di livello i di n per ottenere il fingerprint del g-nodo di livello i + 1 di n. Analogamente, il numero di nodi interni a d va a sommarsi a quelli interni agli altri g-nodi di livello i e al numero di nodi interni al g-nodo di livello i di n per ottenere il numero di nodi interni al g-nodo i + 1 di n.

Quando invece si riceve un percorso verso una destinazione d che già si conosceva attraverso altri percorsi, può capitare che le informazioni riguardo d differiscano.

Se per un g-nodo d vengono rilevati 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 d. Il modulo lo segnalerà con un evento, come descritto prima nell'algoritmo. Nel frattempo il modulo mantiene e trasmette tutti i percorsi verso d che conosce con il loro fingerprint, ma soltanto i percorsi con il fingerprint assegnato dal più anziano x all'interno di d vengono restituiti all'esterno del modulo con il metodo get_paths_to ( d ) .

Se per un g-nodo d vengono rilevati due percorsi che differiscono per il numero di nodi interni a d, invece, questo non indica che il g-nodo d 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 i + 1.

Quando si calcolano il fingerprint e il numero di nodi interni al proprio g-nodo di livello i, per ogni g-nodo noto di livello i - 1 si usano i dati riportati dai percorsi verso quel g-nodo che riportano il fingerprint più anziano, in caso ce ne siano di discordi.

Un approccio particolare va attuato a livello i = 1. Considerando il proprio g-nodo di livello 1, i suoi componenti sono singoli nodi. Per i singoli nodi non ha senso pensare ad uno split, quindi se due percorsi verso una data destinazione di livello 0 riportano un fingerprint diverso può solo significare che il vecchio nodo è morto e un altro nodo ha preso la sua posizione; è solo questione di tempo prima che uno dei due fingerprint scompaia. Non avrebbe senso inoltre cercare di stabilire quale dei due fingerprint discordi sarebbe il più anziano, cercando di confrontare l'anzianità dei suoi g-nodi interni. Infine c'è da dire che si sa con certezza che il numero di nodi interni ad ogni singolo membro di un g-nodo di livello 1 (cioè il numero di nodi interni ad un singolo nodo) è 1. Queste osservazioni saranno chiare quando sotto verrà illustrato l'approccio per i livelli maggiori di 1.

Illustriamo l'approccio da usare a livello 1. E' noto il fingerprint fp₀ del mio nodo. Poniamo nn₀ = 1. Siano g₁ , g₂ , ..., g_y i nodi di livello 0 presenti nella mia mappa. Il calcolo di fp₁ dipende da fp₀ e dai fingerprint fp(g_j) degli altri g-nodi. Il calcolo di nn₁ è dato da 1 (cioè nn₀) più il numero degli altri nodi. Per ogni g_j prendiamo solo il percorso più rapido che abbiamo nella mappa e diamo per buono il fingerprint da esso riportato.

Illustriamo l'approccio da usare ai livelli maggiori. Si parte dal livello i = 2 e si sale fino a l. Diamo per buono il fingerprint fp_i-1 del mio g-nodo di livello i - 1 e il numero di nodi al suo interno nn_i-1. Siano g₁ , g₂ , ..., g_y i g-nodi di livello i - 1 presenti nella mia mappa. Il calcolo di fp_i dipende da fp_i-1 e dai fingerprint fp(g_j) degli altri g-nodi. Allo stesso modo il calcolo di nn_i dipende da nn_i-1 e dal numero di nodi nn(g_j) all'interno degli altri g-nodi. Sia g_j uno di questi e siano p₁(g_j) , p₂(g_j) , ..., p_x(g_j) i percorsi noti verso g_j. Raggruppiamo i percorsi in base al fingerprint che ciascuno riporta, che potrebbero essere diversi. Prendiamo solo il gruppo di percorsi che hanno il fingerprint che risulta essere stato assegnato dal g-nodo interno più anziano (metodo i_qspn_elder_seed). Consideriamo questo fingerprint come il fingerprint fp(g_j) di g_j. Inoltre da questo gruppo prendiamo il percorso più rapido e consideriamo il numero di nodi riportato da questo come il numero di nodi nn(g_j) interni a g_j. Ripetiamo per tutti i g-nodi di livello i - 1 presenti nella mia mappa e usiamo questi valori per il calcolo delle analoghe informazioni relative al mio g-nodo di livello i.

Quando queste informazioni portano ad una variazione nel fingerprint di uno dei g-nodi del nodo corrente, il QspnManager emette il segnale changed_fp. Quando portano ad una variazione nel numero di nodi interni ad uno dei g-nodi del nodo corrente, emette il segnale changed_nodes_inside.

Algoritmo

Dopo aver aggiornato la sua mappa sulla base di un set di ETP, il nodo n procede così per ricalcolare le informazioni dei propri g-nodi:

• Sia my_fingerprints[i] il valore che n conosce attualmente come fingerprint del suo g-nodo di livello i.

• Sia my_nodes_inside[i] il valore che n conosce attualmente come numero di nodi interni al suo g-nodo di livello i.

• changes_in_my_gnodes = False.

• Per il livello i = 1:

  • FP = nuovo set vuoto.

  • NN = 0.

  • Per ogni destinazione d di livello 0 nella mia mappa:

    • best_p = miglior percorso NodePath verso d.

    • fp_d = fingerprint di d come riportato da best_p.

    • Aggiungi fp_d al set FP.

    • Somma 1 a NN.

  • new_fp = my_fingerprints[0] .i_qspn_construct( FP ).

  • Se new_fp ≠ my_fingerprints[1] :

    • my_fingerprints[1] = new_fp.

    • changes_in_my_gnodes = True.

    • Emetti segnale changed_fp a livello 1.

  • new_nn = 1 + NN.

  • Se new_nn ≠ my_nodes_inside[1] :

    • my_nodes_inside[1] = new_nn.

    • changes_in_my_gnodes = True.

    • Emetti segnale changed_nodes_inside a livello 1.

• Per ogni livello i da 2 a l :

  • FP = nuovo set vuoto.

  • NN = 0.

  • Per ogni destinazione d di livello i - 1 nella mia mappa:

    • fp_d = null.

    • nn_d = -1.

    • best_p = null.

    • Per ogni NodePath p in d :

      • fp_d,p = fingerprint di d come riportato da p.

      • nn_d,p = numero nodi di d come riportato da p.

      • Se fp_d = null:

        • fp_d = fp_d,p .

        • nn_d = nn_d,p .

        • best_p = p .

      • Altrimenti:

        • Se fp_d ≠ fp_d,p :

          • Se fp_d è meno anziano di fp_d,p :

            • fp_d = fp_d,p .

            • nn_d = nn_d,p .

            • best_p = p .

        • Altrimenti:

          • Se p.cost < best_p.cost:

            • nn_d = nn_d,p .

            • best_p = p .

    • Aggiungi fp_d al set FP.

    • Somma nn_d a NN.

  • new_fp = my_fingerprints[i-1] .i_qspn_construct( FP ).

  • Se new_fp ≠ my_fingerprints[i] :

    • my_fingerprints[i] = new_fp.

    • changes_in_my_gnodes = True.

    • Emetti segnale changed_fp a livello i.

  • new_nn = my_nodes_inside[i-1] + NN.

  • Se new_nn ≠ my_nodes_inside[i] :

    • my_nodes_inside[i] = new_nn.

    • changes_in_my_gnodes = True.

    • Emetti segnale changed_nodes_inside a livello i.

Ora abbiamo in changes_in_my_gnodes se sono state apportate variazioni alle informazioni relative ai g-nodi di n.

Produzione di percorsi da mettere in un ETP da inviare

La valorizzazione dei dati in una istanza di EtpPath, cioè un percorso da includere in un ETP da inviare, si fa in due fasi.

La prima fase avviene durante l'algoritmo con cui il nodo n aggiorna la sua mappa partendo dai nuovi percorsi noti. In questa fase si valorizzano tutti i dati che possono essere ricavati dalla istanza di NodePath che è stata aggiunta/variata/rimossa nella mappa di n .

Sia q tale istanza di NodePath. Indichiamo con q.path l'istanza di EtpPath inclusa in q. Indichiamo con q.arc l'istanza di IQspnArc inclusa in q.

Il nodo n prepara una nuova istanza p di EtpPath. Copia tutte le informazioni da q.path a p; come costo indica q.cost, cioè la somma dei costi q.path.cost e q.arc.cost . Poi p viene messa in un set P con cui comporre l'ETP.

La seconda fase avviene alla fine degli aggiornamenti alla mappa. Questo perché in questa fase si valorizzano i dati che vanno ricavati non solo dalla istanza di NodePath in esame ma anche da altre informazioni contenute nella mappa di n .

Il nodo n cicla tutte le istanze p in P . Per ognuna, ricalcola tutti i valori booleani che indicano se il percorso p va ignorato all'esterno di un suo g-nodo.

• p .ignore_outside[ 0 ] = False.

• Per ogni livello i da 1 a l - 1 :

  • Se p .hops.last().lvl ≥ i :

    • j = 0.

    • Mentre True:

      • Se p .hops[ j ].lvl ≥ i :

        • Esci dal ciclo.

      • Incrementa j di 1.

    • Se non esiste nella mia mappa la destinazione d che rappresenta p .hops[ j ]:

      • Se p .cost.is_dead():

        • p .ignore_outside[ i ] = False.

        • continue.
      • Altrimenti:
        • assert_not_reached.

    • best_to_arc = null.

    • Per ogni NodePath q in d :

      • Se q .arcs.last() = p .arcs[ j ]:

        • Se best_to_arc = null:

          • best_to_arc = q .

        • Altrimenti:

          • Se q .cost < best_to_arc .cost:

            • best_to_arc = q .

    • Se best_to_arc = null:

      • p .ignore_outside[ i ] = False.

    • Altrimenti:

      • same = False.

      • Se best_to_arc .hops.size = j - 1 :

        • same = True.

        • Per k che va da 0 a j - 1 :

          • Se best_to_arc .hops[ k ] ≠ p .hops[ k ]:

            • same = False.

            • Esci dal ciclo.

          • Se best_to_arc .arcs[ k ] ≠ p .arcs[ k ]:

            • same = False.

            • Esci dal ciclo.

      • p .ignore_outside[ i ] = NOT same .

  • Altrimenti:

    • p .ignore_outside[ i ] = True.

Alla fine tutto il contenuto di P è pronto per essere messo nell'EtpMessage da inviare.

Proof of concept

Come proof of concept è stato realizzato un programma, qspnclient, che si avvale del modulo QSPN per stabilire come impostare le rotte nelle tabelle di routing del kernel di una macchina. Si tratta di un programma specifico per un sistema Linux.

Questo programma imposta le rotte del sistema. L'utente sarà quindi in grado di verificare che il sistema riesca effettivamente a stabilire connessioni con gli altri nodi della rete, che le rotte siano quelle che ci si attende, eccetera. Inoltre il programma interattivamente consente di chiedere al modulo QSPN le informazioni che ha raccolto e mostrarle all'utente.

Di seguito descriviamo le operazioni svolte da questo programma. Sarà interessante anche perché alcuni aspetti analizzati qui saranno ripresi nella realizzazione del demone ntkd completo.

Interazione del programma con l'utente

Il programma qspnclient prevede che l'utente immetta, come argomenti della riga di comando e in modo interattivo dalla console durante la sua esecuzione, tutti i requisiti del modulo. Anche i parametri che normalmente sarebbero individuati in modo autonomo dal demone ntkd (per esempio l'identificativo del nodo, gli indirizzi di scheda, ...) nel caso del qspnclient sono espressamente indicati dall'utente, questo per rendere più facilmente riproducibili gli ambienti di test.

Nel dettaglio questi sono i dati che il programma richiede all'utente:

• Identificativo del nodo. E' un numero che identifica in modo univoco un nodo tra i suoi diretti vicini. Va indicato sulla riga di comando quando si lancia il programma.
• Indirizzo Netsukuku del nodo e topologia della rete. Vanno indicati sulla riga di comando quando si lancia il programma.
• Anzianità del nodo ai vari livelli. Vanno indicate sulla riga di comando quando si lancia il programma.
• Interfacce di rete gestite. Vanno indicate sulla riga di comando quando si lancia il programma. Per ogni interfaccia va indicato:
  • Indirizzo di scheda.
• Archi costituiti. Vanno indicati in modo interattivo durante l'esecuzione del programma. Ogni arco si può:
  • Creare. Alla creazione vanno indicati:
    • Il nome dell'interfaccia del nodo corrente; l'interfaccia deve essere una di quelle gestite.
    • L'indirizzo di scheda del vicino e il suo MAC.
    • Il costo in microsecondi dell'arco.
    • L'indirizzo Netsukuku del vicino.
    • L'identificativo del vicino.
  • Cambiare il costo. Alla modifica vanno indicati:
    • L'indirizzo di scheda del vicino.
    • Il nuovo costo in microsecondi dell'arco.
  • Rimuovere. Alla rimozione va indicato:
    • L'indirizzo di scheda del vicino.

In modo interattivo vengono anche avviate le operazioni del modulo QSPN. Per il primo nodo n0 che forma la rete, il comando di avvio operazioni viene dato subito dopo il lancio del programma, quando ancora il nodo non ha costituito alcun arco. Per gli altri nodi è necessario prima dare almeno un comando di costituzione di un arco con un vicino e poi dare il comando di avvio operazioni. Ad esempio si lancia il programma sul nodo n1, poi si da il comando interattivo (sulla console del nodo n1) di costituzione di un arco con n0, infine si da il comando interattivo (sulla console del nodo n1) di avviare le operazioni. E' inoltre necessario che il corrispettivo comando di costituzione dell'arco venga dato anche sulla console del nodo n0, dopo l'avvio delle operazioni di n1 ma in tempi rapidi. Il tempo massimo di rilevamento dell'arco è infatti fissato dal programma qspnclient a 10 secondi.

In generale quando si formano archi (all'avvio di un nuovo nodo nella rete, ma anche in seguito quando due nodi già entrati formano per qualche motivo un nuovo arco che prima non c'era) e quando si rimuovono archi occorre che i comandi vengano dati dalle console di entrambi i nodi. Queste rilevazioni infatti non sono compiti del modulo QSPN.

Al lancio del programma qspnclient l'utente indica attraverso appositi flag come vuole che il nodo si comporti riguardo le forme di contatto anonimo. Questo concetto verrà spiegato più sotto. Il comportamento di default del programma, se l'utente non indica alcun flag a riguardo, è di:

• abilitare l'anonimizzazione dei pacchetti che transitano per il nodo;
• non accettare richieste indirizzate al nodo da un client in forma anonima.

Indirizzi di scheda e archi verso i vicini

Fra le cose che il programma qspnclient deve gestire senza alcun intervento da parte del modulo QSPN, vi è la costituzione di archi con i vicini. Si tratta di archi che il modulo QSPN riceve come requisito, attraverso i quali deve essere messo in grado di comunicare con i vicini, anche in modo reliable, prima ancora di iniziare a trasmettere e ricevere messaggi ETP, quindi prima di sapere l'indirizzo Netsukuku dei suoi vicini o le destinazioni che possono essere raggiunte attraverso di essi. Questo viene realizzato dal programma qspnclient, e sarà così anche per il demone ntkd, con l'uso di indirizzi locali di scheda. Quindi il programma qspnclient, senza avvalersi del modulo QSPN, ha questi compiti:

• quando inizia a gestire una interfaccia di rete:
  • gli assegna il suo indirizzo di scheda (ip address add 169.254.... dev ...).
  • si mette con una tasklet in ascolto dei messaggi UDP sull'interfaccia.
  • si mette con una tasklet in ascolto dei messaggi TCP sull'indirizzo di scheda.
• quando forma un arco, prima di passare al modulo QSPN l'istanza di IQspnArc:
  • aggiunge una rotta diretta al vicino usando gli indirizzi di scheda suo e del vicino (ip route add 169.254.... dev ... src 169.254....).
• quando rimuove un arco, oppure se il programma termina:
  • rimuove la rotta diretta al vicino (ip route del 169.254.... dev ... src 169.254....).
• quando smette di gestire una interfaccia di rete:
  • gli rimuove il suo indirizzo di scheda (ip address del 169.254..../32 dev ...).
  • termina la tasklet in ascolto dei messaggi UDP sull'interfaccia.
  • termina la tasklet in ascolto dei messaggi TCP sull'indirizzo di scheda.

Spazio di indirizzi Netsukuku

Gli indirizzi dei nodi nella rete Netsukuku, nella sua attuale implementazione, vanno ricavati nella classe IPv4 10.0.0.0/8.

La rete viene suddivisa in un numero arbitrario di livelli. La notazione CIDR usata per individuare classi di indirizzi nelle reti IPv4, ci obbliga ad usare come gsize ad ogni livello una potenza di 2. In teoria, ad esempio, potremmo avere un livello 0 di gsize 5. Ma quando vogliamo indicare nelle tabelle di routing tutti gli indirizzi di un g-nodo di livello 1 (ad esempio da 10.1.2.0 a 10.1.2.4) non potremmo farlo in forma compatta. Invece se usiamo un livello 0 di gsize 8, per riferirci agli indirizzi nel g-nodo da 10.1.2.0 a 10.1.2.7 possiamo usare la notazione 10.1.2.0/29; per gli indirizzi da 10.1.2.8 a 10.1.2.15 useremo 10.1.2.8/29; e così via.

Indichiamo con l il numero dei livelli. Indichiamo con gsize(i) la dimensione dei g-nodi di livello i + 1. Tali dimensioni devono essere potenze di 2. Indichiamo con g-exp(i) l'esponente della potenza di 2 che dà la dimensione dei g-nodi di livello i + 1. Il numero di bit necessari a coprire lo spazio di indirizzi è dato dalla sommatoria per i da 0 a l - 1 di g-exp(i). 𝛴 _{0 ≤ i < l} g-exp(i).

Questo numero di bit non può essere maggiore di 22. Gli indirizzi nella classe 10.0.0.0/8 hanno 24 bit, ma due di questi li riserviamo per notazioni particolari (routing interno ai g-nodi e forma anonima).

Inoltre dobbiamo assicurarci che gsize(l-1) ≥ l. Cioè che nello spazio destinato al livello più alto sia possibile rappresentare un numero da 0 a l - 1. Questo pure ci serve per la notazione usata per il routing interno ai g-nodi.

Indirizzi del nodo

Per assegnarsi un indirizzo IPv4, un nodo parte dal suo indirizzo Netsukuku, che è una sequenza di posizioni all'interno dei vari g-nodi di appartenenza ad ogni livello. Il nodo calcola per prima cosa il suo indirizzo globale N, che è un indirizzo IPv4 che identificherà in modo univoco quel nodo in tutta la rete.

Poi il nodo calcola un indirizzo N_i, che è sempre un indirizzo IPv4, che identificherà in modo univoco quel nodo nel suo g-nodo di livello i; questo per ogni i da 1 a l - 1.

Tutti questi indirizzi il nodo se li assegna.

Inoltre, opzionalmente, il nodo può calcolare per ognuno di questi indirizzi (N, N₁, N₂, ...) un altro indirizzo corrispettivo per i pacchetti che gli sono destinati in "forma anonima". Si tratta sempre di ulteriori indirizzi IPv4 che identificano questo nodo in modo univoco (a livello globale o all'interno di un suo g-nodo). Questi però saranno usati, come vedremo in seguito, dai client per contattare questo nodo senza rivelare il proprio indirizzo. Il nodo quindi può assegnarsi questi indirizzi oppure no. Se lo fa significa che vuole dare la possibilità ai client di usare questo meccanismo per contattarlo e fargli richieste senza essere identificati.

L'opzione di accettare richieste anonime è distinta e indipendente dall'opzione di rendere anonimi i pacchetti che transitano per il nodo nel percorso verso un'altra destinazione. Quest'altra opzione verrà discussa in seguito.

In un altro documento viene spiegato come questi indirizzi vengono calcolati a partire dall'indirizzo Netsukuku. TODO

Vediamo come queste impostazioni si configurano in un sistema Linux e quindi quali operazioni fa il programma qspnclient.

In un sistema Linux il sistema si assegna un indirizzo associandolo ad una interfaccia di rete. In realtà ogni interfaccia può avere più indirizzi e anche lo stesso indirizzo può essere associato a più interfacce; inoltre anche se un indirizzo x viene associato alla interfaccia nicA e non all'interfaccia nicB, un pacchetto destinato a x ricevuto tramite l'interfaccia nicB giunge ugualmente al processo che sta in ascolto sull'indirizzo x.

Si noti che il fatto di associare un indirizzo IP ad una specifica interfaccia di rete ha la sua importanza in relazione al protocollo di risoluzione degli indirizzi IP in indirizzi MAC (Address Resolution Protocol). Infatti quando un nodo a vuole trasmettere un pacchetto IP ad un suo diretto vicino b, esso conosce l'indirizzo IP di b e l'interfaccia di rete di a dove trasmettere. Il nodo a trasmette in broadcast su quel segmento di rete una richiesta: "chi ha l'indirizzo IP XYZ?". Il nodo b risponde indicando al nodo a l'indirizzo MAC della sua interfaccia di rete. Quindi il nodo a può incapsulare il pacchetto IP in un frame Ethernet che riporta gli indirizzi MAC dell'interfaccia che trasmette e dell'interfaccia che deve ricevere.

Se il nodo b ha diverse interfacce di rete tutte collegate allo stesso segmento di rete, il fatto di associare diversi indirizzi IP a diverse interfacce può fornire un modo di identificare una precisa interfaccia di rete a cui un pacchetto va trasmesso. Questo è usato dal modulo Qspn per distinguere i pacchetti che vanno ricevuti da una pseudo-interfaccia, per questo gli indirizzi link-local sono diversi su ogni interfaccia e sulle pseudo-interfacce.

Fatta questa premessa, come si comporta il programma?

Il programma, all'avvio, computa tutti i suoi indirizzi (nello spazio Netsukuku) e li associa tutti a ognuna delle interfacce di rete che gestisce.

Inoltre, prima di terminare, li rimuove da tutte le interfacce che gestisce.

Rotte nelle tabelle di routing

Il programma deve istruire le policy di routing del sistema (che di norma significa impostare delle rotte nelle tabelle di routing) in modo da garantire questi comportamenti:

• Se un processo locale vuole inviare un pacchetto ad un indirizzo d nello spazio di Netsukuku:

  • Se il modulo QSPN non ha alcun percorso verso la destinazione d:

    • Il sistema non trova nelle tabelle del kernel alcuna rotta e segnala al processo che la destinazione d è irraggiungibile.

  • Altrimenti:

    • Il sistema trova nelle tabelle del kernel una rotta il cui gateway è costituito dal primo hop del miglior percorso (fra tutti quelli che il modulo QSPN ha scoperto) verso la destinazione d.

• Se un pacchetto è ricevuto da un vicino v ed è destinato ad un altro indirizzo d nello spazio di Netsukuku:

  • Se il modulo QSPN non ha alcun percorso verso la destinazione d, tale che non contenga fra i suoi hop il massimo distinto g-nodo del vicino v:

    • Il sistema non trova nelle tabelle del kernel alcuna rotta; quindi scarta il pacchetto e invia un pacchetto ICMP "host d irraggiungibile" al mittente.

  • Altrimenti:

    • Il sistema trova nelle tabelle del kernel una rotta il cui gateway è costituito dal primo hop per il miglior percorso verso la destinazione d, tale che non contenga il g-nodo del vicino.

    • Se l'indirizzo d è nello spazio di indirizzi che codificano la richiesta di anonimato:

      • Opzionalmente, il sistema trova una regola che gli impone di mascherare l'indirizzo del mittente (cioè di indicare se stesso come mittente e inoltrare le comunicazioni di risposta che riceverà al vero mittente).

Vediamo come queste impostazioni si configurano in un sistema Linux e quindi quali operazioni fa il programma qspnclient. Esaminiamo prima l'aspetto del source natting e poi del routing.

Source NATting

Il source NATting in un sistema Linux può essere realizzato istruendo il kernel con il comando iptables (utilizzando una regola con l'estensione SNAT nella catena POSTROUTING della tabella nat). Quando un pacchetto da inoltrare rientra nei parametri di questa regola (un esempio di parametro che si può usare è l'indirizzo di destinazione del pacchetto che rientra in un dato range) allora il kernel modifica l'indirizzo mittente nel pacchetto sostituendolo con uno dei suoi indirizzi pubblici. Inoltre compie una serie di altre operazioni volte a mantenere inalterate il più possibile le caratteristiche della comunicazione (ad esempio la connessione stabilita dal protocollo TCP).

Ad esempio, con il comando «iptables -t nat -A POSTROUTING -d 10.128.0.0/9 -j SNAT --to 10.1.2.3» si ottiene che tutti i pacchetti da inoltrare alle destinazioni 10.128.0.0/9 vanno rimappati al mio indirizzo 10.1.2.3

Fatta questa premessa, come si comporta il programma?

Il programma, all'avvio, opzionalmente, istruisce il kernel per il source natting. Con questa configurazione il nodo si rende disponibile ad anonimizzare i pacchetti che riceve e che vanno inoltrati verso una destinazione che accetta richieste anonime.

L'opzione di rendere anonimi i pacchetti che transitano per il nodo nel percorso verso un'altra destinazione è distinta e indipendente dall'opzione di accettare richieste anonime, che è stata discussa sopra.

• NOTA: La seguente spiegazione sui motivi per cui l'operazione è opzionale va spostata in un documento che affronta ad alto livello le implicazioni sul detenere un nodo nella rete Netsukuku. Il documento presente si limita a illustrare i dettagli implementativi del programma qspnclient o del demone ntkd.

• Questa azione è opzionale perché il proprietario di un nodo può avere remore a nascondere il vero mittente di un messaggio prendendo il suo posto. In realtà questo timore sarebbe infondato, vediamo perché. Per far funzionare bene l'operazione di contatto anonimo da parte del client, occorre che il nodo che fa da server (fornisce un servizio) si assegni anche gli indirizzi per essere contattato in forma anonima. Se fa questa operazione opzionale, significa che è pronto a ricevere alcune richieste dalle quali saprà di non poter risalire al mittente. Sarà quindi responsabile di rispondere o meno a tali richieste e non potrà far ricadere tale onere sugli altri nodi.
• Anche considerando quindi non rischiosa l'azione di implementare nel proprio nodo il source natting, l'azione è opzionale perché il nodo che la implementa si carica di un onere che costa un po' in termini di memoria. Se il nodo quindi ha scarse risorse (si intende molto scarse, come pochi mega di RAM) conviene che non la implementi.
• Va considerato che se un nodo decide di non implementare questa azione, comunque il meccanismo di trasmissione anonima risulta efficace se nel percorso tra il mittente e il destinatario almeno un nodo è disposto a implementarla. Invece, se un nodo decide di implementare l'azione e ad un certo punto le sue risorse di memoria venissero meno, in questo caso la comunicazione in corso ne verrebbe compromessa.

Se il nodo decide di implementare il source natting, calcola lo spazio di indirizzi che indicano una risorsa da raggiungere in forma anonima. Una volta calcolato il numero di bit necessari a ricoprire i vari livelli della nostra rete -si rilegga il paragrafo sopra sullo spazio di indirizzi Netsukuku- vanno considerati altri 2 bit in testa; il primo di questi va impostato e tutti gli altri sono liberi. Se ad esempio si usano tutti i 22 bit a disposizione per gli indirizzi, allora il range di indirizzi che indicano una risorsa da raggiungere in forma anonima è 10.128.0.0/9.

Poi il range viene ulteriormente scomposto in un numero di sottoclassi pari al numero dei livelli nella rete. Il primo blocco costituisce gli indirizzi globali delle risorse da raggiungere in forma anonima; si caratterizza per avere NON impostato il secondo bit. Nel nostro esempio, il range di questo blocco è 10.128.0.0/10.

Prendiamo ora ogni livello i della nostra rete, da 1 a l - 1 inclusi, dove l è il numero di livelli. Il blocco del livello i costituisce gli indirizzi interni al nostro g-nodo di livello i delle risorse (interne al suddetto g-nodo) da raggiungere in forma anonima; si caratterizza per avere impostato il secondo bit e per avere codificato il numero i nei bit destinati all'identificativo del livello più alto.

Riprendiamo il nostro esempio e supponiamo che ci siano nella rete 10 livelli e il più alto abbia dimensione 16, vale a dire gsize(9) = 16, g-exp(9) = 4. Allora il blocco del livello i ha impostato il primo e il secondo bit ed ha codificato il numero i nei 4 bit dalla posizione 3 alla 6 incluse. Questi sono quindi i blocchi:

• 10.196.0.0/14
• 10.200.0.0/14
• 10.204.0.0/14
• 10.208.0.0/14
• 10.212.0.0/14
• 10.216.0.0/14
• 10.220.0.0/14
• 10.224.0.0/14
• 10.228.0.0/14

Supponiamo ora che il nostro nodo sia nel g-nodo di livello 9 con posizione 5 e, per semplicità, supponiamo posizione 0 a tutti gli altri livelli. Quindi -si rilegga il paragrafo sopra sugli indirizzi del nodo- il nostro nodo ha assegnati a se questi indirizzi (in forma non anonima):

• 10.20.0.0 (come indirizzo globale)
• 10.68.0.0 (come interno al suo g-nodo di livello 1)
• 10.72.0.0
• 10.76.0.0
• 10.80.0.0
• 10.84.0.0
• 10.88.0.0
• 10.92.0.0
• 10.96.0.0
• 10.100.0.0 (come interno al suo g-nodo di livello 9)

Allora il programma istruisce il kernel di modificare i pacchetti destinati ai seguenti range indicando come nuovo indirizzo mittente uno dei propri indirizzi, come segue:

• iptables -t nat -A POSTROUTING -d 10.128.0.0/10 -j SNAT --to 10.20.0.0

• iptables -t nat -A POSTROUTING -d 10.196.0.0/14 -j SNAT --to 10.68.0.0

• iptables -t nat -A POSTROUTING -d 10.200.0.0/14 -j SNAT --to 10.72.0.0

• iptables -t nat -A POSTROUTING -d 10.204.0.0/14 -j SNAT --to 10.76.0.0

• iptables -t nat -A POSTROUTING -d 10.208.0.0/14 -j SNAT --to 10.80.0.0

• iptables -t nat -A POSTROUTING -d 10.212.0.0/14 -j SNAT --to 10.84.0.0

• iptables -t nat -A POSTROUTING -d 10.216.0.0/14 -j SNAT --to 10.88.0.0

• iptables -t nat -A POSTROUTING -d 10.220.0.0/14 -j SNAT --to 10.92.0.0

• iptables -t nat -A POSTROUTING -d 10.224.0.0/14 -j SNAT --to 10.96.0.0

• iptables -t nat -A POSTROUTING -d 10.228.0.0/14 -j SNAT --to 10.100.0.0

Quando il programma termina, se aveva istruito il kernel per fare il source natting, rimuove le regole che aveva messe nella catena POSTROUTING della tabella nat.

Routing

In un sistema Linux le rotte vengono memorizzate in diverse tabelle. Queste tabelle hanno un identificativo che è un numero da 0 a 255. Hanno anche un nome descrittivo: l'associazione del nome al numero (che in realtà è il vero identificativo) è fatta nel file /etc/iproute2/rt_tables.

In ogni tabella possono esserci diverse rotte. Ogni rotta ha alcune informazioni importanti:

• Destinazione. E' in formato CIDR. Indica una classe di indirizzi. Solo se il pacchetto è destinato a quella classe allora la rotta va presa in considerazione. Se ci sono più classi che soddisfano il pacchetto, allora si prende quella più restrittiva.
• Unreachable. Se presente indica che la destinazione è irraggiungibile.
• Gateway (gw) e interfaccia (dev). Dice dove trasmettere il pacchetto.
• Mittente preferito (src). Questa informazione è usata solo per i pacchetti trasmessi dal sistema locale, non per i pacchetti da inoltrare. E' un indirizzo del sistema locale. Dice quale indirizzo locale usare come mittente, se non viene espressamente specificato un indirizzo locale dal processo che richiede la trasmissione.

Quando un pacchetto va inviato ad una certa destinazione, ci sono delle regole che dicono al sistema su quali tabelle guardare. Queste regole, visibili con il comando ip rule list, di default dicono di guardare per prima la tabella "local", per penultima la tabella "main" e per ultima la tabella "default". Tra la regola che dice di guardare la "local" e quella che dice di guardare la "main" possono essere inserite altre regole.

Ogni regola può dire semplicemente di guardare una tabella, oppure di guardarla solo a determinate condizioni. Una particolare condizione che ci torna utile è questa: "guarda la tabella XXX se il pacchetto da trasmettere è marcato con il numero YYY". La marcatura del pacchetto è virtuale, nel senso che i dati del pacchetto non sono affatto modificati, ma solo il sistema locale lo vede come marcato; ed è sempre il sistema locale che lo ha precedentemente marcato. Questa marcatura viene fatta da una parte del kernel che può essere istruita usando l'azione MARK del comando iptables.

Fatta questa premessa, come si comporta il programma?

Per ogni arco verso un vicino, il programma memorizza una rotta diretta (cioè senza gateway) nella tabella "main", indicando come destinazione l'indirizzo di scheda del vicino e come mittente preferito il proprio indirizzo di scheda. Questo lo abbiamo visto poco sopra; infatti il comando "ip route add" senza specificare un nome di tabella si riferisce alla tabella "main".

Il programma crea una tabella "ntk" con identificativo YYY, dove YYY è il primo identificativo libero nel file /etc/iproute2/rt_tables. Tale tabella sarà inizialmente vuota; in essa il programma andrà a mettere le rotte di pertinenza della rete Netsukuku, cioè quelle con destinazione nello spazio 10.0.0.0/8. Inoltre aggiunge una regola che dice di guardare la tabella "ntk" prima della "main".

Il programma, per ogni suo arco, crea un'altra tabella chiamata "ntk_from_XXX" con identificativo YYY, dove XXX è il MAC address del nodo vicino, YYY è il primo identificativo libero nel file /etc/iproute2/rt_tables. Questa tabella conterrà rotte da esaminare solo per i pacchetti da inoltrare che ci sono pervenuti attraverso questo arco. Il programma quindi aggiunge una regola che dice di guardare la tabella "ntk_from_XXX" se il pacchetto da trasmettere è marcato con il numero YYY. Inoltre istruisce il kernel di marcare con il numero YYY i pacchetti che hanno XXX come MAC di provenienza.

Anche le varie tabelle "ntk_from_XXX" conterranno solo rotte di pertinenza della rete Netsukuku, cioè quelle con destinazione nello spazio 10.0.0.0/8.

Inoltre, sia la tabella "ntk" sia le varie "ntk_from_XXX" conterranno la rotta "unreachable 10.0.0.0/8". Questa rotta verrà presa in esame solo se un pacchetto ha una destinazione all'interno dello spazio di Netsukuku, ma per tale destinazione non esistono altre rotte valide con una classe più restrittiva. In altre parole, una destinazione per la quale non si conosce nessun percorso. Questa particolare rotta dice che il pacchetto non potrà giungere a destinazione e il suo mittente ne va informato.

Sulla base degli eventi segnalati dal modulo QSPN, e se necessario richiamando i suoi metodi pubblici, il programma qspnclient popola e mantiene le rotte nelle tabelle "ntk" e "ntk_from_XXX". I percorsi segnalati dal modulo QSPN contengono sempre un arco del nodo corrente come passo iniziale e da tale arco si può risalire all'indirizzo di scheda del vicino. Le rotte nelle tabelle "ntk" e "ntk_from_XXX" infatti devono avere come campo gateway (gw) l'indirizzo di scheda del vicino, non il suo indirizzo Netsukuku.

Per ogni percorso scelto dal programma qspnclient per entrare in una tabella, in realtà il programma inserisce nella tabella fino a 4 rotte. Sia i il livello del g-nodo destinazione del percorso. Queste sono le rotte:

• Globale. La destinazione di questa rotta è l'indirizzo del g-nodo nella sua forma globale, il suo "src" è il mio indirizzo nella sua forma globale.
• Anonimo globale. La destinazione di questa rotta è l'indirizzo del g-nodo nella sua forma globale e con anonimato, il suo "src" è il mio indirizzo nella sua forma globale.

• Se i < levels - 1:

  • Interno al nostro g-nodo di livello i + 1. La destinazione di questa rotta è l'indirizzo del g-nodo nella sua forma interna al g-nodo di livello i + 1, il suo "src" è il mio indirizzo nella sua forma interna al g-nodo di livello i + 1.

  • Anonimo interno al nostro g-nodo di livello i + 1. La destinazione di questa rotta è l'indirizzo del g-nodo nella sua forma interna al g-nodo di livello i + 1 e con anonimato, il suo "src" è il mio indirizzo nella sua forma interna al g-nodo di livello i + 1.

Quando il programma ha finito di usare una tabella (ad esempio se un arco che conosceva non è più presente, oppure se il programma termina) svuota la tabella, poi rimuove la regola, poi rimuove il record relativo dal file /etc/iproute2/rt_tables.