Routing Protocol

Capitolo 3

Analisi dei protocolli di routing

3.1 Protocolli di routing

In questo capitolo verr data una classicazione degli algoritmi di instrada-

mento descrivendo dettagliatamente alcuni possibili protocolli che permet-

tono di fare routing all'interno di una rete MANET.

Verr inoltre spiegato il motivo per cui dopo aver visionato molti protocolli

di routing si scelto di implementare l'algoritmo Reactive DSR (Dynamic

Source Routing).

3.2 Organizzazione della rete

La topologia di una rete MANET pu essere o di tipo gerarchica o di tipo

piatta.

In una rete gerarchica i nodi sono suddivisi in gruppi, denominati cluster. Per

ogni cluster viene selezionato un cluster head

1

, attraverso il quale passa tutto

il traco della rete. Nell'utilizzo di una rete gerarchica vi un vantaggio,

cio quello di minimizzare il numero di pacchetti di routing scambiati tra i

nodi di uno stesso cluster, e anche tra i vari cluster head.

In una rete piatta invece non esiste nessun tipo di centralizzazione, cos da

permettere di stabilire pi di un percorso tra il nodo sorgente e il nodo

destinazione. Questo un vantaggio perch in tal modo si possono valutare

diverse metriche per stabilire il peso di un collegamento, a seconda delle

richieste di utilizzo della rete stessa.

Di seguito verranno presentati gli algoritmi di instradamento, spiegando quali

sono i vantaggi e gli svantaggi nel loro utilizzo.

1

Identica il nodo a capo di un cluster che organizza i compiti degli altri componenti

del gruppo.

31


3.3 Algoritmi di instradamento

Gli algoritmi di instradamento possono essere classicati in base alle politiche

che adottano per adempiere ai loro compiti; tale politiche possono essere:

Organizzazione della rete. Modalit di reperimento delle informazioni di instradamento. Modalit con cui viene deciso il percorso verso il nodo destinazione.

Classicazione in base all'organizzazione della rete La rete pu

essere organizzata in maniera:

uniforme, in cui lo scambio di informazioni di routing avviene tra tuttii nodi

2

allo stesso modo;

non uniforme, dove cio ogni nodo risponde e genera informazioni dirouting in modo diverso a seconda del suo ruolo. I nodi che com-

pongono la rete non uniforme possono essere a loro volta suddivisi,

a seconda dei compiti che svolgono all'interno della rete, in Neighbor

Selection o Hierarchical.

La Figura 3.1, mostra la suddivisione della rete nelle due diverse tipologie

appena citate.

Nel primo caso il nodo X comunica con il nodo Y passando per nodi inter-

medi, che svolgono le stesse operazioni di instradamento (infatti per marcare

proprio il fatto che i nodi sono tutti uguali e svolgono le medesimi operazioni

si utilizzata la stessa segnatura per rappresentarli).

Nel secondo caso la non uniformit della rete viene rappresentata attraverso

la dierenziazione dei nodi all'interno dei tre involucri (nodo pieno, nodo

vuoto, rappresentano i diversi compiti che un nodo pu assumere).

Classicazione in base alla modalit di reperimento delle infor-

mazioni di instradamento Il reperimento delle informazioni pu avvenire

in modalit Proactive (detta anche Table-Driven) o in modalit Reactive

(detta anche On-Demand).

In modalit Proactive i nodi si scambiano informazioni di routing a interval-

li ssi di tempo; questa caratteristica permette che ci sia un instradamento

immediatamente disponibile ad ogni richiesta di routing; purtroppo per ci

comporta un elevato traco di segnalazione.

In modalit Reactive, viene invocata una procedura per determinare il cor-

retto instradamento solo se si vuole trasmettere un pacchetto. Ci porta

ad avere un ritardo nella trasmissione dei pacchetti dati, riuscendo per ad

2

D'ora in avanti si assumer che il termine nodo, device, host, terminale rappresentano

la stessa cosa.

32

3.4 Suddivisione dei protocolli di routing

Rete uniforme Rete non uniforme

Sorgente

Destinazione

Sorgente

Destinazione

Figura 3.1: Organizzazione della rete

abbassare notevolmente il traco di segnalazione.

Nel paragrafo 3.4 verr ulteriormente approfondito questo aspetto.

Classicazione in base alla modalit con cui viene deciso il per-

corso verso il nodo destinazione Il percorso verso il nodo destinazione

pu essere ottenuto attraverso un approccio source routing, in cui il nodo

sorgente determina l'esatto percorso che il pacchetto dati deve eseguire, per

raggiungere la destinazione, oppure non source routing, dove l'unica infor-

mazione di routing il next-hop

3

: ciascun nodo decide in modo indipendente

a chi ritrasmettere il pacchetto anch questo raggiunga la destinazione.

3.4 Suddivisione dei protocolli di routing

I protocolli di routing [8] forniscono il corretto percorso che un pacchetto deve

compiere, dal nodo sorgente al nodo destinazione, cercando di adattarsi il

pi possibile ai mutamenti topologici della rete.

Essi possono essere suddivisi in tre distinte categorie:

Proactive. Reactive. Hybrid.I protocolli Proactive mantengono aggiornate le informazioni riguardanti l'in-

stradamento tramite continui scambi di pacchetti ad intervalli ssi.

3

Identica il salto ad un dispositivo, dentro il range trasmissivo.

33


Questa tecnica permette di avere sempre disponibile, l'instradamento ad o-

gni richiesta.

L'immediata risposta pu risultare un vantaggio, ma ci determina un note-

vole traco di segnalazione; pu capitare infatti che la rete venga impegnata

anche quando non vi alcuna richiesta di trasmissione dati.

Nei protocolli Reactive, viene invocata una procedura per determinare il cor-

retto instradamento solo ed esclusivamente nel momento in cui il pacchetto

deve essere trasmesso.

Anche se la trasmissione dei pacchetti dati avviene in modo pi lento rispetto

ai protocolli Proactive, ci permette di avere un minor impegno della rete,

dovuto al basso traco di segnalazione.

I protocolli Hybrid, invece, cercano di unire i vantaggi di entrambi i protocolli

precedentemente descritti, ma presentano problemi a livello implementativo.

La Figura 3.2 mostra una sorta di albero gerarchico, in cui i primi gli

della radice (Routing Protocols) rappresentano le famiglie degli algoritmi

Proactive, Reactive e Hybrid, scendendo nei due livelli sottostanti vi la

classicazione dell'organizzazione di rete, come descritto nel paragrafo 3.3,

ed in ultimo menzionati gli attuali protocolli di routing di cui se ne parler

pi avanti.

Figura 3.2: Algoritmi di instradamento

34

3.5 Algoritmi Proactive


Negli algoritmi Procative (anche denominati Table-Driven) i dispositivi mo-

bili, facenti parte di una rete MANET, si scambiano informazioni ad intervalli

