Algoritmi E P2P

Algoritmi SWS e sistemi P2PAlgoritmi SWS e sistemi P2P

Mazza Dario

Merlino Sebastiano

Messina Marco

Università degli studi di Catania

Ingegneria informatica

A.A. 2008/2009

Mazza, Merlino, Messina 2

Studio e analisi degli algoritmi di Studio e analisi degli algoritmi di affinità semantica tra concettiaffinità semantica tra concetti

In questa sezione verranno descritti e analizzati i seguenti algoritmi:● H-Match (An algorithm for dynamically matching ontologies);

● Edamok (An algorithm for dynamically matching ontologies);

● Chatty Web (An algorithm for dynamically matching ontologies);

● Glue (An algorithm for dynamically matching ontologies);

● Kaon (An algorithm for dynamically matching ontologies);

● VSM (Semantic Search in Peer-to-Peer Systems);● ESS (E cient Semantic web Service discovery in centralized and P2P ffi

environments);● pService (Peer-to-Peer based Web Services Discovery and Matching):


H-MatchH-MatchPrincipi di base

L'obiettivo generale delle tecniche di compatibilità

ontologica è quello di trovare tutti i concetti che hanno

un'affinità semantica con un concetto di riferimento.

L'algoritmo H-match considera sia le caratteristiche

linguistiche dei concetti, nonché le relazioni semantiche tra

quelli presenti in una stessa ontologia. La valutazione delle

caratteristiche linguistiche è basata su un “thesaurus”, dove il

significato di ciascun termine è rappresentato da un insieme

di relazioni terminologiche.


H-MatchH-MatchPeculiarità

L'affinità semantica tra due concetti ontologici è valutata, in Helios(o H-Match), dalla stima sia delle relazioni terminologiche attraverso i tesauri sia delle relazioni semantiche valutando il contesto nel quale agiscono i due concetti.H-match ha 3 differenti tecniche di compatibilità:

● compatibilità superficiale: viene preso in considerazione solo l'informazione linguistica proveniente dal thesaurus. Questo tipo di “matching” garantisce alte performance, ma bassa precisione dei risultati;

● compatibilità media: vengono presi in considerazione sia il nome del concetto che le sue proprietà. Si ottiene una precisione più accurata rispetto alla tecnica precedente;

● compatibilità profonda: prende in esame i nomi dei concetti nonché tutto il contesto nel quale essi sono inquadrati.


H-MatchH-MatchInput/Output

L'algoritmo H-match richiede in input i due

concetti di cui si vuole calcolare l'affinità, la

tecnica di compatibilità da utilizzare, il valore del

peso dell'affinità linguistica (WLA). I valori di

default sono compatibilità profonda e WLA =

0,5. L'output dell'algoritmo è il grado dell'affinità

semantica tra i due concetti.


H-MatchH-MatchVantaggi

I vantaggi di questo algoritmo sono:● correlazione tra affinità semantica e affinità

linguistica;● possibilità di scegliere diverse tecniche di

matching (algoritmo dinamico);● ottima precisione utilizzando la compatibilità

profonda.


H-MatchH-MatchSvantaggi

Gli svantaggi dell'H-match sono:

● la compatibilità profonda richiede un'elaborazione troppo onerosa;

● ha una complessità O(N2) dove N è il numero di elementi appartenenti al contesto del concetto considerato;

● l'eterogeneità dei vocabolari in cui sono presenti i concetti da relazionare può causare perdita d'informazione;

● dubbia scalabilità;

● mai testato in un caso reale.


EdamokEdamokDescrizione generale

E' un progetto di ricerca che implementa il KEx (scambio di

conoscenza) nei sistemi P2P, con il quale si riesce a realizzare la

condivisione della conoscenza tra comunità di interesse di tipo paritarie.

Il sistema, per ottenere una mappatura di tipo semantico tra i concetti

presenti nei diversi peer, utilizza un algoritmo chiamato CTX-match.

Tale algoritmo è basato su una fase di esplicitazione semantica durante

la quale i concetti sono associati con i loro significati nel rispetto del

loro contesto. Alla fase di esplicitazione semantica segue una fase di

comparazione semantica dove i concetti vengono tradotti in assiomi

logici e comparati tra loro. L'algoritmo prevede un approccio logico di

tipo descrittivo.


Chatty WebChatty WebDescrizione generale

Questo approccio è applicabile a tutti i sistemi decentralizzati

ed offre l'opportunità di studiare l'interoperabilità semantica

come fenomeno globale. Ogni peer offre i propri dati

organizzati secondo uno schema ben preciso (relazionale,

XML, RDF). Il sistema prevede una mappatura corretta tra i

vari schemi adottati dai peer. Chatty web adotta un algoritmo

che riesce ad identificare un insieme sufficientemente grande

di peer per ottenere un'adeguata risposta ad una data query.


GlueGlueDescrizione generale

E' un sistema che sfrutta la tecnica di apprendimento delle

macchine per trovare una mappatura semantica tra i concetti

ubicati in ontologie diverse e autonome. Glue segue un

approccio di tipo probabilistico: il grado di compatibilità tra

due concetti A e B è calcolato come la probabilità che una

data istanza appartenga ad entrambi i concetti. Sono

applicate 2 tecniche di apprendimento di base. Infine una

procedura di mitigazione dell'etichettatura è utilizzata per

