Network Collision

Quando due reti nate separatamente si incontrano si può verificare che diversi (g)nodi abbiano lo stesso (g)ID.

Per rilevare questa situazione e quindi prendere le misure necessarie a risolvere il problema si adotta la tecnica di assegnare ad una rete un identificativo.

Le problematiche da tenere in considerazione sono:

1. Assegnazione di un netid ad una rete alla sua nascita
2. Gestione della collisione di due reti nate separatamente
3. Gestione della separazione (split) di una rete in due reti disgiunte

Assegnazione di un netid alla nascita di una rete

Il nodo che al suo avvio si ritrova solo, genera un netid random - vedi il modulo hook e anche la fase di startup di un nodo.
Generare un numero random da 0 a 2³² - 1 è un modo abbastanza sicuro di ottenere un ID univoco. Quindi diamo per assunto che due reti nate separatamente avranno sempre un ID diverso.

Il nodo che al suo avvio ha dei vicini attivi (che hanno già superato la fase di startup) vede il netid di questi.
Non può subito appropiarsene, deve prima aver completato con successo il primo hook.
Per diventare membro a tutti gli effetti della rete deve aver ricevuto almeno il primo ETP da un vicino, tramite il quale viene a conoscenza immediatamente di tutti i nodi e g-nodi che ne fanno parte.

• Nota: Normalmente, quando un nodo rileva per la prima volta un link verso un vicino gli invia un ETP con tutte le route che conosce (vedi il modulo qspn), tranne quelle che hanno come gateway lo stesso nuovo vicino. Questo pone un problema quando i primi due nodi di una rete si incontrano, perché il secondo nodo sa di non essere solo e aspetta un ETP. Ma il primo non ha routes da comunicare e quindi non lo invia.
  Per risolvere questo blocco, un ETP in caso di "nuovo link" andrebbe inviato anche in caso di R vuota. TODO: verificare la correttezza e se ok implementare.

Quando un nodo che ancora non ha un netid riceve un ETP, prende il netid del nodo che gli ha inviato l'ETP. Prima di questo evento il nodo non aveva una piena conoscenza della rete in cui stava entrando. Questo significa che prima di questo evento al nodo non deve essere permesso rispondere a richieste che implicano tale conoscenza; ad esempio non può rispondere alla richiesta highest_free_nodes. TODO: verificare la correttezza e se ok implementare.

A regime, ogni singolo nodo che ha superato la fase di startup deve conoscere il netid della sua rete.

Collisione di due reti nate separatamente

Quando un nodo riceve ulteriori ETP (vedi il Modulo QSPN) richiama il metodo collision_check; in esso verifica che il netid del suo vicino sia lo stesso del suo.
Se sono diversi, i due nodi appartengono a due reti prima separate. Ognuno dei due nodi deve stabilire con certezza se appartiene alla rete che deve porre riparo. TODO: Al momento il criterio è "la rete più piccola o, in caso di parità, quella con netid minore". Questo è un criterio efficiente, ma ho il dubbio che non sia sicuro. Se usassimo il criterio "netid minore" staremmo sicuri, ma con grande probabilità di causare un rehook molto diffuso.

1) il nodo che appartiene alla rete che deve porre riparo, calcola il livello (sia level) in cui i due nodi hanno un gnodo padre con lo stesso ID. Ad esempio, se il mio IP è 1.2.3.4 e quello del mio vicino è 1.2.5.6 questi nodi sembrano appartenere allo stesso gnodo di livello 2. In realtà non è così perché appartengono a due reti diverse.
Esamina le destinazioni contenute nelle routes di livello level (TODO: dovrebbe essere level - 1) della porzione di mappa R dell'ETP ricevuto, per vedere se la rete del nodo vicino contiene già un gnodo di livello level (TODO: dovrebbe essere level - 1) con lo stesso (g)ID del mio (g)nodo di livello level (TODO: dovrebbe essere level - 1).
In questo modo ho scoperto se il gnodo di livello level - 1 a cui appartengo è invalido nella rete che ho incontrato. Notare che se il gnodo di livello level non è invalido nella rete che ho incontrato, questo garantisce anche che non stiamo formando un gnodo di livello level non compatto, perché siamo collegati con il vicino da cui abbiamo ricevuto l'ETP, il quale è di quel gnodo di livello level.
Se il gnodo di livello level - 1 a cui appartengo è invalido devo fare il rehook, altrimenti non è necessario che io lo faccia, posso semplicemente entrare nell'altra rete con il mio attuale IP. TODO: Serve in questo caso coordinarsi con il coordinator node? Direi di sì, per accertarsi che qualcun altro non sta facendo hook alla rete con lo stesso gnodo.

Se decido di entrare nella rete nuova senza fare il rehook, rimuovo dalla mia mappa di route locale (quella che era valida nella rete vecchia) le route che avevano destinazioni che sono presenti nell'ETP ricevuto dalla rete nuova. Questo perché i nodi che avevano quegli IP nella rete vecchia dovranno in seguito fare il rehook. E il nodo corrente invece, durante il proseguimento del metodo etp_exec, si vedrà valorizzate le routes verso i nodi della rete nuova che hanno quegli stessi IP.
Sempre in questo caso, la processazione dell'ETP ricevuto in etp_exec di sicuro provocherà qualche cambiamento nella mia mappa di route. Come conseguenza l'ETP sarà inoltrato agli altri vicini, fra cui il resto della vecchia rete. TODO: mi sembra necessario in questo momento cambiare il nostro netid con quello nuovo. Verificare.

Se invece è necessario fare il rehook, il metodo collision_check restituisce True. Di seguito il metodo etp_exec emette il segnale NET_COLLISION con argomento la lista dei suoi vicini (oggetti Neigh) che appartengono all'altra rete, quella nuova. Questo avvia per il nodo corrente la microfunc hook prendendo in esame solo tali nodi vicini.

2) il nodo che appartiene all'altra rete (che ha diritto a restare valida) rimuove dalla mappa di routes R ricevuta nell'ETP tutte le routes verso destinazioni che esso ha già nella sua mappa locale. Significa che (molto probabilmente) sono routes che vanno verso i nodi che nella vecchia rete avevano quegli IP, ma in seguito avranno altri IP. TODO: Non viene invece rimosso il TPL dell'ETP. Forse andrebbe rimosso per sicurezza.
In seguito la processazione dell'ETP può procedere normalmente.

Split di una rete in due reti disgiunte

Quando un gnodo diventa non compatto, cioè per la caduta di alcuni link alcuni suoi nodi non sono più in grado di raggiungere gli altri senza uscire all'esterno del gnodo, si dice che avviene lo split di un gnodo. E' già stato implementato un modo per riconoscere questa eventualità e gestirla nel metodo gnodes_split richiamato a seguito di un ETP ricevuto.
Se lo stesso tipo di frattura avviene al livello più alto ci si trova di fronte allo split di una intera rete in due parti disgiunte. Con lo stesso algoritmo è possibile identificare questa situazione.
Una volta identificata è necessario che, almeno la più piccola delle due reti che si sono disgiunte, generi un nuovo netid e lo faccia aggiornare a tutti i nodi della rete. Questo algoritmo non è stato ancora implementato.
Questa necessità deriva dal fatto che se le due reti si evolvono separatamente e poi si riuniscono, il fatto che hanno lo stesso netid impedisce loro di riconoscere la collisione e di gestire eventuali gnodi in conflitto.