di tempo ssati; per tale motivo l'instradamento immediatamente disponi-

bile ad ogni richiesta di routing.

L'idea di mantenere costantemente aggiornate tutte le informazioni di in-

stradamento, tra tutti i dispositivi che compongono la rete. I protocolli che

fanno parte di questa famiglia sono i seguenti:

DSDV Destination Sequenced Distance Vector.

WRP Wireless Routing Protocol.

CSGR Cluster Switch Gatewey Routing.

STAR Source Tree Adaptive Routing.

Caratteristiche comuni dei protocolli Proactive I protocolli che fan-

no parte della famiglia Proactive sono accomunati dalle seguenti caratteris-

tiche:

Scambio di pacchetti ad intervalli ssi.

Uso di tabelle.

Aggiornamento delle tabelle.

Scambio di pacchetti ad intervalli ssi Come si accennato nel para-

grafo 3.5 i protocolli Proactive hanno la propriet di poter permettere ai

componenti della rete di avere a disposizione le informazioni di routing (es.

come raggiungere la destinazione, quale sono i dispositivi che in un determi-

nato istante sono non raggiungibili etc.) sempre pi aggiornate.

Tale meccanismo possibile poich i dispositivi, senza alcuna necessaria

richiesta, si scambiano tra loro pacchetti informativi.

I pacchetti rivelano, sia le informazione di instradamento sia i relativi cam-

biamenti topologici della rete.

Uso di tabelle L'uso di una o pi tabelle che memorizzano tutte le in-

formazioni riguardanti la topologia della rete una caratteristica peculiare

della classe Proactive: tutti i protocolli in precedenza menzionati ne fanno

uso.

In dettaglio andremo ad esaminare sia qual' in breve il funzionamento e sia

quali tabelle utilizzano i quattro protocolli inizialmente citati.

35


DSDV. Il protocollo DSDV, assegna ad ogni nodo una routing-table, nella

quale sono memorizzate tutte le possibili destinazioni raggiungibili da un

dispositivo e tutti i numeri di salto

4

.

Il protocollo si avvale anche dell'aiuto di una sequenza di numeri, che per-

mette ad un utente mobile di eettuare una distinzione tra un route

5

vecchio

rispetto ad uno nuovo.

WRP. Il protocollo WRP si libera del problema count-to-innity

6

forzando

ogni nodo a compiere dei severi controlli sulle informazioni riportate dai nodi

vicini

7

.

Tutti i dispositivi cercano di evitare cicli all'interno della rete e forniscono

percorsi alternativi quando si di fronte ad un link failure

8

. Ogni nodo

mantiene quattro tabelle:

distance-table, segnala il numero di salti tra un nodo e la destinazionerichiesta.

routing-table:, indica il nodo next hop. link cost-table, indica il ritardo associato ad un particolare link. message retrasmission list table, tabella che nel suo interno mantieneun numero di sequenza del messaggio d'aggiornamento, un contatore

di ritrasmissione, un ag richiesto per il riconoscimento e un elenco

degli aggiornamenti mandati nel messaggio di update.

CSGR. Il protocollo CSGR si avvale del concetto di gerarchia (citato nel

paragrafo 3.2), i nodi vengono suddivisi in gruppi, denominati cluster, ed

ogni gruppo ha il suo cluster head. I cluster head hanno il controllo di pi

dispositivi all'interno del gruppo. Per eleggere un cluster head all'interno di

un cluster si usa un algoritmo. Sebbene il cluster head ore servizi e varie

forme di controllo e di coordinamento, ci pu essere usufruito solo da quei

dispositivi che si trovano all'interno dello stesso cluster.

Durante tutta la durata della sessione, non detto che si debba sottostare

allo stesso cluster head; quanto il cluster head risulta spento o irraggiungi-

bile, un algoritmo si preoccuper di scegliere un altro cluster head.

Il fatto che un cluster head possa cambiare frequentemente per dierenti

4

Determina quanti nodi, bisogna contattare per raggiungere la destinazione.

5

D'ora in avanti si assumer che il termine route, percorso, cammino rappresentino la

stessa cosa.

6

E' un eetto del Distance Vector, nel quale i router non si accorgono che una desti-

nazione diventata irraggiungibile, ma credono che sia ancora attiva anche se riconoscono

che la sua distanza sta aumentando sempre di pi.

7

Dispositivi che si trovano nel range trasmissivo del dispositivo mittente.

8

Si verica quando un link fallisce.

36


motivazioni, pu causare problemi per quei dispositivi che invece di inviare

i dati alla destinazione, cercano di convergere verso quel cluster head, cau-

sando dei rallentamenti di trasmissione all'interno della rete.

Il degrado delle prestazioni, dovuto ai continui cambiamenti di cluster head,

viene tenuto a freno dall'algoritmo LCC; tale algoritmo aerma che si pu

cambiare cluster head soltanto se:

sono presenti due cluster head nello stesso cluster; un nodo si sposta ed esce dal raggio d'azione di qualsiasi cluster head.Pur essendoci una divisione dei nodi in cluster, questo protocollo non esclude

la comunicazione con altri cluster. Infatti il nodo sorgente che fa parte di

un determinato cluster, invia un pacchetto al suo cluster head, questo a sua

volta invia il pacchetto al gateway

9

che si occuper di inviare il pacchetto

ad un altro cluster head. Questa iterazione continua nch non si arriva a

contattare il cluster head del nodo di destinazione.

Nella Figura 3.3. viene mostrata la comunicazione tra tre cluster head.

C1

C2C3

Figura 3.3: Comunicazione di tre cluster head nel protocollo CSGR

Il protocollo CSGR usa il protocollo DSDV, come schema sottostante di rout-

ing ed inoltre viene utilizzato un approccio gerarchico per gestire il traco

9

Nodo che nel range di due o pi cluster head.

37


dalla sorgente alla destinazione.

Ogni dispositivo deve mantenere:

cluster member table; memorizza i cluster head di destinazione di og-ni dispositivo, inoltre la tabella viene trasmessa periodicamente dal

protocollo DSDV.

routing table; determina il next hop per raggiungere la destinazione.

STAR. Il protocollo STAR appartiene alla famiglia dei protocolli Proac-

tive. Ma, a dierenza degli altri che mantengono le informazioni in apposite

tabelle, si avvale dell'aiuto del source-tree

10

, ovvero di una struttura che

mantiene informazioni sui nodi indicante il percorso per giungere a desti-

nazione.

In dettaglio il source-tree altro non che un grafo (albero), in cui il primo

nodo (la sorgente) il richiedente di un percorso, e gli altri nodi sono i suoi

vicini. Scorrendo lungo il grafo si pu giungere, se presente, al nodo di

destinazione.

Nella Figura 3.4 viene mostrato il source-tree tra un nodo A e un nodo B.

Si pensi a questo generico scenario: il nodo A vuole poter comunicare con il

nodo B; per prima cosa A verica la presenza del nodo B nel suo source-tree

