LEADER: un protocollo peer-to-peer per la costruzione dinamica di comunità basato su Gossip

Testo completo

(1)UNIVERSITA’ DEGLI STUDI DI PISA ` di Scienze M.F.N. Facolta Corso di Laurea Specialistica in Informatica. Tesi di Laurea LEADER: un protocollo peer-to-peer per la costruzione dinamica di comunità basato su Gossip. Candidato: Luca Alessi Relatori: prof. Laura Ricci dott. Matteo Mordacchini. Sessione di Dicembre 2010 Anno Accademico 2009/2010. Controrelatore: prof. Dino Pedreschi.

(2) 2.

(3) Indice 1 Introduzione. 5. 2 Stato dell’Arte. 11. 2.1. Gossip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11. 2.2. Spazio e Reti Semantiche . . . . . . . . . . . . . . . . . . . . . . . . . 12. 2.3. 2.4. 2.2.1. GosSkip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12. 2.2.2. Riduzione del Traffico nei Sistemi P2P: un Approccio Semantico 13. 2.2.3. Semantic Overlay Networks (SONs) . . . . . . . . . . . . . . . 14. 2.2.4. Peer Data Management Systems . . . . . . . . . . . . . . . . . 16. 2.2.5. Proactive gossip-based management . . . . . . . . . . . . . . . 19. 2.2.6. Gossple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22. 2.2.7. Full-Text Federated Search . . . . . . . . . . . . . . . . . . . . 24. Clustering ed Elezione dei Leader . . . . . . . . . . . . . . . . . . . . 27 2.3.1. K-Means Distribuito . . . . . . . . . . . . . . . . . . . . . . . 27. 2.3.2. Randomized Leader Election . . . . . . . . . . . . . . . . . . . 29. 2.3.3. Un Algoritmo di Elezione per Reti Ad Hoc . . . . . . . . . . . 31. 2.3.4. CDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32. Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34. 3 Protocollo proposto. 37. 3.1. Architettura generale del sistema . . . . . . . . . . . . . . . . . . . . 37. 3.2. L’ambiente di partenza . . . . . . . . . . . . . . . . . . . . . . . . . . 39. 3.3. Il Protocollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44. 3.4. 3.3.1. Una possibile Criticità . . . . . . . . . . . . . . . . . . . . . . 50. 3.3.2. Evoluzione del protocollo . . . . . . . . . . . . . . . . . . . . . 50. Protocollo in azione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53. 4 Implementazione. 59 3.

(4) 4. INDICE. 5 Valutazione 5.1 5.2. 67. Data Set ed Indici di Valutazione . . . . . . . . . . . . . . . . . . . . 67 Risultati Sperimentali . . . . . . . . . . . . . . . . . . . . . . . . . . 71. 6 Conclusioni. 91. Bibliografia. 93.

(5) Capitolo 1 Introduzione Analisi di scenari in cui entità differenti si mettono in relazione hanno mostrato come sia possibile evidenziare delle strutture, o comunità, che raggruppino omogeneamente tali entità. Nell’ambito di sistemi distribuiti in cui le entità siano identificabili da nodi caratterizzati da diversi profili, riuscire ad individuare queste comunità può essere di fondamentale importanza per assicurare una comunicazione rapida, efficiente ed efficace. Lo scopo del lavoro svolto in questa tesi è relativo alla costruzione e definizione di tali comunità di utenti caratterizzati da interessi simili nel contesto di sistemi altamente distribuiti e dinamici come quelli tipici delle reti peer-to-peer. Con il termine peer-to-peer [1] ci riferiamo ad una rete composta da entità di calcolo (computer, sensori, ecc.) dove, a differenza del modello client-server, ogni nodo della rete offre e richiede servizi agli altri nodi suoi pari. Ogni nodo infatti funge sia da cliente che da servente verso altri nodi della rete. Tali sistemi permettono di utilizzare risorse distribuite in maniera autonoma e totalmente decentralizzata. Il modello di computazione P2P sta ricevendo particolare attenzione sia da parte del mondo accademico che di quello industriale. Il campo applicativo della maggior parte dei sistemi sviluppati è quello del file-sharing. Una prima catalogazione dei sistemi P2P viene fatta in base alla topologia dell’overlay network che connette i peer tra di loro. Possiamo distinguere tra sistemi non strutturati e strutturati [2]. Tra i sistemi non strutturati annoveriamo Napster [3], uno dei primi protocolli peer-to-peer, senz’altro il sistema che ha dato la spinta propulsiva all’espansione del file-sharing attraverso l’utilizzo di sistemi P2P. Napster fa parte della sotto-categoria dei sistemi P2P centralizzati dove, come indicato dal nome, è presente una struttura centralizzata che svolge il compito di indicizzazione delle risorse. Tale struttura, pur permettendo ottime capacità per la ricerca delle informazioni, costituisce un collo di 5.

(6) 6. CAPITOLO 1. INTRODUZIONE. bottiglia per le potenzialità del sistema e allo stesso tempo un critico punto debole. Nel caso in cui venga meno tale nodo, tutto il sistema si blocca. Tra i sistemi non strutturati troviamo i sistemi P2P cos`ı detti puri. Primo fra tutti il protocollo Gnutella 0.4 [18]. In questo caso non esiste alcuna entità centralizzata. Ciò permette di evitare un punto debole che comprometta le funzionalità del sistema. La completa mancanza di una strutturazione dell’overlay network rende però assai difficile la ricerca delle informazioni presenti nel sistema. Per superare a tale problema sono stati introdotti i sistemi P2P ibridi. In questi sistemi avviene una suddivisione dei nodi della rete in due categorie di peer, superpeer e leafnode, che permette la definizione dinamica di un livello gerarchico della rete. I superpeer, scelti in modo dinamico fra i nodi con maggiori capacità di calcolo e di ampiezza di banda della rete, mantengono un numero elevato di connessioni verso altri peer, sia superpeer che leafnode. I leafnodes, invece, mantengono aperte solo un numero limitato di connessioni, solo verso superpeers. Il routing delle queries avviene solo tra superpeers, questo permette di eliminare il carico della gestione del routing dai leafnodes. I superpeer implementano funzionalità di proxy per i rispettivi leafnode. Tra i protocolli caratterizzati da un’overlay network ibrida possiamo annoverare Gnutella 0.6 e FastTrack [4]. Quest’ultimo, pur essendo un protocollo proprietario, è quello che ha ottenuto maggior successo nell’ambiente del filesharing. Alcuni dei punti deboli dei sistemi P2P non strutturati sono la possibile presenza di un overhead di comunicazione e l’eventualità di ottenere dei falsi negativi durante la risoluzione delle query. Al fine di superare tali limiti, non presenti nei sistemi client-server, sono stati introdotti i P2P strutturati caratterizzati da un’overlay network strutturata. Un tipico esempio di tale approccio è rappresentato dalle DHT (Distributed Hash Table [5]). Le DHT sono una classe di sistemi distribuiti decentralizzati che effettuano il mapping dei nodi e dei dati nello stesso spazio di indirizzamento. Sia i peer che i dati vengono identificati tramite un identificatore unico (ID) che li individua univocamente all’interno del sistema. I dati, infatti, sono mappati nello stesso spazio degli indirizzi dei nodi mediante l’utilizzo di una funzione hash. Ad ogni nodo viene assegnata una porzione contigua dello spazio degli indirizzi. In questo modo, ciascun nodo rappresenta l’analogo di un array slot in una hash table. Il routing delle query è guidato dalla chiave del dato cercato, ciò permette di raggiungere rapidamente il peer che lo detiene in suo possesso. Le DHT offrono un valido supporto alla ricerca solo se si è in possesso della chiave del dato cercato e non permettono l’esecuzione di query pi` u complesse, sebbene questo tipo di funzionalità possa essere inserita in uno strato superiore della DHT. Le prime DHT presentate in letteratura sono CAN [10], Chord [12], Pastry [11].

(7) 7 e Tapestry [13]. Da allora, questo settore di ricerca è abbastanza attivo. Al di là degli studi accademici, la tecnologia DHT è stata adottata come un componente di BitTorrent [14] e eMule [15]. L’utilizzo di una funzione hash per calcolare l’ID di un documento da registrare all’interno di una DHT permette un posizionamento veloce e sicuro. D’altro canto la funzioni hash applicata a due documenti che trattano lo stesso argomento, (che siano due file musicali, film, immagini ecc.) con molta probabilità fornisce loro ID molto differenti e in questo caso i documenti sono memorizzanti in posizioni lontane all’interno della rete. Scopo di queste tesi è la definizione di una strategia che consenta di definire un overlay P2P in grado di collegare oggetti simili. Secondo questo approccio ogni oggetto viene caratterizzato da un insieme di features(contenuto, descizione semantica, keywords...). Quindi, pi` u due oggetti si assomigliano, maggiore sarà la vicinanza tra di loro nell’overlay network. Un approccio per affrontare questo problema è quello di usare la descrizione semantica degli oggetti. Le overlay network semantiche creano comunità di nodi che condividono interessi in comune. Un aspetto importante, quindi, è il concetto di similarità. Nell’ambiente peer-to-peer, gli interessi personali concorrono a formare la struttura della rete stessa, dove la vicinanza fra due entità è il riflesso di interessi in comune. In altre parole, pi` u due peer sono simili, cioè maggiore è la similarità tra di loro, pi` u saranno vicini nella struttura della rete peer-to-peer. In [30] è proposto un sistema che permette la creazione di un’overlay semantica attravero l’utilizzo di un doppio layer formato dall’utilizzo combinato dei protocolli Cyclon [24] e Vicinity [30]. Cyclon ricerca in maniera epidemica i nodi della rete, Vicinity, invece, mantiene informazioni aggiornate suoi nodi pi` u simili presenti nel sistema e implementa una propria tabella di routing. Tale approccio permette di ottenere un’overlay in cui ogni nodo si collega ai nodi della rete a lui pi` u simili. La rete non presenta alcuna gerarchia e mantiene le buone capacità di modellazione tipiche delle rete p2p pure. Allo stesso modo non vi è alcun punto debole o collo di bottiglia nella struttura. A differenza però delle reti p2p pure non esiste il problema del flooding dei messaggi per il routing delle query, in quanto l’organizzazione semantica dei dati permette un cammino mirato. Un approccio simile è implementato da Gossple che utilizza un protocollo di campionamento casuale di peer RPS [44] per implementare l’aspetto epidemico e un protocollo di clustering multi-interessi (GNet protocol) per la struttura semantica. Considerando ora un overlay in cui i link rappresentano la similarità tra i peer un aspetto importante è definire delle strategie per individuare sull’overlay cluster di.

