Corso di Protocolli per Reti Mobili

Routing in Reti Ad Hoc

Università di Napoli Federico II – Facoltà di Ingegneria – Corso di Laurea in Ingegneria Informatica

Wireless Ad Hoc Networks● Una wireless ad hoc network è un insieme di nodi

wireless che possono dinamicamente auto-organizzarsi, senza necessitare di una infrastruttura pre-esistente, secondo una topologia di rete arbitraria e temporanea al fine di comunicare dati

● Applicazioni:– Nel campo militare– Organizzazione operazioni in situazioni d'emergenza– Condivisione documenti (riunioni, lezioni, etc.)

● In generale, viene spontaneo pensare ad una modalità di comunicazione ad hoc, considerata la diffusione di dispositivi wireless

Wireless Ad Hoc Networks● Vantaggi

– Semplicità e rapidità di messa in opera– Bassi costi

● Difficoltà– I nodi sono tipicamente mobili

● Si parla di MANET (Mobile Ad hoc Networks)– I nodi possono avere risorse limitate

● capacità computazionale, memoria, alimentazione a batterie

– Trasmissioni wireless...

Wireless Ad Hoc Networks● Non tutti i nodi di una rete ad hoc sono in grado di

comunicare direttamente tra di loro● Ogni nodo deve instradare i pacchetti inviati da altri

nodi verso la destinazione● Ogni nodo si comporta da router ed è necessario

un protocollo di routing● La mobilità dei nodi può causare frequenti

cambiamenti della topologia, che rendono inadatti i protocolli di routing pensati per reti cablate

Protocolli di routing per reti ad hoc● Sono stati proposti diversi protocolli di routing per

reti ad hoc● La principale classificazione è in● Protocolli reattivi (oppure on-demand)

– Il percorso verso la destinazione viene determinato (con una fase di route discovery) solo quando serve

– Elimina l'overhead legato al mantenimento di percorsi non utilizzati

● Protocolli proattivi– Mantiene percorsi verso tutte le destinazioni– Elimina la latenza legata al calcolo del percorso

Protocolli di routing per reti ad hoc● Il gruppo MANET dell'IETF si occupa di standardizzare

protocolli di routing per reti MANET– http://datatracker.ietf.org/wg/manet/charter/

● AODV (Ad hoc On-demand Distance Vector) [RFC 3561]– Reattivo, hop-by-hop routing, distance vector

● DSR (Dynamic Source Routing) [RFC 4728]– Reattivo, source routing

● OLSR (Optimized Link State Routing) [RFC 3626]– Proattivo, hop-by-hop routing, link state

http://datatracker.ietf.org/wg/manet/charter/

AODVAd hoc On-demand Distance Vector

AODV● E' un protocollo di routing reattivo● I percorsi sono calcolati solo quando è necessario

inviare dati (route discovery)– Non ci sono messaggi inviati periodicamente

● I messaggi sono incapsulati in datagrammi UDP con porto destinazione 654

● Ha l'obiettivo di adattare il paradigma distance vector per le reti MANET

● Il principale concetto introdotto è quello del destination sequence number– Elimina routing loop e conteggio all'infinito

AODV Route discovery● Un nodo che vuole raggiungere una destinazione per la

quale non conosce una rotta oppure la rotta è scaduta o invalida, invia un messaggio RREQ in broadcast (all'indirizzo IP 255.255.255.255)– Include l'indirizzo proprio (Originator IP Address) e quello della

destinazione (Destination IP Address)– Include un RREQ ID restituito da un contatore usato da ogni

originator (per tutte le destinazioni)– L'hop count del messaggio è settato a 0– Il campo TTL nell'header IP limita la diffusione del messaggio

● Il valore è preso dalla rotta scaduta, se presente● Se non riceve risposta entro un certo tempo, il nodo invia

una nuova RREQ con un nuovo RREQ ID ed un TTL maggiore

AODV Route Request (RREQ)● Se un nodo riceve una RREQ, la scarta se ha già

ricevuto una RREQ con lo stesso RREQ ID dallo stesso originator

● Altrimenti, incrementa l'hop count● Crea o aggiorna (se esiste ed ha un hop count

maggiore) una rotta verso l'originator (reverse route)

● Se il nodo non conosce una rotta verso la destinazione e il TTL è maggiore di 1, allora re-invia in broadcast la RREQ

A

B

C

D

EF

G

RREQ(A,E,0)

RREQ

(A,E,

0)

RREQ(A,E,1)

RREQ

(A,E,

1)RR