e in caso aermativo A instrada il pacchetto da trasmettere nel suo albero

dei percorsi, raggiungendo il nodo B.

Aggiornamento delle tabelle L'aggiornamento delle tabelle di routing

una qualit fondamentale di questa classe di protocolli, ci fa si che gli utenti

che optano nella scelta di questi protocolli, possano avere a disposizione una

rete consistente.

Di seguito verr descritto come avviene l'aggiornamento delle tabelle nei sin-

goli protocolli di routing.

DSDV. Il protocollo DSDV tiene periodicamente aggiornare le tabelle in

modo da mantenere la consistenza all'interno della rete.

L'aggiornamento delle informazioni pu avvenire in due modi dierenti:

aggiornamento timer driver, in cui i dispositivi periodicamente trasmet-tono le loro routing table ai nodi vicini per mantenere le tabelle con-

sistenti;

aggiornamento event driver, dove un nodo invia la sua tabella a causadi un improvviso cambiamento della stessa.

10

Albero di percorsi.

38


Percorso ad albero di B

Percorso ad albero di A

AB

Figura 3.4: Protocollo STAR

Gli aggiornamenti delle table-driven possono essere fatti o tramite full dump

o incremental update; il primo utilizzato per inviare tutte le informazioni

di routing disponibili, il secondo invece viene usato quando ci sono pochi

cambiamenti rispetto all'ultimo full dump.

WRP. In generale un dispositivo, per mantenere informazioni di routing

accurate, periodicamente scambia con i suoi vicini le routing-table, usando

messaggi di aggiornamento.

Un messaggio di aggiornamento possiede al suo interno:

il nodo di destinazione, la distanza dalla destinazione, il predecessore.Quando i vicini ricevono messaggi di aggiornamento, sono tenuti ad inviare

una risposta di avvenuta ricezione del messaggio.

In caso non vengano rilevati cambiamenti all'interno della rete, ogni nodo

tenuto comunque ad inviare un messaggio di Hello

11

.

11

Il messaggio di Hello notica la presenza del nodo all'interno della rete.

39


Un aspetto interessante che coinvolge tutti i dispositivi della rete, si verica

nella ricezione delle routing-table; infatti i dispositivi vericano se le routing-

table ricevute contengono percorsi migliori rispetto a quelli memorizzati nelle

loro routing-table. In caso aermativo automaticamente i dispositivi mem-

orizzano il percorso nella loro routing-table. In caso negativo non viene

eettuato nessun aggiornamento.

CSGR. Il protocollo CSGR pur appartenendo alla famiglia dei Proactive

non usa messaggi di aggiornamento, poich i cambiamenti topologici della

rete possono essere derivati solo dai movimenti improvvisi del cluster head,

di cui se ne occupa l'algoritmo LCC

STAR. Il protocollo STAR, non tenta di orire percorsi ottimi per rag-

giungere la destinazione. E' per questo motivo che il protocollo non esegue

periodici aggiornamenti, per la memorizzazione dei percorsi.

Solo in un caso i nodi sono tenuti a svolgere aggiornamenti, ovvero quando

la topologia della rete cambia frequentemente. A questo punto tutti i nodi

coinvolti nel cambiamento sono tenuti ad inviare messaggi di aggiornamento,

proprio per evitare la presenza di guasti.

E' evidente che lo scambio di messaggi di aggiornamento comporta un note-

vole traco di rete, ma ci essenziale per mantenere la validit di un source

tree.

Vantaggi dei protocolli Proactive I vantaggi che ore la famiglia dei

protocolli Proactive sono i seguenti:

permettere di avere immediatamente disponibile l'instradamento dipacchetti informativi anche se non si eettua una specica richiesta,

avere un'immediata risposta ai cambiamenti topologici della rete, risul-ta essere un'agevolazione soprattutto in situazioni di poca copertura

radio.

Detto ci andiamo a vedere quali facilitazioni potrebbero portare i quattro

protocolli, se un utente dovesse sceglierli.

DSDV. I vantaggi che ore il protocollo Proactive DSDV sono inerenti

sia alla consistenza della rete, nel tenere frequentemente aggiornate le table-

driven, sia nel tentare di evitare i cicli all'interno di una rete. Inoltre an-

che il continuo aggiornamento delle tabelle sicuramente fornisce un notevole

miglioramento riguardo le informazioni topologiche.

40


WRP. Il protocollo WRP ha come pregio quello di comportarsi molto bene

quando si verica un link failure; infatti, se i dispositivi riescono in un arco di

tempo, a scoprire la rottura del link, questi inoltrano ai nodi vicini un mes-

saggio di aggiornamento, permettendogli di modicare le loro distance-table.

CSGR. 'unico merito che si pu asserire al protocollo CSGR che stato

pensato per agevolare quelle reti dove il numero dei dispositivi elevato.

STAR. Il protocollo STAR usa un source-tree per mantenere le infor-

mazioni relative ai suoi vicini; ci consente di non eettuare aggiornamenti

periodici.

Svantaggi protocolli Proactive Nei protocolli Proactive le problem-

atiche che si evincono sono le seguenti:

eccessivo scambio di messaggi informativi;

elevato traco di segnalazione.

Di seguito vengono riportati gli ulteriori svantaggi che i singoli protocolli

portano alla rete. Non verr menzionato il protocollo DSDV, che in sostan-

za accusa gli stessi problemi appena descritti.

WRP. Come stato precedentemente esposto il protocollo WRP possiede

quattro tabelle per immagazzinare tutti le informazioni inerenti alla rete.

Purtroppo questa propriet risulta essere uno svantaggio, se si pensato di

utilizzare dispositivi mobili come PDA, Smartphone, ect. poich hanno una

memoria abbastanza limitata (circa 128MB).

Inoltre a suo sfavore c' anche l'eccessivo scambio di messaggi di aggiorna-

mento.

CSGR. Notevoli svantaggi nell'utilizzo di questo protocollo sono dovuti

ai continui cambiamenti dei cluster head. Per tale motivo capita che i nodi

passino pi tempo a determinare se un cluster head risulta irraggiungibile

o addirittura spento, piuttosto che preoccuparsi ad instradare il pacchetto

informazione.

41


STAR. Il protocollo STAR ha come pecca quella di non preoccuparsi min-

imamente di orire ad un nodo, il percorso il pi breve.

Purtroppo altrettanto dicile determinare la procedura di reperimento di

un percorso, quando questo non presente nel source-tree.

3.6 Algoritmi Reactive

A dierenza dei protocolli Proactive, i protocolli Reactive creano i percorsi

On-Demand, ossia solo quando un nodo ne fa esplicitamente richiesta.

Tale propriet risulta essere un grande vantaggio, poich nelle reti MANET

insito il concetto di mobilit. Data l'alta possibilit di spostamento dei sin-

goli dispositivi, i percorsi che si vengono a formare cambiano in continuazione

