RICERCA ITALIANA     

CARTOON - Context Aware RouTing Over Opportunistic Networks

Università degli Studi di Milano

Abstract

Nell'esperienza quotidiana di persone che si muovono all’interno di un’area urbana, un’università, o un palazzo ci sono molte applicazioni, che spaziano dal controllo ambientale all’intrattenimento, alla coordinazione di gruppo, alla condivisione di informazioni, per le quali la disponibilità di un’infrastruttura di rete wireless magliata, a basso costo e scalabile offrirebbe capacità di interazione fra dispositivi mobili piu’ flessibile di quanto oggi consentito dalle classiche reti di accesso wireless one hop. Studi recenti sui comportamenti di aggregazione e di mobilità umana, affiancati da esperienze sul campo, hanno messo in luce che una tale infrastruttura ad hoc potrebbe essere facilmente realizzata abilitando i dispositivi radio, trasportati da veicoli e da persone, a comportarsi come nodi di instradamento di una rete a maglia in aggiunta alla loro normale capacità di fornire connessione diretta a punti informativi e di accesso alla rete. Il termine di reti opportunistiche è spesso utilizzato per identificare questo tipo di reti mobili in grado di fornire copertura a corto raggio all’interno di un’area limitata (ad esempio, un quartiere, un campus o un centro commerciale).

Le reti opportunistiche sono reti in grado di tollerare ritardi trasmissivi e nelle quali i nodi stabiliscono connessioni temporanee tra loro per il forwarding dei pacchetti utilizzando l’opportunità di connessione offerta da un’altra stazione all’interno del raggio di comunicazione. Nel caso non siano disponibili altri dispositivi nelle vicinanze, il pacchetto viene memorizzato localmente in attesa di una nuova possibilità di spedizione che si verra’ a creare per effetto della mobilità dei nodi.

Questa è un’area di ricerca emergente ed una tecnologia promettente per supportare ubiquitous computing. Tuttavia, per consentire che cio’ accada, un grosso sforzo di ricerca è richiesto per progettare sistemi di comunicazione tra nodi che siano flessibili, affidabili ed efficienti.

CARTOON si focalizzerà sulla progettazione di protocolli originali per reti sia "reali" che virtuali ( overlay). Per soddisfare i vincoli di efficienza e flessibilità, CARTOON realizzerà protocolli sensibili al contesto, cioè protocolli che tengono conto anche di informazioni provenienti da un gestore di risorse locali e da altri dispositivi vicini oltre che di quelle provenienti dai livelli inferiori e superiori dello stack. In questo contesto emergente la ricerca produrrà tre contributi principali:

i) progettazione ed analisi di nuovi protocolli ed algoritmi per coprire le esigenze funzionali dei livelli di rete e di overlay;

ii) uno strumento di simulazione specifico per reti opportunistiche, ottenuto dal miglioramento di un ambiente di simulazione esistente ( ns2, OMNeT++ o GloMoSim) e che sarà poi rilasciato alla comunità;

iii) l’analisi e le specifiche architetturali di un dispositivo mobile CARTOON-based che costituiranno l’input ad un successivo programma di ricerca e sviluppo in cui i prototipi verranno valutati in un ambiente reale. <<<

Coordinatore Scientifico del Programma di Ricerca

Gian Paolo Rossi Università degli Studi di MILANO

Obiettivo del Programma di Ricerca

2.1.1 ROUTING SU RETI OPPORTUNISTICHE