(8) 8. CAPITOLO 1. INTRODUZIONE. peer caratterizzati da interessi comuni. In molti studi tra cui [6] viene sottolineato quanto la suddivisione dei nodi di una rete in cluster comporti indubbi benefici in termini di leggerezza, qualità nella struttura ed quindi buona efficienza nel routing. Nei sistemi peer to peer conosciuti, anche quando non è presente una esplicita suddivisione dei nodi in comunità, affiora dalla rete una possibile ripartizione logica degli utenti in gruppi aventi interessi in comune. Consideriamo per esempio un grafo i cui nodi sono gli utenti di una rete di filesharing. Aggiungiamo un collegamento fra due utenti nel caso in cui uno dei due ha l’altro nella propria lista di preferenze. In questo modo otteniamo una semplice ma efficace rete di preferenze, una PreferenceNetwork[7]. Un aspetto importante è quindi definire strategie di clusterizzazione per reti P2P in cui link rappresentano la similarità degli oggetti. Ciò ci spinge a cercare un sistema distribuito capace di creare in modo automatico un’overlay network costruita in base alla similarità dei peer, e in grado di far emergere le comunità presenti in una rete peer-to-peer e di rimodellarle in maniera dinamica con l’evolversi dello stato della rete. Diversi approcci per il clustering sono stati proposti in letteratura. Uno fra questi è SONs, Semantic Overlay Network [27], un protocollo distribuito che attraverso una struttura gerarchica di alberi sintattici permette la modellazione dei nodi in comunità e sotto-comunità. SONs risulta un modo elegante di modellare i nodi ma pecca in staticità. Seppur l’appartenenza dei nodi in una data comunità sia dinamica, cioè può cambiare con l’evolversi delle informazioni in possesso di un nodo, la struttura gerarchica rimane prefissata. Al fine di superare tale limitazione, mantenendo le buone qualità di modellazione di SONs, viene presentato PDMS [28], un sistema semantico per la gestione dei dati dei peer. Tale approccio permette una modellazione dell’overlay network che ricalca quella di SONs ma aggiunge flessibilità ai cambiamenti della rete. I peer sono caratterizzati da concetti che li descrivono. Al fine di mappare i peer in SON, viene definito l’elemento centroide, cioè quel concetto che minimizza la distanza con tutti gli altri concetti che caratterizzano i peer appartenenti ad un dato SON ed identifica il SON stesso. La gestione della dinamicità della rete comporta una continua rimodellazione dei centroidi che si ripercuote su tutti i nodi della rete. Ciò appesantisce la gestione dell’overlay network ed introduce overhead. Infine, sono stati introdotti alcuni algoritmi di clustering che permettono di raggruppare in cluster nodi contenente contenuti simili, per esempio LSP2P K-means e USP2P K-means [36]. Tali approcci hanno lo scopo di portare il calcolo dell’algoritmo K-Means in un ambiente dove sia il calcolo che i dati sono distribuiti.