ed per questo motivo che risulta inutile e controproducente mantenere in

anticipo tutti i route esistenti tra di essi.

I protocolli che ne fanno parte di questa famiglia sono i seguenti:

AODVAd Hoc On-Demand Distance Vector Routing. DSR Dynamic Source Routing . TORA Temporally Ordered Routing Algorithm. SSR Signal Stability Routing. LAR Location-Aided Routing. PAR Power-Aware Routing . RDMAR Relative Distance Microdiverity Routing .Del protocollo DSR verr riportata una descrizione pi dettagliata nel para-

grafo 3.8. Grazie alle sue caratteristiche (l'utilizzo di una route cache, la

determinazione di un link failure attraverso l'operazione di Route Maninte-

nance, l'eliminazioni dei cicli all'interno della rete per mezzo dei pacchetti

RREQ, RREP,RRER) esso stato scelto come lavoro della seguente tesi.

Caratteristiche comuni dei protocolli Reactive I protocolli Reac-

tive, per inviare un pacchetto da un nodo sorgente ad un nodo destinazione

eseguono i seguenti passi:

scoperta del percorso tramite Route discovery; mantenimento del percorso tramite Route Manteinence; cancellazione del percorso con Route Deletion.Di seguito verr spiegato il funzionamento e la fase di ricerca del percorso

(Route Discovery) dei singoli protocolli Reactive.

42


Fase di Route Discovery nei protocolli Reactive La fase di Route

Discovery il fulcro dei protocolli Reactive.

Tale procedura riesce a determinare, quando un nodo lo richiede, i molteplici

percorsi per arrivare a destinazione.

Di ogni protocollo si andr a descrivere la seguente fase.

AODV. La ricerca di un percorso nell'algoritmo AODV avviene in tal mo-

do: quando il nodo sorgente richiede un percorso per giungere al nodo di

destinazione, il nodo sorgente inizia una fase di ooding

12

.

Questa richiesta pu arrivare sia direttamente a destinazione, sia ad un nodo

intermedio, il quale deve essere in possesso di un'informazione suciente-

mente aggiornata.

Una volta che un nodo (sia un nodo intermedio sia il nodo destinazione)

riceve una richiesta, deve immediatamente rimandare al nodo sorgente una

risposta, la quale indica l'avvenuta ricezione dell'informazione. Ci pu es-

sere fatto utilizzando il percorso inverso.

Per essere certi di costruire percorsi sia senza loop

13

, sia contenenti infor-

mazioni aggiornate, ogni nodo mantiene un numero di sequenza.

Tale numero univoco per ogni percorso ed per questa ragione che viene

ogni volta incrementato, cos che un nodo riesca a capire se ne gi in pos-

sesso.

Entrando pi nel dettaglio, quando il nodo sorgente richiede un route, oltre

ad eettuare una richiesta di scoperta dei vicini

14

, invia un pacchetto RREQ

(Route Request) che rappresenta l'instanza di un percorso per giungere a des-

tinazione.

Se alla prima iterazione si riesce a contattare la destinazione, la fase di

Route Discovery termina qui. Altrimenti viene eettuato l'invio dei pacchet-

ti RREQ anche dai nodi intermedi, che contattano altri nodi a loro adiacenti,

nch si raggiunge il nodo richiesto.

Il pacchetto RREQ viene identicato dal:

broadcast ID, che viene incrementato ad ogni richiesta di percorso,

l'indirizzo IP del nodo sorgente.

Per concludere nella Figura 3.5 viene mostrata l'operazione di Route Dis-

covery, in cui il nodo uno (N1) inoltra una richiesta a tutti i suoi vicini (ci

viene determinato dall'orientamento delle frecce), che a loro volta spediscono

pacchetti RREQ giungendo a destinazione.

12

Il mittente propaga in tutta la rete una richiesta per arrivare ad nodo destinazione.

13

Cicli all'interno della rete.

14

Fase necessaria ad un dispositivo per capire quali nodi appartengono al suo range

trasmissivo. In questa fase vengono spediti dei pacchetti informazione, che contengono:

l'indirizzo IP del mittente, indirizzo IP della destinazione, il numero di sequenza.

43


Data la bidirezionalit dei link, una volta raggiunta la destinazione, quest'ul-

tima rimander tramite un percorso inverso (nel caso proposto il pi corto,

ma non sempre detto) un pacchetto RREP (Route Reply) contenente il

percorso (insieme di indirizzi IP dei nodi) che stato fatto per giungere ad

essa.

N2

N1

N3

N4

N6

N7

N8N5

Sorgente

Destinazione

Route Discovery

N2

N1 N4

N5

N6N3

N8

N7

Sorgente

Destinazione

Percorso inverso

Figura 3.5: Protocollo AODV

TORA. Di seguito verranno descritte le tre funzionalit base che si dif-

ferenziano (solo per il nome) dalle tre fasi standard inizialmente menzionate.

Esse sono:

Route Creation, stabilisce una sequenza di link diretti dalla sorgentealla destinazione.

Route Maintenance reazione ai cambiamenti topologici della rete perristabilire percorsi dentro un certo tempo.

Route Erasure, si verica quando vengono scoperte partizioni della reteper questo motivo i percorsi coinvolti devono essere cancellati. In tali

casi vengono trasmessi dei clear-packet per noticare che i percorsi

devono essere cancellati.

Durante le prime due fasi viene costruito il grafo (denominato DAG Direct

Aciclic Graph), ed assegnate le direzioni (upstream-downstream) ai link.

La terza fase utile nel momento in cui i nodi all'interno di una rete si

spostano frequentemente. La Route Maintenance infatti cerca proprio di

garantire l'aggiornamento del DAG.

44


La scoperta di un percorso nell'algoritmo TORA avviene tramite la costruzione

di un grafo aciclico (il DAG si estende dal nodo sorgente al nodo desti-

nazione). La sorgente identica la radice del grafo: per questo motivo che

la sua altezza pari a zero; mentre gli altri nodi del DAG hanno altezza pari

al numero di nodi da attraversare per giungere a destinazione. Tora ore

percorsi multipli per ogni coppia sorgente/destinazione.

In questo modo l'algoritmo trova potenzialmente pi di un percorso per ar-

rivare alla destinazione, cosicch la manutenzione dei percorsi in caso di un

guasto o di uno spostamento notevolmente semplicata.

Infatti nella maggior parte dei casi non bisogna ripartire con la richiesta di

un nuovo percorso, ma si utilizza uno di quelli rimasti. Questa fase viene

svolta dalla Route Maintenance.

SSR. L'operazione di Route Discovery avviene col la selezione di percorsi,

in base alla forza del segnale. Il protocollo SSR formato da due protocolli

cooperativi che sono:

DRP Dynamic Routing Protocol SRP Static Routing ProtocolDRP responsabile di monitorare e mantenere sia la stabilit del segnale

SST (Signal Stability Table) sia la tabella di routing RT (Routing Table).

Tutte le trasmissioni sono ricevute e processate dal protocollo DRP, il quale

si preoccupa di aggiornare le due tabelle. Conclusa questa fase, DRP rimane

in attesa nch non riceve i pacchetti dati dal protocollo SRP, che ha come

compito quello di processare tali pacchetti.

Un'altra fase importante del protocollo SSR la gestione dei link failure.

Quando un link fallisce dentro la rete, i nodi intermedi sono tenuti ad inviare

messaggi di errore, per segnalare al nodo che ha iniziato la fase di Route

Discovery qual il canale di comunicazione che ha fallito.

Una volta ricevuti questi cambiamenti, il mittente inizier la ricerca di un

nuovo percorso per giungere a destinazione.

Data la logica del protocollo, se si riesce ad arrivare al nodo destinazione dopo

l'avvento di un link failure, la sorgente tenuta a trasmettere in broadcast

a tutti i nodi tale notica.

LAR. Il protocollo LAR si avvale del GPS

15

[6], per determinare qual la

posizione di un determinato dispositivo.

Vengono deniti inoltre due concetti, ovvero:

request zone: zona richiesta,15

GPS l'abbreviazione di Global Positioning System (Sistema Globale di Rilevamento

della Posizione) una rete di satelliti lanciata, per uso Militare, dagli USA che viene ora