Con il termine reti opportunistiche viene identificato un particolare tipo di reti mobili in grado di fornire una infrastruttura ad hoc sfruttando link radio a corto raggio all’interno di un’area limitata (ad esempio un quartiere, un’università o un centro commerciale). Le reti opportunistiche sono reti in grado di tollerare ritardi trasmissivi e nelle quali i nodi stabiliscono connessioni temporanee tra loro per il forwarding dei pacchetti utilizzando l’opportunità di connessione offerta da un’altra stazione all’interno del raggio di comunicazione. Nel caso non siano disponibili altri dispositivi nelle vicinanze, il pacchetto viene memorizzato localmente in attesa di una nuova possibilità di spedizione che si verra’ a creare per effetto della mobilità dei nodi. Questa è un’area di ricerca emergente ed una tecnologia promettente per supportare ubiquitous computing. Tuttavia, per consentire che cio’ accada, un grosso sforzo di ricerca è richiesto per progettare sistemi di comunicazione tra nodi che siano flessibili, affidabili ed efficienti. È infatti importante osservare che, in un ambiente opportunistico, mobilità, partizionamento della rete e vincoli energetici impongono un distacco da un’architettura rigidamente gerarchica e da comunicazioni basate sul modello-IP. Nuove architetture e protocolli sono necessari per soddisfare i requisiti di un ambiente di rete radicalmente nuovo. Da una parte, sono necessarie politiche flessibili di routing per adattarsi velocemente alle dinamiche della rete che alterna zone sovraffollate ad altre dove la mancanza di dispositivi porta a partizioni. I protocolli devono essere ottimizzati per assicurare un uso efficiente di risorse limitate e, a questo scopo, l’analisi dei protocolli nel contesto di un modello di mobilità che rifletta propriamente il comportamento di uno scenario reale, sta emergendo con un elemento chiave per la loro progettazione. Inoltre, parametri di contesto, come la densità delle periferiche nell’area, la loro velocità e direzione uniti agli interessi degli utenti, la loro posizione e la disponibilità di risorse del dispositivo possono essere tutte usate per controllare l’instradamento dei pacchetti all’interno di un’area limitata portando al progetto di protocolli di routing sensibili al contesto.
In questo ambito applicativo ed architetturale, CARTOON si occupera' del progetto di protocolli originali per reti opportunistiche e di realizzare un ambiente specifico di simulazione.

2.1.2 OBIETTIVI DELLA RICERCA

Gli obiettivi di questo progetto di ricerca sono la progettazione, l’analisi e la specifica di una nuova architettura e protocolli per reti opportunistiche. L'ambito della ricerca è limitato alle funzioni dei livelli di rete e middleware (figura 1), i quali sono considerati le componenti chiave per la realizzazione di una infrastruttura di rete opportunistica capace di supportare applicazioni dipendenti dal contesto e tolleranti ai ritardi in uno scenario urbano. In linea con questa visione, CARTOON punta a raggiungere un stadio pre-prototipale delle componenti progettate ed a fornire i seguenti contributi generali:

i) progettazione ed analisi di nuovi protocolli ed algoritmi per coprire le esigenze funzionali dei livelli di rete e di overlay;
ii) uno strumento di simulazione specifico per reti opportunistiche, ottenuto dal miglioramento di un ambiente di simulazione esistente ( ns2, OMNeT++ o GloMoSim) e che sarà poi rilasciato alla comunità;
iii) l’analisi e le specifiche architetturali di un dispositivo mobile CARTOON-based che costituiranno l’input ad un successivo programma di ricerca e sviluppo in cui i prototipi verranno valutati in un ambiente reale.


Figura 1. Architettura delle principali componenti considerate in CARTOON.

A seguire, descriveremo gli obiettivi di ricerca principali che saranno dettagliati, in termini di organizzazione e risultati attesi nella sezione 2.3.

A. Specifiche di un’architettura funzionale per reti opportunistiche

I comportamenti delle reti opportunistiche rendono lo stack ISO-OSI non piu’ adatto a loro. Da una parte, l’uso di schemi di indirizzamento basati su IP non sono adeguati ad una massa potenzialmente molto grande di dispositivi solo occasionalmente collegati tra di loro e tipicamente non collegati ad Internet. Il sistema terminale in una comunicazione punto a punto non viene più identificato con un indirizzo IP a valore globale, ma per esempio, perché soddisfa una funzione di somiglianza con una certa risorsa o dato locali. Inoltre, il bisogno di protocolli con componenti leggeri ed altamente adattivi richiede nuove architetture in cui i vari livelli cooperano per condividere informazioni di contesto o dati riguardanti l’uso di risorse locali (si veda ad esempio figura 1). Di conseguenza, la progettazione di un’architettura funzionale non è solo un passo nel ciclo di vita del progetto, ma diventa un obiettivo di ricerca chiave per fornire l’ambiente interoperabile in cui i protocolli possono essere progettati.