EQ(A

,E,1

)

RREQ(A,E,1)

RREQ

(A,E

,1)

AODV Route Request (RREQ)

A 1 A

A 1 A

A 2 B

A 2 C

RREQ(A,E,2

) RREQ(A,E,2) RR

EQ(A

,E,2

)

A 3 D

RREQ scartateTTL = 3Dest. = E

AODV Route Reply (RREP)● Un nodo che riceve una RREQ per una data

destinazione genera un messaggio RREP se– È la destinazione stessa

● Hop count field 0– Conosce una rotta (non scaduta) verso la

destinazione● Hop count field distanza dalla destinazione

● Gli indirizzi della destinazione e dell'originator vengono ricopiati in analoghi campi della RREP

● RREP è inviata in modalità unicast verso l'originator della RREQ, usando la reverse route

AODV Route Reply (RREP)● Un nodo che riceve una RREP incrementa il valore

nel campo hop count● Crea o aggiorna (se avente una distanza superiore)

una rotta verso la destinazione indicando come next hop il nodo da cui ha ricevuto la RREP e come distanza il valore incrementato di hop count

● Se il nodo non è l'originator, inoltra la RREP in modalità unicast usando la reverse route verso l'originator

A

B

C

D

EF

G

RREP

(A,E,

1)

RREP

(A,E

,0)

AODV Route Reply (RREP)

A 1 A

A 1 A

A 2 B

A 2 C

A 3 D

Originator = ADestination = E

E 1 E

E 2 C

A

B

C

D

EF

G

AODV Route Reply (RREP)

A 1 A

A 1 A

A 2 B

A 2 C

A 3 D

Originator = BDestination = E

E 1 E

E 2 C

RREQ(B,E,0)

RREQ

(B,E

,0)

RREP(B,E,2)

E 3 A

Gratuitous RREP● Il nodo B ora sa come raggiungere il nodo E● Il problema è che il nodo E non sa raggiungere il

nodo B!● Se B necessita di una comunicazione bidirezionale

con E può settare il flag G nella RREQ● In questo modo, un nodo intermedio (es., A) che

risponde con una RREP e non inoltra la RREQ deve inviare una RREP (gratuita) alla destinazione E in modalità unicast– La RREP gratuita è come se fosse una risposta ad

una RREQ generata da E per raggiungere B

A

B

C

D

EF

G

Routing loops

A 1 A

A 1 A

A 2 B

A 2 C

A 3 D

E 1 E

E 2 C

RREQ(A,E,0)

RREP(A,E,3)

E 3 A

E 4 B

Routingloop !

Sequence numbers● In ogni entry della tabella di routing, la destinazione

è associata ad un sequence number● Ogni nodo cerca di mantenere aggiornato il

sequence number di tutte le destinazioni note● Normalmente, il sequence number di un nodo può

essere incrementato solo dal nodo stesso● I messaggi RREQ (RREP) contengono il sequence

number della destinazione e dell'originator (della destinazione)

● Un sequence number più alto indica un'informazione più aggiornata

Sequence numbers● Un nodo che genera una RREQ

– Inserisce il sequence number della destinazione, se è presente una entry (scaduta) nella tabella di routing

– Incrementa il proprio sequence number e lo pone nel campo originator sequence number

● Un nodo che riceve una RREQ– Aggiorna la reverse route utilizzando l'originator sequence

number contenuto nella RREQ– Se ha una rotta attiva verso la destinazione, il destination

sequence number è maggiore di quello nella RREQ e il flag “destination only” non è settato, invia una RREP contenente il destination sequence number conosciuto

– Altrimenti, re-invia la RREQ aggiornando il campo destination sequence number se conosce un valore più alto

Sequence numbers● Il nodo destinazione

– Genera una RREP con un destination sequence number pari al massimo tra quello contenuto nella RREQ e quello che mantiene

● Un nodo che riceve una RREP– Crea o aggiorna una rotta verso la destinazione

usando il destination sequence number presente nella RREP

A

B

C

D

EF

G

RREQ(A,5,E,?,0)

RREQ

(A,5,

E,?,0)

RREQ(A,5,E,?,1)

RREQ

(A,5,

E,?,1)

RREQ

(A,5

,E,?

,1)

RREQ(A,5,E,?,1)

RREQ

(A,5

,E,?

,1)

AODV Route Request (RREQ)

A 5 1 A

A 5 1 A

A 5 2 B

A 5 2 C

RREQ(A,5,E

,?,2)RREQ(A,5,E,?,2)

RREQ

(A,5

,E,?

,2)

