IL LIVELLO MIDDLEWARE

Capitolo 3

IL LIVELLO MIDDLEWARE

I protocolli per una rete di calcolatori sono organizzati secondo una gerarchia (pila dei protocolli), schematizzata in gura 3.1. A partire dal livello MAC/Physical, in cui si gestiscono i problemi di interazione hardware- software, piu si sale nelle gerarchia e piu aumenta il livello di astrazione dei servizi oerti dai vari protocolli. Ogni protocollo si appoggia sui protocolli di livello piu basso per fornire dei servizi di qualita superiore.

Figura 3.1: Pila di protocolli

In particolare, i protocolli di livello middleware si collocano tra il

livello trasporto e quello applicativo allo scopo di realizzare, basandosi sulle

funzionalita di rete di base, servizi di piu alto livello che semplichino lo sviluppo delle applicazioni.

Attraverso le soluzioni middleware si riesce ad orire un servizio di alto livello per gli utenti ed un elevato livello di astrazione per i programmatori, semplicando inoltre la manutenzione, la stesura e l'integrazione delle applicazioni sviluppate.

Il livello middleware consente di svincolare il programmatore dal dover gestire tutta una serie di dettagli sulla comunicazione tra i nodi e sull'interazione locale tra hardware e software, orendogli delle astrazioni di piu alto livello.

Attualmente, nello sviluppo di molti sistemi mobili ad hoc, non si fa uso di alcun livello middleware, lasciando a ciascuna applicazione il compito di gestire i servizi di cui necessita. La ricerca sulle soluzioni middleware in ambiente MANET e ancora in fase di sviluppo. I principali protocolli di livello middleware esistenti sono stati progettati per reti cablate o per ambienti mobili dotati comunque di una infrastruttura statica cui fare riferimento. Tutto questo rende lo sviluppo delle applicazioni in ambiente MANET molto piu complicato di quanto non lo sia per le architetture dotate di protocolli di livello middleware adabili.

Il livello middleware deve semplicare la realizzazione di determinati servizi, spesso essenziali per le applicazioni che dovranno operare nella rete.

Un ruolo particolarmente importante e occupato da tutti i meccanismi di ricerca dei servizi e della loro collocazione in rete (Service discovery and Location). Infatti, quando un nodo mobile si unisce ad una rete auto- organizzata, deve esplorare l'ambiente per scoprire quali servizi o risorse sono disponibili e dove si trovano. Questa operazione e piuttosto critica in ambienti mobili di tipo ad hoc, dove i nodi hanno capacita limitate e non possono contare su infrastrutture sse.

Per questo motivo, in ambiente MANET, i singoli nodi devono essere

quanto piu possibile consapevoli del contesto in cui si trovano. Infatti

l'informazione sul contesto operativo (posizione geograca o logica del nodo,

conoscenza dei vicini raggiungibili e delle risorse disponibili etc.) permette a

ciascun nodo di ottenere in maniera eciente i servizi e le risorse di cui ha bisogno.

Esistono varie soluzioni middleware [CEM02], spesso progettate per reti cablate tradizionali. Tutte queste architetture permettono di semplicare lo sviluppo delle applicazioni ma spesso non garantiscono prestazioni elevate in un contesto di rete MANET. Tra queste sicuramente risaltano per la loro importanza e popolarita le soluzioni di tipo Peer-to-Peer (P2P).

I sistemi P2P sono sistemi distribuiti in cui tutti i nodi hanno le stesse capacita e responsabilita e la comunicazione e simmetrica.

I sistemi P2P permettono di sfruttare le risorse oerte da un gran numero di nodi, costituendo delle reti auto-organizzate basate sui servizi forniti dai protocolli di livello rete e trasporto convenzionali. Tali reti, in genere prive di controllo centralizzato, sono dette overlay network.

I sistemi P2P hanno diverse caratteristiche in comune con i classici sistemi distribuiti. Infatti, anche i sistemi distribuiti sono costituiti da un insieme di elaboratori separati e connessi tra loro in rete che comunicano e coordinano le loro attivita attraverso lo scambio di messaggi, rendendo possibile la condivisione delle risorse all'interno di comunita di utenti piu o meno estese.

