==== 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 ''x~-,,0,,-~·x~-,,1,,-~·...·x~-,,L-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 ''*·x~-,,l,,-~·...·x~-,,L-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 ''g~-,,l,,-~(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, ''g~-,,L,,-~(x)'' è il grafo di tutta la rete a cui appartiene ''x'' costituito dai g-nodi (contratti) di livello ''L-1''.

All'altro estremo, ''g~-,,1,,-~(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 ''size~-,,m,,-~(g)'', dove ''m'' < ''l'', il numero di g-nodi di livello ''m'' dentro ''g''. Questa definizione va precisata, tenendo in considerazione il fatto che un g-nodo può assumere un indirizzo ''virtuale'' come descritto nella trattazione del modulo QSPN. Quindi un g-nodo di livello ''m'' dentro ''g'' può avere uno o più identificativi ''virtuali'' ai livelli da ''m'' a ''l-1'' inclusi. Precisiamo dunque che includiamo nel computo di ''size~-,,m,,-~(g)'' solo i g-nodi che non hanno identificativi ''virtuali'' ai livelli da ''m'' a ''l-1'' inclusi.

Ricordando che ''g'' è un g-nodo di livello ''l'', se abbiamo che ''size~-,,l-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 ''size~-,,0,,-~(g)'' = ''S~-^l^-~'' 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 uno alla volta tutti i suoi vicini, ''x'' può entrare nella rete e assegnarsi un indirizzo valido se uno dei g-nodi a cui il suo vicino appartiene è ''non saturo''. Se un tale g-nodo non esiste per nessuno dei suoi vicini, allora ''x'' non può entrare nella rete. Analiziamo il caso del singolo vicino ''y''.

Supponiamo che ''size~-,,0,,-~(g~-,,1,,-~(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 ''size~-,,i-1,,-~(g~-,,i,,-~(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 ''y'' un singolo nodo all'interno di un g-nodo ''h'' di livello ''l'' + 1, con ''l'' da 0 a ''L'' - 2. Sia ''size~-,,l,,-~(g~-,,l+1,,-~(y))'' = ''size~-,,l,,-~(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''.

Definiamo ''P'' una migration path a livello ''l'' che parte dal g-nodo ''h'' (di livello ''l'' + 1) se ''P'' è una lista di g-nodi che soddisfa questi requisiti:
 * ''P'' = (''p~-,,1,,-~'', ''p~-,,2,,-~'', ... ''p~-,,m,,-~'').
 * ''p~-,,1,,-~'' = ''h''.
 * Per ogni ''i'' da 1 a ''m-1'':
  * ''lvl(p~-,,i,,-~)'' = ''lvl(h)'' = ''l+1''.
  * ''p~-,,i+1,,-~'' ∈ ''𝛤~-,,l+1,,-~(p~-,,i,,-~)'', cioè ''p~-,,i+1,,-~'' è direttamente collegato a ''p~-,,i,,-~'' nel grafo ''[G]~-,,l+1,,-~''.
  * almeno uno dei g-nodi di livello ''l'' che sono border-nodi di ''p~-,,i,,-~'' verso ''p~-,,i+1,,-~'' ha identificativo ''reale'' al livello ''l''.
  * ''size~-,,l,,-~(p~-,,i,,-~)'' = ''S'', cioè ''p~-,,i,,-~'' è saturo.
 * ''lvl(p~-,,m,,-~)'' = ''lvl(h)'' = ''l+1''.
 * ''size~-,,l,,-~(p~-,,m,,-~)'' < ''S'', cioè ''p~-,,m,,-~'' non è saturo.

==== 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'' = (''p~-,,1,,-~'', ''p~-,,2,,-~'', ... ''p~-,,m,,-~''), dove ''lvl(p~-,,i,,-~)'' = ''l+1'', procede così:
 * Per ogni ''i'' da 1 a ''m-1'':
  * Sia ''b~-,,i,,-~'' un g-nodo (quale?) di livello ''l'' appartenente a ''p~-,,i,,-~'' e border-nodo verso ''p~-,,i+1,,-~''
  * Il g-nodo ''b~-,,i,,-~'' rilascia il suo indirizzo ''reale globale'' in ''p~-,,i,,-~'' e si assegna un indirizzo ''virtuale interno'' in ''p~-,,i,,-~'' e un indirizzo ''virtuale globale'' in ''p~-,,i+1,,-~''.
  . Il precedente indirizzo ''reale'' di ''b~-,,i,,-~'' è stato riservato nel Coordinator del g-nodo ''p~-,,i,,-~''. Esso dovrà venire assegnato al g-nodo ''b~-,,i-1,,-~'' del passo precedente (indicando con ''b~-,,0,,-~'' il g-nodo che ha fatto la richiesta iniziale a ''y'').
  . I due indirizzi ''virtuali'' in ''p~-,,i,,-~'' e in ''p~-,,i+1,,-~'' sono stati precedentemente scelti e riservati dal relativo Coordinator.
 . '''Da completare'''

=== 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''.

 * Per ogni ''l'' che va decrementando da ''L'' a ''ε'' + 1:
  * Consideriamo tutti i g-nodi di livello ''l'' appartenenti a ''G'', cioè ''[G]~-,,l,,-~''. Di ognuno di questi l'algoritmo (in dettaglio: un nodo di ''set_g_neighbors'') deve poter valutare se è ''saturo''.
  . Il ''set_l_gnodes'' può essere costituito da tutti i g-nodi di livello ''l'' appartenenti a ''G'', cioè ''[G]~-,,l,,-~''. Oppure dai soli g-nodi di livello ''l'' diretti vicini di ''x''