A 5 3 D

RREQ scartateTTL = 3Dest. = E

A

B

C

D

EF

G

RREP

(A,E,

3,1)

RREP

(A,E

,3,0

)

AODV Route Reply (RREP)

Originator = ADestination = E

E 3 1 E

E 3 2 C

A 5 1 A

A 5 1 A

A 5 2 B

A 5 2 C

A 5 3 D

A

B

C

D

EF

G

AODV Route Reply (RREP)

Originator = BDestination = E

RREQ(B,6,E,?,0)

RREQ

(B,6

,E,?

,0) RREP(B,E,3,2)

E 3 3 A

E 3 1 E

E 3 2 C

A 5 1 A

A 5 1 A

A 5 2 B

A 5 2 C

A 5 3 D

Evitare i routing loop● Un nodo che non riesce a raggiungere il next hop

lungo un percorso attivo verso una destinazione – Può tentare di riparare la rotta inviando una RREQ

che contiene l'indirizzo della destinazione– Se non tenta di riparare la rotta oppure tenta ma non

ottiene risposta, invia un messaggio RERR a tutti i suoi vicini che lo usano come next hop verso la destinazione

● L'insieme di tali vicini (precursor list) è aggiornato a seguito della generazione di messaggi di RREP

● In ogni caso, il nodo incrementa il sequence number della destinazione prima di inviare i messaggi

A

B

C

D

EF

G

Routing loops

RREQ(A,6,E,4,0)

RREP(A,E,4,4)

E 3 3 AA 5 1 A

A 5 2 B

A 5 3 D

A 5 2 C

E 3 1 EA 5 1 A

E 3 2 C

RREQ

(A,6

,E,4

,1)

RREQ(A,6,E,4,4)

A 6 3 D

A 6 5 F

RREP(A,E,4,0) E 4 1 E

E 4 2 F

E 4 3 G E 3 2 CE 4 5 BA 6 2 B

A 6 4 G

A 6 1 AE 4 4 D

DSRDynamic Source Routing

DSR● E' un protocollo di routing reattivo● I percorsi sono calcolati solo quando è necessario

inviare dati (route discovery)– Non ci sono messaggi inviati periodicamente

● I messaggi sono incapsulati in un header DSR inserito subito dopo l'header IP

● La principale caratteristica è l'uso del source routing– Ogni pacchetto dati contiene la lista dei nodi da

attraversare per giungere a destinazione

DSR● La scoperta di un percorso avviene mediante uno

scambio di messaggi RREQ/RREP● Ogni nodo che inoltra una RREQ aggiunge il

proprio indirizzo alla lista presente nel messaggio● Ogni nodo che riceve una RREQ conserva una

rotta verso l'origine nella propria route cache● Oltre a scartare una RREQ già ricevuta, un nodo

scarta anche le RREQ la cui lista già contiene il dato nodo– Per evitare routing loops

A

B

C

D

EF

G

RREQ(E; A)

RREQ

(E; A

)

RREQ(E; A-B)

RREQ

(E; A

-C)

RREQ

(E; A

-B)

RREQ(E; A-C)

RREQ

(E; A

-C)

DSR Route Request (RREQ)

C→A

B→A

D→B→A

E→C→A

RREQ(E; A-

B-D)RREQ(E; A-B-D)

RREQ

(E; A

-B-D

)

G→D→B→A

RREQ scartateTTL = 3Dest. = E

DSR Route Reply (RREP)● Il nodo destinazione (o un nodo che ha una rotta

verso la destinazione nella route cache) risponde ad una RREQ con un messaggio RREP– Il nodo si aggiunge alla lista presente nella RREQ

● RREP è inviata in modalità unicast verso l'origine della RREQ, usando la reverse route

● Un nodo che ascolta una RREP memorizza nella route cache una rotta verso la destinazione

A

B

C

D

EF

G

RREP

(A-C

-E)

RREP

(A-C

-E)

DSR Route Reply (RREP)

C→A

B→A

D→B→A

E→C→A

Originator = ADestination = E

C→E

A→C→E

G→D→B→A

DSR – considerazioni● Un nodo che deve inviare un pacchetto deve

conoscere un percorso verso la destinazione– Cerca nella route cache– Inizia una route discovery

● Un nodo che deve inoltrare un pacchetto trova il next hop nell'header DSR del pacchetto

● Nella pratica, la route cache sostituisce la routing table

DSR – considerazioni● Vantaggi del source routing

– Possibilità di load balancing– Garantisce facilmente instradamento loop-free

