Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Progetto IS-MANET
WP3: Algoritmi e modelli
Roberto BERALDI
Milano 01.03.2004
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
WP3: Task..
•
Internetworking e protocolli end-to-end
– Definizione di modelli e metodologie per lo studio e la specifica di algoritmi
host-to-host (routing), end-to-end (trasporto).
•
Algoritmi distribuiti e discipline di comunicazione
–
•
Studio e specifica di algoritmi distribuiti fondamentali su MANET,.. discipline
di comunicazione uno-a-molti (group multicast) e molti-a-molti
(publish/subscribe),..
Coordinamento
– Attività di coordinamento tra i workpackage WP4, WP5 e WP6 al fine di
controllare la coerenza delle soluzioni innovative proposte e la loro effettiva
integrabilità
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
WP3: Modelli ed algoritmi
• I Task del WP
– M5: DRAFT; M10: REVISED; M28: FINAL
• Personale
– 3 Strutturati
• Baldoni, Beraldi, Cioffi
– 2 Dottorandi
• Milani, Querzoni
– 1 Tecnico
• Termini
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Contributi…
• Protocolli di routing unicast
• Algoritmi e modelli per sistemi mobili
• Aspetti Applicativi
– (Messina)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Protocolli di routing
•
Stato dell’arte protocolli routing unicast
– R.Beraldi, R.Baldoni, "Unicast Routing Techniques for Mobile Ad Hoc
Networks", The Handbook of Mobile Ad Hoc Networks, Chapter 7, CRC
press, dicembre 2002
•
Studio di schemi di caching in protocolli ibridi
– R. Beraldi, R. Baldoni, “A Caching Scheme for Routing in Mobile Ad Hoc
Networks and Its Application to ZRP”, IEEE Transactions on Computers,
agosto 2003
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Algoritmi e modelli sistemi dinamici
•
Pub/Sub
– A. Virgillito, R. Beraldi, R. Baldoni On Event Routing in Content-Based
Publish/Subscribe through Dynamic Networks, (FTDCS'03),
– R. Baldoni, R. Beraldi, S. Tucci Piergiovanni, A. Virgillito, Measuring
Notification Loss in Publish/Subscribe Communication Systems,
Proceedings of the 10th International Symposium Pacific Rim Dependable
Computing, Papeete, Tahiti, French Polynesia, March 2004
– R. Baldoni, R. Beraldi, S. Tucci Piergiovanni, A. Virgillito, On the Modelling
of Publish/Subscribe Communication Systems, Concurrency and
Computation: Practice and Experiences, John Wiley and Sons (to appear)
•
Architettura middleware per comunicazioni “inter-hoc”
– M. Patini, R. Beraldi, C. Marchetti, R. Baldoni, A Middleware Architecture
for Inter ad-hoc Networks Communication, MMIS03-WISE 2003 - Rome
(Italy)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Algoritmi e modelli sistemi dinamici
•
DMUTEX in reti MANET
– Estensione del lavoro R. Baldoni, A. Virgillito, R. Petrassi. A Distributed
Mutual Exclusion Algorithm for Mobile Ad-Hoc Networks , 7th IEEE
Symposium on Computers and Communications (ISCC 2002), Italy, 1-4 July
2002
– S. Baehni, R. Baldoni, R. Guerraoui, B. Pochon The Driving Philosophers,
http://ic2.epfl.ch/publications/documents/IC_TECH_REPORT_200415.pdf
•
Ordinamento degli eventi in ambienti mobili
– R. Prakash and R Baldoni, Causality and the Spatial-Temporal Ordering
in Mobile Systems, Journal of Mobile Networks and Applications
(MONET), Baltzer, to appear
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Caching
• Problema Nei sistemi wireless è facile ottenere informazioni per
il routing (le trasmissioni sono bcast).
• Il problema e’ assicurarne la validità., ossia che l’informazione
corrisponda all’attuale topologia
• Quando cancellare le info in cache? (timeout..)
• Proposta Sistema di caching basato su zone con un nodo
(cache leader) responsabile della propagazione e validita’ delle
informazioni da scrivere in cache da parte dei nodi della zona..
• Studio simulativo dello schema nel framework ZRP (Zone
Routing Protocol)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Caching
• Il cache leader diffonde informazioni di routing relative ai
percorsi attivi (ai quali partecipa) dentro una zona (caching
zone) e ne assicura la validità
cache leader
A
S
A
C2
caching zone
D
path attivo
• Ad esempio, C2 può diffondere nella sua zona informazioni di
raggiungibilità dei nodi che formano il percorso attivo (ne
diventa il “next-hop” rispettivamente ai nodi della zona)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Pub/Sub
• Problema Definzione di un modello computazionale per sistemi
Pub/Sub
• Approccio Assumiamo l’esistenza di due bound sui tempi di
propagazione nel sistema per le operazioni di …
– sottoscrizione (desottoscrizione) (Tsub e Tusub) e
– pubblicazione di un evento (Tdiff)
• Ciò consente di (i) definire un intervallo di sottoscrizione, usato
nelle definizioni di liveness e safety; (ii) sviluppare un modello
per valutare le prestazioni del sistema (notification probability)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Pub/sub
•
•
Dopo il tempo Tsub, tutti i processi del
sistema conoscono con probabilità 1
la nuova sottoscrizione,
(analogamente per Tusub)
L’intervallo di sottoscrizione e’
delimitato dagli eventi sub/usub
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Pub/sub
•
Dopo Tdiff tutti i processi ricevono
le notifiche con prob. 1
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Proprietà…
• History H, insieme ordinato di eventi generati dalle operazioni
pub, sub, pub, notify
•
Safety
– Legality: Nessun processo riceve notifiche di eventi per i quali non
è interessato
– Validity: Nessun processo riceve notifiche di eventi mai pubblicati
•
Liveness
– Se la sottoscrizione di un processo P ha inizio at tempo s ed ha
durata maggiore di Tdiff, allora P riceve almeno le notifiche di tutti
gli eventi pubblicati in [s+Tsub, s+TON -Tusub]
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
pub/sub: perfomance model 1
• Tempo di pubblicazione di un evento, dato che essa si è
verificata nell’intervallo di sottoscrizione è una v.c.
uniformemente distribuita
• Probabilità di notifica, d
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
pub/sub: perfomance model
• Classe di funzioni potenza,
– Parametro esponente (1/r)
1
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
0
0,2
0,4
0,6
0,8
1
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
pub/sub: perfomance model
• Classe di funzioni potenza,
– Parametro esponente (1/r)
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
pub/sub: perfomance model
• Modello epidemico
– Sistema composto da N nodi..
– Se un nodo riceve una sottoscrizione
è infettato
– La rapidità con cui nuove parti sono
infettate è direttamente
proporzionale alla percentuale del
sistema infettato ed al numero di
nodi non ancora infettati
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
DMutex
• Algoritmo token-based con circolazione del token on-demand
• Il token segue un ring logico e dinamico
– Il prossimo nodo e’ stabilito da una Politica P, nel nostro caso si
sceglie il nodo più vicino (con il minimo numero di hop) tra quelli
non ancora visitati
– Informazioni di routing mediante DSR
• Simulazioni mediante GloMoSim
• Prestazioni:
– combinano quelle degli algoritmi Token Asking e Circulating Token
Università di Roma “La Sapienza”
Dipartimento di Informatica e Sistemistica
Conclusioni…
• Affrontati temi relativi ad algoritmi e modelli (routing
unicast, pub/sub, dmutex)
• Altri dettagli nel deliverable…