(9) 9 fra un insieme di nodi. Essi necessitano però di un meccanismo generale per la sincronizzazione dei nodi nel sistema non permettendo loro una completa autonomia. Dai lavori citati e discussi nello stato dell’arte possiamo trarre gli aspetti fondamentali che un buon protocollo per la costruzione delle comunità su un ambiente peer-to-peer deve possedere: la semplicità nell’implementare il concetto di similarità presente in [26] senza l’utilizzo di strutture esterne come WordNet [29], la connettività di tutta la rete e la adattabilità ai cambiamenti, chiarezza nella modellazione delle comunità come proposta in SONs [27] con una modellazione pi` u leggera di quella già proposta in PDMSs[28], una buona suddivisione dei nodi in comunità come quella presentata in [37] La struttura del protocollo ottimale che implementi i suddetti aspetti deve possedere alcune caratteristiche importanti: • avere una esecuzione completamente asincrona e distribuita fra i nodi della rete • essere leggero e necessitare di poca banda di rete; • essere robusto nonostante l’alta dinamicità dei nodi e quindi avere una buona procedura di ricablaggio che mantenga inalterate le caratteristiche di ordinamento della rete, considerata in alcuni studi [33] come il fattore determinante per avere buone prestazioni nelle query; • riuscire a rimodellarsi mano a mano che gli interessi dei vari utenti si evolvono • lasciare molta autonomia ad ogni peer; • permettere la totale raggiungibilità fra i nodi della rete (ogni peer può contattare qualsiasi altro peer presente nella rete) In questa testi viene proposto LEADER, un protocollo asincrono per la creazione di comunità dinamiche su reti peer to peer. Il protocollo viene eseguito su una rete epidemica. La struttura della rete permette di collegare peer con contenuti simili, dove la similarità è misurata in base ai profili degli utenti. La natura epidemica della rete permette la diffusione delle informazione in tutto il sistema in completa autonomia da una struttura centrale. La tecnica gossip [16] utilizzata per la generazione e il mantenimento dell’overlay network permette un aggiornamento costante delle informazioni e di conseguenza facilita la modellazione dinamica della stessa. Al fine di avere una rete con le caratteristiche suddette, sono stati utilizzati due protocolli già presenti in letteratura. Per ottenere la natura epidemica della rete è.

(10) 10. CAPITOLO 1. INTRODUZIONE. stato utilizzato Cyclon[24], un protocollo che permette la diffusione capillare delle informazioni. In concerto con il protocollo precedente è stato utilizzato Vicinity [30] con il fine di sfruttare il concetto di similarità tra nodi. L’uso combinato dei due protocolli rappresenta una base solida già ben studiata. La natura gossip sia dei due protocolli sopra citati che del protocollo LEADER possiede numerose qualità che permettono buona agilità e semplicità nella stesura dell’algoritmo alla base di LEADER. Il sistema proposto, formato dai tre livelli, Cyclon-Vicinity pi` u LEADER, come confermato dai test eseguiti, possiede tutte le caratteristiche del protocollo ideale. L’utilizzo di un protocollo con le suddette caratteristiche permette di unire le qualità e gli aspetti positivi delle reti semantiche con quelli ottenuti tramite una clusterizzazione dei dati. La struttura dell’overlay network cos`ı creata ha in sé qualità di leggerezza e di buona modellazione che permettono un’ottimizzazione nella gestione della ricerca di informazioni. La conoscenza dei soli leader permette di ottenere una visione globale della struttura dei dati e delle informazioni presenti nell’intero sistema. Infatti, venire a conoscenza del profilo di un leader, significa scoprire un gruppo di peer molto simili a quel profilo. Ciò permette miglioramenti nell’instradamento dei dati e delle informazioni. La struttura della tesi è la seguente. Nel secondo capitolo viene presentato lo stato dell’arte. Alcune caratteristiche presentate saranno riprese per la stesura del protocollo LEADER. Inoltre, in analogia con la soluzione proposta, sono evidenziati alcuni algoritmi rivolti alla clusterizzazione e alla elezione dei leader. Nel terzo capitolo viene presentato il protocollo LEADER, che permette la creazione delle comunità a partire da una overlay network costruita in base alla similarità dei peer. Vengono descritte le funzioni e le strutture dati utilizzate durante l’esecuzione dell’algoritmo, viene presentato lo pseudocodice e indicate le sue possibili evoluzioni. Inoltre, attraverso un esempio, viene mostrato passo passo come l’algoritmo opera sui nodi di una rete. Il quarto capitolo mostra come il protocollo LEADER è stato implementato. Sono presentati i moduli che ne costituiscono la struttura e le classi che li implementano. Inoltre viene descritto il simulatore utilizzato per l’esecuzione dei test e la sua implementazione. Nel quinto capitolo, dopo la definizione in dettaglio degli indici utilizzati in fase di test, vengono mostrate le prestazioni dell’algoritmo eseguito in differenti scenari al fine di testarne le proprie qualità. Infine nel sesto capitolo riporto alcune conclusioni..

(11) Capitolo 2 Stato dell’Arte In questo capitolo viene presentato il protocollo Gossip, successivamente sono riportati alcuni lavori che evidenziano gli aspetti preponderanti nell’ambito della similarità dei contenuti (Semantic Overlay Network). Inoltre, per analogie con il protocollo proposto nel prossimo capitolo, sono presentati alcune soluzioni per l’elezione dei leader.. 2.1. Gossip. Un protocollo Gossip [16] è una modalità di comunicazione tra computer ispirata al gossip-pettegolezzo presente nelle social network. Il protocollo Gossip è detto epidemico perché diffonde le informazioni in modo simile alla diffusione di un virus in una comunità biologica. Il concetto di una comunicazione gossip può essere illustrata per analogia con il “passaparola”. Ogni nodo detiene una finestra limitate di informazioni del sistema. Ad intervalli regolari seleziona in modo probabilistico (che sia completamente casuale o in modo pi` u mirato) un nodo da lui conosciuto al quale invia parte delle informazioni in suo possesso. Si può notare come la scelta casuale possa portare ad una ridondanza nell’invio dei messaggi: ogni nodo può infatti ricevere pi` u volte lo stesso messaggio. Ciò garantisce una buona resistenza di base alla perdita dei pacchetti. Inoltre, tale caratteristica comporta la mancanza di un singolo punto di fallimento in quanto nessun nodo della rete ha un ruolo fondamentale o compiti particolari in essa. Ogni nodo mantiene solo una vista parziale delle informazioni della rete, il numero dei messaggi che ogni nodo invia è costante e predeterminato a prescindere dal numero di nodi totale della rete. Ciò garantisce una maggiore scalabilità. Un protocollo gossip non necessita di specifici meccanismi di adattabilità in quanto direttamente attraverso lo scambio di messaggi gossip si perdono le vecchie informazioni a favore delle nuove. Il tempo di convergenza della 11.

(12) 12. CAPITOLO 2. STATO DELL’ARTE. coerenza, cioè il tempo impiegato dal protocollo per propagare nuove informazioni a tutti i nodi interessati è di ordine logaritmico in termini di dimensione del sistema. Aldilà degli aspetti positivi sopra citati, rimane una controparte negativa derivante dalla natura probabilistica del protocollo. I destinatari dei messaggi hanno infatti una probabilità di non ricevere una certa informazione.. 2.2 2.2.1. Spazio e Reti Semantiche GosSkip. In [9] viene proposta una struttura dati distribuita che provvede un miglior compromesso tra l’espressività delle query e l’efficienza delle query presenti nelle Distribute Hash Table (es. Pastry [11] e Chord [12]). Come negli altri sistemi, GosSkip ha l’importante proprietà di preservare il contenuto locale nello spazio semantico. Struttura della rete: GosSkip collega oggetti/applicazioni (piuttosto che entità di calcolo) in una struttura formata da un insieme di alberi bilanciati. GosSkip è costruito usando un protocollo basato su Gossip [16] che organizza i peer in modo tale che essi formano una linked list doppia ordinata (o ring). I peer immediatamente vicini (ad un hop di distanza) sono a livello 0, i vicini che sono a distanza k salti sono a livello k-1. Una volta che un peer ha localizzato se stesso in una lista ordinata, si collega ai vicini di livello 0. Ogni peer possiede dei long range per ogni i-esimo livello, con 1 ≤ i ≤ logk (N ) (N il numero dei peer). Questi link formano un insieme di skip list, fornendo la funzionalità di bilanciare k-ari alberi ottenendo O(logk N ) per il costo di ricerca e inserzione. Ogni peer è presente in tutti i logk (N ) livelli. Infine, i cammini di routing delle query sono distribuiti in maniera uniforme tra tutti peer della rete. Caratterizzazione del peer: in GosSkip un peer è associato ad un singolo elemento dei dati. Della sua gestione è responsabile il nodo fisico (l’entità di calcolo) che ha pubblicato tale elemento. Ogni peer ha un nome che descrive la semantica dell’oggetto a cui è associato. La sola proprietà necessaria è che tali nomi seguano un ordine totale e deterministico. Quindi la posizione di un elemento è pienamente determinata dal suo nome. Ad ogni messaggio è associato il livello dei vicini a cui è destinato. Il numero di link gestiti da un peer è nell’ordine di 2 log N . Join al sistema: quando un peer vuole collegarsi alla rete invia un semplice messaggio di join a un peer che fa già parte del sistema, come nella maggior parte degli algoritmi p2p [12][17]. Il messaggio di join scorre la lista ordinata dei peer fino a quando viene trovata la posizione del nuovo peer e viene inserito preservando.

(13) 2.2. SPAZIO E RETI SEMANTICHE. 13. l’ordinamento. Poi, tramite lo scambio di messaggi, il nuovo peer è gradualmente integrato negli elenchi del livello superiore. Disconnessione dalla rete: quando un peer intende lasciare il sistema, interrompe i messaggi di gossip e gradualmente viene eliminato dalle liste dei suoi vicini. Aspetto critico: associare i collegamenti all’oggetto pubblicato può portare ad un numero molto elevato di collegamenti per le entità di calcolo specialmente nelle reti in cui il numero di oggetti condivisi da ogni utente è, rilevante. Un esempio sono le reti per la condivisione di file multimediali. Inoltre, su una rete GosSkip risulta difficile effettuare una ricerca quando non si è in possesso del nome esatto che identifica l’applicazione.. 2.2.2. Riduzione del Traffico nei Sistemi P2P: un Approccio Semantico. L’approccio classico per affrontare il problema della riduzione del numero dei messaggi nei sistemi p2p prevede l’utilizzo di uno o pi` u peer per l’indicizzazione delle risorse. Tale metodo, per quanto abbastanza funzionale, risulta non scalabile in quanto al crescere del numero di risorse deve aumentare il numero di peer utilizzati per indicizzarle. Inoltre, appare non conforme al paradigma dei sistemi P2P che prevede il massimo di parità possibile nei compiti e nel funzionamento dei vari peer. Nei sistemi totalmente distribuiti (in cui tutti i nodi sono pari), la localizzazione di una risorsa avviene attraverso una ricerca quasi esaustiva: ogni peer che riceve una richiesta per una risorsa, tenta di soddisfarla con le risorse in possesso, ed, inoltre, la propaga in maniera broadcast ad ogni peer conosciuto in modo da favorire una risposta pi` u completa possibile. Il lavoro [26] propone una soluzione al precedente problema, che si basa sulla restrizione, da parte di ogni peer, dell’insieme dei peer a cui sottomettere (o propagare) una query. In altre parole, l’obiettivo che tale soluzione intende raggiungere è di avere, a parità di numero di peer coinvolti nella risoluzione di una query, una frazione maggiore di peer significativi rispetto alla query. Caratterizzazione della rete: l’originalità dell’approccio si riconduce essenzialmente al fatto di utilizzare, oltre a proprietà locali, anche proprietà globali, legate cioé al contesto dei peer in cui un dato peer è inserito ed alla iterazione reciproca che ne scaturisce. Il sistema P2P proposto è un sistema totalmente decentralizzato in cui si cerca di limare, per ciascun peer, il numero dei peer a cui sottomettere una richiesta, al fine di ridurre il traffico dovuto al passaggio della query da un peer.

(14) 14. CAPITOLO 2. STATO DELL’ARTE. all’altro e consentire tempi di vita maggiori per le query, aumentando in tal modo la probabilità di successo. Caratterizzazione del peer: riuscire a estrapolare gli interessi di un utente, partendo dai dati da lui condivisi, può essere utile per aiutarlo nella ricerca di nuovi dati di potenziale interesse. A tale scopo viene implementata un’ontologia per ogni peer, ovvero una rappresentazione sintetica dei dati da lui condivisi in grado di evidenziare quelle che sono le sue preferenze. Nella definizione dell’ontologia utilizzata che sia in grado di rispecchiare gli interessi del peer vengono sfruttati i metadati associati ad ogni risorsa. Nel calcolare il grado di similarità tra due ontologie, e di conseguenza una percentuale degli interessi comuni tra due utenti, viene calcolato il numero di risorse dei due peer aventi valori uguali per metadati uguali; il denominatore, per come è calcolato, normalizza il risultato in modo che la similarità abbia un valore compreso tra 0 e 1. Per rilevare la capacità di fare da tramite verso peer con alta similarità, viene utilizzata una proprietà globale chiamata aspettativa. Ciò che viene codificato è l’aspettativa di un nodo Pi verso un certo nodo Pj , tale valore può essere alto (prossimo ad 1) anche se la similarità tra Pi e Pj non è elevata. Viene mantenuta la proprietà di equilibrio globale: se l’aspettativa verso Pj è alta pur essendo bassa la similarità con Pj , dovrà essere alta la similarità di Pj con altri peer verso cui l’aspettativa di Pi è alta. In altre parole, l’aspettativa verso Pj potrà essere ottenuta combinando la similarità con Pj (componente locale) e l’insieme delle aspettative verso gli altri peer, pesate attraverso la similarità di tali peer verso Pj (componente globale). Si produce uno smorzamento di aspettativa verso i peer che non rispondono positivamente alle query. Aspetto critico: l’inconveniente pi` u rilevante è l’attendibilità dei metadati che descrivono le risorse sia per i possibili errori sia per l’ambiguità causata da parole differenti ma il cui significato è simile. Inoltre risulta difficile da garantire che ogni peer abbia la possibilità di comunicare con qualsiasi altro peer presente nella rete.. 2.2.3. Semantic Overlay Networks (SONs). I sistemi peer-to-peer in cui la creazione dell’overlay network avviene in modo random comportano una marcata inefficienza nella gestione delle query. Come alternativa sono stati proposti sistemi P2P rigidi in cui il posizionamento del contenuto tra i nodi si basa su funzioni hash. Tale soluzione comporta buone prestazione nel-.

