Analizziamo ora gli algoritmi di routing utilizzati: • BubbleRap:
BubbleRap[16] `e un algoritmo di routing per le reti opportunistiche che sfrutta
performance. I parametri fondamentali su cui si basa questo protocollo sono la centralit`a, social centrality, e la comunit`a, social community. In particolare combina la conoscenza della struttura della comunit`a con la centralit`a dei nodi per decidere i best forward nodes, ossia i nodi a cui inoltrare i messaggi che si occuperanno di recapitarlo a destinazione.
In particolare: – Centralit`a:
Questo parametro indica una sorta di “popolarit`a” tra i nodi, alcune persone sono pi`u popolari di altre e di conseguenza interagiscono molto di pi`u, han- no quindi elevata centralit`a e vengono scelti dall’algoritmo per diffondere i messaggi. A tal proposito ad ogni nodo viene assegnato un ranking globale che indica la popolarit`a del nodo all’interno della rete e un ranking locale che indica la popolarit`a del nodo all’interno della sua comunit`a.
– Comunit`a:
Questo parametro indica un’interazione sociale tra organismi dello stesso ti-
po. Si assume che ogni nodo appartiene ad almeno una comunit`a, quindi po-
tr`a avr`a pi`u ranking locali. Per identificare le comunit`a dei nodi, BubbleRap utilizza l’algoritmo K-Clique [7] che verr`a presentato nel paragrafo 4.5. BubbleRap diffonde le informazioni sfruttando sia le comunit`a dei nodi sia la loro centralit`a, in particolare: un nodo sorgente che vuole inviare ad esempio messag- gi di query o di advertisement a un determinato nodo destinatario, inizialmente utilizza il ranking globale per identificare un nodo a cui inoltrare il messaggio che appartiene alla stessa comunit`a del nodo destinatario. Una volta identificato tale nodo si utilizza il ranking locale per diffondere l’informazione all’interno della sua
comunit`a fino a che non raggiunge il nodo di destinazione. Questo sistema non
assume che ogni nodo debba sapere il ranking degli altri nodi, ma solo che un nodo sia capace nel confrontare il proprio ranking con quello del nodo incontrato. In Figura 4.7 `e possibile vedere un esempio illustrato. Il nodo s vuole spedire un messaggio al nodo d. Inizialmente individua il nodo u con pi`u alto ranking globale appartenente alla stessa comunit`a di d e successivamente tramite il ranking locale viene individuando v che pu`o inoltrare l’informazione a d.
Ogni messaggio diffuso nella rete ha un tempo massimo di vita, TTL: time to leave, oltre il quale poi viene eliminato. Ci`o `e stato introdotto per evitare che i messaggi scaduti circolino nella rete.
d v u s Cd Cglobale
Figura 4.7: Diffusione delle informazioni basandosi sul ranking dei nodi
• Epidemic:
Epidemic `e un protocollo di routing proposto da Vahdat e Becker [17] basato sulla tecnica del flooding in cui vengono diffuse molte copie di un messaggio nella rete
in modo da avere un’elevata probabilit`a che arrivi a destinazione con un basso
ritardo a discapito di un maggior consumo delle risorse disponibili dovute alle elevate trasmissioni. E’ considerato l’algoritmo che utilizza la tecnica pi`u semplice di diffusione dei messaggi.
L’idea su cui si basa `e quella di distribuire una copia del messaggio ad ogni nodo incontrato, come in un’epidemia, fino a che non raggiunge la destinazione oppure fino a che il tempo di vita del messaggio non si esaurisce, se previsto. L’obiettivo `
e quello di massimizzare la probabilit`a che un messaggio arrivi a destinazione,
minimizzare la latenza e minimizzare, per quanto sia possibile, il consumo delle risorse del sistema (energia, banda o memoria).
La diffusione dei messaggi avviene nel seguente modo: 1. Scambio delle summary vector:
Quando due nodi entrano in contatto, si scambiano le loro summary vector, ossia una lista memorizzata nella cache di ogni nodo costituita da tutti i messaggi che ha originato e da quelli ricevuti, Figura 4.8.
2. Scambio dei messaggi:
Una volta ricevuta la summary vector del nodo incontrato, ogni nodo identifica i messaggi che non possiede e ne richiede una copia, Figura 4.9.
Per evitare doppi scambi nel caso in cui i due nodi rientrano in contatto nel tempo, ogni nodo memorizza nella propria cache una lista di tutti gli incontri.
i
{m,n,p}u
i
{n,p}u
ID del messaggio m n p ID del messaggio m p ID del messaggio m n p ID del messaggio m pFigura 4.8: Scambio delle summery vector
i
mu
ID del messaggio m n p ID del messaggio m pFigura 4.9: Scambio dei messaggi
Ad ogni messaggio vengono associate le seguenti propriet`a: – Un identificatore univoco del messaggio.
– L’hop count, definito come il numero massimo di scambi di cui pu`o essere
protagonista un messaggio. Ogni volta che un messaggio viene passato da un nodo all’altro, tale valore viene decrementato di uno e quando HopCount = 1 pu`o essere consegnato solo al destinatario finale.
– Una richiesta di conferma chiesta al destinatario non appena il messaggio viene recapitato con successo.
• Spray&Wait:
Spray&Wait [18] `e un’estensione del precedente protocollo, Epidemic, in cui si cerca di controllare il livello di diffusione dei messaggi nella rete delimitando il numero
totale di copie, rendendolo costante anzich´e farlo dipendere dal numero di nodi; senza compromettere le performance. E’ un protocollo semplice e non richiede alcun tipo di informazione sulla topologia della rete.
Le fasi principali sono due:
– Spray Phase: In questa fase per ogni messaggio generato da un nodo sorgente S, vengono fatte L copie. Ogni volta che S incontra un nodo B che non contiene una copia del messaggio, S trasmette a B una singola copia. Se tale trasmissione ha avuto successo B procede con la seconda fase di Wait mentre S continua a diffondere le sue L − 1 copie, finch´e non ne rimane una sola, con la speranza di trovare cosi il nodo destinatario.
– Wait Phase: Questa fase viene eseguita se nella spray phase il messaggio non raggiunge la destinazione, in particolare ogni nodo che ha ricevuto una copia del messaggio attende di entrare in contatto con il destinatario finale per poterglielo inoltrare direttamente.
Si assume che il nodo destinatario riceva solo una copia del messaggio, dal primo nodo che riesce a consegnarglielo. Una volta ricevuto il messaggio, il destinatario rifiuta la ricezione dello stesso messaggio da altri nodi.
S
B
C
D
i°
l°
E
L/2 L/4 L/8 L/2i 1 L/4 L → L/2 → L/4 → L/8 → … → L/2i → … → 1Figura 4.10: Spray&Wait binario
Una variante della fase di spray molto usata riguarda il modo in cui vengono
trasmesse le L copie ed `e chiamata Binary Spray&Wait Figura 4.10 . Il nodo
sorgente S di un messaggio all’inizio possiede L copie, e poi quando incontra un
nodo B che non ha copie gliene consegna L
2 e si tiene per se l’altra met`a. A questo
punto sia S che B possono trasmettere la met`a delle copie che possiedono e cosi via fino a che ogni nodo che ha ricevuto almeno una copia non rimane con una sola,
a quel punto pu`o effettuare solo la trasmissione diretta. Questa euristica rispetto alla versione originale produce ritardi di consegna minori. La scelta di L incide sul ritardo di consegna dei messaggi, non dipende dalla dimensione della rete e dal raggio di trasmissione, ma dipende solamente dal numero di nodi.
• Prophet:
Prophet [19] `e un’evoluzione del protocollo di routing Epidemic in cui viene usato un approccio probabilistico basato sull’ipotesi che la mobilit`a dei nodi non `e pura- mente random, ma ha una serie di propriet`a deterministiche, basate per esempio su comportamenti ripetuti. A tal proposito si assume che se un nodo tende a visitare determinati luoghi pi`u di altri, `e probabile che ci passer`a nuovamente in futuro; oppure se due nodi si sono incontrati spesso `e probabile che si incontreranno nuo- vamente in futuro.
Prophet introduce il concetto di “prevedibilit`a di consegna”, delivery predictability P (a, b) ∈ [0, 1], una metrica probabilistica che stima la probabilit`a che un nodo a sia in grado di consegnare un messaggio al destinatario finale b.
Come in Epidemic, ogni volta che due nodi si incontrano si scambiano le loro sum- mary vector, ma in Prophet tale lista non contiene solo i messaggi ma anche i valori delle delivery predictability rispetto ai nodi destinatari dei messaggi (se conosciu- ti); sulla base delle informazioni scambiate ogni nodo aggiorna le proprie delivery predictability. Successivamente, uno dei due nodi inoltra all’altro i messaggi che non possiede solo se quest’ultimo ha pi`u probabilit`a di incontrare il destinatario fi- nale del messaggio Figura 4.11. In questo modo si ha un aumento delle trasmissioni nella rete, ma si limitano ancora di pi`u le copie dei messaggi e si ottiene migliori prestazioni nella loro diffusione. Le fasi principali sono le seguenti:
1. Calcolo dei valori di delivery predictability:
Ogni volta che due nodi si incontrano aggiornano i propri valori incrementan- doli. Sia Pinit∈ [0, 1] la costante di inizializzazione, abbiamo che l’incremento
`e dato da:
P
(a,b)= P
(a,b)old+ (1 − P
(a,b)old) ∗ P
init(4.1)
Se due nodi non si incontrano per un determinato lasso di tempo i loro valori invecchiano. Sia γ ∈ [0, 1] la costante di invecchiamento, k l’unit`a di tempo trascorso dall’ultimo aggiornamento della prevedibilit`a:
Inoltre la delivery predictability gode della propriet`a transitiva, se il nodo a incontra spesso il nodo b che a sua volta incontra spesso il nodo c, allora il nodo a ha un’alta probabilit`a di incontrare il nodo c, di conseguenza qualsiasi altro nodo i che ha un messaggio per c lo pu`o inoltrare direttamente ad a. Sia β ∈ [0, 1] la costante transitiva che riflette l’impatto della transitivit`a:
P
(a,b)= P
(a,b)old+ (1 − P
(a,b)old) ∗ P
(a,c)∗ P
(a,c)β(4.3)
2. Decidere una strategia di consegna:
Quando un nodo riceve un messaggio e non ci sono percorsi verso la destinazio- ne, memorizza il messaggio localmente all’interno del proprio buffer e attende di incontrare un nodo per inoltrarglielo. Ad ogni incontro `e necessario pren- dere una decisione sulla consegna, e non `e sempre facile. Pu`o succedere che il nodo a incontra b e il valore della delivery predictability di b con il destinata- rio di m `e pi`u basso di quello di a, quindi il messaggio non viene consegnato, ma b pu`o a sua volta incontrare c che ha un alta probabilit`a di incontrare il destinatario, pi`u alta anche di a stesso. A tal proposito `e utile fissare una so- glia e consegnare un messaggio a un nodo soltanto se la delivery predictability supera tale soglia.