utilizzata in tutto il Mondo.

45


expected zone: zona supportata.

Expected Zone(Xd+ R,Yd+R)

Destinazione(Xd,Yd)

Sorgente(Xs,Ys)

R

Request Zone

Figura 3.6: Protocollo LAR

Questo protocollo fa delle severe assunzioni.

Come prima cosa si assume che il mittente sappia la posizione della desti-

nazione e la velocit di trasmissione per giungervi.

Inoltre nella zone expected viene denito sia la posizione del nodo di desti-

nazione sia la velocit di trasmissione per giungere a destinazione.

Nella Figura 3.6 tale zona individuata dal rettangolo pi piccolo, mentre la

request zone dal rettangolo pi grande, in esso sono inclusi sia la posizione del

mittente (Xs,Ys) sia la zone expected contenente il nodo di destinazione(Xd,

Yd).

LAR limita la ricerca di un nuovo percorso in un'area ristretta, cos da ridurre

il traco di segnalazione.

PAR La scoperta di un percorso nell'algoritmo PAR vincolata dal livello

di batteria dei singoli dispositivi. Ci viene preso come metrica di routing.

In tale algoritmo si cerca di:

minimizzare l'energia che si consuma per inviare un pacchetto,

massimizza il tempo prima che venga partizionata la rete,

46


minimizza la varianza in un nodo, minimizza il costo per pacchetto, minimizza il massimo costo di un nodo.Come viene evidenziato dalla Figura 3.7, il processo di Route Discovery si

basa sulla scoperta di un percorso in cui il livello della batteria pi elevato.

Verr scartato infatti il cammino dove presente un dispositivo, in cui il

livello di batteria molto basso.

L'utilizzo di questo algoritmo quindi non da consigliare in una rete com-

posta dai soli dispositivi quali PDA e Smartphone.

-

+

-

+

-

+

+

-

+

-

+

-

+

Figura 3.7: Protocollo PAR

RDMAR. Il protocollo di routing RDMAR basato sul calcolo della di-

stanza stimata tra i nodi, limitando cos il ooding di pacchetti nella fase di

Route Discovery.

In RDMAR si assume che tutti i nodi sono migranti e aventi la stessa velocit

di movimento. Questa assunzione pu permettere in pratica di stimare la

relativa distanza di percorrenza per giungere a destinazione, che altrimenti

porterebbe un notevole dispendioso di tempo.

In RDMAR l'operazione di Route Discovery, compatta la trasmissione dei

47


pacchetti informazione nella ricerca di un percorso per giungere a desti-

nazione. Inoltre quando un link si rompe, il processo di Route Maintenance

usato per riparare l'eventuale percorso formato.

I vantaggi dei protocolli Reactive I protocolli Reactive a dierenza dei

protocolli Proactive hanno i seguenti vantaggi:

creano i percorsi solo ed esclusivamente su richiesta (On- Demand),

eliminano l'elevato traco della rete, cosi ch' la rete non venga inon-data dall'invio dei pacchetti informazione,

l'assenza di innumerevoli tabelle per memorizzare i dati relativi all'in-stradamento, permette un minor dispendio di memoria, soprattutto nei

riguardi di quei dispositivi che non ne hanno una quantit limitata.

AODV. Il protocollo di routing AODV migliora quelle che sono le caratter-

istiche del protocollo Proactive DSDV, minimizzando il numero di richieste

per creare percorsi dal nodo sorgente al nodo destinazione.

L'algoritmo, come si gia detto, inizia la sua logica facendo l'operazione di

ooding ad ogni richiesta di route, ci permette un funzionamento adeguato

per reti di piccole dimensioni (cinquanta o cento nodi al massimo), dove ore

un basso overhead.

TORA. Questo protocollo stato pensato per minimizzare le azioni, quan-

do ci si trova di fronte a dei cambiamenti topologici della rete. Infatti tale

protocollo molto adatto ad ambienti mobili altamente dinamici.

Come si evince dalla Figura 3.8 tra il nodo D e il nodo F avvenuto un link

failure, ma ci non desta problemi poich automaticamente il nodo D riesce

ad ottenere un collegamento sia con il nodo B che C.

L'immediato collegamento del nodo D con gli altri nodi dovuto grazie al-

l'operazione tempestiva di Route Maintenance.

Il protocollo Tora si avvale anche dell'aiuto della metrica, denominata height,

che si basa su cinque elementi:

un time logico per la gestione dei link failure,

un identicatore univoco ID di un nodo, che denisce il nuovo livello acui ci si referenzia,

un indicatore di bit,

una propagazione di parametri,

un identicatore per il nodo.

48


I primi tre elementi rappresentato collettivamente i reference level

16

. Per

concludere in TORA non si totalmente sicuri di garantire che i percorsi

siano esenti da cicli, ma si pu accertare che saranno almeno di breve durata.

AB

E

CD

F

G

(1)A

E

B

D

F

C

G(2)

Link Failure

AB

E

C

F

D G A

E

B

D G

C

F(3) (4)

Link Reversal

Figura 3.8: Protocollo TORA

SSR. SSR si comporta come DSR e AODV quando si verica un link fai-

lure. La sorgente si mobilita ad inviare dei messaggi di aggiornamento, per

informare che i nodi coinvolti nel percorso possano aggiornare le tabelle SST

e RT.

LAR Il protocollo LAR deriva dal protocollo DSR.

In questo protocollo si cercato di migliorare il ood iniziale per la ricerca di

un percorso. Se si inoltre a conoscenza della posizione (anche approssimata)

della destinazione, si cerca di mandare i pacchetti di richiesta verso quella

