|
Size: 37788
Comment:
|
← Revision 35 as of 2016-07-28 08:54:14 ⇥
Size: 100
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Modulo QSPN - Dettagli Tecnici = <<TableOfContents(4)>> Il presente documento assume che siano stati letti il documento di [[Netsukuku/ita/docs/ModuloQSPN/AnalisiFunzionale|Analisi Funzionale]] e quelli in esso indicati ([[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete|Esplorazione della rete]] e [[Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti|Percorsi disgiunti]]). == Requisiti == L'utilizzatore del modulo QSPN per prima cosa inizializza il modulo richiamando il metodo statico ''init'' di !QspnManager. In tale metodo viene anche passata l'istanza di INtkdTasklet per fornire l'implementazione del sistema di tasklet. 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 il !QspnManager memorizza i suoi archi, per ognuno genera un identificativo, cioè un intero random in uno spazio grande. Memorizza in una lista gli archi, accertandosi che non ci siano archi ripetuti. Memorizza inoltre un dizionario (!HashMap) che associa identificativi e archi. Quando ci sono variazioni sugli archi, il nodo richiama sul !QspnManager i metodi: * arc_add (IQspnArc ''arc''). * arc_is_changed (IQspnArc ''changed_arc''). * arc_remove (IQspnArc ''removed_arc''). In questi metodi, in particolare in arc_add e arc_remove, il !QspnManager gestisce sia la lista degli archi che il dizionario che associa identificativi e archi. == 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 considera da subito completato il suo bootstrap. Il modulo lo segnala attraverso il segnale ''qspn_bootstrap_complete'' di !QspnManager. Se invece ci sono degli archi il modulo li memorizza in una sua lista ''my_arcs'' e si considera in fase di bootstrap. 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 hanno ancora completato il loro bootstrap. 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 considera completato il suo bootstrap, quindi emette il segnale ''qspn_bootstrap_complete'' 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 ha completato il suo bootstrap con il metodo ''is_bootstrap_complete'' 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. == 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'' . * 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 [[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete|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 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 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 === Il seguente algoritmo per processare un set di ETP viene eseguito 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 [[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete#GroupingRule|Grouping Rule]] su tale lista per renderla coerente con i g-nodi a cui ''n'' appartiene. Poi esegue la [[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete#AcyclicRule|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~-,,0,,-~'' di ''np'' con costo ''dead'' e la mette nel set ''Q'' . Per farlo, crea una nuova istanza di !EtpPath ''p~-,,0,,-~'' copiando i valori di ''np''’ e mettendo ''cost'' a ''dead''. Non c'è bisogno di valorizzare ''ignore_outside'' . Poi crea una istanza di !NodePath ''np~-,,0,,-~'' associando al percorso ''p~-,,0,,-~'' 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 [[Netsukuku/ita/docs/ModuloQSPN/EsplorazioneRete|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 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 e ordina le destinazioni per livello crescente. 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''. * 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 [[Netsukuku/ita/docs/ModuloQSPN/PercorsiDisgiunti|percorsi disgiunti]] per scartare quelli non sufficientemente disgiunti e tenere solo i ''max_paths'' più rapidi. Nel fare questo deve tener conto del requisito di mantenere per la destinazione ''d'' e per ogni proprio vicino ''v'', almeno 1 percorso, se esiste, indipendentemente dal valore di ''max_paths'' e dalle regole di disgiunzione, verso ''d'' che non contiene ''v'' tra i suoi passaggi. Ed anche del requisito di mantenere per la destinazione ''d'' almeno 1 percorso per ogni diverso fingerprint di ''d'' che gli viene segnalato. 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'' : * Per ogni ''p'' ∈ ''O~-,,d,,-~'' : * Se ''p'' ∉ ''M~-,,d,,-~'' : * ''p2'' = copia iniziale di ''p'' . Vedere sotto l'algoritmo di produzione di un percorso da inviare. * Metti ''p2'' in ''P''. * Prepara un segnale di ''path_added'' e aggiungilo al set ''S~-,,d,,-~''. * Per ogni ''p'' ∈ ''M~-,,d,,-~'' : * Se ''p'' ∉ ''O~-,,d,,-~'' : * ''p2'' = copia iniziale di ''p''. * ''p2''.cost = ''dead''. * Metti ''p2'' in ''P''. * Prepara un segnale di ''path_removed'' e aggiungilo al set ''S~-,,d,,-~''. * Altrimenti: * Se ''p'' ∈ ''V~-,,d,,-~'' : * ''p2'' = copia iniziale di ''p''. * Metti ''p2'' in ''P''. * Prepara un segnale di ''path_changed'' e aggiungilo al set ''S~-,,d,,-~''. * 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,,-~''. * 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 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 ) ''. 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 ''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 dal numero di nodi ''nn(g~-,,j,,-~)'' all'interno 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''. 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 ogni livello ''i'' da 1 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. * Assert esiste nella mia mappa la destinazione ''d'' che rappresenta ''p'' .hops[ ''j'' ]. * ''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. |
[[https://github.com/lukisi/documentation/blob/master/ita/ModuloQspn/DettagliTecnici.md|Redirect]] |
- Diff for "Netsukuku/ita/docs/ModuloQSPN/DettagliTecnici"