Inoltre molte problematiche proprie dei sistemi distribuiti, quali la scalabilita e la distribuzione del carico di lavoro tra i vari nodi, devono essere arontate anche nei sistemi P2P.

Nonostante le somiglianze esistenti tra sistemi P2P e sistemi distribuiti, occorre notare che tipicamente questi ultimi si sono sviluppati a partire dalla collaborazione di piccoli gruppi di utenti connessi tra loro. Al contrario i sistemi P2P sono stati pensati per la condivisione di risorse in ambienti caratterizzati da milioni di utenti con sistemi diversi e banda di trasmissione limitata (come Internet). Queste condizioni hanno portato a focalizzare l'attenzione sulla tolleranza ai malfunzionamenti e sulla scalabilita (ovvero la capacita di gestire in modo eciente l'incremento nel tempo del numero di nodi partecipanti).

E' ragionevole ipotizzare una convergenza tra queste due architetture, dal

momento che i sistemi distribuiti tendono a diventare sempre piu estesi e ad

orire nuovi servizi.

3.1 I sistemi P2P: oltre il modello client-server

3.1 I sistemi P2P: oltre il modello client- server

Per capire l'architettura di un sistema P2P puo essere utile confrontarla con quella dei sistemi che seguono il classico paradigma client-server. In un sistema client-server abbiamo un nodo server che ore le proprie risorse (documenti, servizi etc.) ad uno o piu client. Tipicamente il server e costituito da hardware molto piu potente di quanto non lo siano i client.

Il sistema e quindi fortemente asimmetrico ed il server diventa un punto critico dal punto di vista delle prestazioni. Per questo motivo spesso uno stesso server "logico" viene implementato con piu macchine e si usano tecniche di replicazione delle informazioni e bilanciamento del carico delle richieste per migliorare le prestazioni.

Con il miglioramento delle prestazioni dei PC e con la crescente diusione di connessioni di rete ad alta velocita diventa sempre piu sottile la distinzione a livello hardware tra dispositivi client e server. Risulta ragionevole, quindi, pensare di sfruttare le risorse che ciascun nodo client della rete e in grado di orire

I sistemi P2P rimuovono l'asimmetria di ruoli tra nodi client e nodi server.

Infatti in una rete P2P i client sono anche server che rendono disponibili agli altri nodi le proprie risorse. Dunque un nodo, oltre a chiedere risorse ad altri (comportandosi da client), mette a disposizione le proprie (assumendo il ruolo di server). La distinzione tra client e server e di fatto eliminata. Tutti i nodi sono potenziali fruitori e oerenti di un servizio.

In un sistema P2P i vari nodi mettono a disposizione le proprie risorse e l'elaborazione complessiva viene suddivisa tra di loro (sia essa uno scambio di messaggi, una complessa elaborazione numerica o semplicemente uno scambio di le). Naturalmente perche questo approccio cooperativo funzioni

e necessario che i vari componenti del sistema siano eettivamente disponibili a collaborare, spendendo parte delle proprie risorse per conto di terzi.

In una architettura client-server, il server dopo aver risposto alla richiesta

di un client non deve tenere in memoria alcuna informazione sul client stesso

o sulla richiesta ricevuta. Si dice quindi che il sistema e "stateless" ovvero non

3.1 I sistemi P2P: oltre il modello client-server

deve registrare in memoria informazioni di stato. Nonostante questa strategia consenta di migliorare le prestazioni e ridurre l'occupazione di memoria lato server, molti sistemi che orono servizi Web memorizzano informazioni sulle richieste fatte dai client, ovvero devono gestire dell'informazione di stato.

Anche nei sistemi P2P e in genere necessario che un nodo conservi qualche informazione di stato. In particolare ogni nodo generalmente non conosce in modo diretto quali sono i nodi che possono soddisfare le sue richieste, e quindi deve memorizzare e mantenere consistente nel tempo una lista di vicini cui passare le richieste stesse. Questa informazione di stato deve essere mantenuta con il minor overhead possibile. Per questo motivo e caratterizzata da dimensioni limitate e si parla quindi di "soft state".