● Svantaggi del source routing– La presenza della lista dei nodi da attraversare in

ciascun pacchetto dati può comportare un notevole overhead

– L'utilizzo della route cache può rallentare la consegna dei pacchetti se le rotte fornite sono datate

OLSROptimized Link State Routing

OLSR● E' un protocollo di routing proattivo● Le informazioni sulla topologia sono scambiate

periodicamente● I messaggi sono incapsulati in datagrammi UDP

con porto destinazione 698● Ha l'obiettivo di ottimizzare il paradigma link state

per le reti MANET● Il principale concetto introdotto è quello dei nodi

MPR (Multi-Point Relay)

Link State routing● Nel paradigma link state, ogni nodo invia

informazioni sui propri vicini a tutti gli altri nodi● La tecnica utilizzata per disseminare le informazioni

è il flooding con qualche accorgimento– Ogni nodo re-inoltra tutti i messaggi ricevuti sulle

altre interfacce– Un campo age serve a limitare il numero di

ritrasmissioni– Un campo sequence number serve ai nodi per capire

se il messaggio ricevuto è stato già elaborato/inoltrato

OLSR● OLSR tenta di minimizzare il numero di messaggi

scambiati per disseminare le informazioni sulla topologia

● Non tutti i vicini di un nodo A re-inoltrano i messaggi inviati da A, ma solo i Multi-Point Relay del nodo A– Tutti i vicini elaborano il messaggio

● Il nodo A seleziona, tra i propri vicini, i propri MPR in maniera tale che i suoi messaggi arrivino a tutti i 2-hop neighbor– Questa condizione assicura che i messaggi arrivano

a tutti i nodi della rete

OLSR

HA

IF

B

C

D

E

L

G

Neighbors(A)2-hop neighbors(A)MPR(A)

E inoltra il messaggio se è un MPR di C o H D inoltra il messaggio se è un MPR di C G inoltra il messaggio se è un MPR di B I inoltra il messaggio se è un MPR di H F inoltra il messaggio se è un MPR di B

OLSR● Ogni messaggio contiene:

– Un campo Time To Live, usato per limitare il numero di ritrasmissioni

– Un campo Sequence Number, usato per evitare che un messaggio venga elaborato/inoltrato più volte del necessario

– L'indirizzo del nodo che lo ha originato– Informazioni specifiche per il tipo di messaggio

● Ogni nodo sceglie un valore di willingness ad indicare la misura della sua volontà di ritrasmettere i messaggi dei vicini– Compreso tra WILL_NEVER e WILL_ALWAYS

Information repositories● Ogni nodo mantiene le seguenti informazioni:

– Link set: insieme di coppie (indirizzo interfaccia locale, indirizzo interfaccia del vicino)

– Neighbor set: insieme di coppie (indirizzo, willingness) per ciascun vicino

– 2-hop neighbor set: insieme di coppie (indirizzo del vicino, indirizzo del 2-hop neighbor)

– MPR set: insieme dei vicini usati come MPR– MPR Selector set: insieme dei vicini che hanno

selezionato il dato nodo come MPR– Topology Information: insieme delle coppie (indirizzo

destinazione, indirizzo penultimo hop)● Il penultimo hop è in genere un MPR della destinazione

HELLO message● I vari database sono popolati usando le

informazioni presenti nei messaggi ricevuti● Le informazioni presenti nei database sono usate

per generare i messaggi da inviare in broadcast● Un messaggio di HELLO generato da un nodo

include:– Il proprio valore di willingness– Gli indirizzi dei nodi vicini– Gli indirizzi dei vicini non più raggiungibili– Gli indirizzi dei propri MPR– Un TTL = 1 (non viene mai re-inoltrato)

Topology Control (TC) message● Ogni nodo selezionato come MPR (da qualche altro

nodo) invia messaggi TC che includono– L'indirizzo di almeno i vicini che hanno selezionato il dato

nodo come MPR– Un TTL = 255 (deve pervenire a tutti i nodi)

● Quindi non tutti i nodi inviano messaggi TC e nei messaggi non tutti i vicini devono essere indicati– Ulteriore riduzione dell'overhead legato al flooding

● Le informazioni contenute nei messaggi TC sono usate per popolare il database Topology Information

● La frequenza di invio dei messaggi può essere incrementata in caso di variazioni nell'insieme dei vicini

Calcolo della tabella di routing● La tabella di routing è calcolata a partire da Link set,

2-hop neighbor set e Topology Information– Una modifica in questi database richiede un ricalcolo

