PERMESSO
PERsistent MESSaging in ad hOc networks
Corso di Reti di Calcolatori L-S AA 2005-2006
Presentazione di Roberto Gamboni
Progetto di Giuseppe Vitalone, Melli Michele, Roberto Gamboni e
Valentina Bonsi
Prof. Antonio Corradi
Tutor Eugenio Magistretti
Sommario
• Introduzione Manet
• PERMESSO: struttura e progetto
• Discovery
• Replicazione
• Presence awareness
• Sviluppi futuri
Cosa è una MANET
• Mobile ad hoc networks (MANETs) come
reti ad-hoc di dispositivi mobili
• Assenza di infrastruttura di comunicazione
• Elevata dinamicità: la topologia della
MANET cambia in continuazione in base
agli spostamenti dei nodi.
PERMESSO: progetto
• Instant Messaging su MANET





Solo distanze 1-Hop
J2ME
802.11
Serializzazione fatta ad-hoc
Utilizzo di broadcast
PERMESSO: struttura
Instant messaging fra
utenti presenti nella
MANET con scambio
reliable di messaggi
Messaggistica persistente
per utenti non presenti
contemporaneamente
nella MANET
Chat Sincrona
Chat Asincrona
Discovery & Presence Awareness
Gestione dell’entrata, dell’uscita e della caduta dei nodi
nella rete organizzata in modo distribuito, con il ruolo
del coordinatore che ruota fra i presenti.
Discovery
• Fornire ad un nodo entrante le
informazioni per operare nella MANET
Soluzione decentralizzata: ogni nodo risponde per sè
 elevato numero di risposte: Overhead
Soluzione centralizzata: un nodo coordinatore
 Chi fa da coordinatore?
 Se cade il coordinatore?
Discovery
• Il nodo coordinatore risponde per tutti!
Indica l’elenco dei nodi presenti
X
X : Eccomi!
D
Nodi:
A,B,C,D,X
La risposta è inviata in Broadcast,
in modo che anche tutti gli altri
dispositivi possono aggiornare le
loro liste.
Coordinatore notifica a tutti i nodi
ogni cambiamento nella MANET
A
C
B
Chi fa il coordinatore?
• Nessun nodo ha il compito specifico di
mantenere l’elenco dei nodi online.
• Rotazione del compito di coordinatore
– Struttura ad anello logico
– Token rappresenta l’attività di coordinatore
Chi fa il coordinatore?
Ultimo nodo entrato
Coordinatore
Coordinatore
Node X
X:M ...
T
Q
Refuse
X
W
Y:M ...
Accept
Z
Y
Node Y
Se cade il coordinatore?
• In un modello centralizzato se cade il
•
coordinatore non si ha più servizio.
La dinamicità dell’anello logico non consente di
applicare politiche di rigenerazione del Token
basata su time out.
Modello di Replicazione
un nodo si preoccupa di mantenere la lista dei
nodi in modo da essere in grado di sostituire il
coordinatore in caso di guasto.
Modello di Replicazione
• Modello a copie calde
Ogni modifica viene comunicata alla copia
• Modello Passivo?
Fase di checkpoint con cui la copia viene
aggiornata
• Modello Attivo?
La copia provvede ad aggiornarsi appena entra
un nuovo nodo
Modello di Replicazione
Coordinatore
Node X
Replicatore
EXIT
EXIT
Elaborazione attiva
della copia.
Ridondante!
Ma con poco aumento di
computazione otteniamo
una lista sempre corretta
in caso di caduta di un
nodo in un qualsiasi
momento.
ONLINE
ONLINE rappresenta la fase di Checkpoint
tra copia principale e copia passiva.
Politica Eager?
Politica Lazy?
Presence Awareness
• Obiettivo: fornire a tutti gli utenti una visione
aggiornata dei nodi presenti con cui possono
chattare
 Ogni nodo deve confermare periodicamente la
sua presenza al coordinatore
 Dopo la mancata ricezione di due messaggi si
suppone che il nodo sia caduto (si ritarda la
rilevazione ma un solo messaggio potrebbe
essere perso)
Presence Awareness
Coordinatore
Node X
Aumento notevole del
numero di messaggi inviati!
CONFIRM
CONFIRM
Aumento del carico
computazionale del nodo
coordinatore!
 Servizio costoso
Dopo l'assenza di due Confirm
si assume la caduta del Nodo X
L’alto numero di messaggi non
deve influire sulla qualità del
servizio di messaging.
Conclusioni
• Discovery e Presence Awareness
forniscono il supporto base per lo sviluppo
dei servizi di chat sincrono e asincrono.
• Replicazione per maggiore affidabilità.
Possibili sviluppi
• Load balacing
• Scalabilità
• Protocolli Reattivi per Multi-hop