Grazie al successo delle prime applicazioni, quali Napster, Gnutella e SETI@home, si e creata a livello mondiale una vasta comunita di ricerca che continua a studiare i principi e le soluzioni del paradigma P2P.

Ad esempio Napster [NAP] e un sistema di condivisione dei le che consente di cercare e scaricare le musicali, tipicamente in formato MP3, direttamente dai PC dei suoi utenti. Quando viene avviata l'applicazione, vengono registate in una directory globale (collocata in server centrali noti a tutti i partecipanti) delle informazioni che consentono di individuare i brani musicali presenti in rete e la loro collocazione. Un utente, quindi, puo eettuare una richiesta di un brano e il sistema, attraverso una ricerca con opportune parole chiave nella directory, provvede a restituire una lista di nodi che condividono il brano. A questo punto i nodi interessati allo scambio provvedono a stabilire una connessione diretta tra di loro, per il trasferimento del brano stesso. Possiamo osservare che l'esistenza di una directory centralizzata, collocata in alcuni nodi ben determinati della rete, fa si che il sistema non possa essere considerato P2P in senso stretto. Infatti i nodi che ospitano la directory possono essere considerati "speciali" e il loro ruolo risulta determinante per il corretto funzionamento del sistema.

Sono state sviluppate, quindi, soluzioni P2P completamente decentralizzate. Tra queste possiamo ricordare Gnutella [FIR00]. Gnutella

e un protocollo distribuito per la ricerca e la condivisione di le. Al contrario

di Napster non fa uso di alcuna directory centralizzata per tenere traccia

3.1 I sistemi P2P: oltre il modello client-server

dei le presenti nella rete e della loro collocazione. Ogni nodo Gnutella deve conoscere uno o piu vicini che partecipano al servizio. La ricerca di un le viene eettuata inviando la richiesta a tutti i vicini, che continueranno ad inoltrarla ai rispettivi vicini no al raggiungimento di un nodo in grado di soddisfarla. A questo punto il nodo che ha avviato la richiesta puo stabilire una connessione diretta con il nodo in grado di soddisfarla, ad esempio per scaricare un le.

Occorre osservare che l'ammontare di traco generato dall' "inondazione"

in rete della richiesta e notevole e questo limita notevolmente la scalabilita del sistema.

L'esperienza maturata con i sistemi sopra descritti ha permesso di sviluppare delle nuove soluzioni P2P piu scalabili e in grado di suddividere meglio il carico di lavoro tra i vari nodi della rete. Inoltre, osservando che in reti P2P su scala globale i nodi entrano ed escono continuamente dal sistema, occorre che ciascun nodo riesca a mantenere almeno una parte della visione globale della rete con meno overhead possibile.

Sono stati sviluppate, quindi, delle procedure di routing a livello middleware per sistemi P2P con lo scopo di distribuire messaggi o individuare

"oggetti" nell'ambito della rete seguendo determinate strategie. Le tecniche

piu popolari prevedono l'uso di tabelle hash distribuite (DHT - Distributed

Hash Table) per "mappare" gli indirizzi sici dei nodi in uno spazio di

indirizzi logico. Si parla quindi di "overlay network". A ciascun nodo della

rete viene assegnato un identicativo pseudo-casuale univoco che determina

la posizione del nodo in uno spazio logico, detto spazio delle chiavi. I

messaggi sono rappresentati da una coppia (chiave,valore) e vengono inoltrati

attraverso i nodi che costituiscono lo spazio logico no al raggiungimento

del nodo con identicativo piu vicino al valore della chiave. A seconda di

come le applicazioni sfruttano questo tipo di servizio oerto dal middleware,

un messaggio con una chiave specica puo rappresentare la richiesta di un

determinato servizio identicato dal valore della chiave stessa.

3.1 I sistemi P2P: oltre il modello client-server

3.1.1 Classicazione dei sistemi P2P

I sistemi P2P basati su overlay network possono essere suddivisi in due categorie: strutturati e non strutturati.

Nei sistemi ad overlay ogni nuovo nodo che si unisce alla rete P2P deve essere a conoscenza di almeno un nodo gia presente nella rete da cui recuperare le informazioni relative ad altri nodi partecipanti al sistema.