direzione, provando a coprire un'area tanto pi ampia quanto pi imprecisa

la conoscenza della posizione.

16

Si creano ogni volta che un nodo perde il suo ultimo downnstream a causa di un link

failure.

49


PAR. L'unica propriet che ha il protocollo PAR l'essere conveniente se

si sceglie di adottare dispositivi con un'alta durata di batteria, poich riesce

ad minimizzare l'energia che si consuma nell'invio di pacchetti.

RDMAR. L'utilizzo del GPS considerato un vantaggio perch riesce a

determinare con esattezza la posizione del nodo di destinazione.

Gli svantaggi dei protocolli Reactive Di seguito verranno menzionati

gli svantaggi dei singoli protocolli.

AODV. Non viene garantito che i percorsi siano i pi corti e a causa del

funzionamento On-Demand, alcuni pacchetti dati potrebbero essere persi

nch non si riesce a trovare un percorso per la destinazione. Inoltre per

reti composte da pi di 100 dispositivi si ha un alto overhead dovuto dalla

propagazione di pacchetti di richiesta da parte del nodo sorgente.

TORA. Il tempo di creazione da parte del protocollo nella creazione del

grafo eccessiva. Inoltre i percorsi oerti non sono sicuramente ottimali, e

anche in questo protocollo di routing c' la possibilit della formazione di

loop.

SSR. Nel protocollo SSR c' un dispendio di tempo notevole quando si

in presenza di canali comunicativi deboli, poich come precedente citato

tale protocollo seleziona i percorsi solo ed esclusivamente se la potenza del

segnale alta.

LAR LAR purtroppo non permette il suo utilizzo se non si provvisti del

Global Positioning System.

PAR Non indicato per chi volesse usare dispositivi mobili come PDA e

Smartphone, poich la loro batteria dura all'incirca 60min. Inoltre questo

protocollo massimizza il tempo per partizionare la rete.

RDMAR. I limiti che vengono attribuiti a tale algoritmo sono tre:

la distanza stimata in funzione della previsione della distanza stessa;

l'assunzione di una velocit ssata dei dispositivi mobili;

si deve ssare un range di trasmissione.

50

3.7 Protocolli Hybrid

3.7 Protocolli Hybrid

I protocolli Hybrid cercano di unire quelli che sono i vantaggi dei protocolli

Proactive e Reactive. Di seguito verr descritto solo il protocollo ZPR -

Zone Routing Protocol poich ad oggi, questa famiglia di protocolli molto

dicile da implementare e basa il suo funzionamento sulla cooperazione dei

protocolli Reactive e Proactive.

Protocollo ZPR. Il protocollo ZPR usa una routing zone, (letteralmente

zona di routing), che pu essere pensata simile al menzionato utilizzo dei

clusters, con l'eccezione che ogni nodo si comporta come un cluster head,

potendo essere quindi membro di un qualsiasi cluster.

Le zone di routing possono essere sovrapposte. Ogni nodo specica una zona

radio in termini di radio hops

17

.

Le dimensioni di una zona di routing possono andare ad incidere sulle prestazioni

della comunicazione della rete ad hoc.

ZPR utilizza nella zona di routing uno dei protocolli di instradamento Proac-

tive. Ci fa evincere che ogni dispositivo deve avere a disposizione delle

tabelle all'interno delle quali vengono memorizzati i percorsi per raggiungere

i nodi all'interno della zona.

Gli aggiornamenti dei percorsi (in caso di cambiamenti topologici della rete

o in caso di link failure), vengono eettuati dai singoli nodi all'interno della

zona di routing.

Per realizzare invece la ricerca dei nodi (operazione di Route Discovery), che

si trovano in zone diverse, viene utilizzato uno dei protocolli Reactive.

Il protocollo ZPR si avvale dell'aiuto di tre sotto-protocolli, che sono:

un protocollo Proactive denominato IARP (IntrAzone Routing Proto-col). Il compito principale assicurare che ogni nodo, dentro una zona

di routing, abbia a disposizione una tabella di routing consistente e

che venga aggiornata periodicamente per esprimere informazioni at-

tendibili, atte a determinare la ricerca di tutti i nodi all'interno della

zona.

Un protocollo Reactive denominato IERP (IntEr Routing Protocol). Ilsuo compito eettuare la ricerca sia di nodi in altre zone, sia la ricerca

di un percorso per giungere a destinazione. La Figura 3.9 presenta un

possibile scenario. I cerchi identicano univocamente le tre zone X, Y,

Z, che come si nota sono sovrapposte e al loro interno si trovano alcuni

dispositivi.

La ricerca di un percorso On-Demand viene eettuata dai nodi po-

sizionati sui bordi di una zona (border node), che si preoccupano di

reperire le informazione riguardanti i nodi risiedenti in altre zone. Ci

17

I radio hops, identicano sempre, come stato precedentemente illustrato, quanti salti

un nodo obbligato a fare per arrivare al nodo destinazione.

51


Border Node

Border Node

Zona dei nodi Y

Zona dei nodi Z

Zona dei nodi X

Figura 3.9: Protocollo ZPR

non avviene tramite query broadcast

18

, ma tramite l'invio di messaggi

dai nodi marginali ai nodi posizionati all'interno di altre zone.

BRP Bordercast Resolution Protocol.

Per concludere il protocollo di routing ZPR, teoricamente, ha la possibilita'

di ottimizzare la gestione sia di molti dispositivi che di un numero di dis-

positivi piu' stretto, ma allo stato attuale molto dicile da implementare,

poich non si ancora stabilito uno standard di utilizzo, cio permettere la

cooperazione delle due famiglie di protocolli Reactive e Proactive.

3.8 Protocollo DSR

Nel seguente paragrafo verranno prima di tutto descritte le funzionalit del

protocollo di routing DSR, analizzate le due principali operazioni di Route

Discovery e Route Maintenance e poi in ultimo spiegato il motivo per il quale

si scelto di implemantarlo.

18

Continue domande trasmesse a tutti i nodi.

52

3.8 Protocollo DSR

3.8.1 Funzionamento generale

Il protocollo DSR fa parte della famiglia dei protocolli Proactive, per cui i

nodi che intendono conoscere un determinato percorso devono farne esplici-

tamente richiesta.

Ogni dispositivo possiede una route cache nella quale vengono memorizzati

una serie di percorsi atti ad arrivare al nodo di destinazione. In questa tabel-

la i percorsi sono mantenuti per un determinato periodo di tempo (scelta che

viene gestita dal programmatore): quando questo tempo scade, il percorso,

cancellato se non viene referenziato.

La prima fase che un nodo sorgente utilizza nella determinazione di un per-

corso (se questo non gi memorizzato in route cache) la scoperta dei

vicini. In questa fase si riesce a determinare quali sono i dispositivi che si

trovano nel range trasmissivo del nodo che ha richiesto un route. Una volta

scoperti i vicini, si inizia la fase di Route Discovery.