(15) 2.2. SPAZIO E RETI SEMANTICHE. 15. la gestione delle query solo nei caso in cui è conosciuta l’esatta chiave di ricerca e quindi mal si presta ad interrogazioni testuali. L’obiettivo del lavoro [27] è quello di diminuire i tempi di ricerca nelle query nelle reti peer-to-peer che creano l’overlay network in modo random, e allo stesso tempo mantenere un alto grado di autonomia dei nodi. Struttura della rete: la rete è organizzata in Semantic Overlay Networks. Figura 2.1: la struttura della gerarchia delle SONs (da [27]) (SONs): una struttura ad albero dove ogni nodo è formato da cluster di peer. Un gruppo di peer semanticamente simili tra di loro viene identificato come SON. Come definire la rete: si parte da una classificazione gerarchica come base per l’overlay network. Tale classificazione viene valutata usando l’attuale distribuzione dei nodi per arrivare ad una buona gerarchia. Ad ogni SON viene associato un concetto c della classificazione gerarchica (es. per la musica Rock, Jazz, Soft, Pop, ecc), indicato con SON c. Tale gerarchia viene salvata da tutti (o alcuni) nodi del sistema ed è usata per definire SON. Ogni peer può essere associato a uno o pi` u SON. Join al sistema: un nodo per collegarsi al sistema invia sulla rete richieste sulla gerarchia (con un approccio simile a Gnutella [18]), poi esegue la classificazione dei suoi documenti basandosi sulla gerarchia appena ottenuta. Successivamente, un nodo classificatore assegna al nodo specifici SON; poi, il nuovo nodo si collega a tutti i nodi dei SON di cui fa parte (stile Gnutella o usando una directory centralizzata) Caratterizzazione dei peer: Un peer viene classificato in base ai suoi documenti tramite due possibili strategie: • un peer è aggiunto in una SON c se ha almeno un documento classificato con c.

(16) 16. CAPITOLO 2. STATO DELL’ARTE • un peer è aggiunto in una SON c se il numero di documenti classificati con c supera una soglia prefissata.. La prima (strategia di base) garantisce la rintracciabilità di tutti i documenti ma accresce il numero di nodi di ogni SON e il numero di connessione che ogni nodo deve mantenere. La seconda è una strategia meno conservativa, dove i nodi si collegano solo ad alcuni dei possibili SON. Ciò permette di ottenere migliori perfomance. Un nodo determina i SON a cui collegarsi in base al numero di documenti di ogni categoria, siano esse categorie principali che sotto categorie. Se un nodo supera la soglia prefissata di documenti di una categoria di base, la supererà anche nella categoria pi` u generica che la contiene, per questo il nodo si collegherà ad entrambe. Inoltre potrà collegarsi, quindi superare la soglia, in una categoria pur non raggiungendo la soglia nelle singole sotto categorie. La strategia pi` u conservativa, cioè quella di collegarsi ai SON di cui ho almeno un documento, si ottiene ponendo la soglia a 0. Query: quando un nodo vuole inviare una query, prima la classifica e poi la invia ai relativi SONs. Come meccanismo di propagazione può essere usato il flooding stile Gnutella o super peers. Aspetto Critico: la struttura della rete è rigida e occorre prefissarla a priori. La rete non permette una modellazione dinamica della stessa e quindi comporta la formazione col tempo di cluster altamente disomogenei all’aumentare dei nodi privi di un’adeguata collocazione all’interno della struttura delle SONs.. 2.2.4. Peer Data Management Systems. Obiettivo dell’articolo: Nel lavoro [28] è introdotto il Peer Data Management Systems (PDMSs) come soluzione al problema della condivisione su larga scala di dati semanticamente ricchi. Un PDMS consiste di peers semantici connessi tramite mappature semantiche. L’interrogazione di una PDMS può portare a scarsi risultati a causa dalle approssimazioni fornite durante la costruzione delle mappe semantiche determinando cos`ı il problema di come promuovere una mappatura della rete nelle PDMS. Viene proposta una strategia per il mantenimento incrementale di una organizzazione flessibile della rete che clusterizza insiemi di peers in relazione semantica tra di loro in SON pur mantenendo un elevato grado di autonomia del nodo. Struttura della rete: la rete è organizzata in una serie di SON. La mancanza di un dizionario comune tra i peers può portare ad avere contenuti simili se non addirittura gli stessi, ma non descritti con gli stessi concetti. Per risolvere tale eterogeneità sono raggruppati nella stessa SON nodi con concetti semanticamente simili..