migliorare l'accuratezza della predizione dell'affinità.


KaonKaonDescrizione generale

E' un sistema di tipo prototipale descritto

solo per via matematica. Il sistema Kaon

pone l'accento sulla definizione ontologica e

sulle proprietà formali dei concetti al fine di

ottenere correttezza e completezza delle

espressioni.


VSMVSMDescrizione generale

Ogni documento VSM è rappresentato da un vettore di termini. I termini sono parole che si trovano all'interno del documento stesso. Ad ogni termine del vettore viene assegnato un peso. Termini con un peso superiore sono generalmente ritenuti centrali in un documento. Per valutare se un documento è rilevante per una query, il sistema misura la pertinenza tra il vettore della query e il vettore del documento. Un certo numero di sistemi di ponderazione per i termini sono stati proposti per VSM, tra i quali tf-IDF che è un sistema in cui il peso di un termine è alto , se il termine è frequente nel documento considerato, ma infrequente in altri documenti. Lo svantaggio principale della TF-IDF è che richiede informazioni a livello mondiale per il calcolo del peso di un termine.


ESSESSGeneralità

L'obiettivo del progetto ESS è quello di migliorare la qualità della

ricerca, minimizzando i relativi costi. La filosofia progettuale di

ESS è migliorare l'efficienza e l'efficacia della ricerca, pur

mantenendo semplice, robusta, e completamente di natura

decentralizzata Gnutella. In ESS, ogni nodo è dotato di un vettore

che è una sintesi compatta del suo contenuto. E ogni nodo può

avere due tipi di collegamenti, ossia collegamenti casuali e

collegamenti semantici. I collegamenti casuali collegano nodi

irrilevanti, mentre i collegamenti semantici organizzano i nodi in

gruppi semantici.


ESSESSDescrizione dell'algoritmo

L'algoritmo di adattamento della topologia è eseguito la prima volta per collegare un nodo al resto della rete tramite collegamenti casuali, o collegamenti semantici o entrambi. L'obiettivo dell'adattamento della topologia è quello di garantire che: (1) nodi pertinenti siano organizzati in gruppi semantici attraverso collegamenti semantici, e (2) la rete possa sostenere un alto numero di nodi. Data una query, il protocollo di ricerca dell'algoritmo ESS individua rapidamente un importante gruppo semantico per la ricerca, basandosi su un meccanismo di tipo selettivo dei nodi. Una volta localizzato il gruppo semantico, ESS inonda il gruppo con la query semantica per recuperare i documenti pertinenti. Le inondazioni semantiche all'interno di un gruppo, che ha nodi semanticamente associati, tendono ad essere rilevanti per la ricerca stessa della query.


pServicepServiceDescrizione dell'algoritmo

La rete p2p su cui si basa l'algoritmo può essere strutturata o non strutturata. L'overlay network generalmente usata prende il nome di skip graph consistente in un albero bilanciato con accesso in posizioni random. L'utilizzo di skip graph permette una più facile maniera di indirizzare le query ed inoltre di bilanciare l'albero della rete. Le informazioni inerenti i servizi più importanti sono inserite sotto forma di hash key all'interno della rete Chord e si utilizza skip graph per distribuire gli altri servizi. Quando un service provider aggiorna la sua descrizione possono avvenire due processi differenti di aggiornamento a secondo che essa si trovi originariamente all'interno dell'albero della rete chord o del sistema skip graph. Per ricercare dei dati, si effettuerà una ricerca fra i nodi della rete Chord. Per ottenere risultati più profondi si ricercheranno le informazioni conservate nella rete skip graph.


pServicepServiceRisultati di una richiesta

Tramite un'equazione matematica si può determinare se due servizi descritti mediante WSDL-S sono uguali; i risultati possono essere di 4 tipi:

● Il risultato è esattamente uguale alla richiesta;

● il risultato contiene i servizi richiesti ed inoltre esegue dell'altro; il risultato sussume la richiesta;

● il risultato è contenuto nella richiesta e la soddisfa solo in parte; la richiesta sussume il risultato;

● il risultato e la richiesta sono differenti.


pServicepServiceComponenti principali

I risultati di ogni query sono memorizzati nel System Monitor dal quale possono essere facilmente invocati. Il sistema pService include tre componenti principali: ● service Inquiry; ● service Matching;● service Invocation.


pServicepServiceService Inquiry

Il sistema di Service Inquiry è costruito sulla rete ibrida p2p ed è strutturato mediante l'utilizzo di tre livelli:

● Chord_ON (Top level) che mantiene relazione con i vicini nell'overlay network Chord; permette operazioni di osservazione stato, inserimento e cancellazione sui peer dell'overlay Chord;

● SkipGraph_ON (Middle level) che mantiene relazione con i vicini nell'overlay network SkipGraph; permette operazioni di osservazione stato, ricerca, inserimento, cancellazione sui peer dell'overlay SkipGraph;

● TreeNode_ON.


pServicepServiceService Matching

Il sistema Service Matching introduce due operazioni:

● matchWithOnt(doc1, doc2) in grado di trovare attinenze e similitudini fra i documenti passati;

● matchWithIOPE(doc1, doc2) in grado di trovare le relazioni che legano i due documenti.


pServicepServiceService Invocation

Il sistema Service Invocation fornisce due primitive:

● fetchService() che restituisce il servizio con la migliore QoS fra quelli memorizzati nella memoria dei ServiceResults;