della tabella di routing● I passi per il calcolo della tabella di routing sono:1. Per ogni coppia (L_local_addr, L_neigh_addr) nel Link

set, si aggiunge la regola DEST=L_neigh_addr NH=L_neigh_addr HC=1

2. Per ogni nodo N_2hop_addr tale che una coppia (N_neigh_addr, N_2hop_addr) esiste nel 2-hop neighbor set, si aggiunge la regola

DEST=N_2hop_addr NH=N_neigh_addr HC=2

Calcolo della tabella di routing3. for (h=2; no new entry is added; h++)

Per ogni coppia (T_dest_addr, T_last_addr) nel Topology Information

Se non c'è una regola per T_dest_addr e c'è una regola per T_last_addr con HC=h (e NH=next_hop)

Allora si aggiunge la regola DEST=T_dest_addr NH=next_hop HC=h+1

● Questo algoritmo calcola il percorso più breve (in termini di hop count) verso tutte le destinazioni conosciute

OLSR – esempio

HA

IF

B

C

D

E

L

G

Nodo MPR set

A B, C, H

B A, F, G

C A, D, E

D C, G

E C, H

F A, B, I

G B, D

H A, E

I F, H

L E, I

TC message

B, C, F, H

A, F, G

A, D, E

C, G

C, H, L

B, I

B, D

A, E, I

F, L

Non inviato!

OLSR – esempio

Nodo TC message

A B, C, F, H

B A, F, G

C A, D, E

D C, G

E C, H, L

F B, I

G B, D

H A, E, I

I F, L

Topology Information

(B,A) (C,A) (F,A) (H,A)

(A,B) (F,B) (G,B)

(A,C) (D,C) (E,C)

(C,D) (G,D)

(C,E) (H,E) (L,E)

(B,F) (I,F)

(B,G) (D,G)

(A,H) (E,H) (I,H)

(F,I) (L,I)

Link set (L)

OLSR – esempio

Topology Information (L)

Link set (L)

(L,E) (L,I)

(I,F) (I,H) (E,C)Routing Table (Nodo L)

DEST Next Hop Hop Count

E E 1

I I 1

F I 2

H I 2

C E 2

(E,H)

(B,A) (C,A)  (F,A)  (H,A)

(A,B) (F,B) (G,B)(A,C) (D,C)  (E,C) 

(C,D)  (G,D) (C,E)  (H,E)  (L,E) 

(B,F)  (I,F) 

(B,G)  (D,G) 

(A,H)  (E,H)  (I,H) 

(F,I)  (L,I) 

(B,A)

(A,B)

h=2

(G,B)

A E 3

D E 3

(G,D) 

B I 3h=3

G I 4

Link set (L)

OLSR – considerazioni

Topology Information (L)

Link set (L)

(L,E) (L,I)

(I,F) (I,H) (E,C) (E,H)

(B,A) (C,A)  (F,A)  (H,A)

(A,B) (F,B) (G,B)(A,C) (D,C)  (E,C) 

(C,D)  (G,D) (C,E)  (H,E)  (L,E) 

(B,F)  (I,F) 

(B,G)  (D,G) 

(A,H)  (E,H)  (I,H) 

(F,I)  (L,I) 

HA

IF

B

C

D

E

L

G

● Le informazioni presenti nei database sono sufficienti a calcolare la topologia della rete

OLSR – considerazioni

Routing Table (Nodo L)DEST Next Hop Hop Count

E E 1

I I 1

F I 2

H I 2

C E 2

A E 3

D E 3

B I 3

G I 4

HA

IF

B

C

D

E

L

G

● L'algoritmo usato per il calcolo della tabella di routing equivale ad un algoritmo shortest path con pesi unitari

MPR construction● Più piccolo è l'insieme degli MPR, minore sarà

l'overhead legato al flooding1. N = {neighbors} N2 = {2-hop neighbors}2. MPR = { nN | willingness(n) = WILL_ALWAYS }3. Aggiungi ad MPR i nodi di N che sono gli unici a consentire

di raggiungere almeno un nodo in N24. Elimina da N2 i nodi raggiungibili da nodi in MPR5. Finchè N2 non è vuoto

5.1. Aggiungi ad MPR il nodo che consente di raggiungere il maggior numero di nodi tra quelli in N2; in caso di più scelte, aggiungi il nodo che consente di raggiungere il maggior numero di 2-hop neighbors

5.2. Elimina da N2 i nodi raggiungibili da nodi in MPR

Riferimenti● Request for Comments (RFCs)

– 3561, 3626, 4728