Capitolo 5
CrossROAD - CROSS-layer Ring Overlay for AD Hoc Networks
CrossROAD (CROSS-layer Ring Overlay for AD Hoc Networks) [Del05]
e un nuovo protocollo middleware, che utilizza delle interazioni di tipo cross-layer con il livello routing per sempli care la costruzione e il mantenimento dell'overlay network in ambiente MANET. CrossROAD
e stato sviluppato nell'ambito del progetto MobileMAN [MOB] presso l'Istituto di Informatica e Telematica del CNR di Pisa.
CrossROAD nasce dall'idea di realizzare un sistema P2P per reti ad hoc con particolare riferimento ai sistemi basati su overlay strutturato.
In particolare CrossROAD si ispira al protocollo Pastry per quanto riguarda la strategia di distribuzione e recupero delle informazioni all'interno dell'overlay, ovvero il routing basato su soggetto. Inoltre Pastry presenta una buona scalabilita rispetto al numero di nodi presenti nell'overlay ed esistono gia un gran numero di servizi che lo utilizzano come piattaforma middleware. CrossROAD eredita le funzionalita principali di Pastry ma ottimizza le prestazioni attraverso un approccio cross-layer con il livello routing.
Studi sperimentali [BCDP05], svolti in ambiente MANET con un'implementazione open source di Pastry (FreePastry - [FRE]), hanno mostrato come la gestione dell'overlay, a causa del gran numero di connessioni TCP necessarie, determina un overhead elevato, riducendo le prestazioni complessive del sistema. Infatti, nel protocollo Pastry, risulta estremamente costoso costruire e mantenere consistenti nel tempo le strutture dati necessarie per la gestione dell'overlay. Questo perche occorre stabilire un elevato numero di connessioni remote verso gli altri nodi che partecipano all'overlay per recuperare le informazioni di routing da memorizzare nelle strutture dati di Pastry. Questo aspetto risulta ancora piu critico in ambiente MANET dove, a causa dell'elevata mobilita e dinamicita della topologia, il mantenimento dell'overlay viene svolto piu frequentemente, con un conseguente incremento dell'overhead necessario. .
In Pastry, a causa delle dimensioni limitate delle tabelle interne che contengono l'informazione di stato, ogni nodo conserva solo una parte della topologia dell'overlay, in funzione del suo indirizzo logico. Questo, assieme alla politica di routing basata su soggetto, fa si che la destinazione nale di un messaggio possa essere sconosciuta al mittente, determinando un inoltro in piu passi a livello middleware. Abbiamo gia visto che, normalmente, Pastry riesce ad inoltrare un messaggio verso il destinatario in O(log N) passi, dove N e il numero di partecipanti all'overlay.
Allo scopo di migliorare le prestazioni e sempli care la gestione dell'overlay si puo utilizzare un approccio cross-layer, prelevando informazioni sulla topologia della rete direttamente dal livello routing.
In particolare CrossROAD e progettato per interagire direttamente con un protocollo di routing proattivo in grado di garantire una conoscenza completa della topologia della rete. In questo modo si riesce a mantenere una corrispondenza tra gli spazi di indirizzamento logico e sico, senza incrementare l'overhead.
Osserviamo, tuttavia, che la semplice conoscenza della topologia della rete non e suciente per poter sempli care la costruzione dell'overlay. Infatti ogni overlay e associato ad un determinato servizio e solo i nodi che lo o rono possono entrarne a far parte. Quindi e necessario sviluppare un sistema di
ricerca per identi care quali servizi sono disponibili in rete e quali nodi li o rono. Anziche sviluppare un protocollo indipendente per inoltrare in rete le informazioni sui servizi o erti (con un ulteriore aumento dell'overhead), possiamo sfruttare l'approccio proattivo utilizzato dal routing nell'inviare periodicamente i messaggi necessari per aggiornare la topologia.
In particolare, ogni nodo puo inserire in un messaggio la descrizione di ciascun servizio o erto e aggiungere tale messaggio all'interno dei pacchetti di routing emessi periodicamente. Un servizio viene descritto attraverso un identi cativo numerico univoco e il numero di porta locale al nodo su cui viene reso disponibile. Quindi la descrizione di un dato servizio e rappresentabile in maniera estremamemnte compatta, ottenendo cos un traco aggiuntivo a quello del routing del tutto trascurabile. Quando un nodo riceve messaggi che descrivono dei servizi presenti in rete, deve aggiornare una struttura dati (concettualmente collocata nel modulo NeSt) che tiene traccia di quali servizi sono disponibili e quali nodi li o rono.
CrossROAD assegna ad ogni nodo un indirizzo logico univoco ottenuto applicando una funzione hash distribuita all'indirizzo IP del nodo stesso.
Attraverso il sistema di ricerca dei servizi, implementato come estensione del routing proattivo, CrossROAD e in grado di ottenere (accedendo direttamente alle strutture del NeSt) l'elenco degli indirizzi IP dei nodi che partecipano ad un dato servizio. Puo quindi costruire autonomamente l'overlay, calcolando l'indirizzo logico dei partecipanti al servizio ottenuti come sopra. Questo permette di evitare completamente la creazione di connessioni remote iniziali per la raccolta delle informazioni di routing, necessarie in Pastry per stabilire l'overlay. Quindi la costruzione dell'overlay, che in Pastry determinava un costo elevato a livello middleware (a causa del gran numero di connessioni remote necessarie), risulta in CrossROAD un'operazione svolta localmente al nodo, senza alcun costo a livello middleware.
Piu in dettaglio, quando un nodo decide di entrare a far parte di un determinato overlay perche inizia a fornire un servizio, l'applicazione provvedera a creare una nuova istanza di CrossROAD, pubblicando l'identi cativo del servizio corrispondente attraverso il NeSt e richiedendo
la lista degli indirizzi IP degli altri partecipanti eventualmente gia presenti.
E' compito del protocollo di routing mantenere aggiornate e consistenti nel tempo le informazioni relative ai servizi disponibili in rete e ai nodi corrispondenti che li o rono. Una volta che CrossROAD ha recuperato queste informazioni, puo calcolare gli identi cativi logici e memorizzarli nelle proprie strutture dati interne.
CrossROAD sintetizza le strutture dati usate da Pastry (LeafSet, Neighborhood set e Routing Table) in un unica tabella di routing che conterra l'indirizzo logico di tutti i nodi che costituiscono l'anello oltre ad eventuali informazioni sul comportamento del nodo (mobilita, adabilita etc.). Tale tabella e organizzata secondo la stessa metrica basata sui pre ssi degli indirizzi logici (pre x-based metric) usata da Pastry e la sua dimensione dipende dal numero di nodi che prendono parte al servizio in un dato istante.
Nella peggiore delle ipotesi, ovvero se tutti i nodi della rete sica prendono parte al servizio, avra una dimensione pari al loro numero (questa ipotesi risulta ragionevole per reti MANET di piccola dimensione).
Come si vede, quindi, le strutture dati necessarie per il mantenimento dell'overlay vengono drasticamente ridotte e questo sempli ca notevolmente la loro gestione. CrossROAD non ha bisogno di stabilire connessioni remote e per mantenere l'overlay consistente si limita ad accedere (quando deve costituire la rete o mandare un messaggio) alle strutture dati del NeSt che gli forniranno una visione aggiornata dei nodi presenti e dei servizi o erti.
Sfruttando gli aggiornamenti della topologia della rete gestiti dal protocollo di routing e il conseguente aggiornamento delle astrazioni presenti nel NeSt, CrossROAD diventa consapevole della topologia della rete con gli stessi tempi del protocollo di routing. Quindi, per rilevare disconnessioni di nodi, non ha bisogno di e ettuare costosi cicli di interrogazione come quelli svolti all'interno di Pastry.
Un'altra caratteristica di Pastry e rappresentata dalla determinazione del destinatario di un dato messaggio. Pastry, infatti, inoltra i messaggi utilizzando il routing basato su soggetto e questo puo determinare, a livello middleware, un percorso costituito da piu passi. In realta, in una rete ad hoc di piccole dimensioni, ogni nodo mantiene nella sua struttura dati
Figura 5.1: Routing a livello middleware e network
tutti gli altri partecipanti e quindi si veri ca raramente un routing multi- hop a livello middleware. Tuttavia, sfruttando l'interazione cross-layer con il protocollo di routing, CrossROAD conosce tutti gli identi cativi logici di tutti i nodi dell'overlay e quindi puo determinare autonomamente la destinazione logicamente piu vicina alla chiave e stabilire con essa una connessione diretta di tipo P2P (come mostrato in gura 5.1). Dunque CrossROAD rimuove tutto l'overhead speso da Pastry per mantenere la tabella di routing e riduce la complessita del routing ad un valore costante (O(1)) in funzione della distanza sica tra i nodi, mantenendo sempre il principio del routing basato su soggetto. Infatti il protocollo di instradamento a livello network provvede ad inviare sicamente il messaggio a destinazione attraverso il percorso piu breve.
La gura 5.2 mostra un esempio di interazione cross-layer per la generazione di un overlay tra due nodi. Supponiamo che A e B siano due nodi che fanno parte della stessa rete ad hoc e che B, inoltre, faccia gia parte di un dato overlay a cui A vuole partecipare. Il nodo A, per poter entrare a far parte dell'overlay, deve avviare il servizio corrispondente, appoggiandosi su CrossROAD. In particolare CrossROAD riconosce il servizio fornito da A e invia questa informazione al NeSt che noti ca l'evento al protocollo di routing. Questa informazione verra incapsulata dal protocollo di routing nel successivo LSU (Link State Update) che viene inviato in rete. Quando il
5.1 Struttura software di CrossROAD
Figura 5.2: Interazione cross-layer tra CrossROAD e protocollo di routing
nodo B (o qualche altro nodo) ricevera questa informazione, provvedera ad aggiornare la topologia e le strutture dati del NeSt (associando il nuovo nodo A al servizio annunciato) per mantenere una visione consistente.
Ogni volta che l'applicazione che opera sul nodo B vuole mandare un messaggio in rete, chiede a CrossROAD di veri care che il contenuto della sua tabella di routing sia consistente con l'attuale topologia della rete (rappresentata all'interno del NeSt). In questo modo, CrossROAD ottiene una visione aggiornata della rete ad ogni invio di un messaggio applicativo, riducendo la possibilita di prendere in considerazione destinazioni sbagliate.
Questa soluzione sempli ca in maniera drastica la manutenzione dell'overlay network, senza sovraccaricare troppo le funzionalita della rete.
5.1 Struttura software di CrossROAD
CrossROAD e costituito da diversi moduli software ed e scritto interamente in Java. I vari componenti che lo costituiscono devono gestire le strutture dati locali e l'interazione verso l'alto con il livello applicativo e verso il basso con il routing.
In gura 5.3 e illustrato il diagramma dei package che costituiscono l'architettura software di CrossROAD.
In particolare, il modulo NodeHandle mantiene le corrispondenze tra gli
5.1 Struttura software di CrossROAD
Figura 5.3: Architettura software CrossROAD
indirizzi sici e logici (calcolati attraverso il modulo HashIDFactory) di un nodo.
Di seguito abbiamo Endpoint, che e il modulo che si occupa della gestione delle interazioni con l'applicazione, Routing table che gestisce la struttura dati relativa all'overlay, Messages che rappresentano i messaggi inviati all'interno dell'overlay ed in ne CrossROAD Node che rappresenta il modulo principale con le funzionalita di gestione dei processi di interazione cross-layer, selezione dei destinatari e connessione P2P per la distribuzione delle informazioni.
Quando viene avviata un'applicazione che opera su CrossROAD, viene creata un'istanza del nodo locale, con le relative strutture dati, che si unisce ad un overlay gia esistente o ne crea uno nuovo. Nel momento in cui viene creata un'istanza del nodo CrossROAD, esso invia immediatamente una richiesta di tipo PublishService al NeSt che inoltrera l'informazione relativa all'ID del servizio e del nodo che lo fornisce al protocollo di routing. Quest'ultimo provvedera a distribuirla in rete, attraverso il successivo LSU. In modo concorrente tutti i nodi che riceveranno l'annuncio (incapsulato nel pacchetto LSU) di un servizio presente in un nodo, aggiorneranno coerentemente le proprie strutture.
A questo punto il nodo locale puo iniziare a mandare messaggi in rete attraverso l'overlay, ma prima di ogni invio deve veri care la consistenza delle proprie strutture dati con quelle del NeSt, inviandogli un messaggio di richiesta della topologia di rete (Network Topology Request).
In gura 5.4 e illustrato il diagramma dei package con evidenziate le
5.1 Struttura software di CrossROAD
Figura 5.4: Architettura software CrossROAD e schema delle interazioni tra i suoi packages
interazioni tra di essi. Maggiori dettagli sui messaggi che CrossROAD scambia con il livello routing saranno forniti nel capitolo sull'architettura del plugin.
CrossROAD esporta verso il livello applicazioni un'interfaccia che rispetta le speci che descritte nalla cosidetta p2p CommonAPI [DDZ03].
Questa API (Application Programming Interface) e stata sviluppata per ottenere un'interfaccia comune tra le applicazioni P2P e tutti i sistemi che implementano overlay network basati su routing strutturato. Tutti i livelli middleware che esportano questo tipo di interfaccia verso le applicazioni risultano compatibili con le stesse.
Per concludere, possiamo riassumere i principali vantaggi o erti da CrossROAD rispetto a Pastry:
CrossROAD elimina l'overhead aggiuntivo, necessario per la creazione e il mantenimento dell'overlay presente in Pastry;
CrossROAD elimina completamente le connessioni TCP e UDP utilizzate da Pastry (e i corrispondenti picchi di traco) necessarie
5.1 Struttura software di CrossROAD
per monitorare lo stato dei vicini. E' compito del routing proattivo noti care a CrossROAD tutti i cambiamenti della topologia;
In CrossROAD il routing multi-hop a livello middleware viene trasformato in una semplice connessione P2P con il destinatario, mantenendo il principio del routing basato su soggetto. Dunque il costo della ricerca del destinatario presente in Pastry (dell'ordine di O(log N)) assume un valore costante, che dipende esclusivamente dalla distanza sica tra i nodi.
Nei prossimi capitoli illustreremo i dettagli dell'implementazione di una possibile soluzione di interazione cross-layer tra routing e middleware.
5.1 Struttura software di CrossROAD