B. Progettazione di protocolli di routing e per overlay per reti opportunistiche

Uno dei principali obiettivi di ricerca di CARTOON è la progettazione di meccanismi di rete e di overlay per ottenere un accesso alle informazioni scalabile e auto-organizzato in un ambiente opportunistico. Gli specifici modelli energetici, di mobilità e di fallimento costituiscono la base teorica per la valutazione ed il confronto degli algoritmi.

B1. Protocolli di routing
Nonostante le reti opportunistiche abbiano delle caratteristiche in comune con le reti ad hoc, il loro comportamento particolare rende difficoltosa l’adozione di protocolli di routing tipici di queste ultime per soddisfare i nuovi bisogni (si veda sezione 2.2). La ricerca di CARTOON concentra gli sforzi sull’uso di approcci epidemici e facenti uso di tecniche di gossip che, con i meccanismi di routing geografico, sono considerati più adatti per operare con l’estrema dinamicità della connettività sottostante opportunistica e sono in grado di diventare una componente fondamentale anche per la costruzione di servizi di overlay.

B2. Infrastruttura di overlay
La fornitura di servizi su reti di overlay e’ un problema ampiamente studiato per reti fisse ed in parte anche mobili (si veda § 2.2.) che rimane tuttavia un problema totalmente aperto se applicato alle reti opportunistiche. In questo nuovo ambito, infatti, vanno riprogettati i moduli a controllo distribuito che sono la base fondazionale su cui costruire generici servizi. Per questa ragione, CARTOON privilegia l’identificazione ed il progetto di componenti funzionali elementari allo studio dei servizi ottenibili attraverso di essi. La ricerca si occuperà dunque di fornire meccanismi di base ed efficienti nei tradizionali schemi uno-a-uno e uno-a-molti. In ambito P2P, l’obiettivo principale diventa la disponibilità dei contenuti, la loro raggiungibilità e la capacità di trasferimento robusto nei confronti di partizioni di rete o carenza di risorse. In ambito di gruppo, invece, a dominare sono le problematiche di gestione di una membership, di diffusione sul gruppo in assenza di infrastrutture multicast e di aggregazione spontanea.

C. Strumenti di analisi e simulazione

I protocolli e gli algoritmi distribuiti che il progetto definirà saranno valutati e confrontati con strumenti sia analitici che di simulazione. A questo fine, i ricercatori di CARTOON adotteranno ambienti di analisi e simulazione comuni per assicurare uniformità e comparabilità tra i prodotti della ricerca. I modelli di mobilità e di consumo energetico disponibili in letteratura saranno studiati e, se richiesto, adattati all’ambiente opportunistico in uso. Le componenti software che implementano i modelli selezionati rappresenteranno le librerie da aggiungere all’ambiente di simulazione adottato. Lo strumento di simulazione risultante sarà reso disponibile al resto della comunità di ricerca. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

CARTOON considera un ambiente urbano opportunistico dove veicoli, utenti mobili e dispositivi portatili giocano un triplice ruolo su una rete mobile che fornisce connettività radio all’interno di un’area limitata (ad esempio un quartiere, un campus universitario o un centro commerciale). Infatti, questi dispositivi possono agire come: (i) sistemi terminali per comunicazioni uno-a-uno o uno-a-molti, (ii) nodi per l’instradamento di pacchetti quando altri dispositivi sono disponibili nel raggio di comunicazione e (iii) trasportatori di pacchetti in una cache, quando la rete è partizionata e non ci sono dispositivi nel raggio di comunicazione.