● invokeService() che invoca direttamente il servizio con la migliore QoS.


Studio e analisi degli approcci P2P Studio e analisi degli approcci P2P semantici al service discoverysemantici al service discovery

Dopo un'introduzione inerente la descrizione generale delle caratteristiche delle reti P2P, si procederà all'analisi dei seguenti approcci:

● Semantic Overlay Network (SON);

● Skip Graphs (Skip Graphs ASPNES);

● WSPDS (BanaeilSWS2004);

● HyperCube (A Scalable and Ontology-Based P2P Infrastructure for Semantic Web Services);

● pSearch (PeertoPeer Information Retrieval Using SelfOrganizing Semantic Overlay Networks).


SWS in sistemi P2PSWS in sistemi P2PGeneralità

L'uso di tecnologie basate sul P2P per pubblicare e scoprire i Web Services aumenterà l'affidabilità e la scalabilità delle attuali architetture di calcolo distribuito. Un approccio P2P basato sull'uso delle ontologie permette di ottenere scoperte di servizi in modo dinamico, scalabile e decentralizzato. L'architettura di questo sistema prevede alcuni componenti funzionali:

● Costruttore del modello del processo (PMC);

● Richiesta di acquisizione e descrizione;

● Compositore di processi;

● Esecuzione del processo e valutazione;

● Motore per la scoperta dei servizi;

● Organizzazione del servizio e distribuzione;

● Repository di ontologie.


SWS in sistemi P2PSWS in sistemi P2PCostruttore del modello del processo

La funzione del PCM è quella di costruire e conservare

un processo logico in un database che contiene modelli

di processi basati sull'analisi del dominio e sull'ontologia

dei processi. Un processo logico potrebbe contenere

descrizioni di tipo semantico delle attività di un processo

e delle relazioni tra esse.


SWS in sistemi P2PSWS in sistemi P2PRichiesta di acquisizione e descrizione

Attraverso una buona interfaccia gli utenti possono

esprimere le loro richieste individuali al sistema. La

richiesta degli utenti contiene la descrizione sul dominio,

sulla semantica, sulle funzioni e sulle parole chiavi del

servizio.


SWS in sistemi P2PSWS in sistemi P2PCompositore di processi

Il compositore di processi cerca nel database dei processi

per trovare la logica del processo e poi stabilisce quali

sono i documenti che descrivono l'eseguibile di

quest'ultimo. Dopo ciò informa il motore di ricerca dei

servizi dove è possibile trovare il Web Service

appropriato.


SWS in sistemi P2PSWS in sistemi P2PEsecuzione del processo e valutazione

Il motore che esegue i processi lega direttamente

il servizio di corrispondenza al processo da

raggiungere durante la procedura di esecuzione.


SWS in sistemi P2PSWS in sistemi P2PMotore per la scoperta dei servizi

Il motore per la scoperta dei servizi chiede alla struttura

P2P di individuare il gruppo che comprende il servizio

richiesto e poi va al servizio di corrispondenza di tale

gruppo. Dopodiché, il sistema si lega a questo servizio e

lo ritorna al motore di esecuzione del processo affinché

venga eseguito.


SWS in sitemi P2PSWS in sitemi P2PMotore per la distribuzione dei servizi

Per facilitare l'organizzazione dei servizi, i peer possono

essere divisi in gruppi. Ogni gruppo contiene un certo tipo di

servizi. Il motore per la distribuzione dei servizi cerca un

appropriato gruppo di peer ed inserisce un nuovo peer in tale

gruppo. Questa organizzazione riduce lo spazio di ricerca

durante la scoperta dei servizi.


SWS in sistemi P2PSWS in sistemi P2PRepository di ontologie

Le funzioni componenti il sistema sono supportate da 3 categorie di ontologie:

● Ontologie di dominio: definiscono le informazioni semantiche in uno specifico dominio;

● ontologie di un Web Service: descrivono la gerarchia dei servizi, nella quale una sottoclasse di servizi eredita le proprietà e le funzionalità dalla superclasse;

● ontologie dei processi: rendono nota la sintassi e l'informazione semantica tra le attività presenti nella logica dei processi.


Ricerca in una rete P2P non Ricerca in una rete P2P non strutturatastrutturata

In sistemi P2P non strutturati come Gnutella, si organizzano i nodi della rete in un grafo casuale e si utilizza il flooding sul grafo per recuperare i documenti rilevanti per una query. Data una query, ogni nodo visitato, valuta la query localmente, confrontando la richiesta con il proprio contenuto, e poi inoltra la richiesta a tutti i suoi vicini. Query arbitrariamente complesse pertanto possono essere facilmente sostenute su tali sistemi. Anche se questo approccio è semplice e robusto, comporta degli enormi costi dovuti al flooding della rete ogni volta che una query viene inoltrata. Sono stati studiati miglioramenti del meccanismo usato da Gnutella: random walk, ricerca guidata, e l'organizzazione di nodi con contenuti simili in segmenti o gruppi.


Random WalkRandom Walk