(17) 2.2. SPAZIO E RETI SEMANTICHE. 17. La rete contiene un Access Point Structure(APS). Si tratta di una struttura leggera che conserva le informazioni circa i SONs disponibili nella rete. E’ concettualmente centralizzata, ma può essere salvata in modo distribuito fra peers diversi, ad esempio, per mezzo di una Distrubuted Hash Table (DHT). Come definire la rete: per superare i problemi inerenti la caratterizzazione. Figura 2.2: esempio di organizzazione della rete (da [28]) di un cluster di peer con solo un concetto, ogni SON è trattato utilizzando una sua rappresentazione sintattica chiamata Semantic Feature(SF). A tale scopo è stato definito il concetto di clustroid (concetto pi` u generale). Dato un insieme di concetti C, il clustroid di C è definito come il concetto Cl appartenente a C tale che ∀c ∈ C, DistF actor(Cl) = DistF actor(c), dove DistF actor è un’adeguata funzione che calcola la distanza fra due concetti. Sia Cptj un cluster di concetti che rappresenta il SONj , definiamo SFj di un SONj come la struttura dati formata da: • nj la cardinalità di Cptj • Clj , il clustroid di Cptj , insieme al DistF actor(Clj ) e all’identificatore univoco del peer CPj a cui appartiene • rj , il raggio (la radice della media delle distanze degli n concetti dal loro clustroid) • sampj , un insieme di p concetti di esempio selezionati da Cptj con i loro DistF actor..

(18) 18. CAPITOLO 2. STATO DELL’ARTE Caratterizzazione dei peer: un peer è rappresentato da un insieme di concetti. che descrivono il contenuto semantico dei propri temi di interesse. Il calcolo della distanza tra peer e quindi tra concetti viene fatto utilizzando la classificazione data da WordNet [29]. Join al sistema: quando un peer entra nel sistema per prima cosa esegue una selezione preliminare mediante l’accesso all’Access Point Structure(APS). L’APS confronta i Cpt dei SON con i concetti del nuovo peer e segnala a quest’ultimo i SON a cui collegarsi e se formare nuovi SON fornendo i concetti che rappresenteranno il nuovo SON. Ad ogni concetto che caratterizza il peer viene associato un SON esistente in base alla distanza tra il concetto del peer e il clustroid della SON. Nel caso in cui un concetto sia distante oltre una data soglia da tutti i clustroid dei SON esistenti, viene creato un nuovo SON il cui clustroid è il concetto stesso del peer. A questo punto il peer inizia a navigare tra i link all’interno di ogni struttura dei SON scelti, per scegliere i peer semanticamente a lui pi` u vicini. Ciò avviene utilizzando due criteri: Range-based, KNN-based. Nel primo,il nuovo peer si connette a tutti i peer all’interno di un determinato intervallo di somiglianza semantica; nel secondo, il peer sceglie i k peer semanticamente a lui pi` u vicini. Per entrambe le politiche si introducono algoritmi efficienti che sfruttano strutture indicizzate distribuite su tutta la rete per ridurre lo spazio di ricerca. Viene proposto un processo di selezione dei vicini guidato da un meccanismo di indicizzazione distribuito che mantiene per ogni nodo un apposito indice chiamato Semantic Clustering Indices (SCIs) [20]. SCI contiene un’informazione sintetizzata circa i concetti dei SON disponibili in ogni direzione. In particolare, lo SCI di un peer è una matrice di n + 1 righe e m colonne dove n è il numero di peer vicini e m il numero di SON a cui i peer sono collegati. L’elemento (i, j) si riferisce all’insieme di concetti Cpt per l’i-esimo peer collegato al j-esimo SON. Come per la definizione degli SF , ogni elemento contiene le seguenti informazioni circa SON(i,j) : • Cl(i,j) , il clustroid della sub-SON SON(i,j) insieme al DistF actor(Cl); • r(i,j) , il raggio esterno: la massima distanza tra Cl e i concetti di SON(i,j) ; • samp(i,j) , un insieme di 2p esempi di concetti, i p pi` u vicini e i p pi` u lontani dal clustroid, selezionati dal SON(i,j) e il corrispondente valore DistF actor. Gli indici SCI sono utilizzati per alleggerire il processo di selezione dei vicini. L’obbiettivo è di ridurre il numero di accessi e la quantità di calcolo richiesto per ogni collegamento..

(19) 2.2. SPAZIO E RETI SEMANTICHE. 19. Update del sistema: le informazioni memorizzate nell’APS (Access Point Structure) descrive l’attuale impostazione del sistema e di conseguenza deve essere tenuto aggiornato per riflettere le eventuali modifiche della rete. L’evoluzione dell’ APS è gestito in maniera incrementale; • quando un nuovo Peer entra nel sistema instanzia in parte la sua lista di posizionamenti associando ad ogni suo concetto il SON semanticamente pi` u vicino, se esso esiste. • i concetti mappati nello stesso SON sono raggruppati assieme • entra nei SON i cui insiemi di concetti non sono vuoti. A questo punto, ogni Cpt dei SON ai quali si collega deve essere aggiornato. I concetti nel nuovo peer per i quali non ci sono corrispondenti SON sono riuniti in gruppi, ed ogni gruppo forma un nuovo SON. Si adotta un approccio di agglomerazione standard che definisce la distanza tra i clusters come la media dei legami del gruppo [19]. Poi, per ogni SON viene calcolato un nuovo SF e aggiunto nello APS. Tale approccio è anche quello adottato dal primo peer che entra nel sistema. Query: per l’esecuzione di una query viene utilizzato la Semantic Rounting Indices(SRIs) [20], meccanismo di indicizzazione completamente distribuito che sintetizza la semantica sottostante ogni sottorete. Disconnessione dalla rete: le disconnessioni sono trattate in maniera simile alle connessioni. Quando un nodo si disconnette dalla rete, ciascuno dei i suoi vicini deve eliminare la riga del peer disconnesso dalla propria SCI (Semantic Clustering Indices) e quindi informa i vicini rimanenti del verificarsi di una modifica inviando loro le nuove informazioni aggregate del suo SCI. Aspetto critico: L’evoluzione degli interessi di un peer comporta la modifica dei concetti che lo rappresenta. Tale aspetto appesantisce la gestione dei SON (introduce overhead) in quanto i cambiamenti comportano modifiche nella struttura della rete che sono effettuate tramite complesse procedure, simili a quelle di connessione e di disconnessione dei peer. Infatti, ogni modifica innesca un meccanismo distribuito di rimodellazione che si estende a tutti i peer vicini(e non, se si usa il criterio KNN-based) facenti parte dei SON interessati.. 2.2.5. Proactive gossip-based management. Molte procedure di ricerca dei contenuti presenti in reti P2P di file-sharing sono focalizzate sullo sfruttamento delle relazioni semantiche fra peers per migliorane la.

(20) 20. CAPITOLO 2. STATO DELL’ARTE. qualità dei risultati. La metodologia corrente richiede metodi reattivi per gestire relazioni semantiche: questi confidano sull’uso dei meccanismi basilari di ricerca, e deducono relazioni semantiche basandosi sulle query poste e le corrispondenti risposte ricevute. In [30] si introduce un approccio differente proponendo un metodo proattivo per costruire le overlay semantiche. Il metodo è basato su un controllo capillare della rete che clusterizza i peer con contenuto simile. La clusterizzazione dei peer è fatta in un modo completamente implicito, cioè senza la richiesta da parte dell’utente di specificare alcuna preferenza o di caratterizzare il contenuto di file da lui condivisi. Ogni peer mantiene una propria lista semantica contenente informazioni sullo stato della rete. Infine, attraverso una simulazione, viene dimostrato come tali liste siano altamente efficienti nella ricerca per contenuti, e come la loro costruzione sia efficiente e robusta anche in presenza di cambiamenti nella rete. Struttura della rete: viene formata una overlay network semantica, formata attraverso collegamenti tra peer in relazione semantica tra di loro, che riflette anche desiderate proprietà dei random graph e reti complesse in generale [21],[22]. La struttura è completamente distribuita, non c’è una struttura che descriva globalmente la rete. In uno studio recente [23] risulta che tutte le ricerche basate su reti peer-to-peer semantiche seguono la costruzione di liste semantiche mentre allo stesso tempo occorre gestire il cambiamento dell’insieme dei nodi. Mantenere un’overlay network semantica su nodi molto dinamici risulta molto complesso. Tali reti esibiscono un’alta clusterizzazione che facilita la ricerca semantica per contenuto dove non ci sono cambiamenti. La loro struttura, non si adatta quindi facilmente ad ambienti in cui sono presenti scenari dinamici dove la propagazione dei cambiamenti può accadere in ogni luogo della rete. Queste overlay network dovrebbero riflettere anche le proprietà dei random graph e delle reti complesse in generale. Questi due conflitti richiedono alta complessità per la loro integrazione in un unico protocollo. Il framework di ricerca basato sui contenuti divide questi due aspetti: da un lato, per quanto riguarda la costruzione delle liste semantiche, il protocollo deve ottimizzare questi elenchi esclusivamente per la ricerca, a prescindere da qualsiasi altra proprietà. Dall’altra parte, quando si tratta della gestione dinamica della rete, un protocollo separato si occupa di fornire informazioni aggiornate. Il progetto disaccoppia questi due aspetti adottando un approccio a due livelli basati su protocolli gossip. Il livello inferiore, chiamato Cyclon [24] si occupa di mantenere un connected overlay e di alimentare periodicamente il protocollo del livello superiore con nodi selezionati in modo uniforme e casuale su tutta la rete. Il protocollo di livello superiore, chiamato Vicinity, si occupa di scoprire i peer a lui semanticamente pi` u vicini, e aggiungerli alla propria lista di vicini semantici. Tali liste semantiche.

(21) 2.2. SPAZIO E RETI SEMANTICHE. 21. sono ottimizzate per l’esecuzione delle ricerche. Caratterizzazione dei peer: un peer è caratterizzato mediante gossip item utilizzati durante la comunicazione. Un gossip item creato da un peer P è una tupla contente i seguenti tre campi: • informazioni per la connessione di P (indirizzo di rete e porta) • ora della creazione dell’item • dati specifici dell’applicazione, in questo caso la lista dei file di P Nel modello proposto ogni peer mantiene una lista di vicini semantici (semantic view) di piccola dimensione prefissata. Consideriamo una funzione di prossimità semantica S(P ; Q) che quantifica la prossimità semantica tra due peer P e Q, basata sugli elenchi di file in loro possesso. Lo scopo è quello di trovare una lista di vicini Q1 , ..., Qn tale che la somma dei S(P ; Qi) è massimizzata. Una buona funzione di prossimità può soddisfare la proprietà transitiva: se P e Q sono simili, Q e R sono simili, è probabile che P e R siano simili. Tale proprietà non è comunque obbligatoria per il sistema. L’obbiettivo è quello di costruire, per ogni peer, una lista semantica che contiene i peer semanticamente pi` u vicini di tutta la rete. Questi elenchi devono essere adattati in modo dinamico per riflettere lo stato attuale della rete. Join al sistema: come indicato in Cyclon, un nuovo peer per collegarsi alla rete deve semplicemente conoscere un peer che fa già parte dello overlay network, chiamato quindi bootstrap. Tale nodo può essere ricavato in vari modi, per esempio attraverso servizi della rete locale, avvalendosi di un gruppo multicast designato, o anche contattando un server noto, ecc. Il nodo di bootstrap del nuovo peer avvia c (dimensione cache) cammini casuali (random walk), impostando il time to live (TTL) con un piccolo valore della durata prevista di un percorso medio, come quattro o cinque (tali valori ottimali sono stati ricavati a seguito di test). Il nodo in cui termina un random walk, farà parte della lista dei vicini iniziale del nuovo peer. Una volta collegato ad un peer semanticamente a lui vicino viene sfruttata, se presente, la transitività della funzione S, un peer esplora i vicini del suo vicino. In secondo luogo, occorre esaminare i nodi di tutta la rete in quanto limitandosi solo ai vicini dei vicini, può capitare che la ricerca non vada oltre il singolo cluster semantico mentre un buon vicino può essersi collegato in un qualsiasi punto della rete. C’è quindi la necessità di creare dei link ad altri cluster semanticamente correlati cos`ı come avviene per i long range link delle small-world networks [25]. A tale scopo viene utilizzato il protocollo Cyclon..

(22) 22. CAPITOLO 2. STATO DELL’ARTE Update al sistema: il protocollo Cyclon periodicamente seleziona dei nodi in. modo uniforme e casuale su tutta la rete e li passa al protocollo Vicinity. Aspetto critico: una clusterizzazione dei concetti troppo elevata può portare alla non raggiungibilità tra peer. Ogni peer è collegato solamente a quelli semanticamente a lui simili, ciò può comportare al partizionamento dei peer in sottoinsiemi isolati tra di loro. La mancanza di una struttura globale o distribuita che descriva lo stato della rete non permette un routing globale per query a meno di utilizzare una procedura come quella di Cyclon per contattare in modo random peer nella rete. Tale approccio è fortemente a discapito dell’efficienza.. 2.2.6. Gossple. All’interno del documento [43] viene presentato il protocollo gossip-like Gossple per la costruzione di una social network di conoscenze anonime utilizzata per migliorare la navigazione all’interno di applicazioni WEB 2.0 Struttura della rete: ogni utente viene collegato ad una rete di conoscenti anonimi che hanno interessi simili, indipendentemente da come essi esprimono i propri interessi, per esempio le parole chiavi utilizzate per taggare i propri oggetti. Tali conoscenti sono implicitamente usati per guidare e raffinare le operazioni di ricerca degli utenti: la presenza di due termini presenti nel profilo di un utente esprime infatti un legame tra due concetti che può guidare un altro utente nelle proprie ricerche.. Figura 2.3: la struttura della rete Gossple (da [43]).

(23) 2.2. SPAZIO E RETI SEMANTICHE. 23. Al fine di stabilire e mantenere i collegamenti tra nodi, Gossple si basa su due sotto-protocolli: un protocollo di campionamento casuale di peer RPS [44] e un protocollo di clustering multi-interessi (GNet protocol). Ogni nodo mantiene una strutturata dati separata per ogni sotto-protocollo. In RPS ogni nodo mantiene le informazioni di un sottoinsieme random dei nodi della rete. Periodicamente ne viene scelto uno in modo casuale fra quelli in suo possesso, con il quale scambia parte delle proprie informazioni. Per ogni nodo RPS mantiene: l’IP address e Gossple id del nodo, un riassunto delle informazioni del profilo sotto forma di un filtro Bloom [45] e il numero di elementi del profilo. GNet utilizza una lista contenente informazioni di c nodi della rete, con c parametro del sistema. Per i c nodi, oltre alle informazioni già contenute da RPS, viene mantenuto il loro profilo completo e il timestamp dell’ultimo aggiornamento. I c nodi sono i conoscenti del nodo. GNet, basandosi su gossip, richiede aggiornamenti periodici ai propri nodi conoscenti. Caratterizzazione dei peer: il profilo di un nodo è composto da un insieme di elementi. Ogni elemento può essere descritto da un numero potenzialmente ampio di meta informazioni. Sia Ii l’insieme di elementi del nodo i, la cosine similarità tra due nodi i e j è definita come | Ii ∩ Ij | ItemCos(ni, nj) = p | Ii | × | Ij | Per non perdere informazioni verso interessi pi` u marginali a favore esclusivo di quello preponderante, si considerano insiemi di profili invece di profili singoli. Per calcolare la similarità tra due utenti, quindi tra due insiemi di profili, vieni introdotta la set cosine similarity metric come generalizzazione della cosine similarity metric [46, 47]. Dati due vettori di attributi, A e B, la cosine similarity metric è definita come Pn. Ai × Bi qP 2 n 2 i=1 (Ai ) × i=1 (Bi ). A·B = qP similarity = cos (θ) = kAk kBk n. i=1. Il filtro Bloom provvede una buona approssimazione del profilo che può essere usato durante il calcolo della similarità tra nodi con un trascurabile margine di errore. Update al sistema: il protocollo RPS periodicamente seleziona dei nodi in modo uniforme e casuale su tutta la rete. Le informazioni cos`ı ricavate da RPS sono utilizzate da GNet per aggiornare la propria struttura al fine di avere conoscenza di quei nodi che massimizzano la funzione di similarità..

(24) 24. CAPITOLO 2. STATO DELL’ARTE Aspetto critico: la mancanza di una conoscenza globale dello stato della rete o. comunque l’assenza un elemento che caratterizzi porzioni della rete, per esempio un cluster di nodi, limita le informazioni disponibili per un nodo a solo quelle disponibili nel suo intorno di conoscenti.. 2.2.7. Full-Text Federated Search. Il lavoro presentato in [31] è finalizzato alla creazione di una rete peer-to-peer che fornisca funzionalità di ricerca federata su larga scala in una rete di biblioteche di testi digitali. La struttura distribuita non utilizza le classiche tecniche di ricerca semplice che si basano sul nome dei documenti e limitati termini di un vocabolario, ma permette una ricerca full-text del contenuto del documento. Caratterizzazione dei peer: a livello funzionale abbiamo tre entità: • Consumer, rappresenta un utente che richiede informazioni. Esso invia richieste tramite query; • Provider, rappresenta la libreria digitale che condivide i documenti all’interno della rete. Provvede al servizio di ricerca full-text tramite l’esecuzione di un algoritmo di ricerca su collezioni di documenti. Oltre a rispondere alle query, fornisce, su richiesta, un’accurata descrizione del suo contenuto ai suoi hub vicini; • Hub, è una risorsa che fornisce servizio di directory per una regione della rete. Acquisisce e conserva i dati dei fornitori e quelli contenuti negli hub limitrofi; utilizza tali informazioni per fornire una selezione delle risorse (per il routing delle query). Infine, effettua la fusione dei risultati integrando i risultati ritornati da altri fornitori. Struttura della rete: il modello dello overlay network per la ricerca full-text federale è basato su un’architettura peer-to-peer gerarchia. La rete usa hub (con funzione di directory service regionali) per definire un livello superiore (o backbone) a copertura della rete senza dover contare su un’autorità centrale. Le connessioni tra utenti e hub sono stabilite in base agli interessi degli utenti stessi. Il livello pi` u basso della gerarchia è costituito dalle biblioteche digitale e dagli utenti. Nel livello superiore della gerarchia la prossimità nella rete corrisponde ad aree con contenuti simili per una buona navigabilità in quanto provider con contenuto simili tendono a collegarsi allo stesso hub. Nel livello inferiore le connessioni tra biblioteche digitali e hub sono organizzate in modo da formare cluster basati sui contenuti. La ricerca full-text e l’auto organizzazione dei peer coinvolge costi di comunicazione non.

(25) 2.2. SPAZIO E RETI SEMANTICHE. 25. Figura 2.4: un esempio della struttura della rete (da [31]) banali, per questo, per svolgere i compiti di directory service occorre un’adeguata potenza di calcolo ed elevata banda di connessione. Architetture peer-to-peer strutturate non risultano idonee in quanto utilizzano tabelle hash distribuite che non si adattano per query multi-attributo; è difficile per questo un sostegno efficace ed efficiente per la ricerca full-tex. La tipologia Hub-Hub ha le proprietà di una smallworld [8] basata sui contenuti. In questo modo la distanza tra peer è basata sulla similarità dei contenuti. Ogni hub mantiene connessioni sia con hub su aree di contenuti simili (connessioni locali) sia con hub su aree di contenuti differenti(long-range connections). Join al sistema: i consumer e i provider si collegano solo agli hub, in questo modo, gli hub hanno funzione di gateway, collegando le foglie (consumer e provider) al resto della rete. Una foglia si può connettere a uno o pi` u hub. I provider con contenuti simili, connettendosi allo stesso hub, formano un cluster basato sui contenuti. Ognuno di essi definisce una zona di contenuti nella rete. Tale località permette che il routing della query sia efficace ed efficiente. Query: Il routing delle query si basa sulla descrizione delle risorse delle biblioteche collegate agli hub, in modo che i messaggi di query siano inoltrati solo ai fornitori che hanno pi` u probabilità di generare risposte pertinenti. Inoltre, la selezione di un hub vicino non è basata solo sulla capacità di fornire documenti dai propri providers, ma anche considerando la sua potenzialità di fornire un percorso per altri peer che possono soddisfare la richiesta della query. Il meccanismo di ricerca non adotta l’algoritmo di Kleinberg [32] per la navigazione efficiente in una rete p2p, perché i presupposti e i requisiti dell’algoritmo non possono essere soddisfatti nella ricerca full-text federate. In particolare, l’algoritmo di ricerca di.

(26) 26. CAPITOLO 2. STATO DELL’ARTE. Kleinberg presuppone che data una query la posizione del peer che ha contenuti rilevanti sia conosciuta, e la procedura di ricerca è quella di trovare il percorso che conduce pi` u rapidamente a destinazione. Nella ricerca full-text, invece, la posizione del peer contenente informazioni rimane tipicamente non conosciuta. Un hub utilizza le descrizioni delle risorse dei suoi vicini per orientare la rotta delle query. I vicini sono raggruppati per similarità in quartieri, le descrizioni delle risorse presenti in essi hanno la stessa funzionalità degli indici di routing [34]. Un record degli indici di routing contiene il numero di documenti che possono essere trovati lungo un percorso per una serie di argomenti rappresentati da un piccolo insieme di parole chiavi. La differenza fondamentale tra le descrizioni delle risorse dei quartieri e gli indici di routing è data dalla descrizione delle risorse mediante modelli di lingua unigram [41] (termini con le loro frequenze), a differenza degli indici di routing che le rappresentano con un piccolo insieme di parole chiave per i vari argomenti. All’invio di una query occorre scegliere l’hub iniziale. Per migliorare tale scelta viene eliminata quella casuale e viene proposto a supporto l’utilizzo di un modello dell’utente persistente con interessi a lungo termine basato sulle ricerche precedenti. In questo modo si riduce il numero di passaggi hub-hub. Aspetto critico: il lavoro presentato mette in evidenza la necessità per le ricerche full-text di un livello di peer (backbone) che disponga di buona potenza di calcolo e alta banda di rete. Concettualmente si richiama il modello client-server dove il lato server è costituito, invece che da un unica entità, da pi` u peer che si suddividono in modo semantico le librerie e i client..

(27) 2.3. CLUSTERING ED ELEZIONE DEI LEADER. 2.3. 27. Clustering ed Elezione dei Leader. In questa sezione sono menzionati due algoritmi per il calcolo distribuito dell’algoritmo K-Means e alcuni protocolli che mostrano gli aspetti preponderanti delle procedure presenti in letteratura adibite all’elezione di un leader fra i nodi della rete.. 2.3.1. K-Means Distribuito. L’algoritmo K-Means [36] è un algoritmo di clustering. La suddivisione dei dati/oggetti in K cluster viene effettuata con lo scopo di minimizzare la varianza totale intracluster. L’algoritmo esegue una procedura iterativa. • gli oggetti sono ripartiti casualmente nei k gruppi • vengono calcolati i punti medi dei cluster (centroidi) • ogni oggetto viene assegnato al cluster il cui centroide risulta essere a lui pi` u vicino si ripete la procedura partendo dal secondo punto e si itera fino a quando l’algoritmo non converge, cioè fino a quando l’assegnamento degli oggetti non viene pi` u modificato. Descrito in modo formale, si definisce X = x1 , x2 , ..., xN come l’insieme degli N oggetti; p1 , p2 , ..., pk le k partizioni in cui suddividere gli oggetti; la funzione obbiettivo che si vuole minimizzare è la seguente:. J=. k X X. || xj − ci ||2. i=1 xj ∈pi. dove || xj − ci ||2 è la distanza tra l’oggetto xj e il centroide ci del cluster i. Occorre inoltre soddisfare le seguenti proprietà: •. Sk. p = X: tutti gli oggetti devono appartenere ad almeno un cluster;. •. Tk. p = ∅: ogni oggetto può appartenere ad un solo cluster;. 1. 1. • ∀i pi 6= ∅: ogni cluster deve contenere almeno un oggetto.

(28) 28. CAPITOLO 2. STATO DELL’ARTE L’algoritmo K-Means cos`ı proposto viene eseguito in centralizzato.. Nelle prossime sezioni sono presentate due procedure per l’esecuzione del KMeans al fine di clusterizzare dei nodi presenti in una rete in base alle informazioni che li caratterizzano. L’esecuzione dell’algoritmo avviene in maniera distribuita su ogni nodo. LSP2P K-means Descrizione dell’algoritmo: un singolo nodo da inizio all’algoritmo. Tale nodo genera in modo random un insieme iniziale di centroidi che invia ai suoi vicini adiacenti insieme ad una soglia, gamma. Quando un vicino riceve per la prima volta i centroidi iniziali e gamma li inoltra ai suoi vicini dando luogo all’inizio dell’iterazione 1. Una ricezione futura dell’insieme iniziale di centroidi viene ignorata. L’algoritmo ad ogni iterazione modifica i centroidi per ogni nodo. Ad ogni iterazione un nodo raccoglie i centroidi e i loro cluster in riferimento alla i-esima iterazione calcolati dai suoi vicini adiacenti. Tali dati sono usati dal nodo per calcolare a sua volta in locale i propri centroidi che saranno inoltrati ai propri vicini e da loro usati nell’iterazione successiva. Nel caso in cui i nuovi centroidi non si differenziano in modo sostanziale dai precedenti il nodo termina il protocollo. In dettaglio se la massima distanza tra i centroidi del nodo all’inizio e alla fine dell’i-esima iterazione è maggiore del parametro gamma si passa all’iterazione i+1, altrimenti l’algoritmo termina. Aspetto critico: LSP2P K-means non richiede sincronizzazione globale, nel senso che tutti i nodi della rete non devono eseguire in modo sincrono la stessa iterazione. Tuttavia, l’algoritmo non è completamente asincrono, ma una sincronizzazione locale è necessaria. Poiché un nodo deve attendere delle risposte da suoi vicini per poter eseguire la propria iterazione, lo scarto temporale tra due vicini sarà al massimo di una iterazione. Quindi, la differenza di numero di iterazione tra due nodi non è mai oltre il numero di collegamenti di rete (hops) tra i due nodi. USP2P K-Means Descrizione dell’algoritmo: ad ogni iterazione vengono selezionati in modo uniforme dalla rete s nodi, ad essi è affidato il compito di aggiornare i centroidi. L’algoritmo presuppone che un singolo nodo, N1, senza perdita di generalità, agisca come un leader e coordini le iterazioni. La procedura prevede la specifica dei seguenti parametri: • c, soglia di precisione del clustering; • p, precisione della probabilità della soglia.

(29) 2.3. CLUSTERING ED ELEZIONE DEI LEADER. 29. • s, dimensione del nodo; • m, numero massimo di iterazioni. All’inizio dell’i-esima iterazione avremo il vettore dei centroidi Vi stimato fino a quel punto che potenzialmente potrebbe contenere degli errori di accuratezza del clustering che occorre ridurre. La misura di tale precisione è chiamata clustering confidence e denota la percentuale di punti assegnati al giusto cluster. Quando tale coefficiente rimane sotto la soglia c o sono state eseguite le m iterazioni, l’algoritmo termina. Ad ogni i-esima iterazione al fine di calcolare Vi viene eseguito il seguente algoritmo distribuito: il nodo iniziale N1 seleziona s nodi in modo uniforme su tutta la rete, i quali invieranno ai lori vicini il vettore Vi-1. Ogni nodo che riceve tale vettore calcola i propri centroidi locali e i loro cluster e ritorna ad N1 tali informazioni. N1 fa una media dei valori a lui ritornati per calcolare il nuovo vettore Vi. Aspetto critico: USP2P richiede una sincronizzazione solo fra sottoinsiemi di nodi ad ogni iterazione, ma a differenza di LSP2P l’algoritmo assicura una accuratezza garantita anche se con l’ipotesi che i dati presenti nella rete rimangano invariati. Inoltre, occorre una certa conoscenza globale per la scelta dei nodi e per calcolare il clustering confidence effettivo.. 2.3.2. Randomized Leader Election. In [38] viene proposto un algoritmo random efficiente per l’elezione di un leader in un sistema di larga scala distribuito; ottimizzato rispetto al numero dei messaggi, che sono dell’ordine di O(n) con n numero dei nodi della rete. L’algoritmo ha complessità logaritmica rispetto al numero di nodi del sistema e garantisce con alta probabilità l’elezione di un unico leader per tutto il sistema. L’algoritmo si adatta sia a modelli sincroni che asincroni. Struttura della rete: non vengono fatte assunzioni sulla struttura della rete. Occorre solo la completa raggiungibilità tra i nodi che eleggono un leader. Caratterizzazione dei nodi: • Processo: singola entità di un sistema distribuito che può partecipare al protocollo di elezione del leader. Nel caso di un sistema sincrono tutti processi anno un clock comune. • Contendente: l’algoritmo di elezione può essere visto come un gioco al quale partecipano i processi. I processi che stanno partecipando al gioco nelle varie fasi dell’algoritmo sono i contendenti..

(30) 30. CAPITOLO 2. STATO DELL’ARTE • Mediatore: decide i vincitori delle tappe intermedie del gioco. In particolare, un mediatore è un processo che riceve un messaggio da un concorrente e decide se il concorrente partecipa alle fasi successive del protocollo. • Round: una comunicazione tra singoli processi e un insieme di mediatori. Se alla fine di un round un processo è ancora un concorrente, inizia per lui un nuovo round. • Vincitore: un processo che non ha ricevuto riposte negative dai mediatori attraverso l’intera esecuzione dell’algoritmo.. Procedura di elezione: l’algoritmo si suddivide in due fasi. Nella prima fase l’algoritmo riduce il numero dei nodi contendenti, nella seconda fase trova il vincitore. In dettaglio, la prima fase consiste in log (n − 1) rounds per un sistema di n processi. Nel round i ogni contendente getta fi palle in n cestini. Un contendente vince se la sua palla rimane da sola nel cestino e può accedere al round successivo. Nella realizzazione di questa fase astratta con palle e cestini, un processo può essere contendente e mediatore allo stesso tempo. Gettare una palla in un contenitore scelto a caso corrisponde ad un messaggio da un concorrente ad un mediatore scelto casualmente in accordo ad una distribuzione uniforme. Un contendente è un vincitore se il suo mediatore non riceve messaggi da altri contendenti. La seconda fase del protocollo consiste in un singolo round. Ogni contendente ancora in gioco genera un numero random tra 0 e n4 e lo invia ad un insieme di p (n ln n) mediatori scelti uniformemente in modo random. Un contendente vince in questa fase se esso genera il numero pi` u grande fra tutti i contendenti. Nell’esempio in figura 2.5 i contendenti sono indicati dai quadrati, i mediatori dai secchi, e i messaggi dai contendenti al mediatore da palle etichettate (l’etichetta indica la fonte della palla). In ogni turno, i peer contendenti che non sono pi` u in corsa viene annerito il relativo quadrato. Nel primo turno, ogni contendente mette una palla in un cestino. I contendenti 2, 4, 5 e 6 possono procedere al turno successivo in quanto sono i soli ad occupare il secchio scelto. Nel round 2 (ultimo turno della prima fase), ciascun concorrente lancia due palle e i contendenti 5 e 6 superano il turno. Infine, nel round 3 (l’unico turno della seconda fase), ciascun contendente lancia cinque palle. Il contendente 6 è selezionato come leader in quanto pur ottenendo l’occupazione esclusiva di 3 secchi come il nodo 5, l’ID del nodo è superiore a quello del nodo 5 (nel nostro protocollo, come criterio della seconda di discriminazione della seconda fase, utilizziamo un numero a caso. In questo esempio è stato usato l’ID del nodo per la facilità di illustrazione)..

(31) 2.3. CLUSTERING ED ELEZIONE DEI LEADER. 31. Figura 2.5: Un esempio in cui sono illustrate le due fasi del protocollo (da [38]). Aspetto critico: Il protocollo è completamente probabilistico. Non viene scelto il rappresentate migliore ma uno in modo casuale.. 2.3.3. Un Algoritmo di Elezione per Reti Ad Hoc. In [39] viene presentato un algoritmo di elezione del leader per una rete mobile ad hoc in cui la comunicazione tra nodi è consentita solo tra nodi vicini. L’algoritmo utilizza la minima quantità di risorse wireless e non pregiudica la libertà di mobilità dei nodi. L’algoritmo rispecchia la necessità di individuare un nodo leader che coordini le comunicazioni tra i nodi. Viene garantita sia l’elezione di un leader al termine dell’esecuzione dell’algoritmo, sia che non ci possa essere pi` u di un leader per ogni componente connessa. Inoltre si ha un costo minimo per lo scambio di messaggi e la garanzia che in un dato momento ci sia solo un leader eletto. Struttura della rete: i nodi comunicano utilizzando un livello peer-to-peer in una rete mobile ad-hoc. Si considera un sistema di n nodi mobili che vengono gestiti con la seguente serie di ipotesi: • ogni nodo ha un identificativo unico,.

(32) 32. CAPITOLO 2. STATO DELL’ARTE • tutti i link di comunicazione sono bi-direzionali ed affidabili, • i cambiamenti della topologia della rete sono finiti.. Viene usato ZRP[40] come protocollo di routing per dispositivi di reti mobili ad hoc. Procedura di elezione: durante ogni turno di votazione ogni nodo propaga il suo identificatore ai suoi vicini. L identificatore con il valore maggiore viene propagato nei turni successivi fino a d round, con d corrispondente al diametro della zona. Alla fine della procedura di votazione ogni nodo è in possesso dell’identificatore della zona con il valore pi` u alto. Il nodo con l’identificatore maggiore viene eletto come leader. Nell’esempio mostrato in figura 2.6 lo spazio logico degli identificatori dei nodi è formato dalle lettere dell’alfabeto e il valore del raggio di routing è settato a 2; i nodi distanti fino a 2 hop dal nodo s eleggono tale nodo come proprio leader.. Figura 2.6: una zona di routing di raggio 2 (da [39]) Aspetto critico: occorre uno spazio logico lineare sul quale poter confrontare gli identificatori dei nodi.. 2.3.4. CDC. In [42] è presentato l’algoritmo CDC (Connectivity based Distributed node Clustering scheme )che basandosi sulla connettività crea un sistema di cluster su nodi.

(33) 2.3. CLUSTERING ED ELEZIONE DEI LEADER. 33. distribuiti in una rete peer-to-peer . Un sistema CDC è completamente decentralizzato e per ogni nodo si assume la conoscenza dei soli suoi diretti vicini. Il protocollo permette di clusterizzare l’intera rete intorno ad un insieme di nodi di partenza. Struttura della rete: la struttura di connessione di una rete P2P è rappresentata da un grafo indiretto dove i nodi formano i vertici e le connessioni tra nodi i rami del grafo. L’algoritmo può essere esteso ed utilizzato in un grafo pesato dove il peso associato ad un collegamento tra due nodi rappresenta la similarità fra i due vicini. Ogni nodo ignora completamente la struttura della rete. Inoltre si considera di lavorare su una rete altamente dinamica con il frequente ingresso e l’uscita di nodi. L’algoritmo si basa sulla individuazione di un insieme di nodi, detti originatori, che iniziano il protocollo. Gli originatori inviano un messaggio ai propri vicini. Ogni messaggio è una tupla composta da: • Id del nodo iniziale che ha inviato il messaggio, • Id del messaggio, • Weight, peso del messaggio, • Id dell’ultimo nodo da dove è passato il messaggio, • TTL, time to live. Il nodo iniziale imposta il valore di weight a 1. Ogni nodo che riceve un messaggio a sua volta lo inoltra ai suoi vicini impostando il valore di peso a quello ricevuto diviso il numero dei suoi vicini. Infine decrementa di 1 il TTL. Nel caso di un grafo pesato, il peso associato al messaggio verso il vicino V i viene calcolato come. W (Oi, V i) j|Vj is vicino (W (Oi, V j)). P. con V j vicino del nodo iniziale Oi, e W funzione che restituisce la similarità fra due nodi. In questo caso, ogni nodo che riceve un messaggio, al fine di inoltrarlo ai suoi vicini, ricalcola il valore del peso utilizzando la formula precedente moltiplicando il risultato per il weight del messaggio ricevuto. Ogni nodo V mantiene per ogni nodo iniziale il valore T otalW eight(V, Oi), con Oi i-esimo nodo iniziale. Questo valore indica la somma dei weights di tutti i messaggi generati dal Oi e ricevuti da V . Dopo che un nodo ha ricevuto l’ultimo messaggio, si collega al cluster di riferimento a quel nodo iniziale che ha il T otalW eight maggiore. Per collegarsi ad un particolare cluster, il nodo invia un messaggio al nodo.

(34) 34. CAPITOLO 2. STATO DELL’ARTE. iniziale di riferimento informandolo della proprio decisione. Se tutti i T otalW eight rimangono sotto ad una soglia predefinita, il nodo decide di rimanere un outlier, cioè un nodo che non appartiene ad alcun cluster.. Figura 2.7: un esempio dell’esecuzione del protocollo CDC su un grafo con i rami non pesati (da [42]) Join al sistema: quando un nodo si collega alla rete, per decidere se far parte di uno dei cluster già esistenti o considerarsi un nodo isolato, calcola un valore approssimato di TotalWeight ottenuto dalle informazioni ricevute dai suoi vicini. Aspetto critico: la suddivisione dei nodi in cluster dipende molto dalla scelta dei nodi iniziali che danno il via all’algoritmo. Ciò può determinare che il nodo scelto si scosti molto da quello ideale per rappresentare il cluster, il cos`ı detto medoide. Inoltre, il numero dei cluster risulta prefissato, non ci sono quindi operazione né di merge né di split delle cluster/community. Infine i cluster risultanti sono tutti allo stesso livello escludendo la possibilità di modellare sotto categorie cos`ı come descritte in SON[27].. 2.4. Conclusioni. Nell’ambito delle reti semantiche, un aspetto fondamentale è riuscire a modellare la similarità tra entità/peer. Occorre trovare un buon compromesso tra la precisione nel caratterizzare un utente, la leggerezza delle informazioni scambiate a tale scopo tra le entità, e la capacità di adattamento alle continue evoluzioni del sistema. Nella proposta data in [26] è apprezzabile la semplicità dell’approccio che si limita a confrontare i tag presenti nei propri documenti. Ciò permette un sem-.

(35) 2.4. CONCLUSIONI. 35. plice adattamento sia che si tratti di una condivisione di file multimediali, di testi o quant’altro. Inoltre ciò comporta una totale indipendenza del peer da fonti esterne cosa che non avviene in [28] e in [30] dove ogni peer deve appoggiarsi a WordNet [29] per calcolare la propria similarità con gli altri. Una caratteristica cercata nello spazio semantico è la rintracciabilità di ogni peer. Si vuole garantire la connettività tra due peer presenti ai capi opposti della rete: chiunque deve poter collegarsi con chiunque allo scopo che peer simili si trovino nella stesa comunità pur trovandosi distanti tra loro. Tale proprietà, non garantita da [26] è invece ben realizzata da [30] e [43] dove il protocollo è suddiviso in due livelli; quello inferiore tramite il protocollo rispettivamente Cyclon [24] e RPS[44], esplora tutta la rete in ricerca di nodi similari. Le soluzioni descritte in [30, 43] pur adattandosi con semplicità ed efficienza all’evoluzione della rete non permettono l’individuazione delle community che caratterizzano i peer uniti in una rete di interessi comuni, cos`ı come sono ben presentate in [27] dove però, per contro parte, vi è una designazione statica del mondo suddiviso in categorie e sotto-categorie che non permettono dei cambiamenti nella struttura. Una possibile rappresentazione delle community è fornita dalla struttura presente negli AccessPoint d i[28] dove viene utilizzata per indirizzare i nuovi peer al join del sistema. Tale struttura, basandosi su ogni singola parola che caratterizza i peer e i suoi documenti, ha il difetto di fornire una suddivisione molto dettagliata che richiede pesanti meccanismi che prediligono una rete in cui gli interessi dei peer siano stabili. Entrambi i protocolli presentati in [37] riescono ad identificare i medoidi con i relativi cluster che possiamo far combaciare con i leader e le rispettive community. Tali procedure però hanno il difetto di richiedere una sincronizzazione tra i nodi nell’esecuzione delle iterazioni del protocollo. Altri due aspetti negativi, in comune con l’algoritmo CDC [42] sono il fissare preventivamente il numero dei cluster/comunità creati in cui verranno suddivisi i peer di una rete, e il dover individuare degli specifici nodi che iniziano l’esecuzione dell’algoritmo..

(36) 36. CAPITOLO 2. STATO DELL’ARTE.

(37) Capitolo 3 Protocollo proposto In questo capitolo viene presentato LEADER un protocollo asincrono che attraverso una procedura di elezione dei leader permette di far emergere dall’overlay network la suddivisione logica degli utenti in communità. Tale protocollo possiede al suo interno le migliori caratteristiche presenti nei lavori citati nel capitolo precedente: la semplicità nell’implementare il concetto di similarità presente in [26], la connettività di tutta la rete e la adattabilità ai cambiamenti di [30], la chiarezza nella modellazione delle community in [27] con una modellazione pi` u leggera di quella già proposta in [28], una buona suddivisione dei nodi in cluster/cummunity come quella presentata in [37] e la scelta autonoma del proprio leader/community da parte di ogni nodo come in [39]. L’utilizzo di un protocollo con le suddette caratteristiche permette di unire insieme le qualità e gli aspetti positivi delle reti semantiche con quelli ottenuti tramite una clusterizzazione dei dati. La struttura dell’overlay network cos`ı creata è caratterizzata da qualità di leggerezza e di buona modellazione che permettono un’ottimizzazione nella gestione della ricerca di informazioni. La conoscenza dei soli leader permette di ottenere una visione globale della struttura dei dati e delle informazioni presenti nell’intero sistema. Infatti, venire a conoscenza del profilo di un leader, significa scoprire un gruppo di peer molto simili a quel profilo. Ciò permette miglioramenti nello instradamento dei dati e delle informazioni.. 3.1. Architettura generale del sistema. Il protocollo LEADER è inserito in un sistema per la gestione dei profili di supporto ai peer del sistema. In tale sistema viene mantenuto un indice aggiornato dei profili delle comunità e degli indici di alcuni membri di ogni comunità, permettendo di ricercare i profili per similarità. Essa è basata su due DHT. La prima 37.