11170
Comment:
|
← Revision 3 as of 2016-01-22 16:11:43 ⇥
11322
|
Deletions are marked like this. | Additions are marked like this. |
Line 67: | Line 67: |
* 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''. |
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. 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 sizem(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 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 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 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 y un singolo nodo all'interno di un g-nodo h di livello l + 1, con l da 0 a L - 2. 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.
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 = (p1, p2, ... pm).
p1 = h.
Per ogni i da 1 a m-1:
lvl(pi) = lvl(h) = l+1.
pi+1 ∈ 𝛤l+1(pi), cioè pi+1 è direttamente collegato a pi nel grafo [G]l+1.
almeno uno dei g-nodi di livello l che sono border-nodi di pi verso pi+1 ha identificativo reale al livello l.
sizel(pi) = S, cioè pi è saturo.
lvl(pm) = lvl(h) = l+1.
sizel(pm) < S, cioè pm 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 = (p1, p2, ... pm), dove lvl(pi) = l+1, procede così:
Per ogni i da 1 a m-1:
Sia bi un g-nodo (quale?) di livello l appartenente a pi e border-nodo verso pi+1
Il g-nodo bi rilascia il suo indirizzo reale globale in pi e si assegna un indirizzo virtuale interno in pi e un indirizzo virtuale globale in pi+1.
Il precedente indirizzo reale di bi è stato riservato nel Coordinator del g-nodo pi. Esso dovrà venire assegnato al g-nodo bi-1 del passo precedente (indicando con b0 il g-nodo che ha fatto la richiesta iniziale a y).
I due indirizzi virtuali in pi e in pi+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