Questi tipi di reti si considerano reti con tolleranza nel ritardo di trasmissione (Delay Tolerant Networks, DTNs) in quanto, in conseguenza della mobilità e del partizionamento della rete, esse possono introdurre lunghi tempi di latenza nella consegna dei pacchetti e sono capaci di offrire solo un semplice servizio di 'consegna eventuale' degli stessi. La Internet Research Task Force (IRTF) ha cominciato solo recentemente a formalizzare le DTN [C+06]. Le attività di CARTOON si collocano all’interno di questo filone di ricerca, benché considerino solo un ambito di architetture di rete limitato; infatti, il progetto è focalizzato su reti mobili che forniscono connettività radio a corto raggio all’interno di un’area limitata, come quelle prese in considerazione in [C+05,H+05,S+04] o applicate in ZebraNet [J+02], dove è facile osservare partizionamenti della rete, e in SPAWN [D+04].

Questa è un’area di ricerca che sta attirando un crescente interesse scientifico a causa delle grandi sfide che comporta e dell’innovazione che richiede. CARTOON si concentra sulle funzionalità di rete e di overlay che coinvolgono i livelli dove sono necessari i maggiori sforzi nel medio termine. Questi livelli appartengono ad una sorta di architettura porosa dove le informazioni di contesto, provenienti dagli strati adiacenti, sono libere di percolare attraverso le interfacce e influenzare il comportamento dei protocolli (figura 1). Quindi, le informazioni energetiche [M+06], la posizione del dispositivo [C03] e altre informazioni ambientali sono utili per ottimizzare l’instradamento dei pacchetti, unitamente alle informazioni aggiornate riguardanti la mobilità degli utenti. Per esempio, è facile far vedere come la conoscenza che un insieme di dispositivi si muove come uno sciame sia altamente utile per consentire una distribuzione efficiente dei pacchetti all’interno dello sciame stesso. Analogamente, le informazioni di contesto legate alle applicazioni possono avere effetto sulla infrastruttura di overlay [A+04,RJH02]. La progettazione di un’architettura dove le informazioni di contesto vengono sfruttate e sono libere di fluire tra gli strati software può portare alla progettazione di protocolli efficienti e specializzati in grado di adattarsi a condizioni di connettività e richieste di applicazioni altamente variabili.

La sensibilità al contesto rappresenta il primo di molti obiettivi e spunti innovativi di questa proposta. Il secondo riguarda i meccanismi di instradamento a livello di rete. Come abbiamo già notato in precedenza, le reti opportunistiche necessitano di un distacco da algoritmi basati sulla topologia progettati per la MANET. In effetti, i classici algoritmi di routing ad hoc, come ad esempio quelli descritti in [RT99], non sono più utilizzabili in quanto essi o fanno uso di flooding oppure sprecano risorse per tenere aggiornate le tabelle di instradamento. Per le reti opportunistiche sono più adatti meccanismi di flooding controllato, come per esempio quelli basati su gossip o su politiche epidemiche, oppure il routing geografico. Descriveremo brevemente entrambi gli approcci qui di seguito.

Il routing basato su posizione sembra essere facilmente applicabile allo scenario preso in considerazione. I nodi non mantengono nessuna informazione sulla topologia; piuttosto, quando una certa destinazione D deve essere raggiunta, il nodo sorgente S recupera la posizione attuale di D tramite un servizio di localizzazione [C03]. S instrada quindi il pacchetto tentando di approssimare il percorso più breve tra la propria posizione attuale e quella di D. I protocolli che adottano questa strategia sono, ad esempio, Greedy Geographic Forwarding [GSB04,KSU99], GPSR [KK00], SAR [T+03], DREAM [B+98] e LAR [KV00]. Essi differiscono per il modello di mobilità considerati (open-space per Greedy Geographic Forwarding e GPSR, vincolato da una mappa stradale per SAR) e nella politica adottata per l’instradamento dei pacchetti (flooding ristretto per DREAM e LAR, punto-a-punto per gli altri). Altri approcci simili sono descritti in [GSB04].

Recentemente è stato proposto un nuovo approccio di routing geografico, basato su percorsi definiti come linee, per scenari dove le caratteristiche fisiche dell’area forzano i terminali mobili a spostarsi lungo percorsi predefiniti. Trajectory Based Forwarding (TBF) [NN03] considera uno schema di instradamento che, in maniera simile a source routing, richiede al nodo sorgente di codificare una traiettoria geografica nell’intestazione del pacchetto. Siccome la sequenza dei nodi da attraversare non è specificata, i pacchetti sono instradati hop-by-hop basandosi sulla posizione dei nodi rispetto alla traiettoria.