E' utilizzato per affrontare il problema della scalabilità posto dal flooding su sistemi P2P non strutturati come Gnutella. Data una query, un random walk è essenzialmente una ricerca random in cui ad ogni passo la query è trasmessa ad un nodo scelto in modo casuale, senza prendere in considerazione suggerimenti di come probabilmente il prossimo nodo avrà risposte per la query. Due tecniche sono state proposte per porre fine al random walk: TTL (time-to-live) e "controllo". TTL significa che, come accadeva nel flooding, ogni random walk termina dopo un certo numero di salti, mentre il "controllo" si intende un walker controllato periodicamente dal nodo che ha prodotto la query prima di essere trasmesso al prossimo nodo.


Ricerca guidataRicerca guidata

La ricerca guidata rappresenta la tecnica di ricerca che permette di trasmettere ai nodi vicini le query che hanno maggiori probabilità di avere risposte, invece di inoltrare le query ai vicini scelti casualmente o di intasare la rete con le query da trasmettere. Si hanno tre schemi RI (routing indices): il composto, il count-hop e l'indice di routing esponenziale. L'idea di base della ricerca guidata è un meccanismo di indici distribuiti che mantiene un riferimento a ciascun nodo. Questi indici distribuiti sono piccoli e danno informazioni relativi alla "direzione" da prendere per giungere al documento, piuttosto che la sua effettiva ubicazione. Data una query, il routing indices di un nodo consente di selezionare i "migliori" vicini a cui inviare una query. Un RI è una struttura dati che, data una query, restituisce un elenco di vicini, classificati in base alla loro bontà per la query. La nozione di bontà generalmente riflette il numero dei documenti rilevanti in un nodo "vicino".


Ricerca basata su gruppi aventi Ricerca basata su gruppi aventi contenuti simili (parte 1)contenuti simili (parte 1)

L'idea di base dei gruppi di ricerca di contenuto analogo è quello di organizzare i nodi contenenti simili documenti in gruppi su sistemi P2P non strutturati come Gnutella. L'intuizione alla base di questa tecnica di ricerca è che i nodi all'interno di un gruppo tendono ad essere rilevanti per la stessa query. Di conseguenza, questa tecnica di ricerca guida la query per i nodi che hanno più probabilità di avere le risposte alla domanda, evitando in tal modo una notevole quantità di inondazioni. La ricerca in SETS, si avvale di un modello di ricerca guidato dal protocollo di routing su un sistema segmentato sovrapposto alla rete costruita da Gnutella.


Ricerca basata su gruppi aventi Ricerca basata su gruppi aventi contenuti simili (parte 2)contenuti simili (parte 2)

Il sistema è costruito ragruppando dei nodi in cluster, e per ogni cluster corrisponde un argomento. Pertanto,si creano partizioni di nodi in argomenti, in modo che i nodi con documenti simili appartenenti allo stesso segmento. Data una query, prima si calcola l'argomento R, si scelgono i segmenti che sono più rilevanti per la query e quindi si esegue la ricerca di questi documenti. Tuttavia, il nodo designato è potenzialmente un punto di fallimento ed anche un collo di bottiglia . Si organizzano i nodi utilizzando dei predicati associativi. Una regola guida è un insieme di nodi che soddisfano alcuni predicati; ogni nodo può appartenere a una serie di regole guida, e per ciascuna regola guida a cui partecipa in esso mantiene un piccolo elenco di altri nodi appartenenti alla stessa guida regola. L'idea chiave delle regole guide è che i nodi appartenenti ad una di esse devono contenere dati simili. Di conseguenza, la ricerca guidata limita la propagazione di query all'interno di alcune regole-guida specificate, invece di inondare tutta la rete.


Ricerca in sistemi P2P strutturatiRicerca in sistemi P2P strutturati

Dopo la prima generazione di sistemi P2P come KaZaA e Gnutella, sistemi P2P strutturati (o DHT-based), la seconda generazione di sistemi P2P, è stata proposta per fornire scalabilità a quei sistemi P2P Gnutella-based. Tali sistemi DHT-based data una chiave, possono individuare il corrispondente documento con solo O (log N) salti (N è il numero dei nodi del sistema). In sistemi P2P strutturati, la replica è stata sfruttata per migliorare la disponibilità dei dati e l'efficienza della ricerca. E' stato proposto un algoritmo probabilistico per migliorare la posizione di latenza esistente nei sistemi che fanno uso di una DHT, se la replica di un documento richiesto esiste vicino alla fonte della query. Una struttura ad indici distribuiti è costruita su ciascun nodo. Comunque, sostenere query complesse, come la ricerca di parole chiave e semantica del contenuto / ricerca su DHT è un compito non banale.


Ricerca tramite parola chiave Ricerca tramite parola chiave (parte 1)(parte 1)

Nella ricerca di parole chiave, una query contiene una o più parole chiave (o le condizioni) e il sistema di ricerca restituisce una serie di documenti che contengono tutte le parole chiave richieste per la query. Fondamentalmente, sono state proposte tre strutture di indicizzazione a sostegno dei sistemi P2P strutturati che fanno uso della ricerca tramite parole chiave: indicizzazione globale, indicizzazione ibrida, indicizzazione ibrida ottimizzata. Nella indicizzazione globale, il sistema nel suo insieme mantiene un indice invertito dei documenti che contengono il termine ricercato. Ogni nodo memorizza l'elenco invertito completo di questi termini che sono mappati nella sua DHT tramite un identificatore. Per rispondere a una query contenente più termini, la query viene instradato ai nodi responsabili di tali termini. A questo punto si individuano i documenti che sono costituiti da tutti i termini richiesti. Anche se l'indicizzazione globale comporta solo un piccolo numero di nodi per una query di ricerca, ha l'inconveniente di richiedere la comunicazione tra più nodi.



