Progetto di un Group
Communication System
Reti di Calcolatori LS
A.A. 2003-2004
Giampaolo Capelli
Obiettivi
Realizzazione di un sistema per la
comunicazione di gruppo:
basato su view (stato del gruppo visibile a un
membro), con ipotesi di gruppo dinamico
membri del gruppo peer-to-peer:
coordinamento senza centralizzazione
comunicazione tramite invio di messaggi di
gruppo: invio di un messaggio a tutti i
membri del gruppo (a quelli della view)
Obiettivi (2)
Aggiunta di reliability al multicast:
ritrasmissione messaggi persi, ma senza
duplicazione
Tolleranza ai guasti dei membri del gruppo:
crash detection
Ordinamento FIFO e causale dei messaggi
Ogni membro può offrire dinamicamente al
gruppo dei servizi
–
–
acceduti come oggetti remoti
scoperti tramite discovery
View
View = conoscenza che un membro ha del
gruppo
Gruppo dinamico: variabile nel tempo, uso
di un meccanismo di membership per
costruire le view
Problema di sincronizzazione e consistenza
delle view, anche a fronte di eventuali crash
dei membri
Scenario
1
2
4
1
2
3
4
1
2
3
4
3
1
1
2
2
3
4
3
4
Membership
Problema della consistenza delle view nel
tempo, a fronte di tre tipi di evento
–
–
–
join: adesione al gruppo
leave: uscita dal gruppo
crash: blocco
join e leave notificati al gruppo con messaggi
dagli stessi membri che aderiscono o
abbandonano
crash rilevato in modo ipotetico da ogni membro,
basandosi su un timeout
Supporto per lo scambio di messaggi
Multicast di IGMP, a cui si aggiunge reliability
Il mittente ha la responsabilità di verificare l’avvenuta
ricezione dei messaggi inviati: attende conferma (ack)
di ricezione da parte dei membri della view
Due categorie di messaggi:
–
–
di controllo
ordinari (applicativi)
Ordinamento causale oneroso, viene imposto solo sui
messaggi ordinari
Ordinamento FIFO imposto per tutti i messaggi tranne
quelli critici, esempio di ipotesi di crash
semantica della Reliability per la
consegna dei messaggi
sincronizzazione fra le view: risolta in maniera passiva,
nessun uso di sincronizzazioni forti (come ad es. 2 phase
lock). Modifica delle view a fronte di:
–
–
Possibili inconsistenze temporanee fra view dei membri
garanzia di consegna dei messaggi a tutti i membri, in
ordine e senza duplicati sotto le ipotesi di:
–
–
–
rilevazioni di crash: basate su ipotesi da confermare
messaggi di join o leave: ricevuti in maniera asincrona
view complete e consistenti
membri non bloccati
tempi di ricezione compatibili con timeout di crash detection
Altrimenti, consegna ai membri presenti nella view del
mittente, a meno di loro crash
Protocollo di join
Il nuovo arrivato, 3, manda un messaggio di join al
gruppo, ancora non ne conosce la composizione
Gli altri rispondono con un messaggio di conferma
(has joined), utile a 3 per costruire la propria view
(discovery)
1
has joined
join
3
2
Protocollo di join (2)
il nuovo entrante, durante il join, non ha
conoscenza del gruppo, perciò non può
controllare che il proprio messaggio di
adesione venga ricevuto da tutti
è sufficiente che raggiunga un membro, il
quale, divulgando il messaggio di tipo has
joined, propagherà a tutti la notizia della sua
entrata
Crash Detection
a carico dei membri ancora “vivi”
Non è un meccanismo esatto, funziona tramite ipotesi di
crash (problemi di rete possono causare finti crash)
Legato alla reliability del multicast: un mittente aspetta
conferma di ricezione, allo scadere di un timeout
ritrasmette, ma dopo n volte sospetta dei destinatari che
non hanno risposto.
dimensione del timeout critica per le prestazioni:
rispetto alla frequenza media dei crash o alla velocità
di comunicazione della rete:
Timeout piccolo sistema instabile (continui sospetti)
Timeout grande molte inconsistenze (membri bloccati
considerati come ancora vivi)
Crash Detection (2)
4
1
messaggio M
2
3
ack dei membri per M (in unicast)
Messaggio di suspect crashed di 2
invio di messaggi di hello a cui 2 non risponde
e conferma di suspect crashed di 2
Ordine di rimuovere 2 dalla view
Crash Detection (3)
È possibile la ricezione di messaggi da un
membro M escluso per ipotesi di crash:
–
–
se M è stato escluso ingiustamente per un ritardo di
risposta dovuto a rallentamenti nella rete
oppure se, dopo il blocco, M riprende l’esecuzione
In entrambi i casi M non invia messaggi di join:
un suo messaggio provoca comunque la
divulgazione dei messaggi has joined negli altri,
che lo considerano nuovamente nel gruppo
Ritrasmissioni
Messaggi inviati vengono bufferizzati fino a
che non si ricevono gli ack dei destinatari o
ne è stato dichiarato il crash
Periodicamente, se non arriva l’ack, si
riinviano fino a un certo numero di volte
Fino a che il crash detector non inizia il
protocollo di crash detection mandando al
gruppo un sospetto
Ordinamento dei Messaggi
FIFO: tramite uso di numeri di sequenza progressivi e
riordinamento sui riceventi
Causale (solo per msg applicativi): protocollo basato su
vector clock e causal delivery rule
Ogni membro gestisce un vettore di clock logici, prima di
inviare un msg incrementa di uno la propria componente
e inserisce nel msg una copia del vettore
Sui riceventi: a ogni ricezione di un messaggio ordinario,
si ritarda il delivery fino a che non è vera la causal
delivery rule
Al delivery si aggiornano le componenti del vector clock
locale relative agli altri: max{valore nel msg, valore
corrente}
Causal delivery rule
Delivery (consegna al livello applicativo)
ritardato fino a che sono vere entrambe:
1.
2.
VT(msg)[sender] = VT(receiver)[sender_id]+1
VT(msg)[k] <= VT(receiver)[k], k, ksender_id
Il cui significato è:
1.
2.
Il msg è il successivo inviato dal mittente
Dall’ultimo msg inviato dal mittente, gli altri non ne
hanno mandati altri
Protocollo per causal order
Gruppo in evoluzione nel tempo: necessaria
una fase preliminare di scambio di
informazioni di clock tra membri.
In questa fase si ignora la causal delivery
rule e non è garantito l’ordinamento causale:
–
–
esempio in caso di aggiunta di un nuovo membro
non è un problema, se in questa fase si mandano
solo msg di controllo
Protocollo per causal order
C{0,0,3}
C{3,0,3}
B{0,5,0} B{3,5,0}
C{3,6,3} C{3,6,4}
B{3,6,0}
B{3,6,4}
C{3,6,5}
C{3,7,5}
B{3,7,5}
B{3,6,5}
{3,7,5}
A{2,0,0}
A{3,0,0}
A{3,6,0}
A{3,6,4}
A{3,6,5} A{3,7,5}
Pubblicazione di servizi
I membri possono pubblicare dei servizi (come
oggetti remoti) a disposizione del gruppo. I
membri non hanno alcuna conoscenza a priori
dei servizi.
Un membro può:
–
–
eseguire discovery dei servizi, ottenendo l’elenco e
la locazione di quelli attualmente disponibili,
assieme alle funzionalità che offre
richedere un particolare servizio e invocarlo, se
disponibile
Realizzazione del prototipo
Uso della piattaforma Java
Socket multicast (con datagrammi UDP)
Servizi come oggetti remoti acceduti con RMI,
esecuzione di rmiregistry sui membri
Uso della reflection di Java per conoscere
l’interfaccia dei servizi (signature dei metodi)
Semplificazioni:
–
–
un servizio membro
ack mandati in unicast con UDP
Limiti e sviluppi futuri
IGMP per il multicast: uso limitato
Sistema poco scalabile:
– alto numero di messaggi di controllo
– meccanismo pesante per la gestione degli ack: si
attende un ack per ogni messaggio
Possibili migliorie:
– politiche di ritrasmissione con ack relativi a un
insieme di messaggi e selective repeat, ack negativi
– uso di unicast, invece che multicast, per le
ritrasmissioni e i messaggi di hello
– aggiungere meccanismo di publish/subscribe per la
richiesta e notifica di servizi
Conclusioni
protocolli e soluzioni per group communication
system view-oriented con coordinamento fra pari:
supporto per gruppo dinamico
fault tolerant e crash detection dei partecipanti
qualità nel servizio di consegna dei messaggi
ordinamento FIFO e causale dei messaggi
servizi conoscibili tramite discovery e accessibili
come oggetti oggetti remoti.
timeout T del crash detector: punto cruciale per la
stabilità compromessa in caso se T troppo piccolo
rispetto ai tempi medi di comunicazione
dell’infrastruttura di rete
Scarica
