logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-10042006-130555


Tipo di tesi
Tesi di laurea specialistica
Autore
Iacopini, Iacopo
Indirizzo email
iacopo@whoopy.it
URN
etd-10042006-130555
Titolo
Progettazione e valutazione di un protocollo di routing dipendente dal contesto per reti di tipo opportunistico
Dipartimento
INGEGNERIA
Corso di studi
INGEGNERIA INFORMATICA
Relatori
Relatore Anastasi, Giuseppe
Relatore Conti, Marco
Relatore Prof. Marcelloni, Francesco
Parole chiave
  • forwarding
  • networking di tipo opportunistico
  • opportunistic networking
  • routing
  • opportunistic
  • context aware routing
  • reti ad-hoc
Data inizio appello
23/10/2006
Consultabilità
Non consultabile
Data di rilascio
23/10/2046
Riassunto
<p><i><b>HiBOp: Progettazione e valutazione di un protocollo di routing
dipendente dal contesto per reti di tipo opportunistico</b></i></p>
<p>L'avvento di dispositivi mobili a basso costo e dalle prestazioni sempre
migliori ha aperto la strada ad una vasta gamma di nuove ed entusiasmanti
applicazioni. La connettività fornita dai telefoni cellulari, dai palmari e dai
laptop consente l’accesso ad informazioni in ogni momento ed in ogni luogo.
Questo tipo di dispositivi introduce problematiche nuove all’interno delle reti,
quali risorse limitate, tempo di vita limitato legato alla durata della
batteria, … </p>
<p>Un building block fondamentale di questa visione sono le reti ad hoc. La rete
Internet tradizionale si basa su una infrastruttura pre-esistente (il core
network) non gestita dagli utenti, cui i nodi si connettono per comunicare tra
loro. Il core network fornisce principalmente servizi di forwarding agli utenti
finali. Una rete ad hoc è invece completamente de-infrastrutturata, nel senso
che elimina la necessità di avere un core network pre-esistente per la
comunicazione. Nel tipico esempio di rete ad hoc, un insieme di nodi
appartenenti agli utenti comunica in maniera wireless e crea in maniera dinamica
l’infrastruttura necessaria per il forwarding dei dati. Ogni computer mobile in
questo scenario fa sì che l’utente sia in grado di comunicare, come nel caso dei
computer collegati alla rete Internet tradizionale. Inoltre, svolge anche le
funzioni di routing e forwarding per gli altri nodi della rete, come i router
fissi fanno nell’architettura Internet. Esempi classici di utilizzo di tali reti
sono community networks, disaster recovery networks, reti di supporto alla
protezione civile, ecc.</p>
<p>Una delle assunzioni di base delle reti ad hoc tradizionali è che due nodi
possono comunicare solamente se è possibile individuare un path multi-hop nella
rete che colleghi i due nodi contemporaneamente uno all’altro. Se tale path non
esiste, i dati inviati tra i due nodi vengono scartati in qualche punto della
rete. Tale assunzione deriva dall’architettura tradizionale di Internet, che
assume una topologia connessa. Però, tale assunzione risulta particolarmente
limitante nelle reti ad hoc, in cui il livello di dinamicità della rete è
chiaramente molto superiore. Una delle evoluzioni più interessanti delle reti ad
hoc sono le reti opportunistiche. In una rete opportunistica le disconnessioni
degli utenti sono viste non come eccezioni, ma come condizioni normali. Dati inviati verso utenti disconnessi non vengono scartati, ma vengono memorizzati temporaneamente sui nodi della rete in attesa che l’utente si riconnetta. Da questo tipo di comportamenti che sfrutta i nodi della rete non solo come forwarder ma anche come portatori deriva il nome di networking opportunistico.<br>
Le reti ad hoc disconnesse corrispondono a scenari applicativi molto diffusi. Ad
esempio è il caso di uno scenario cittadino in cui si hanno gruppi di nodi
isolati tra loro (perché si trovano in una zona distante dal centro della città
oppure in un luogo in cui non è disponibile alcun tipo di connettività), o di
una rete di sensori in cui, per risparmiare le batterie, i dispositivi passano
gran parte del tempo disconnessi o di gruppi di soccorso che si trovano ad
operare in territori in cui l’infrastruttura di rete sia andata distrutta in
seguito ad un evento catastrofico.<br>
<br>
Rilasciare il vincolo di connessione ha un effetto dirompente sul progetto dei
protocolli di rete tradizionali, persino su quelli progettati per reti ad hoc
classiche. Innanzitutto, la rete deve includere molta più “intelligenza”. Se un
utente è disconnesso, la rete deve trovare un sottoinsieme di nodi adatti a
bufferizzare i messaggi per lui. Inoltre, la mobilità in questo scenario diventa
un alleato, perché consente alla rete di raggiungere nodi che altrimenti
diventerebbero disconnessi. È chiaro che in particolare gli algoritmi di routing
e forwarding cambiano in maniera radicale. In un certo senso, in una rete
opportunistica si integrano a livello di rete funzionalità che in alcune
applicazioni Internet erano relegate al livello applicativo. La posta
elettronica è un esempio di applicazione che supporta la disconnessione degli
utenti. Le reti opportunistiche estendono questo concetto, lo inseriscono nelle
caratteristiche fondamentali della rete in modo che tutti i protocolli ne siano
consapevoli.</p>
<p>Le tipologie di forwarding per questo tipo di reti sono principalmente due.
Un approccio è quello di consegnare il messaggio a tutti i nodi vicini, che a
loro volta lo instraderanno a tutti i loro vicini, e così via. Questa è la
soluzione scelta dai protocolli di forwarding basati sulla disseminazione dei
messaggi. L’altra soluzione è quella di valutare la validità di un nodo come
next hop in base alla probabilità del nodo di incontrare la destinazione. Per
far questo è necessario che ogni nodo tenga memoria della storia dei suoi
contatti con gli altri nodi. Gli algoritmi che adottano questa soluzione vengono
chiamati context-based, cioè basati sul contesto. Ovviamente la soluzione più
semplice è quella basata sulla disseminazione dei messaggi, che però presenta un
problema intrinseco, ovvero la massiccia occupazione delle risorse di memoria
dei nodi e delle risorse trasmissive della rete. Pertanto negli ultimi tempi
l’attenzione si è spostata sul trovare una soluzione ottimale per la valutazione
del contesto di un nodo, a partire dal quale si va poi a impostare una politica
di forwarding dei messaggi.<br>
In particolare, in alcuni tipi di reti mobili disconnesse, chiamate Pocket
Switched Networks, in cui i dispositivi mobili sono portati da umani, il
problema del contesto del nodo si trova ad essere inscindibilmente legato alle
caratteristiche proprie della mobilità e delle abitudini degli individui
associati ai dispositivi. Ne consegue che il concetto di contesto può includere
al suo interno informazioni di alto livello sulle abitudini e le esperienze
dell’individuo portatore del dispositivo. Questa considerazione si inserisce
all’interno di un nuovo modo di vedere le reti mobili che ha ispirato nuove
architetture di rete, come l’architettura HAGGLE. I principi base di queste
nuove soluzioni mettono l’utente e i suoi dati al centro del processo di
networking, introducendo paradigmi innovativi per quanto riguarda
l’indirizzamento (che adesso si compone di un insieme di informazioni di alto
livello sull’utente che possiede il dispositivo), la diffusione delle
informazioni (es. i nodi intermedi possono analizzare i pacchetti che ricevono e
decidere di memorizzare quelli contenenti informazioni a loro utili, come pagine
Web, etc…) e i metodi di trasferimento dei dati (vengono utilizzati tutti i tipi
di connettività disponibili). Tali architetture di rete sono intrinsecamente
cross-layer, nel senso che la tradizionale separazione tra i livelli dello stack
viene re-interpretata e spesso evitata. È chiaro come instradare traffico in
queste reti richieda non solo informazioni topologiche, ma informazioni
applicative e, più in generale, di contesto. È più corretto in questo caso
parlare di funzionalità implementate sul nodo ed interagenti tra di loro, che di
stack di protocolli. Ogni funzionalità è libera di accedere ad informazioni che
tradizionalmente risiedono a livelli di rete differenti. Per avere un sistema
portabile e manutenibile, è necessario individuare interfacce ben definite tra
funzionalità, in modo da non perdere la tradizionale portabilità delle
architetture Internet.</p>
<p>Prendendo spunto dai principi sopra esposti, l’obiettivo di questa tesi è
l’esplorazione delle potenzialità di algoritmi di routing e forwarding basati su
ampie informazioni di contesto in reti opportunistiche. Viene trattata la
costituzione del contesto dei nodi come magazzino di informazioni di alto
livello e la progettazione di un protocollo di forwarding basato su queste
informazioni. In particolare per ogni nodo vengono mantenute separatamente
informazioni sul suo presente (dove si trova, con chi è in contatto, …) e sulla
sua storia (luoghi frequentati spesso, nodi incontrati, …). Le informazioni sul
passato del nodo vengono utilizzate per fare previsioni sui suoi comportamenti
futuri, in base alla considerazione che l’uomo è un animale sociale ed
abitudinario e quindi tenderà a incontrare di nuove le stesse persone e a
frequentare gli stessi posti in cui è già stato in passato. In base all’analisi
delle abitudini del nodo è possibile valutare la sua probabilità di incontrare
un altro nodo o di trovarsi nello stesso posto in cui esso si trova. La politica
di forwarding non fa altro che analizzare le abitudini e l’ambiente di un nodo e
valutare se questi sono favorevoli o meno al raggiungimento della destinazione
del messaggio da instradare. Tale approccio si rivela effettivamente
estremamente efficiente, sulla base dei risultati ottenuti e presentati in
questa tesi. In particolare, abbiamo trovato che i nostri algoritmi basati sul
contesto sono in grado di ridurre drasticamente il consumo di risorse dei nodi
(in termine di banda e memoria utilizzata), senza degradare significativamente,
rispetto ad algoritmi basati su disseminazione, la qualità del servizio offerta
all’utente in termini di ritardo nella consegna dei messaggi e di probabilità di
consegna dei messaggi stessi.<br>
</p>
File