Il costo della comunicazione cresce proporzionalmente con la lunghezza della lista. Nell'indicizzazione ibrida, ogni nodo mantiene l'elenco completo di tali termini mappato nella sua DHT. In aggiunta, per ogni documento nella lista invertita per alcuni termini t, il nodo mantiene inoltre la lista completa dei documenti che si riferiscono a tali termini. Dato un documento e più parole chiave di ricerca, la query viene instradato a nodi responsabili di tali termini. Ognuno di questi nodi esegue una ricerca locale senza contattare gli altri, poiché essi hanno la lista completa per ciascun documento nei rispettivi elenchi. Questa indicizzazione ibrida aumenta l'efficienza di ricerca al costo di pubblicare più meta-dati.



Per diminuire i costi associati all'indicizzazione ibrida, fu proposto un sistema di indicizzazione ibrida ottimizzato. L'idea di base dietro tale sistema è che i meta-dati di un documento sono pubblicati solo per alcuni termini, piuttosto che per tutti i suoi termini. Ad esempio, un documento contenente D termini pubblica la sua lista solo per il termine responsabile in una query. Dato che conoscendo, la locazione di tali termini è ancora possibile determinare il documento che è la risposta completa alla query. Tuttavia, i risultati della ricerca possono essere non ottimali. Fu proposto di adottare tecniche di espansione automatica della query per affrontare questo problema.


Ricerca semanticaRicerca semantica

La ricerca semantica è basata su un contenuto di ricerca costituito da solo testo, le query sono espresse in linguaggio naturale. Quando una query è rilasciata da un utente, una rappresentazione della query è derivata dal suo testo integrale, abstract, o titolo, e poi presentata al sistema di recupero delle informazioni. La ricerca semantica presenta un impegnativo problema per i sistemi P2P strutturati: data una query, il sistema di ricerca deve o avere un gran numero di nodi o perdere alcuni documenti rilevanti. Sono stati proposti alcuni sistemi di ricerca semantica posti in cima ai sistemi P2P strutturati. Una caratteristica importante di tali sistemi di ricerca è di estendere gli algoritmi come Vector Space Model (VSM) e Latent Semantic Indexing (LSI), in ambiente P2P. La sovrapposizione semantica è una logica di rete in cui i documenti sono organizzati in vettori in modo che la distanza tra due documenti è proporzionale alla loro differenza semantica.


Semantic Overlay Network Semantic Overlay Network ( SON)( SON)

In generale il sistema prevede che le query siano instradate verso

un adatto SONs, incrementando le possibilità che il servizio

ricercato sia ritrovato velocemente e riducendo il carico relativo

alla ricerca ai soli nodi contenenti il servizio. E' un'organizzazione

della rete di tipo flessibile che migliora le performance relative

alle query mantenendo un alto grado di autonomia del nodo. I

nodi sono connessi tra loro in base alla somiglianza tra i loro

contenuti a livello semantico.


Costruzione di una Semantic Costruzione di una Semantic Overlay NetworkOverlay Network

● Valutazione della potenziale gerarchia di classificazione usando la distribuzione attuale dei dati nei nodi, trovando una buona gerarchia;

● decidere se questa gerarchia va posta (salvata) in ogni nodo o solo in alcuni.

Ogni nodo che si unisce al sistema deve:● mandare un pacchetto in flooding nella rete per ottenere la gerarchia

adottata;● avviare un classificatore di documenti basato sulla gerarchia

ottenuta, classificando tutti i propri documenti;● essere assegnato ad uno specifico SON.

Si possono usare due meccanismi per propagare le informazioni su tutta la rete:● flooding;● adozione di super peer.


Gerarchia di classificazioneGerarchia di classificazione

Una buona gerarchia di classificazione è quella che :

● produce un insieme di documenti che appartengono ad un piccolo numero di nodi;

● produce dei nodi che hanno un numero sufficientemente piccolo di insiemi di documenti;

● permette la facile implementazione di algoritmi di classificazione che commettono un basso numero di errori.


Vantaggi nell'adozione di SONVantaggi nell'adozione di SON

● Alta percentuale di richiamo con solo 1/5 dei messaggi necessari agli altri approcci ( Gnutella);

● facilità nel trovare anche servizi poco richiesti;

● autonomia dei nodi;● alta scalabilità.


Svantaggi nell'adozione di SONSvantaggi nell'adozione di SON

● Non si raggiunge in alcun caso il 100% di richiamo;

● difficoltà nella precisa classificazione dei nodi in maniera automatica;

● difficoltà nella precisa classificazione delle query.


Skip GraphsSkip GraphsDescrizione struttura dati (parte 1)

