PERMESSOPERMESSOPERsistent PERsistent MESSagingMESSaging in ad hOc in ad hOc

networksnetworks

Corso di Reti di Calcolatori L-S AA 2005-2006Corso di Reti di Calcolatori L-S AA 2005-2006

Presentazione di Presentazione di Roberto GamboniRoberto Gamboni

Progetto di Progetto di Giuseppe Vitalone, Melli Michele, Roberto Giuseppe Vitalone, Melli Michele, Roberto Gamboni e Valentina BonsiGamboni e Valentina Bonsi

Prof. Antonio CorradiProf. Antonio CorradiTutor Eugenio MagistrettiTutor Eugenio Magistretti

SommarioSommario

• Introduzione ManetIntroduzione Manet

• PERMESSO: struttura e progettoPERMESSO: struttura e progetto

• DiscoveryDiscovery

• ReplicazioneReplicazione

• Presence awarenessPresence awareness

• Sviluppi futuriSviluppi futuri

Cosa è una MANETCosa è una MANET

• Mobile ad hoc networks (MANETs) come Mobile ad hoc networks (MANETs) come reti ad-hoc di dispositivi mobili reti ad-hoc di dispositivi mobili

• Assenza di infrastruttura di Assenza di infrastruttura di comunicazionecomunicazione

• Elevata dinamicità: la topologia della Elevata dinamicità: la topologia della MANET cambia in continuazione in base MANET cambia in continuazione in base agli spostamenti dei nodi.agli spostamenti dei nodi.

PERMESSO: progettoPERMESSO: progetto

• Instant Messaging su MANETInstant Messaging su MANET

Solo distanze 1-Hop Solo distanze 1-Hop

J2MEJ2ME

802.11802.11

Serializzazione fatta ad-hocSerializzazione fatta ad-hoc

Utilizzo di broadcastUtilizzo di broadcast

PERMESSO: strutturaPERMESSO: struttura

Discovery & Presence Awareness

Chat Sincrona Chat Asincrona

Instant messaging fra utenti presenti nella MANET con scambioreliable di messaggi

Messaggistica persistenteper utenti non presenti contemporaneamente

nella MANET

Gestione dell’entrata, dell’uscita e della caduta dei nodinella rete organizzata in modo distribuito, con il ruolo

del coordinatore che ruota fra i presenti.

DiscoveryDiscovery

• Fornire ad un nodo entrante le Fornire ad un nodo entrante le informazioni per operare nella MANETinformazioni per operare nella MANET

Soluzione decentralizzata: ogni nodo risponde per sèSoluzione decentralizzata: ogni nodo risponde per sè

elevato numero di risposte: Overheadelevato numero di risposte: Overhead

Soluzione centralizzata: un nodo coordinatoreSoluzione centralizzata: un nodo coordinatore

Chi fa da coordinatore?Chi fa da coordinatore?

Se cade il coordinatore?Se cade il coordinatore?

• Il nodo coordinatore risponde per tutti!Il nodo coordinatore risponde per tutti!

Indica l’elenco dei nodi presentiIndica l’elenco dei nodi presenti

DiscoveryDiscovery

A

C

B

D

X : Eccomi!

Nodi: A,B,C,D,X

X

La risposta è inviata in Broadcast, in modo che anche tutti gli altri dispositivi possono aggiornare le loro liste.

Coordinatore notifica a tutti i nodiogni cambiamento nella MANET

Chi fa il coordinatore?Chi fa il coordinatore?

• Nessun nodo ha il compito specifico di Nessun nodo ha il compito specifico di mantenere l’elenco dei nodi online.mantenere l’elenco dei nodi online.

• RotazioneRotazione del compito di coordinatore del compito di coordinatore– Struttura ad anello logicoStruttura ad anello logico– Token rappresenta l’attività di Token rappresenta l’attività di

coordinatorecoordinatore

Chi fa il coordinatore?Chi fa il coordinatore?

T

Y

X

Q

Z

W

CoordinatoreUltimo nodo entratoCoordinatore Node X Node Y

X:M ...

Refuse

Y:M ...

Accept

Se cade il coordinatore?Se cade il coordinatore?

• In un modello centralizzato se cade il In un modello centralizzato se cade il coordinatore non si ha più servizio.coordinatore non si ha più servizio.

• La dinamicità dell’anello logico non La dinamicità dell’anello logico non consente di applicare politiche di consente di applicare politiche di rigenerazione del Token basata su time out.rigenerazione del Token basata su time out.

Modello di Modello di ReplicazioneReplicazioneun nodo si preoccupa di mantenere la lista un nodo si preoccupa di mantenere la lista dei nodi in modo da essere in grado di dei nodi in modo da essere in grado di sostituire il coordinatore in caso di guasto.sostituire il coordinatore in caso di guasto.

Modello di ReplicazioneModello di Replicazione

• Modello a copie caldeModello a copie caldeOgni modifica viene comunicata alla copiaOgni modifica viene comunicata alla copia

• Modello PassivoModello Passivo??Fase di checkpoint con cui la copia viene Fase di checkpoint con cui la copia viene aggiornataaggiornata

• Modello AttivoModello Attivo??La copia provvede ad aggiornarsi appena La copia provvede ad aggiornarsi appena entra un nuovo nodoentra un nuovo nodo

Modello di ReplicazioneModello di Replicazione

Coordinatore Node X Replicatore

EXITEXIT

ONLINE

ONLINE rappresenta la fase di Checkpointtra copia principale e copia passiva.

Elaborazione attivadella copia.

Ridondante!Ma con poco aumento di computazione otteniamo una lista sempre corretta in caso di caduta di un nodo in un qualsiasi momento.

Politica Eager?Politica Lazy?

Presence AwarenessPresence Awareness

• ObiettivoObiettivo: fornire a tutti gli utenti una : fornire a tutti gli utenti una visione aggiornata dei nodi presenti con visione aggiornata dei nodi presenti con cui possono chattarecui possono chattare

Ogni nodo deve confermare Ogni nodo deve confermare periodicamente la sua presenza al periodicamente la sua presenza al coordinatorecoordinatore

Dopo la mancata ricezione di due Dopo la mancata ricezione di due messaggi si suppone che il nodo sia messaggi si suppone che il nodo sia caduto (si ritarda la rilevazione ma un solo caduto (si ritarda la rilevazione ma un solo messaggio potrebbe essere perso)messaggio potrebbe essere perso)

Coordinatore Node X

CONFIRM

CONFIRM

Dopo l'assenza di due Confirmsi assume la caduta del Nodo X

Aumento notevole del numero di messaggi inviati!

Aumento del carico computazionale del nodo coordinatore!

Servizio costoso

Presence AwarenessPresence Awareness

L’alto numero di messaggi non deve influire sulla qualità del servizio di messaging.

Possibili sviluppiPossibili sviluppi• Load balacingLoad balacing

• ScalabilitàScalabilità

• Protocolli Reattivi per Multi-hopProtocolli Reattivi per Multi-hop

ConclusioniConclusioni• DiscoveryDiscovery e e Presence AwarenessPresence Awareness

forniscono il supporto base per lo sviluppo forniscono il supporto base per lo sviluppo dei servizi di chat sincrono e asincrono.dei servizi di chat sincrono e asincrono.

• ReplicazioneReplicazione per maggiore affidabilità. per maggiore affidabilità.