L’albero di mapping

In XCone l’aggregazione delle risorse è garantita dall’utilizzo di un albero binario, che offre la possibilità di sfruttare diverse strategie a seconda della

CAPITOLO 4. AGGREGAZIONE DI DATI IN HASP 71 funzione di mapping adottata, basato sullo spazio degli identificatori della DHT.

Sono definiti nodi logici quei nodi dell’albero XCone che risultano essere mantenuti in modo distribuito tra i nodi fisici o peer della rete. I nodi logici foglia sono associati in modo univoco ai nodi fisici attraverso un processo di integrazione con la DHT che sarà illustrato in seguito, mentre, per quanto riguarda i nodi logici non foglia, l’associazione con i nodi fisici è effettuata per mezzo di una funzione di mapping. Il numero di nodi logici non foglia da associare a ciascun peer è determinato per mezzo di tale funzione di mapping e, nel caso pessimo, il numero di nodi logici assegnati ad un peer è inferiore ad un valore h pari al cammino dalla foglia alla radice dell’albero. La funzione di mapping ha un ruolo fondamentale nella costruzione dell’albero di XCone, in quanto a partire da due nodi logici a livello l 1 gestiti da due peer distinti, decide a quale dei due nodi assegnare la gestione del nodo logico di livello l. In linea teorica, ad un qualsiasi peer può essere associato un qualsiasi no- do logico, ma per ottenere buone prestazioni in fase di entrata di un nodo nella rete (join) e di risoluzione delle query è necessario imporre alcuni vin- coli. Ciascun peer è identificato da un ID univoco in formato binario e la sua posizione all’interno dell’albero è determinata in base al valore di tale identificatore. Ogni peer può gestire solo nodi logici che abbiano un ID tale da avere un prefisso comune ad esso. Questa regola di assegnazione dei nodi logici ai peer permette di implementare in modo efficiente la fase di join, in quanto il peer, che si unisce nell’albero XCone per la ricerca dei nodi logici da gestire, deve risalire l’albero a partire dalla foglia assegnata, evitando di visitare diversi sotto-alberi. Da ciò si deduce come l’assegnamento dei nodi foglia ai peer sia univoco, mentre, per quanto riguarda i nodi logici interni, i quali condividono il proprio prefisso con più nodi foglia, essi possono essere assegnati ad uno qualunque dei peer che corrispondono a tali foglie. Un ul- teriore vincolo è dato dal fatto che il generico nodo P gestisca un insieme di nodi logici, che corrispondono ad un suffisso del proprio identificatore (ID). Il nodo P gestisce dunque una sequenza continua di nodi logici a partire dalla foglia da lui gestita, fino ad un certo livello l dell’albero in modo da ridurre

CAPITOLO 4. AGGREGAZIONE DI DATI IN HASP 72 al minimo il numero di hops tra i diversi peer in fase di ricerca durante la risalita dell’albero XCone.

In XCone è definita un’altra funzione: la funzione di digest. Tale funzione associa a ciascun nodo una struttura in grado di sintetizzare le chiavi con- tenute nel sotto-albero radicato in esso. Esistono diversi tipi di funzioni di mapping in grado ciascuna di valutare aspetti diversi, quali il carico dei nodi logici gestiti da ogni nodo o la tipologia di banda. Ad esempio è possibile adottare una tecnica per migliorare il bilanciamento del carico in modo da regolare il numero di entrate significative presenti nella routing table di cia- scun nodo. Nel momento in cui un nuovo nodo P entra in XCone, controlla se nel cammino che lega la foglia ad esso associata e la radice esistono nodi logici mappati a peer carichi. In tal caso il nodo P prende in gestione alcune entrate della tabella di routing di tali nodi. Questa operazione è naturalmen- te seguita da un aggiornamento del mapping di alcuni logici ai peer presenti sul cammino di P dalla foglia alla radice.

Nel caso di XCone la funzione di mapping adottata coincide con quella di Cone basata sulla scelta del peer avente in gestione la chiave di valore massi- mo ma, come vedremo in seguito, XCone definisce funzioni di digest diverse rispetto a Cone per supportare più efficacemente le range query.

L’assegnamento tra i peer della rete e i nodi foglia XCone viene realizzato a seguito dell’integrazione con la rete DHT sottostante. Se consideriamo una rete DHT con spazio degli identificatori (ID) di m bit, i nodi logici foglia sono assegnati ai peer attraverso un trie.

A ciascun peer in fase di join viene associato un identificatore di m bit in maniera casuale e ad ogni peer può essere associato un unico nodo foglia all’interno del trie in quanto l’albero XCone definisce un trie basato sui prefissi degli identificatori.

La Figura4.1illustra, attraverso un esempio, il mapping tra nodi logici foglia dell’albero XCone ed i peer di una rete DHT Chord con identificativi di 4 bits.

CAPITOLO 4. AGGREGAZIONE DI DATI IN HASP 73

Figura 4.1: Overlay XCone-DHT

L’associazione nodo/foglia rimane fissata per tutta la permanenza del peer in rete. L’identificatore di ogni nodo è generato tramite una funzione hash impiegata dalla DHT per assegnare i peer alla rete e ciascun nodo gestisce in maniera indipendente la propria chiave, la quale può variare e non comporta uno spostamento del nodo all’interno dell’albero. Il dominio delle chiavi e quello degli identificatori risulta quindi essere distinto.