Di seguito verranno descritti dettagliatamente i passi che bisogna compiere

per arrivare a determinare un percorso.

3.8.2 Determinazione di un percorso

Per costruire un source route nel quale si invier un pacchetto dati, le tappe

da eseguire sono le seguenti:

si verica se nella route cache presente o meno un percorso, selo si trova, si utilizza questo percorso per inviare il dato al nodo

destinazione;

se non si ha memorizzato un percorso in route cache, si esegue la sco-perta dei vicini. Se un vicino proprio il nodo di destinazione, si invia

il dato;

se la fase di scoperta dei vicini non andata a buon ne si procede conl'operazione di Route Discovery.

In generale un nodo inoltra una richiesta, denominata RREQ (route request),

quando o nella sua route cache non ha un percorso per giungere a desti-

nazione o la scoperta dei vicini non ha dato come esito il nodo destinazione.

3.8.3 Operazione di Route Discovery

Questa fase permette di scoprire dinamicamente un percorso verso un altro

host, sia se l'host di destinazione ricercabile direttamente dentro il suo

stesso wireless trasmission range, sia se necessario utilizzare nodi intermedi

per ottenere il percorso.

Un host inizia l'operazione di Route Discovery trasmettendo un RREQ ai

nodi che si trovano nel suo stesso wireless trasmission range.

53


Il pacchetto RREQ identica sia il mittente e sia quale il destinatario della

richiesta. Se la RREQ riesce ad ottenere un percorso, allora viene mandata

indietro al mittente una RREP (route reply), nella quale memorizzato il

percorso completo sorgente-destinazione.

Il pacchetto RREQ composto da:

indirizzo del mittente, indirizzo della destinazione request ID che indica il numero generato dal mittente, che identicaunivocamente una RREQ,

route record che memorizza in un record la sequenza dei salti necessariper raggiungere l'host di destinazione. Tali dati sono ricavati attraverso

la Route Discovery.

Per scoprire ed evitare che ci siano RREQ duplicate nella ricerca di un per-

corso, ogni host mantiene una lista delle coppie (indirizzo sender, request

id) ricevute dalle varie RREQ. Quando un device riceve una richiesta si pu

comportare nei seguenti modi:

se la coppia indirizzo sender,request ID nota nella lista, allora l'hostscarta la richiesta senza processarla;

se l'indirizzo dell'host gi presente nel route record di una richiesta,allora scarta la richiesta senza processarla;

se la richiesta giunge alla destinazione, allora il route record contieneil percorso dal quale la richiesta giunta. Inne, la destinazione copia

il percorso memorizzato nel route record e lo pone in una RREP che

invier al mittente;

se la richiesta giunge ad un host intermedio, esso aggiunge al routerecord il suo indirizzo e inoltra la richiesta.

Anch sia fornita una RREP al mittente, la destinazione deve possedere

un percorso per la sorgente.

Se la destinazione ha nella propria route cache un percorso per il mittente,

invia la RREP su questo percorso.

Diversamente, se non si possiede un percorso, pu essere utilizzato quel-

lo memorizzato nel route record della RREQ ricevuta. Questo approccio

richiede che la comunicazione tra coppie di host sia bidirezionale.

Nella Figura 3.10 viene mostrata l'operazione di Route Discovery all'inter-

no di una rete composta da otto dispositivi. Nel primo passo, si evince la

trasmissione da parte del nodo sorgente (nodo 1) del pacchetto route record.

I nodi successivi controllano se nella loro route cache presente un percorso

54

3.8 Protocollo DSR

per giungere al nodo 8 (si supposto che tutti i nodi hanno la route cache

vuota), in seguito eseguono la fase di scoperta dei vicini (anche qui si voluto

far notare che non si arriva subito al nodo di destinazione), e come ultimo

anche loro inviano i pacchetti route record n tanto che non si giunge al nodo

destinazione. Una volta giunti al nodo 8 la seconda fase la trasmissione

del pacchetto RREP, destinato al nodo sorgente, il quale una volta ricevuto

potr utilizzare tale percorso per inviare il dato al nodo 8.

Un ulteriore approccio oerto dal protocollo DSR per mandare un pacchetto

di risposta al nodo sorgente (RREP), pu essere quello di utlizzare la modal-

it piggyback. Questa tecnica permette di inviare all'interno del pacchetto

RREP anche quello RREQ, ma di ci verra trattato nel paragrafo 3.8.4.

N1

N3

N4

N6 N7

N8

N5N2N1

N1,N2 N1,N2,N5

N3

N1,N3

N1,N3

N1,N3,N4

N1,N3,N6

N1,N3,N6,N7

N1,N3,N4 1) Pacchetto RouteRecordDurante la Route Discovery

N1

N2 N5

N8

N3

N4

N6 N7

SorgenteDestinazione

Sorgente

Destinazione

N1,N2,N5,N8

N1,N2,N5,N8N1,N2,N5,N8 2) Propagazione del pacchetto

RouteReply con il pacchettoRouteRecord

Figura 3.10: Protocollo DSR

3.8.4 Piggybacking sulla Route Discovery

Abbiamo visto, che quando un host vuole inviare un pacchetto dati ad un

altro host, prima controlla se nella sua cache presente un percorso, poi se

non lo , comincia l'operazione di Route Discovery. L'attesa del pacchetto

RREP da parte del nodo richiedente pu essere ridotto, usando la tecnica di

piggyback. Nel pacchetto RREP infatti ci sono anche i pacchetti RREQ, ci

per evitare che una volta arrivati a destinazione, questa rifaccia nuovamente

la scoperta di un percorso per giungere al nodo sorgente.

55


Questa tecnica se pur molto utile bisogna usarla con cautela. Attualmente

si usa la tecnica di piggybacking quando si inviano o pacchetti RREP o

pacchetti RRER (pacchetti di errore), dato che sono per natura piccoli di

dimensione.

3.8.5 Route Maintenance

Gli algoritmi di routing Reactive precendentemente descritti usano uno scam-

bio continuo di messaggi per noticare lo stato della rete. In questo algoritmo

ci non eettuato.

Il protocollo DSR quando riesce a trovare un percorso, utilizzata una pro-

cedura di Route Maintenance per monitorare le operazioni da eettuare sul

percorso, ed informare sia il mittente, sia i nodi intermedi di qualsiasi errore

di routing.

Dato che le reti wireless sono per natura meno adabili delle rete con li,

molte di esse utilizzano un riconoscimento hop-by-hop a livello data link,

per scoprire e ritrasmettere i pacchetti persi o danneggiati. In queste reti, la

Route Maintenance pu essere facilmente fornita ad ogni hop.

Se il livello data link riscontra un problema di trasmissione, l'host manda un

pacchetto RRER (route error) al mittente che ha provocato l'errore.

Il pacchetto RRER contiene gli indirizzi dei due host posti alle estremit del

