Architetture di service discovery

Le architetture di service discovery si distinguono in: (i) directory-less architecture e (ii) directory-based architecture. Una directory `e un’entit`a che memorizza le informa- zioni sui servizi disponibili nella rete, detti service description, in modo da permettere la ricerca dei servizi e la loro invocazione. Nelle MSN sono usati diversi formalismi (lin- guaggi) per descrivere le propriet`a di un servizio: un esempio `e la coppia chiave-valore, dove la chiave indica l’attributo, oppure attraverso una descrizione XML.

La distinzione sulle architetture si basa su come vengono diffuse le informazioni riguar- danti i servizi:

• Directory-based : Con questa architettura si assume l’esistenza della directory il cui ruolo `e quello di facilitare la comunicazione tra il service provider e il service client, Figura 2.12, in particolare si occupa di:

– Memorizzare i service description.

– Gestire gli advertisement forniti dai dispositivi.

– Gestire le query che riceve dai dispositivi che stanno cercando un servizio. Se la query corrisponde con uno o pi`u advertisement allora la directory risponde con l’advertisement corrispondente.

La directory pu`o essere implementata in diversi modi, a tal proposito possiamo

identificare un’ulteriore classificazione dell’architettura directory-based:

– Centralizzata: Con questa architettura esiste un unico dispositivo che fa da directory e memorizza le informazioni su tutti i servizi disponibili nella rete. Tutti gli altri dispositivi sono a conoscenza del dispositivo-directory. I service provider pubblicizzano i propri servizi alla directory centrale con un messag- gio unicast, mentre i service client prima contattano la directory per ottenere le informazioni sul servizio, successivamente sulla base del service description ottenuto interagiscono con il provider. La tecnica centralizzata non `e una buo- na soluzione per le MSN in cui un nodo potrebbe non essere raggiungibile in un determinato istante, per altro individuiamo diversi problemi in quanto ab- biamo un singolo punto critico che in caso di guasto non sar`a pi`u in condizioni di gestire i messaggi e i dispositivi non potranno pi`u condividere e ricercare i servizi, inoltre non `e scalabile in quanto un singolo dispositivo non `e in con- dizioni di gestire un gran numero di messaggi che viaggiano all’interno di una MSN.

– Distribuita: Con questa architettura esistono pi`u dispositivi che fanno da di- rectory e comunicano costantemente tra loro per distribuirsi gli advertisement. Le directory distribuite sono pi`u adatte e vengono implementate configurando in modo statico i dispositivi che implementano la directory oppure dinamica- mente eleggendo i dispositivi che soddisfano una determinata metrica. A sua volta possiamo distinguerla in:

∗ Infrastructure-less: Con questa architettura non si assume l’esistenza di alcuna infrastruttura e le directory vengono selezionate dinamicamente

tra i nodi che hanno una capacit`a sufficiente come batteria, memoria,

in pi`u nella rete in quanto si vuole selezionare una directory che si adatti bene alla topologia variabile della rete e si vuole informare tutti gli altri nodi sulla sua identit`a.

∗ Infrastructure-based : Questa architettura `e caratterizzata dalla presenza di pi`u reti separate e connesse tra loro mediante una rete fissa dotata di un’infrastruttura contenente la directory. Un service client che necessita di un servizio contenuto in un’altra rete vi si connette indirettamente at- traverso la rete fissa. Questa architettura assume che l’ambiente contenga pi`u di un milione di nodi in questo modo si riducono i costi di calcolo e il sovraccarico di memoria.

E’ importante notare che gli approcci basati sull’esistenza di una directory impli-

cano pi`u costi di comunicazione per mantenere la directory e per supportare lo

scambio di dati tra quest’ultimo e gli altri nodi

Service

client

providerService

Directory

Figura 2.12: Architettura basata sulla directory

• Directory-less : Con questa architettura non esiste alcuna directory, Figura 2.13, quindi tutti i dispositivi provvederanno a registrare i service description localmen- te. Quando un dispositivo riceve una query, controlla se esiste un advertisement memorizzato nella propria cache che pu`o rispondere alla richiesta confrontando i service description, in caso affermativo invia il servizio altrimenti propaga la query a determinati nodi. Allo stesso modo un dispositivo che vuole pubblicizzare i propri servizi diffonde gli advertisement nella rete usando le strategie viste in precedenza nella fase di advertisement. Questa tipologia viene preferita nelle MSN in quan- to permette di evitare ulteriori comunicazioni costose nella rete come l’eccessiva

comunicazione tra la directory e il service client/provider. L’unico problema che deve essere affrontato `e determinare la frequenza con cui i nodi pubblicizzano i propri servizi, in modo tale da ridurre il carico nella rete ed evitare trasmissioni ridondanti.

Service

client

providerService

Service request Service reply

Figura 2.13: Architettura senza la directory

• Ibrida : Questa architettura `e una combinazione delle due architetture in cui esiste una directory, ma se un nodo che richiede un servizio non riceve risposta dalla directory allora propaga la query nella rete.

CAPITOLO

3

CORDIAL: COllaborative seRvice DIscovery

ALgorithm

CORDIAL, COllaborative seRvice DIscovery ALgorithm [8], `e un protocollo per la

