La rete con i suoi vertici

Indichiamo con G = (V, E) una rete, cioè un grafo con i suoi vertici e archi.

Consideriamo una topologia gerarchica con L livelli dove ogni livello ha gsize = S

Sappiamo che un nodo x ha indirizzo x0·x1·...·xL-1.

I nodi x e y appartengono allo stesso g-nodo di livello l se hanno un l-suffisso uguale, cioè i valori nelle posizioni dalla l fino alla L-1.

Lo denotiamo scrivendo x ~l y, come una relazione di equivalenza.

In particolare, x ~0 y significa che x = y, cioè hanno lo stesso indirizzo.

Mentre x ~L y significa solo che appartengono alla stessa rete, possono avere diversa anche l'ultima posizone.

Con il simbolo [x]l indichiamo la classe dei nodi accomunati al nodo x tramite tale equivalenza. Cioè tutti i nodi che hanno un indirizzo nella forma *·xl·...·xL-1.

In particolare, [x]0 = {x}.

Mentre, [x]L = V, cioè tutti i vertici del grafo G, tutta la rete.

G-nodi

Quando parliamo di un g-nodo, ad esempio il g-nodo di livello l a cui appartiene il nodo x, facciamo riferimento ad un particolare grafo. Lo indichiamo con gl(x).

Esso si ottiene considerando solo i nodi della classe [x]l e contraendo tutti i nodi che hanno lo stesso (l-1)-suffisso, considerandoli come singoli vertici.

Ad esempio, gL(x) è il grafo di tutta la rete a cui appartiene x costituito dai g-nodi (contratti) di livello L-1.

All'altro estremo, g1(x) è il grafo dei singoli nodi (livello 0) che appartengono allo stesso g-nodo di livello 1 di x.

Continuiamo a chiamare (impropriamente) nodi questi vertici e chiamiamo singoli nodi i vertici del grafo originale G.

Se prendiamo tutti i g-nodi di livello l del grafo originale G e li consideriamo come singoli vertici, otteniamo un altro grafo che rappresenta tutta la rete come composta da vertici di livello l. Questo grafo lo indichiamo così: [G]l.

Sia g un g-nodo di livello l. Indichiamo con 𝛤l(g) l'insieme dei vicini (vertici direttamente collegati) di g nel grafo [G]l.

Indichiamo con sizem(g), dove m < l, il numero di g-nodi di livello m dentro g.

Ricordando che g è un g-nodo di livello l, se abbiamo che sizel-1(g) = S diciamo che il g-nodo g è saturo: cioè non esistono dentro g g-nodi di livello l-1 non allocati. Va notato che ogni singolo nodo x appartenente a g è in grado autonomamente (tramite le sole conoscenze della sua mappa) di calcolare tale valore.

Se invece abbiamo size0(g) = Sl diciamo che il g-nodo g è pieno: cioè non ci sono più dentro g indirizzi liberi. Va notato che un singolo nodo x appartenente a g non è in grado di calcolare tale valore, se non nel caso in cui l = 1.

Ingressi problematici

Sia x un nodo che cerca di fare ingresso in una rete. Considerando ad uno ad uno tutti i suoi vicini, x può entrare nella rete e assegnarsi un indirizzo valido solo entrando in uno dei g-nodi a cui il suo vicino appartiene. Analiziamo il caso del singolo vicino y.

Supponiamo che size0(g1(y)) = S. Cioè il g-nodo di livello 1 è pieno (equivalente di saturo a livello 1).

Continuando, per ogni i da 2 a L, supponiamo che sizei-1(gi(y)) = S. Cioè tutti i g-nodi a cui appartiene y sono saturi.

Allora il nodo x non può entrare, cioè non è possibile assegnargli un indirizzo, in nessuno dei g-nodi di y. A meno di trovare una migration path a livello 0.

La stessa cosa si può dire di un g-nodo x di livello ε che vuole entrare in blocco. In questo caso vanno analizzati tutti i vicini collegati ad ogni singolo border-nodo di x, ma alla fine la domanda da fare ad ogni singolo vicino y è la stessa. In questo caso si usa i da ε + 1 a L. Se tutti i g-nodi a cui appartiene y sono saturi, per entrare in uno di essi bisogna trovare una migration path a livello ε.