In particolare nei sistemi non strutturati le richieste vengono inviate in multicast: ogni nodo invia la richiesta ai propri vicini che faranno altrettanto no al recupero della risorsa ovvero no al raggiungimento di un massimo numero di passi. Quindi a livello middleware non e possibile individuare in maniera deterministica un contenuto o un altro nodo presente nella rete.

In una scenario statico come nelle reti sse, i nodi tendono a mantenere nel tempo sempre gli stessi vicini (a meno che non interrompano l'erogazione del servizio). In questo modo la dimensione della rete cresce in maniera arbitraria e non strutturata, determinando percorsi di routing sempre piu lunghi e orendo prestazioni scadenti. Inoltre il carico di lavoro sui vari nodi puo non essere distribuito in modo uniforme e quindi alcuni di loro possono rappresentare un punto critico dal punto di vista delle prestazioni per l'intero sistema. In ambito Internet la rete P2P Gnutella utilizza questo tipo di tecnica. Ogni nodo "inonda" la rete trasmettendo in broadcast la propria richiesta e determinando una crescita esponenziale del traco che rende il sistema non scalabile.

Nei sistemi basati su overlay strutturato i nodi sono organizzati logicamente in modo che ciascuno possa essere raggiunto in un numero limitato di passi, tipicamente di ordine logaritmico rispetto al numero di nodi presenti nella rete. Ogni nodo attua delle precise politiche di routing per inoltrare i messaggi. La maggior parte di essi si basa sull'uso delle tabelle DHT. In letteratura esistono molti studi sui sistemi P2P basati su routing strutturato, prevalentemente orientati alle reti cablate tradizionali.

Questo tipo di sistemi consentono di stabilire dei percorsi di comunicazione

adabili tra i nodi che costituiscono la rete e separano in modo netto

3.2 Pastry

l'instradamento a livello middleware da quello a livello routing, ssando dei criteri di distribuzione dei contenuti e di inoltro dei messaggi basati sulla prossimita logica tra il valore di una chiave e l'identicativo di un nodo.

3.1.2 Analogie tra sistemi P2P e reti ad hoc

Le reti ad hoc hanno molti aspetti in comune con i sistemi P2P. Tra questi possiamo ricordare: la natura distribuita delle elaborazioni, la cooperazione tra i nodi e la comunicazione tra utenti nali. In particolare la distribuzione dei servizi e dei dati si adatta bene alla natura decentralizzata delle reti ad hoc. Nelle reti ad hoc come nei sistemi P2P si ha una distribuzione delle risorse disponibili tra nodi eterogenei. Inoltre in entrambi gli scenari occorre gestire interazioni temporanee tra i nodi e eventi di disconnessione. Il fatto che i nodi di una rete P2P entrino ed escano continuamente dalla rete li rende molto simili ai nodi mobili di una rete ad hoc, soggetti a problemi di trasmissione e comunicazione.

Tuttavia molte delle soluzioni P2P esistenti sono state progettate per reti cablate tradizionali e la loro applicabilita in ambiente MANET e ancora oggetto di studio. La possibilita di integrare i sistemi P2P nell'ambiente MANET permetterebbe di utilizzare tutta una serie di applicazioni gia diuse in ambiente Internet.

Nonostante i sistemi P2P appaiano come un modello di elaborazione naturale per le reti MANET, occorre ancora valutare le prestazioni di tali sistemi in ambiente ad hoc.

3.2 Pastry

Nell'ambito di questa tesi abbiamo analizzato in dettaglio il protocollo

Pastry. La scelta e stata determinata dalla sua scalabilita rispetto alla

dimensione della rete e dalla disponibilita di un'implementazione open

source (FreePastry [FRE]). In particolare, dopo un'analisi dettagliata di

Pastry, illustreremo una nuova soluzione ad esso ispirata (CrossROAD

- Cross-layer Ring Overlay for AD Hoc Networks)[Del05], in grado di

3.2 Pastry

utilizzare un approccio di tipo cross-layer sfruttando un protocollo di routing proattivo (OLSR).

Pastry [DR01b] e un sistema P2P che fornisce un servizio di distribuzione e recupero di oggetti attraverso l'inoltro di messaggi in rete.

Tale servizio e completamente decentralizzato e caratterizzato dalla costruzione di un'overlay network al di sopra dei protocolli tradizionali di trasporto e di rete (ad esempio il TCP/IP).

Ad ogni nodo di una rete Pastry viene univocamente associato un identicativo logico su 128 bit (d'ora in poi indicato con nodeID). Tale identicativo permette di individuare la posizione del nodo in uno spazio logico circolare che comprende identicativi da 0 a 2 ¹²⁸ 1. I nodeID vengono assegnati in modo pseudo-casuale quando un nodo entra a far parte della rete Pastry e l'insieme dei nodeID deve essere quanto piu possibile uniformemente distribuito nello spazio logico a 128 bit. Ad esempio i nodeID potrebbero essere il risultato dell'applicazione di una funzione hash sull'indirizzo IP del nodo o qualsiasi altro identicativo univoco.

Osserviamo che non esiste alcuna corrispondenza tra la distanza logica e la distanza sica tra due nodi. Infatti a seguito della distribuzione casuale dei nodeID e ragionevole che nodi adiacenti nello spazio logico risultino lontani da un punto di vista geograco o amministrativo.

Le applicazioni che basano il loro funzionamento su Pastry ottengono un

servizio di instradamento eciente ed adabile. In particolare quando un

nodo Pastry riceve dall'applicazione un messaggio ed una chiave numerica

provvede ad inoltrare il messaggio verso il nodo Pastry avente nodeID

numericamente piu vicino alla chiave. Data una rete Pastry costituita

da N nodi, il numero previsto di passi eettuati dal messaggio no al

raggiungimento del nodo numericamente piu vicino alla chiave e dell'ordine

di O(log N). Piu precisamente, dati b e L parametri di congurazione il cui

valore vale in genere 4 e 16 (o 32), Pastry e in grado di inoltrare un messaggio

verso il nodo piu vicino alla chiave in meno di dlog ₂

Ne passi, nelle normali

condizioni operative. In caso di cadute di nodi e ugualmente in grado di

garantire un corretto inoltro a meno che non cadano contemporaneamente

3.2 Pastry

bjLj=2c nodi con nodeID adiacenti.

Dal punto di vista dell'inoltro dei messaggi, i nodeID e le chiavi sono visti da Pastry come delle sequenze di cifre in base 2 ^b (dove b e il parametro di congurazione sopracitato). Per inoltrare il messaggio verso il nodo avente nodeID piu vicino possibile alla chiave data, ad ogni passo dell'instradamento il nodo locale passa il messaggio verso un altro nodo che condivide con la chiave un presso piu lungo, almeno di una cifra (ovvero b bit), rispetto al nodo locale. Se non riesce ad individuare un nodo in grado di soddisfare tale proprieta, inoltra il messaggio verso un nodo il cui nodeID ha un presso a comune con la chiave lungo quanto quello del nodo locale ma numericamente piu vicino.

Sono state sviluppate diverse applicazioni che sfruttano il servizio di instradamento fornito da Pastry. Tra queste ricordiamo PAST [DR01a]

e SCRIBE [CDRK01].

PAST e un sistema per la replicazione e la distribuzione di le in una rete di tipo P2P. Ad ogni le viene associato un identicativo (leID) calcolato come risultato della funzione hash applicata al nome del le e del proprietario. Tale leID viene usato come chiave per individuare il le stesso nella rete Pastry. In particolare, memorizzando delle repliche del le nei k nodi aventi nodeID numericamente piu vicino possibile al leID, si garantisce la possibilita di individuare un nodo contenente il le utilizzando il leID come chiave (purche almeno uno dei k nodi che contengono le repliche sia attivo). Tale nodo inviera il le al richiedente e concludera l'elaborazione del messaggio.

SCRIBE, invece, e un'applicazione distribuita in grado di fornire un

servizio di tipo publish/subscribe sfruttando l'instradamento fornito da

Pastry. In un sistema publish/subscribe abbiamo dei nodi (publisher), che

rendono disponibili delle informazioni o annunciano il vericarsi di eventi, e

dei nodi subscriber che dichiarano il loro interesse ad essere informati. In

generale occorre trovare dei sistemi ecienti per tenere traccia di quali nodi

sono interessati a determinati eventi e per noticare gli eventi stessi. SCRIBE

prevede di associare ad ogni "argomento" di interesse un identicativo

(topicID) calcolato come funzione hash del nome dell'argomento. Una

3.2 Pastry

lista dei nodi interessati a quell'argomento (subscriber) viene memorizzata nel nodo avente nodeID numericamente piu vicino al topicID. I subscriber noticano il proprio interesse ad un dato argomento attraverso un messaggio Pastry avente come chiave il topicID. Tale interesse verra registrato nel nodo sopradetto. Quando un publisher invia un messaggio avente come chiave il topicID, questo raggiungera il nodo contenente la lista dei subscriber che provvedera a noticarlo agli interessati.

3.2.1 Informazioni di stato

Per tenere traccia della corrispondenza tra indirizzi logici e sici dei vari nodi conosciuti, ciascun partecipante alla rete Pastry deve memorizzare e mantenere consistenti nel tempo delle informazioni di stato, organizzate in 3 strutture dati: insieme dei vicini logici (LeafSet), insieme dei vicini sici (Neighborhood set) e tabella di routing (routing table) (un esempio di queste strutture e riportato in gura 3.2).

I nodi caratterizzati da un identicativo presente nel LeafSet sono sicamente distribuiti nella rete e costituiscono un sottoinsieme dell'overlay network avente come centro l'indirizzo logico del nodo locale. Sia b un parametro di congurazione (tipicamente avente valore 4) ed L il valore 2 ^b . Il LeafSet sara costituito dagli L/2 nodi con nodeID numericamente piu piccolo e dagli L/2 nodi con nodeID numericamente piu grande del nodeID del nodo locale.

L'insieme dei vicini (Neighborhood set) (indicato d'ora in poi con M) contiene un sottoinsieme dei vicini sici (logicamente distribuiti nella rete).

In particolare e costituito dagli jMj vicini sici piu vicini al nodo locale (in accordo alla metrica usata per valutare la distanza, ad esempio il numero di passi per raggiungerli). Tipicamente M vale 2 x 2 ^b .

La tabella di routing (routing table) (indicata d'ora in poi con R) e

costituita da dlog ₂

Ne righe ciascuna con 2 ^b 1 entrate. Ciascuna delle

2 ^b 1 entrate della n-sima riga di R si riferisce ad un nodo il cui nodeID

ha le prime n cifre a comune con il nodeID del nodo locale ma la cui n+1

cifra ha uno dei restanti 2 ^b 1 valori possibili, diverso da quello della cifra

3.2 Pastry

n+1 del nodeID locale. In altre parole ogni riga di R contiene un insieme di nodeID che condividono con l'indirizzo logico del nodo locale un presso lungo quanto l'indice della riga e la cui cifra successiva ha lo stesso valore dell'indice della colonna in cui si trova il nodeID. Ciascun elemento di R contiene l'indirizzo IP di uno dei molti possibili nodi il cui nodeID ha il presso appropriato. In particolare sara scelto l'indirizzo di un nodo che risulti vicino in accordo alla metrica utilizzata (tipicamente numero di hop di distanza). Se non si conosce alcun nodo con nodeID appropriato, l'elemento corrispondente di R rimane vuoto.

Figura 3.2: Informazioni di stato ipotetiche su un nodo con nodeID 10233102, b=2 e l=8. Tutti i numeri sono in base 4

Osserviamo che la scelta del parametro di congurazione b e condizionata

dalla necessita di bilanciare la dimensione di R (approssimativamente pari

a dlog ₂

Ne x (2 ^b 1)) con il massimo numero di passi necessari per far

arrivare un messaggio a destinazione dlog ₂

Ne. A causa delle dimensioni

3.2 Pastry

tipicamente limitate delle strutture dati che contengono l'informazione di stato (un esempio di tabelle e riportato in gura 3.2), ogni nodo Pastry puo memorizzare soltanto una piccola parte della topologia della rete. Quindi la destinazione nale di un messaggio puo essere sconosciuta al mittente, rendendo necessario un inoltro con piu passi a livello middleware.

Nei prossimi paragra illustreremo il processo di inoltro dei messaggi all'interno di Pastry e come le informazioni di stato necessario vengono gestite e mantenute consistenti nel tempo.

3.2.2 Routing dei messaggi

La procedura di instradamento dei messaggi viene avviata da un nodo Pastry ogni volta che riceve un coppia (chiave,messaggio) (un esempio di tale processo e illustrato in gura 3.3). Si parla di routing basato su soggetto in quanto per distribuire e ricercare gli "oggetti" nello spazio logico si utilizzano informazioni quali il nome del le o l'identicativo dell'oggetto.

Ciascun nodo verica se la chiave rientra nell'intervallo dei nodeID presenti nel proprio LeafSet (insieme dei vicini logici). Se si verica questa condizione il messaggio viene inviato direttamente al nodo destinatario, ovvero il nodo del LeafSet il cui nodeID risulta essere il piu vicino (nello spazio logico) possibile alla chiave. Notiamo che tale nodo potrebbe essere anche il nodo locale stesso che sta eseguendo la procedura di inoltro.

Se la chiave, invece, non rientra nel LeafSet, il nodo locale consulta la tabella di routing ed inoltra il messaggio verso un nodo che condivide con la chiave un presso piu lungo di almeno una cifra rispetto a quello condiviso con la chiave dal suo stesso nodeID. Se non riesce a trovare nella tabella di routing un nodeID in grado di soddisfare la condizione sopradetta, il messaggio viene inoltrato ad un nodo il cui nodeID condivide con la chiave un presso lungo quanto quello del nodo locale ma che sia numericamente piu vicino alla chiave rispetto al nodeID del nodo locale.

Questa procedura di routing converge sempre perche in ogni passo il

messaggio viene mandato verso un nodo il cui nodeID o condivide con la

3.2 Pastry

chiave un presso piu lungo di quello condiviso dal nodeID del nodo locale o

e numericamente piu vicino alla chiave.

Figura 3.3: Routing di un messaggio dal nodo con ID 10233102 e avente chiave 23302121 (con riferimento alla tabella di routing di gura 3.2)

3.2.3 Ingresso e uscita dalla rete

Per un protocollo middleware come Pastry e essenziale gestire in modo eciente l'ingresso e l'uscita di nodi dalla rete. Quando un nuovo nodo entra in gioco, deve inizializzare le proprie tabelle di stato e comunicare la propria presenza agli altri partecipanti che costituiscono l'overlay.

Quando un nuovo nodo vuole entrare in una rete Pastry gia costituita deve conoscere almeno un vicino sico (A) gia presente nella rete.

Tale nodo potrebbe essere individuato autonomamente (con tecniche tipo

"expanding ring" o multicast) ovvero indicato dall'amministratore del

sistema. Supponiamo, inoltre, che il nuovo nodo prenda X come identicativo

logico (X potrebbe essere il risultato del calcolo di una funzione hash

sull'indirizzo IP del nodo).

3.2 Pastry

Per potersi unire all'overlay il nuovo nodo X chiede ad A di inoltrare uno speciale messaggio di join avente come chiave proprio X. Come ogni altro messaggio verra inoltrato al nodo Z (gia presente nella rete) con nodeID numericamente piu vicino a X. In risposta alla richiesta di join ricevuta dal nodo A, tutti i nodi che inoltrano il messaggio da A no al raggiungimento di Z inviano le proprie tabelle di stato al nuovo nodo X.

Considerando che A e un vicino sico di X, l'insieme dei vicini sici (Neighborhood set) di X viene inizializzato con i valori presenti in quello di A. Inoltre X potra inizializzare il proprio Leaf Set prendendo i valori da quello del nodo Z che risulta essere il nodo logicamente piu vicino ad X.

Per costruire la tabella di routing iniziamo con l'osservare che i nodeID del nodo A e del nodo X non hanno a comune alcun presso. Indichiamo con A i la riga i-esima della tabella di routing del nodo A. Osservando che gli elementi presenti in corrispondenza della riga 0 sono indipendenti dal nodeID, possiamo usare i valori di A 0 per inizializzare X 0 . Notiamo che le altre righe della tabella di routing di A non possono essere utilizzate per inizializzare quella di X, avendo assunto per ipotesi che i nodeID di A e X non abbiano alcun presso a comune. Per poter inizializzare i valori di X ₁ possiamo prendere i valori di B ₁ , dove B e il primo nodo che si incontra nel percorso da A verso Z durante l'invio del messaggio di join. Infatti gli elementi di B 1

e di X 1 condividono lo stesso presso, in quanto X e B hanno la stessa prima cifra nei loro nodeID. In modo simile X puo ottenere gli elementi di X 2 dal nodo C, dove con C si intende il nodo incontrato dopo B nel percorso verzo Z e cos via. In altre parole, il nodo X inizializza la propria tabella di routing prendendo come i-esima riga la riga corrispondente della tabella di routing dell'i-esimo nodo attraversato dal messaggio di join nel percorso da A verso Z. Quindi l'operazione di join richiede l'apertura di molte connessioni con nodi "remoti", operazione estremamente costosa in termini di overhead di traco.

Una volta che il nuovo nodo X ha costruito le proprie tabelle di stato, ne invia una copia a tutti i nodi conosciuti. I nodi che ricevono questa informazione aggiornano coerentemente il proprio stato.

Un nodo di una rete Pastry puo uscire dalla rete o fallire (ad esempio

3.2 Pastry

per un malfunzionamento) senza alcun preavviso. Questa condizione viene rilevata dai nodi vicini nello spazio logico dei nodeID quando non riescono piu a stabilire una comunicazione con esso. Quando un nodo vuole sostituire un vicino appartenente al LeafSet contatta il nodo avente nodeID piu grande (tra quelli piu vicini al nodo da sostituire) e prende il suo LeafSet. La sostituzione viene eettuata scegliendo un nodo appropriato dal LeafSet ricevuto e vericando che sia eettivamente attivo.

Anche l'insieme dei vicini deve essere mantenuto consistente nel tempo.

Quindi ogni nodo prova periodicamente a stabilire delle connessioni con ciascun membro dell'insieme dei vicini per vedere se risulta attivo. Se questo non risponde, il nodo chiede agli altri membri di ottenere i rispettivi insiemi dei vicini e aggiorna coerentemente il proprio.

Ogni nodo deve gestire una procedura di interrogazione (polling) anche per mantenere consistente lo stato dei vari nodi "remoti" presenti nella tabella di routing. Un nodo che non risponde alla richiesta di connessione entro lo scadere di un dato intervallo di tempo si considera disconnesso dalla rete. Dopo aver rilevato un evento di disconnessione il nodo deve aggiornare l'entrata della tabella di routing corrispondente all'elemento uscito dalla rete stabilendo altre connessioni remote con i nodi dell'overlay.

In particolare, per sostituire un elemento della tabella di routing corrispondente ad un nodo caduto, viene contattato un nodo appartenente alla stessa riga e gli viene chiesto il valore di cui dispone nella posizione corrispondente all'elemento da rimpiazzare. Se nessun nodo della riga dispone di un elemento valido nella stessa posizione di quello da rimpiazzare, la stessa richiesta viene fatta al nodo che si trova nella riga successiva e in corrispondenza della stessa colonna.

Nei prossimi capitoli osserveremo, attraverso un'analisi sperimentale su reti ad hoc reali, come queste procedure di interrogazione (polling) necessarie per tenere aggiornate le informazioni di stato richiedono la gestione di un grande numero di connessioni di rete e determinano un notevole overhead, che penalizza notevolmente le prestazioni in ambiente MANET.

In denitiva possiamo osservare che Pastry, attraverso l'uso delle tabelle

DHT, consente una suddivisone uniforme del carico di lavoro nella rete e

3.2 Pastry

degli identicativi logici dei nodi, presentando una buona scalabilita nelle operazioni di inoltro dei messaggi al crescere del numero di nodi della rete.

Inoltre l'uso di un instradamento basato sulla prossimita logica permette

di adattare molte applicazioni a questo tipo di strategia. Tuttavia occorre

osservare che la gestione delle tabelle di routing basata su connessioni remote

determina un notevole overhead nel sistema.

3.2 Pastry