Entrambi gli schemi di comunicazione punto-a-punto e punto-a-multipunto possono essere supportati da sistemi di routing geografico. In questo ultimo caso, comunque, l’insieme dei riceventi è normalmente definito come l’insieme di terminali in un’area di destinazione secondo il paradigma di geocast [KV00b,LTLS00].

Tutti gli schemi di routing geografico menzionati prima necessitano di mantenere una lista di nodi prossimi con la loro rispettiva posizione per poter dinamicamente selezionare il miglior nodo verso il quale instradare ogni pacchetto. Un nuovo approccio per l’instradamento geografico sposta la decisione di instradamento dal nodo sorgente al ricevente utilizzando trasmissioni broadcast [ZR03,G+05,BM05,CFFP06].

La rapida presentazione dei sistemi di routing geografico vista prima mette in luce che esiste molta letteratura sull’argomento. E` però importante far notare che i vari approcci non possono essere applicati senza modifiche a questo nuovo scenario; quindi si motiva uno specifico sforzo di CARTOON sul routing geografico. Nonostante questo, è anche chiaro che uno scenario opportunistico è ricco di casi in cui l’indirizzamento diretto di un dispositivo tramite la sua locazione od il suo indirizzo IP non è nè richiesto nè possibile. Sotto queste condizioni, le varianti di strategie di flooding potrebbero essere utilizzate con successo. Recentemente, algoritmi randomizzati [JFP04] sono stati proposti per l’instradamento in DTN, che trattano il problema del routing come un problema di ottimizzazione. I sistemi basati su strategie di gossip sono stati usati congiuntamente a tecniche di cancellazione di codice per garantire affidabilità [W+05], o per aumentare le probabilità di successo utilizzando uno storico degli incontri recenti (approccio history based [W+05,J+02]). Altri approcci adottano tecniche di trasmissioni ridondate di r copie su cammini multipli e algoritmi di ritrasmissione di tipo two hops [C+05,GT02,W+05] derivati dalla teoria della ritrasmissione epidemica [D+87]. Il numero r delle copie è una funzione sia della densità dei nodi sia del modello di mobilità, e permette di trovare un compromesso tra il sovraccarico della rete ed il ritardo di consegna. I primi studi sul gossiping [D+87] hanno sollevato il dubbio riguardo al fatto che questo approccio possa non essere adatto ad ambienti mobili per via della criticità di mantenere una struttura topologica. Oggi è chiaro che gli algoritmi basati su gossip possono essere impiegati in scenari altamente dinamici sotto l’ipotesi di utilizzare informazioni di stato approssimative ed evitare il mantenimento di tabelle di instradamento. In questo modo, il gossiping è estremamente leggero in termini di uso di memoria e capacità computazionale (e presenta un costo di comunicazione più basso del puro flooding) ed è quindi appropriato per dispositivi con forti vincoli energetici. Inoltre, è anche utilizzabile per applicazioni tolleranti ai ritardi, anche se diversi miglioramenti sono necessari, come ad esempio i) la scelta dei nodi coinvolti nella ritrasmissione, ii) la definizione di meccanismi dipendenti dal contesto che siano reattivi agli spostamenti ed alla dinamicità dei dispositivi mobili con lo scopo di ridurre la latenza di trasmissione e di assicurare un uso ottimizzato delle risorse. Oggi, molti di questi algoritmi sono probabilistici; la possibilità di implementarli nella realtà dovrebbe essere valutata. Dovrebbe essere effettuato un confronto tra le diverse soluzioni proposte per mettere in risalto pregi e difetti quando vengono adottate come supporto per applicazioni distribuite su reti opportunistiche. In [LW05] viene presentato un modello analitico per confrontare tra loro tecniche epidemiche rispetto alla loro capacità di disseminare informazioni.

I passi richiesti verso lo sviluppo di applicazioni con tolleranza al ritardo vanno oltre le possibilità offerte da meccanismi di routing efficienti e necessariamente includono una infrastruttura wireless. Le reti di overlay sono un sistema interessante per rendere virtuali le topologie di rete e permettono di ottenere un ambiente per lo scambio dei dati lineare e facilmente utilizzabile dalle applicazioni, mentre tutti i dettagli relativi alla topologia reale ed alla dinamicità delle connessioni vengono nascosti. Con la progressiva adozione delle reti wireless nell'esperienza quotidiana e la loro presenza costante attorno a noi, la creazione di overlay su richiesta e altamente dinamiche sta diventando una necessità. La letteratura relativa alle reti di overlay si concentra normalmente su aspetti di ottimalità e scalabilità [RKV04,H+03,JMW03], mentre pochi sforzi sono stati fatti per investigare aspetti riguardanti la dinamicità di creazione e mantenimento di queste reti.
Fino ad ora, alcune architetture sono già state studiate per reti cablate, mentre un numero limitato di lavori esiste riguardo a overlay su reti wireless. Il gossiping può essere usato anche per operazioni di gestione nelle reti di overlay, come il mantenimento della composizione di un gruppo o la diffusione delle informazioni tra i nodi. In letteratura sono state presentate alcune proposte facenti uso di gossip per la consistenza dei dati al fine di distribuire aggiornamenti periodici ([MJB05], approccio anti-entropy [D+87,VB00]) e istantanei (politica rumor [D+87,BE02]) di un database a uno o più nodi vicini. Inoltre, la distribuzione di contenuti e la condivisione di informazioni tra nodi è un altro problema aperto che ha un effetto marcato sulla rete di overlay che dovrebbe fornire i servizi per organizzare i contenuti, per renderli disponibili e facilmente reperibili. Numerose soluzioni sono già state proposte in letteratura per supportare il reperimento di contenuti secondo un approccio peer-to-peer (P2P) in reti wired. Però il loro utilizzo non è in generale adatto per reti wireless per ragioni di scalabilità. Proposte che adottano un approccio P2P nelle MANET sono ad esempio AdTorrent [N+06], usato per la condivisione di contenuti in reti veicolari con Access Point, e HIGH-GRADE [YLZ04], che adatta Chord -- proposto per reti wired -- all'ambiente wireless allo scopo di mantenere un'infrastruttura di overlay costituita da location server che registrano informazioni riguardo alle posizioni dei nodi. Eventualmente un meccanismo simile potrebbe essere adottato per memorizzare e recuperare informazioni riguardo alla locazione di contenuti, in modo distribuito. In CARTOON verranno sfruttate anche le esperienze pregresse di partecipanti al progetto su sistemi peer-to-peer [CG05, MM05].

Come visto in precedenza, le reti opportunistiche differiscono in maniera significativa dalle reti wireless tradizionali viste fino ad ora. Questo è principalmente una conseguenza di comportamenti di dinamicità e mobilità dei nodi radicalmente diversi. La possibilità di caratterizzare questi comportamenti mediante un modello di mobilità adatto è il punto di partenza per ogni ricerca sull’argomento.
Una grande attività di ricerca sulle reti opportunistiche è fiorita in questi ultimi anni, da quando è stato dimostrato che la mobilità fisica dei nodi facenti la funzione di ripetitori può aumentare in maniera significativa le potenzialità di una rete wireless [GT02]. In [C+05] viene proposto un modello analitico per reti opportunistiche. In [CBD02], alcuni modelli vengono descritti e confrontati rispetto alla loro capacità di rappresentare correttamente il comportamento reale. In [C+03] viene presentato un modello per descrivere la dinamicità della conformazione di un gruppo. In [S+04,H+05] vengono descritte delle sperimentazioni riguardanti monitoraggio e analisi della mobilità umana. Alcuni lavori teorici [SM04,EG+04,LS04] hanno raffinato le idee in [GT02] analizzando le prestazioni di reti opportunistiche usando diverse semplici tecniche di instradamento. Come risultato è stata provata l’esistenza di un compromesso accettabile tra il throughput asintotico (quando il numero di nodi diventa arbitrariamente grande) di una rete wireless con nodi mobili e il tempo di ritardo nella consegna dei messaggi. <<<