link, che hanno generato l'errore. Quando un host riceve un RRER, l'hop che

ha generato l'errore rimosso dalla route cache dell'host, e tutti i percorsi

che contengono l'hop che ha generato l'errore sono troncati in quel punto.

Esistono diverse modalit per dichiarare l'avvento di un errore:

passive acknowledgement, se la rete wireless non supporta un riconosci-mento a basso livello, dopo che stato inviato un pacchetto, l'host in

grado di capire se l'host seguente sta trasmettendo di nuovo il pacchetto

lungo il percorso assegnato;

viene usato un bit, incluso nell'header del pacchetto, per permetteread un host di richiedere al nodo seguente una risposta di avvenuta

ricezione;

quando un host intermedio riceve un pacchetto RREP, l'host deve avereun percorso verso il mittente del pacchetto originale, per poter inviare

un pacchetto RRER. Se questo host ha memorizzato nella sua route

cache un percorso, utilizza questo per inviare il pacchetto,

altrimenti se l'host non ha il percorso nella route cache, per inviare ilpacchetto d'errore potrebbe invertire il percorso che stato usato per

giungere a lui dalla sorgente.

Si potrebbe usare piggibacking come nel caso di un pacchetto RREP.

56

3.8 Protocollo DSR

Un'altra opzione per restituire un pacchetto d'errore quello di salvarelocalmente il route error in un buer, eseguire l'operazione di Route

Discovery per trovare il mittente originale, e in seguito mandare il

pacchetto route error attraverso il percorso trovato.

3.8.6 Miglioramenti delle operazioni

Di seguito verranno illustrate le ottimizzazioni possibili per le operazioni di

Route Discovery e di Route Maintenance.

I miglioramenti che si possono eseguire sulla route cache di un host sono:

riguardanti i dati, che possono essere immagazzinati in ogni formato;

un host pu sempre aggiungere un nuovo percorso in route cache.

Di quest'ultima miglioria si andr ad analizzare quali sono le situazioni

tipiche che portano un nodo ad aggiungere nella sua route cache nuovi

percorsi. In particolare un nodo aggiunge i percorsi in route cache se:

un host ottiene il percorso mediante una RREP;

un nodo deputato ad avanzare un pacchetto dati controlla l'intero per-corso (che dovr arontare il pacchetto per giungere a destinazione).

In questo caso il nodo pu memorizzare quel dato percorso,

un nodo che inoltra una RREP, pu rilevare il percorso memorizzatonel route record e memorizzarlo nella sua route cache.

Un host inoltre usa la sua route cache per evitare la propagazione nella rete

di copie uguali di pacchetti RREQ, ricevuti dai suoi vicini.

Un'ultima ottimizzazione sarebbe quella di aggiungere in un record il nu-

mero massimo di hop, sui quali un pacchetto pu essere propagato. Questa

miglioria potrebbe essere molto importante per ridurre il numero di richieste

propagate nella fase di Route Discovery.

Per eettuare questa ottimizzazione si seguono i seguenti passi:

per compiere l'operazione di Route Discovery, inizialmente si manda laRREQ con un limite di hop posto a uno;

se dopo un certo intervallo di tempo, non si riesce ad avere una risposta(RREP) alla RREQ formulata nel passo precedente, allora viene man-

data una nuova richiesta con un numero massimo di salti ssato (di

solito si sceglie come numero massimo di salti 10).

57


3.9 Motivazione della scelta del protocollo

Nell'appendice B vengono riportate quattro delle pi salienti esperienze eet-

tuate, sia in ambienti chiusi che in spazi aperti (senza intralci di trasmissioni

radio) che hanno permesso di avere l'assoluta certezza, che nelle reti ad hoc,

non esistendo infrastrutture, non possibile avere una comunicazione point-

multipoint.

Ossia ci non possibile se nonch si usufruisca di un protocollo di routing.

E' per tale motivazione che si scelto di sviluppare il protocollo Reactive

DSR.

La scelta ricaduta sul protocollo DSR, poich per prima cosa, appartiene

alla famiglia dei protocolli Reactive, di cui si sono elencati i vantaggi nel

paragrafo 3.6.

In una rete MANET, l'idea della creazione di percorsi solo On-Demand,

sicuramente pi attuabile, rispetto ad un continuo scambio di informazioni

ad intervalli di tempo ssati.

In secondo luogo, il protocollo DSR, rispetto a tutti i protocollo visionati, of-

fre non una ma tre diverse alternative per garantire la ricerca di un percorso.

Queste fasi sono:

ricerca in route cache; permettere un notevole ridimenzionamento deltraco di pacchetti nella rete, poich se in route cache presente un

percorso per giungere a destinazione automaticamente si instradano

pacchetti di informazione.

Scoperta dei vicini; consente ad un nodo la ricerca dei vicini nel suorange trasmissivo. Se infatti il nodo di destinazione un vicino, il nodo

mittente invia immediatamente pacchetti contenenti i dati.

Route Discovery; questa fase consente di cercare un percorso tra nodiche non si trovano nello stesso range trasmissivo.

Inoltre il protocollo DSR, appropriato per una rete dove i dispositivi che la

compongono sono all'incirca cinquanta e per i nostri scopi, ovvero una rete

composta al massimo pochi dispositivi (circa venti), sembrato quello che

pi si adattava bene a queste esigenze.

Ma il motivo pi importante il mantenimento da parte di tutti i dispositivi

di una sola tabella, denominata route cache. Tale route cache mantiene tutte

le informazioni necessarie a far si che si abbiano a disposizione i percorsi nec-

essari per giungere ad un nodo destinazione.

Il mantenimento di un'unica tabella un grande vantaggio, dovuto anche

al fatto che l'applicazione pensata fa uso soprattutto di dispositivi mobili,

come palmari; con bassa capacit di memoria (circa 128 MB), quindi tenere

in memoria solo una tabella, risulta molto utile in termini di risparmio di

risorse.

58

3.9 Motivazione della scelta del protocollo

DSR permette inoltre, che la comunicazione tra due host possa essere fat-

ta, utilizzando percorsi pi brevi, come pure permette di eliminare, tutti

i problemi relativi alla creazione di cicli nel percorso, proprio perch vi

il continuo controllo da parte dei nodi, nei confronti dei pacchetti RREQ,

RREP, RRER.

Infatti se un device si accorge di aver gi ricevuto uno di questi pacchetti

non fa nient'altro che riutare.

L'operazione di Route Maintenance invece, determina i link failure nella rete,

cos da permettere ai dispositivi di cercare un'alternativa, una volta noti-

cato il fallimento.

Concludendo il protocollo DSR sembrato quello che pi si adatta sia allo

scenario proposto nel Capitolo 2, riguardante la squadra di soccorso, che

deve necessariamente avere a disposizione PDA, laptop, etc. sia alle scelte

di progetto discusse nel Capitolo 4.

59

Routing Protocol

Documents

Transcript of Routing Protocol