L'approccio dell'algoritmo è quello di sfruttare la struttura di base ad albero per garantire certe funzionalità, mentre l'applicazione di un semplice sistema di bilanciamento di tipo distribuito serve a preservare l'equilibrio e la distribuzione del carico. E' un nuovo modello per una rete peer-to-peer basato su una struttura di dati distribuiti che viene detta skip graphs. Questa struttura dati distribuita dispone di diversi vantaggi: posizione dinamica delle risorse l'inoltro del nodo e la cancellazione può essere effettuata in tempo logaritmico, e ogni nodo in un skip graphs richiede soltanto lo spazio per memorizzare le informazioni sui suoi vicini. Questo può essere utile per alcune applicazioni come il prefetching di pagine web poiché rafforza la navigazione, la ricerca e l'efficienza. Vi è stato un certo interesse nel sostenere le query complesse in sistemi peer-to-peer. Skip graphs è resistente al fallimento dei nodi: uno skip graphs tollera la rimozione di una grande frazione dei suoi nodi scelti in modo casuale senza creare problemi alla rete. Skip graphs può essere costruito anche senza la conoscenza del numero complessivo di nodi in anticipo. Al contrario, sistemi come Pastry e Chord richiedono la conoscenza a priori della dimensione del sistema. I sistemi skip graphs non hanno bisogno di conoscere la dimensione del keyspace in anticipo.



Una skip list è una struttura dati ad albero randomizzata ed equilibrata, organizzata come una torre di liste collegate. Il livello 0 di una skip list è una lista di tutti i nodi in ordine crescente di chiave. Per ogni i superiore a 0, ogni nodo di livello i - 1 appare in modo indipendente al livello i fissato. In una skip list doppiamente legata, ogni nodo memorizza un puntatore predecessore e un puntatore successore per ogni elenco in cui appare, per una media di 1-p puntatori per nodo. Le liste, al livello superiore agiscono come "corsie di passaggio rapido" che consentono di ottenere la sequenza di nodi da attraversare rapidamente. La ricerca di un nodo, con una particolare chiave di ricerca coinvolge prima il livello più alto, fino a scendere la livello in cui il nodo si trova.



Considerando il percorso di ricerca in senso inverso si ha che non più di 1-p nodi sono posti in media per ogni livello. Una skip list da sola non è sufficiente per un sistema P2P scalabile e robusto, in quanto è priva di ridondanza e quindi è vulnerabile a fallimenti e congestione. Poiché solo pochi nodi appaiono nella lista di più alto livello, ciascuno di tali nodi agisce come un unico punto di fallimento, e costituisce un "hot spot" che deve elaborare una frazione costante di tutte le operazioni di ricerca. Le skip list offrono anche alcune garanzie: i singoli nodi non sono separati dal resto anche con guasti casuali. Dal momento che ogni nodo è collegato, in media, a solo O (1) altri nodi, anche una costante probabilità di fallimenti farà isolare una grande frazione di nodi sopravvissuti. La soluzione è quella di definire una generalizzazione di una lista chiamata skip graphs. Come in una skip list, ciascuno degli n nodi in un skip graphs è un membro di più liste collegate. Il livello 0 della lista consiste di tutti i nodi in sequenza. Uno skip graphs supporta la ricerca, l'inserirmento, la cancellazione e operazioni analoghe a quelle delle liste. Perché ci sono molte liste ad ogni livello, la possibilità che ogni singolo nodo partecipa in alcune ricerche è piccola, ciò elimina i singoli punti di guasto. Inoltre, ogni nodo ha Θ (log n) vicini di casa, in media, e con elevata probabilità nessun nodo è isolato.


Skip GraphsSkip GraphsAlgoritmo (parte 1)

In una reale attuazione in un sistema P2P che utilizza uno skip graph, ogni nodo di tale struttura sarà una risorsa. Le risorse sono ordinate in ordine crescente lessicografico delle loro chiavi. La mappatura di queste chiavi può essere fatta in due modi: o ogni macchina è responsabile per le risorse che essa ospita o si utilizza un approccio che fa uso di una DHT. Il primo approccio dà sicurezza e gestibilità, mentre il secondo dà buon bilanciamento del carico. Ogni nodo in uno skip graphs memorizza l'indirizzo e la chiave del suo successore e predecessore, a ciascuno dei O (log n) livelli. Inoltre, ogni nodo ha bisogno anche di O (log n) bit di spazio per la sua adesione al vettore. In entrambi gli approcci di cui sopra, con n risorse in rete, ogni macchina deve mantenere O (log n) collegamenti per ogni risorsa che ospita, per un totale di O (n log n) collegamenti in tutta la rete. Questi fattori possono portare ad alto traffico di messaggi se ogni macchina periodicamente deve controllare se i suoi legami sono funzionali, come è comune in molte implementazioni P2P. Re-recentemente, una nuova struttura di dati chiamata albero è stata introdotta. Essa supera queste limitazioni. Un albero utilizza un numero costante di puntatori per nodo. Un tema centrale per l'attuazione di un grafico è la gestione delle liste.


Skip GraphsSkip GraphsAlgoritmo (parte 2)

La costruzione, l'inserimento in nuovi nodi, e la ricerca in uno skip graphs può essere fatta utilizzando semplici algoritmi. Gli skip graphs sono molto resistenti, tollerano una grande frazione di fallimento dei nodi senza perdere la connettività. Utilizzando il meccanismo di riparazione, l'interruzione della struttura può essere riparata in assenza di altri difetti. Rimane una questione da affrontare: il gran numero di puntatori per macchina nel sistema. Sarebbe interessante per la progettazione di un sistema peer-to-peer che si mantenesse un minor numero di puntatori possibile per macchina. Sarebbe interessante studiare le prestazioni in questa direzione, magari utilizzando degli skip graphs multidimensionali. Come con altri overlay network, sarebbe interessante vedere come la rete funziona in presenza di guasti. Infine, sarebbe utile sviluppare un meccanismo autonomo di stabilizzazione e riparazione.


