Differences between revisions 6 and 7
Revision 6 as of 2015-03-11 07:46:47
Size: 15194
Editor: lukisi
Comment:
Revision 7 as of 2015-03-12 18:30:36
Size: 16831
Editor: lukisi
Comment:
Deletions are marked like this. Additions are marked like this.
Line 129: Line 129:
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. Si parte dal livello ''i'' = 1 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~-,,1,,-~'' , ''g~-,,2,,-~'' , ..., ''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 dai fingerprint ''nn(g~-,,j,,-~)'' degli altri g-nodi. Sia ''g~-,,j,,-~'' uno di questi e siano ''p~-,,1,,-~(g~-,,j,,-~)'' , ''p~-,,2,,-~(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 più anziano. 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''.

Modulo QSPN - Dettagli Tecnici

Requisiti

L'utilizzatore del modulo QSPN per prima cosa inizializza il modulo richiamando il metodo statico QspnManager.init ( ) .

Prima di iniziare ad usare il modulo QSPN, il nodo deve essere a conoscenza del suo indirizzo Netsukuku; deve essere un indirizzo non ancora preso nella rete; deve essere un indirizzo compatibile con gli archi del nodo, cioè tale che se il nodo entra in un g-nodo esistente g di livello i abbia almeno un arco verso un altro nodo appartenente a g. Di fatto per ottenere questo il nodo contatta i suoi vicini e raccoglie informazioni sui loro g-nodi di appartenenza ai vari livelli, compreso il livello più alto; poi sceglie uno di questi g-nodi per entrarvi, quindi contatta il Coordinator del g-nodo scelto e si accorda con lui per farsi assegnare un posto al suo interno. Tutta questa operazione, ripetiamo, non è di pertinenza del modulo QSPN.

La strategia che si adotta per la scelta del g-nodo non è di competenza del modulo QSPN. Viene descritta nel documento TODO: inserire.

Dallo stesso Coordinator del g-nodo g il nodo ottiene anche altre informazioni che servono al modulo QSPN, come l'anzianità di g e dei suoi g-nodi superiori e l'anzianità del g-nodo che il nodo corrente costituirà, per poter produrre il proprio fingerprint di nodo. L'identificativo del fingerprint è generato dal nodo come numero random in uno spazio abbastanza grande di modo che sia presumibilmente univoco a livello di rete.

Quindi il nodo istanzia il suo QspnManager passando al costruttore:

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

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

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

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

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

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

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

Quando ci sono variazioni sugli archi, richiama sul QspnManager i metodi:

  • arc_add (IQspnArc arc).

  • arc_is_changed (IQspnArc changed_arc).

  • arc_remove (IQspnArc removed_arc).

Deliverables

Quando viene costruito il QspnManager gli viene passata una lista di archi. Se non ci sono archi significa che il nodo sta generando una nuova rete, quindi il modulo si considera da subito maturo. Il modulo lo segnala attraverso il segnale qspn_mature di QspnManager.

Se invece ci sono degli archi il modulo li memorizza in una sua lista my_arcs e si considera non maturo. In questo caso chiede ai vicini di comunicargli le loro mappe con un ETP completo.

Le richieste sono fatte su ogni singolo arco, in parallelo, con protocollo reliable. Se una richiesta fallisce (per problemi al link) il relativo arco viene rimosso dalla lista del modulo (my_arcs) e viene emesso il segnale arc_removed di QspnManager.

Alcuni dei nodi vicini possono rifiutare la richiesta perché il nostro nodo non risulta tra i loro archi. Anche per questi il relativo arco viene rimosso dalla lista del modulo (my_arcs) e viene emesso il segnale arc_removed di QspnManager.

Alcuni dei nodi vicini possono rifiutare la richiesta perché a loro volta non sono ancora maturi. Per questi non viene rimosso l'arco, ma semplicemente non abbiamo potuto ricevere da loro un ETP.

Quando tutte le richieste hanno terminato si avrà una lista di ETP. Se tale lista risultasse vuota allora il modulo emette il segnale failed_hook di QspnManager affinché il nodo consideri fallito l'ingresso nella rete e riprovi da capo. Quando viene emesso il segnale failed_hook l'utilizzatore del modulo è tenuto a scartare l'istanza di QspnManager.

Se invece la lista contiene uno o più ETP, il modulo li elabora. Poi si considera maturo, quindi emette il segnale qspn_mature di QspnManager.


Il modulo segnala quando rimuove dalla sua lista un arco non funzionante attraverso il segnale arc_removed di QspnManager.


Il modulo segnala 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 segnala 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 segnal path_changed di QspnManager.


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


Il modulo segnala il cambio nel numero di nodi stimati all'interno di uno dei suoi g-nodi attraverso il segnale changed_nodes_inside di QspnManager.


Il modulo segnala 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 si considera maturo con il metodo is_mature 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 conoscere la stima del numero di nodi all'interno di uno dei suoi g-nodi con il metodo get_nodes_inside di QspnManager.

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.


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, cioè quando un nuovo nodo vuole fare hook 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 una istanza di ISerializable.

Al modulo viene passato il fingerprint del nodo a livello 0 come istanza dell'interfaccia IQspnFingerprint. Anche questa si assume che sia un ISerializable. 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 ISerializable. 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 TP-List, che è una lista di HCoord, una classe serializzabile che il modulo conosce. Un nodo che produce un ETP nuovo vi mette una TP-List vuota.

In conclusione il modulo è in grado di costruire una istanza della classe EtpMessage con i dati necessari e serializzarla per usarla nelle chiamate a metodi remoti.


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 IQspnREM che rappresenta il suo costo. Anche questa si assume che sia un ISerializable.

Popolamento della mappa

Quindi il modulo comincia a popolare la mappa del nodo. Infatti: chiamiamo n il nodo che ci ha inviato l'ETP e v il nodo corrente; anche quando la lista P nell'ETP ricevuto fosse vuota, l'ETP contiene intrinsecamente un percorso verso il massimo distinto g-nodo di n per v. Per rappresentare questo percorso intrinseco, il modulo nel nodo v costruisce una istanza della classe EtpPath con questi dati:

  • La TP-List è composta da un solo g-nodo che è il massimo distinto g-nodo di n per v.

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

  • Il fingerprint del g-nodo è il fingerprint indicato nell'ETP al livello del massimo distinto g-nodo di n per v.

  • Il numero di nodi nel g-nodo è il numero di nodi indicato nell'ETP al livello del massimo distinto g-nodo di n per v.

In tutte le istanze di EtpPath ricevute nell'ETP (più quella costruita come detto adesso per rappresentare il percorso intrinseco) il costo del percorso rappresenta il costo da n alla destinazione. Invece il costo da v ad n è 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 v ogni percorso è in realtà memorizzato come istanza della classe NodePath, la quale include l'istanza di EtpPath.

La prossima volta che il nodo v produce un ETP la sua mappa non sarà più vuota. Sia q una istanza di NodePath della mappa di v che va comunicata. Indichiamo con q.path l'istanza di EtpPath inclusa in q. Indichiamo con q.arc l'istanza di IQspnArc inclusa in q. Il nodo v prepara una nuova istanza di EtpPath copiando tutte le informazioni da q.path; ma come costo dovrà indicare la somma dei costi q.path.cost e q.arc.cost. Questa nuova istanza va messa nella lista P dell'EtpMessage da inviare.

Aggiornamento dei dati dei propri g-nodi

Attraverso la ricezione di messaggi ETP il nodo aggiorna anche i dati relativi ai propri g-nodi. Supponiamo infatti che il nodo v 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 v per ottenere il fingerprint del g-nodo di livello i+1 di v. 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 v per ottenere il numero di nodi interni al g-nodo i+1 di v.

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. Nel frattempo il modulo mantiene e trasmette tutti i percorsi che conosce con il loro fingerprint, ma soltanto i percorsi con il fingerprint più anziano, per ogni destinazione d, vengono restituiti all'esterno del modulo con il metodo get_paths_to ( d ) .

Il tempo di tolleranza è direttamente proporzionale alla somma delle latenze associate ai due percorsi che differiscono; ma il modulo QSPN non ha questa informazione in quanto il costo associato ad un percorso non sappiamo se sia espresso in latenza, in larghezza di banda o in altra metrica; quindi il calcolo di tale tempo di tolleranza va demandato all'utilizzatore del modulo il quale fornisce una callback 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.

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. Si parte dal livello i = 1 e si sale fino a l. Diamo per buono il fingerprint fpi-1 del mio g-nodo di livello i-1 e il numero di nodi al suo interno nni-1. Siano g1 , g2 , ..., gy i g-nodi di livello i-1 presenti nella mia mappa. Il calcolo di fpi dipende da fpi-1 e dai fingerprint fp(gj) degli altri g-nodi. Allo stesso modo il calcolo di nni dipende da nni-1 e dai fingerprint nn(gj) degli altri g-nodi. Sia gj uno di questi e siano p1(gj) , p2(gj) , ..., px(gj) i percorsi noti verso gj. 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 più anziano. Consideriamo questo fingerprint come il fingerprint fp(gj) di gj. Inoltre da questo gruppo prendiamo il percorso più rapido e consideriamo il numero di nodi riportato da questo come il numero di nodi nn(gj) interni a gj. 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.

Netsukuku/ita/docs/ModuloQSPN/DettagliTecnici (last edited 2016-07-28 08:54:14 by lukisi)