La stessa cosa per un nodo x che vuole fare da gateway verso una sottorete a gestione autonoma e che vuole riservarsi un g-nodo di livello ε.

Migration Path

Sia un singolo nodo y all'interno di un g-nodo h di livello l + 1, con l da 0 a L - 1. Sia sizel(gl+1(y)) = sizel(h) = S. Cioè h è saturo.

Supponiamo che il nodo y voglia trovare una migration path a livello l per liberare un posto di livello l all'interno di h.

Una migration path P che parte dal g-nodo h di livello l è una lista di g-nodi di livello l che soddisfa questi requisiti:

Implementazione della ricerca

La ricerca della migration path si fa usando un algoritmo di Breadth-First Search. L'intento infatti è quello di trovare la migration path più breve, oppure la non esistenza di una migration path.

Il singolo nodo interessato alla ricerca di una migration path, y contatta ad uno ad uno il primo singolo nodo x che incontra in ognuno dei g-nodi di livello l+1 direttamente collegati al suo. Nota implementativa: Questa comunicazione avviene tramite l'inoltro di un pacchetto al miglior gateway verso la destinazione, con successivo collegamento reliable interno al g-nodo comune, come per il modulo PeerServices.

Il nodo x deve saper valutare se il suo g-nodo di livello l è saturo. Questo lo può fare guardando la sua mappa prodotta dal modulo QSPN.

Se il suo g-nodo è saturo, il nodo x deve indicare quali sono i g-nodi di livello l direttamente collegati al suo. Dovrà restituire un elenco in cui tali g-nodi sono indicati con tutte le loro posizioni da l a L-1, poiché dovrà includere anche quelli che non appartengono al suo stesso g-nodo di livello l+1.

Il nodo y, ricevute queste informazioni, esegue localmente l'algoritmo di Breadth-First Search.

Alla fine il nodo y sa quale sia la lunghezza della migration path più breve. Può applicare la migration path, oppure soltanto comunicare la sua lunghezza a chi ne aveva fatta richiesta. Il richiedente potrà con questo dato implementare una qualsivoglia strategia di ingresso.

Applicazione della migration path

L'applicazione di una migration path P di livello l, con P = (p1, p2, ... pm), dove lvl(pi) = l+1, procede così:

Strategie di ingresso

Sia un nodo x che, essendo collegato ad alcuni vicini appartenenti ad una rete G, vuole assegnarsi un posto in [G]ε, con 0 ≤ ε < L. Può essere ad esempio che x sia un nodo che non appartiene a G, per esempio perché è stato appena acceso, o perché si sono creati collegamenti a G che prima non c'erano. Poteva essere x in precedenza appartenente ad una diversa rete G’ oppure un nodo isolato. Ma può anche essere che x sia già appartenente a G ma vuole migrare.

Abbiamo detto che vuole un posto in [G]ε, con 0 ≤ ε < L. Non diciamo direttamente ε = 0 perché, come detto sopra, x può essere un border-nodo di un g-nodo g di livello ε che vuole fare ingresso in blocco. In questo caso le operazioni che vedremo sotto vanno fatte in modo concertato da tutti i border-nodi di g che hanno collegamenti con vicini appartenenti alla medesima rete G.

Oppure può essere ε > 0 perché il nodo x vuole fare da gateway verso una sottorete a gestione autonoma.

Il nodo x può adottare due strategie di ingresso: dispersiva o aggregativa.

Strategia Dispersiva

Durante le operazioni che esaminiamo, il nodo x dialoga esclusivamente con alcuni diretti vicini appartenenti ad un set che chiameremo set_g_neighbors. Di norma tale set comprende tutti i vicini di x che appartengono alle rete G; ma lasciamo aperta la possibilità che il nodo x escluda di proposito alcuni suoi diretti vicini. Ad esempio, se x è border-nodo di un g-nodo g che già appartiene a G ma vuole migrare in blocco, allora escluderà i vicini che appartengono a g.

Le operazioni di comunicazione con il resto della rete G sono portate avanti dai nodi appartenenti a set_g_neighbors.