ricerca dei servizi all’interno di una MSN distribuita (in cui non si sfrutta alcuna infra- struttura di rete stabile) e dotata di un’architettura “directory-less” che trae vantaggio dalle caratteristiche sociali del comportamento umano, una tra le pi`u importanti `e la mobilit`a degli individui che permette di creare le opportunit`a di comunicazione. Le per- sone si muovono a seconda degli obbiettivi e delle attivit`a derivanti dalle loro relazioni sociali, possiamo quindi individuare tre aspetti chiave che caratterizzano il modo in cui si muove un individuo : (i) la mobilit`a `e determinata dalla sua relazione sociale, per esempio le persone che hanno molte conoscenze all’interno di una grande area urbana tendono a muoversi con maggiore frequenza rispetto alle persone pi`u solitarie. (ii) Il numero dei luoghi visitati `e limitato (si va a lavoro, al supermercato, in ufficio), (iii) le persone tendono a viaggiare per percorsi brevi anzich´e per percorsi pi`u lunghi. Un’ altra caratteristica molto importante `e la condivisione degli interessi, strettamente correlata alla mobilit`a degli utenti in quanto le persone che condividono alcuni interessi tendono a frequentare gli stessi luoghi, le stesse persone, a svolgere attivit`a comuni, e

di conseguenza tendono a incontrarsi spesso e per tempi pi`u lunghi formando comu-

nit`a. Per esempio guardando la Figura 3.1[4], Alice, rappresentata con un cerchio nero, durante il giorno entra a far parte di tre comunit`a diverse, rappresentate con un cerchio bianco, i colleghi di lavoro in ufficio con cui condivide interessi nell’attivit`a lavorativa, gli amici incontrati al pub con cui condivide interessi riguardo hobby/attivit`a preferite come il calcio o andare a ballare, e la famiglia a casa con cui condivide interessi per eventi ricreativi come guardare programmi in Tv. In alcuni momenti Alice `e in grado di comunicare con alcuni di loro (linee dirette) e in altri no (mancanza di linee) in quanto

non sono abbastanza vicini per garantire una comunicazione e scambiare informazioni.

Figura 3.1: Esempio della formazione di comunit`a a seguito della mobilit`a di un

individuo [4]

In CORDIAL ogni nodo sfrutta la propria mobilit`a e quella degli altri per diffondere messaggi (query o advertisement) in quanto possono non esistere cammini diretti tra il nodo sorgente e il nodo destinatario, quindi ogni nodo intermedio collabora inoltrando i messaggi nella rete secondo il modello store, carry and forward. Inoltre l’algoritmo sfrutta le caratteristiche sociali dei nodi per implementate efficienti politiche di ricerca e pubblicazione dei servizi mediante la diffusione nella rete di messaggi.

I prossimi paragrafi introducono alcune nozioni base e mostrano nel dettaglio le fasi principali dell’algoritmo CORDIAL e i loro obiettivi.

La fase di selezione e quella di accesso sono fuori dagli scopi di questa tesi e quindi non verranno descritte.

3.1

Concetti preliminari

La rete e le comunit`a

Rappresentiamo una MSN come un grafo non orientato al tempo t: Gt = (V, Et) in

cui V = {n1, ...nv} `e l’insieme dei nodi e Et = {eij = (ni, nj) : ni, nj ∈ V } `e l’insieme

comunicazione a una via tipica delle reti opportunistiche. Le principali strutture che individuiamo sono:

• Neighborhood [Ni

t]: Questa struttura contiene tutti i nodi che comunicano con

ni al tempo t, in particolare contiene nj ∈ V tale che eij ∈ Et.

• Contact-history [Ti_{]: Questa struttura contiene i nodi che entrano in contatto}

con ni nel tempo. Un record di tale tabella contiene:

– ID del nodo incontrato;

– l’ultima volta che `e stato incontrato; – il tempo medio tra due incontri successivi.

• Comunit`a [C]: Questa struttura `e un sottoinsieme di Ni

t contenente ni e tutti

i nodi che sono entrati in contatto con lui i quali soddisfano determinati criteri stabiliti da un algoritmo di community detection.

Ricerca dei servizi

Come abbiamo accennato le fasi principali su cui ci focalizzeremo sono la pubblicazione e la richiesta dei servizi, le principali strutture che caratterizzano queste fasi sono:

• Interessi [I]: Questa struttura contiene tutti gli interessi che modellano i possi- bili topic a cui gli utenti di una MSN possono essere affiliati, come per esempio “sport”,“videogiochi”, “cronaca” o “spettacolo”. Tale insieme rappresenta quindi una tassonomia degli interessi possibili delle MSN.

• Service advertisement [advj]: Questa struttura `e memorizzata all’interno della

service cache CH dei nodi. Un advertisement descrive le caratteristiche pi`u im-

portanti di un servizio come per esempio l’identificatore del provider, gli interessi associati, le informazioni relative alla qualit`a ed alle performance e i parametri necessari per l’invocazione.

• Service query [q]: Questa struttura contiene un’insieme di caratteristiche che descrivono il tipo di servizio richiesto dal client, come per esempio il tipo di fun- zionalit`a che il client necessita e altre caratteristiche che richiedono determinate performance.

• Pending query [P Qi]: Questa struttura contiene tutte le query generate da ni che

non hanno ancora ricevuto risposta, pi`u precisamente non `e stato ancora trovato un advertisement corrispondente. Oltre alla query appartenente a ni conterr`a anche

quelle appartenente ad altri nodi, vedremo quali quando descriveremo le fasi di CORDIAL.

• ForwardingCache: Questa struttura contiene gli advertisement da inoltrare al destinatario finale.

Una nozione molto importante `e quella di coefficiente di similarit`a di Jaccard che verr`a utilizzato in particolare per confrontare una query con un advertisement corrisponden- te. L’indice di Jaccard J ∈ [0, 1] tra una query q e un advertisement advjviene calcolato

sull’insieme degli interessi che li compongono ed `e definito come:

J (q, advj) =

|q ∩ advj|

|q ∪ advj|

Un advertisement corrisponde a una query se J (q, advj) ≥ τ per una data soglia di

similarit`a 0 ≤ τ ≤ 1.