WSPDSWSPDSDescrizione generale (parte 1)

Servizio di discovery decentralizzato basato su una architettura Peer-to-peer non strutturata (Gnutella). I vari serventi collaborano nella risoluzione delle query, il servizio di discovery, quindi, può essere visto come un servizio cooperativo. Vengono utilizzati, per descrivere i servizi, WSDL (per l'analisi dei parametri di input/output tramite sintassi description:location) e, come già detto, WSIL (per i metadati aggiunti e la ricerca basata su name/abstract). Viene utilizzato un sistema di flooding detto probabilistico basato sul sistema QDN (Query Data Network); ogni servente viene descritto in base ai servizi che offre ed inoltre, ogni volta che un servente si ritrova a dover fare il forward di una query esso la inoltra solo ai serventi suoi vicini aventi identità simile alla descrizione fornita tramite query.


WSPDSWSPDSDescrizione generale (parte 2)

Nel set-up della rete, quindi, ogni servente non tiene memoria di tutti i suoi vicini (sarebbe inutile), ma solo di quelli aventi descrizione semantica simile alla sua. Durante la ricerca delle query si tiene conto anche di meccanismi di sussunzione.Si può osservare come ogni servente sia composto da due motori:

● Motore di comunicazione;

● local query.


WSPDSWSPDSMotore di comunicazione (parte 1)

Responsabile di ricevere le query degli utenti trasformandole in local query e global query unendo i risultati e fornendo una risposta all'utente. In grado, inoltre, di ricevere le query dai propri vicini, risolverle localmente e fornire risposta al richiedente. Si occupa del forwarding dei messaggi nella rete. Per la comunicazione vengono utilizzati messaggi basati su SOAP. Il sistema Gnutella è stato migliorato utilizzando una tecnica detta probabilistic flooding. Il set-up della rete avviene tramite un sistema di caching; ogni servente mantiene una cache dei peer che ha recentemente osservato come attivi. Tale cache viene utilizzata dal servente ogni volta che il servente verrà riattivato e dovrà valutare i propri vicini.


WSPDSWSPDSMotore di comunicazione (parte 2)

La prima volta che un servente viene attivato può sfruttare la conoscenza di peer che forniscono servizi d'uso generale e che sono praticamente sempre attivi. I serventi valutano periodicamente i propri vicini utilizzando il classico sistema implementato da Gnutella (ping-pong). La ricerca avviene tramite un sistema di forwarding dei messaggi nella rete. Quando un peer riceve una query, inoltra la stessa ai propri vicini; esso esegue, inoltre, una query locale per verificare se esso stesso possiede il servizio ed in caso positivo restituisce una risposta al richiedente. Il messaggio è marcato tramite un campo TTL.


WSPDSWSPDSLocal query

Riceve le query dal motore di comunicazione, esegue una ricerca locale e passa nuovamente i risultati al motore di comunicazione. Sfrutta le specifiche WSIL per trovare servizi locali corrispondenti alle query ricevute. Il file WSIL fornisce per ogni servizio dei metadati che verranno utilizzati dal parser per il discovery del serivizio. Secondo lo standard WSIL possono essere anche specificate le features che nel futuro il servizio implementerà.


HyperCubeHyperCubeDescrizione generale (parte 1)

La rete è strutturata mediante l'utilizzo di un ipercubo i cui vertici sono i nodi della rete stessa. Il diametro della rete è definito come la massima distanza fra due nodi nella struttura. La struttura è simmetrica e nessun nodo ha posizione di maggior rilievo rispetto agli altri. La distanza fra due nodi vicini è marcata da un indice di distanza. I messaggi vengono inviati tramite un sistema broadcast a distanza predefinita (diametro della rete), ossia il nodo che invia il messaggio predetermina la distanza massima ed invia il messaggio a tutti i suoi vicini. Il messaggio sarà taggato con un indice rappresentante la distanza fra il nodo che invia il messaggio e quello che lo riceve. Ogni nodo ricevuto il messaggio valutera d=diam-t ove diam è il diametro della rete e t è il valore del tag sul messaggio. d rappresenta la distanza massima verso cui il messaggio possa essere inoltrato; esso sarà, quindi, inviato a tutti i vicini a distanza minore o uguale a d. Il sistema di broadcast può anche essere ristretto a dei sub-ipercubi.



Quando un nuovo peer entra nella rete esso può essere innestato al posto di un peer attualmente presente che verrà quindi spostato di posizione (il nuovo peer occuperà la posizione più adatta alla sua posizione semantica rispetto agli altri); nel momento in cui un peer invece esca dalla rete, un altro peer presente occuperà il suo posto. Una struttura simile è assicurata dal fatto che un peer può essere connesso più volte ad un altro nella struttura dell'ipercubo (anche con distanze differenti) e un peer può occupare una posizione anche solo temporaneamente in attesa di ingressi futuri. Un simile algoritmo (ricorsivo) presenta complessità logaritmica. Possiamo utilizzare topologie di rete differenti dall'ipercubo; lo stesso appartiene ad una classe di grafi detta di Cayley. Un grafo di Cayley che assicura migliori prestazioni in termini di scalabilità di numero di peer (complessità sottologaritmica).



La struttura della rete è organizzata semanticamente in modo che i peer siano raggruppati in strutture dette Cluster che sono assegnate a specifiche combinazioni logiche di concetti ontologici. Ogni cluster presenta una struttura ad ipercubo o a stella e tutti i cluster sono tenuti insieme mediante una struttura ad ipercubo o a stella i cui nodi sono rappresentati dai cluster. Lo schema di indirizzi concatena un set di concept coordinates ed un set di storage coordinate. Le concept coordinates permettono di identificare un cluster nell'ipercubo esterno. Le storage coordinates permettono, invece, di indicizzare i peer all'interno di un cluster. La concatenazione di concept coordiates e di storage coordinates rappresenta l'indirizzo logico del peer.



Il sistema di invio delle query consiste di due momenti; dapprima, la query è inviata al cluster ove si ipotizza che si trovi un peer che fornisce il servizio richiesto e poi si utilizza un invio broadcast a tutti i peer del cluster. Una query, prima di essere inviata, viene ridotta ai suoi mintermini (ossia elementi di base della query; ad esempio la query E A D ∨ ∧consiste nei mintermini E ed A D). Si osserva a quale ∧gruppi potrebbe essere indirizzata la query; ogni mintermine rappresenta un gruppo di concept cluster nella rete. La query è inoltrata al gruppo cosicché possa essere inviata in broadcast a tutti membri del gruppo. Una volta che la query raggiunga un peer, questo ha la possibilità di rispondere alla stessa (ad esempio contattando il richiedente).



I peer possono entrare a far parte della struttura contattando altri peer. La descrizione semantica dei servizi offerti dal peer sarà utile per poterlo assegnare ad un dominio. Se il peer descrive se stesso tramite concetti non specifici di nessun gruppo esso sarà inserito all'interno del gruppo (comunque) più specifico. Determinato il gruppo di appartenenza di un peer, sarà inviato in broadcast un messaggio a tutti i peer del gruppo affinché essi lo inseriscano nelle loro tabelle di routing. È desiderabile utilizzare un algoritmo in grado di valutare automaticamente se è il caso di realizzare un nuovo gruppo (ciò non è stato ancora realizzato, i gruppi sono attualmente preimposti).


pSearchpSearchOrganizzazione dell'overlay semantico

I peer sono organizzati in semantic overlay che formano i pSearch Engine all'interno dei quali i nodi hanno funzioni omogenee. Non tutti i nodi nella struttura devono far parte dell'engine ma verranno utilizzati solo quelli stabilmente connessi (il tutto rimane comunque dinamico) ogni componente dell'engine si occuperà dell'indirizzamento in un proprio sottoinsieme di vicini. pSearch utilizza una rete CAN per organizzare i nodi di engine l'algoritmo è detto pLSI. Il pLSI impone che la dimensione della rete CAN sia pari a quella dello spazio semantico LSI. La chiave identificativa nella rete di un documento sarà pari al suo vettore semantico. Allorquando venisse ricevuta una query, essa sarà instradata usando il suo vettore semantico. Qualunque nodo dell'engine confronterà il vettore semantico della query con il proprio e quello dei propri vicini.


pSearchpSearchSvantaggi

Esistono vari problemi dovuti all'utilizzo di un simile approccio:

● pLSI setta la dimensione della CAN ad un numero di nodi pari allo spazio semantico LSI, tuttavia la dimensione massima per la CAN è notevolmente più ridotta;

● l'utilizzo di vettori semantici come chiavi per la CAN risulta sbilanciare la struttura della rete stessa;

● risulta difficile limitare la ricerca a spazi ridotti di molte dimensioni.


pSearchpSearchRolling Index

Per risolvere le query più velocemente pSearch utilizza un metodo detto Rolling Index. Dato un vettore semantico esso viene ricombinato un certo numero di volte così da creare dei rotated semantic vectors. I vettori “ruotati” di documenti diversi generati con lo stesso numero di rotazioni formano un rotated space all'interno del quale possono essere effettuate ricerche (essendo il matching indipendente dalla posizione degli elementi nel vettore). In questo modo, sacrifichiamo spazio in memoria ma ottimizziamo le ricerche. Per occupare meno spazio, i vettori rotati vengono suddivisi in sottovettori; si dimostra come la ricerca non risenta di questo accorgimento. La ricerca globale migliora di molto tramite l'utilizzo del Rolling Index tuttavia, non si notano grandi miglioramenti nella ricerca di singoli documenti; per risolvere tale difetto si utilizzerà una cosiddetta selective rotation tramite la quale, oltre che memorizzare l'indice del documento nei suoi rotated spaces lo memorizzeremo anche nei rotated spaces dei suoi sottovettori.


pSearchpSearchBilanciamento del carico

Al fine di bilanciare il carico di rete, all'ingresso di un nuovo peer nella stessa, il vettore che lo rappresenta viene ruotato un numero casuale di volte e tale vettore è usato come punto attraverso il quale inizia il routing; tale processo è detto content-aware node bootstrapping. Per ridurre lo spazio di ricerca si suppone che i vari nodi formino, attorno ad essi, dei cluster di nodi trattanti argomenti semanticamente simili (se si trova un documento rilevante, in prossimità di esso vi saranno risultati simili. Vengono utilizzati sistemi di euristica). La ricerca avverrà, quindi, in sottoinsiemi formati dai cluster.

Algoritmi E P2P

Technology

Transcript of Algoritmi E P2P