Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 6.Comunicazioni


Sommario

  • Comunicazioni di gruppo
  • Multicast
  • Reliable multicast
  • Ordinamenti
    • FIFO multicast
    • Causal multicast
    • Total multicast
  • Implementazione

Comunicazioni di gruppo

Gruppo chiuso: solo i membri possono inviare messaggi in multicast al gruppo
Gruppo aperto: anche i non membri possono inviare messaggi in multicast al gruppo

Comunicazioni di gruppo tolleranti ai guasti e/o ordinate

Obiettivo

  • Assicurare che i processi possano scambiare messaggi di gruppo anche in presenza di fallimenti dei canali di comunicazione e/o dei processi stessi.

e/o

  • Assicurare che i messaggi inviati a un gruppo siano ricevuti in maniera ordinata

Consegna affidabile dei messaggi

Principali strategie:

  • Error Masking
    • ridondanza spaziale
    • ridondanza temporale
  • Error Detection and Recovery
    • basata su acknowledgements (acks) e timeout

Error Masking

Ridondanza Spaziale: I processi sono connessi con collegamenti ridondanti
Per mascherare k omissioni, occorrono k+1 collegamenti


Error Masking

  • Ridondanza temporale: il messaggio viene inviato più volte
  • Per mascherare k omissioni, il messaggio deve essere inviato k+1 volte

Error Masking

  • In entrambi i casi si pone il problema dei messaggi duplicati: essi devono essere scartati dal ricevente
  • È difficile in generale trovare il giusto compromesso tra semplicità di recovery e consumo di banda.

Error detection e recovery

  • Gli ack possono essere inviati quando:
    • Un messaggio viene ricevuto (positive ack, v. figura)
    • Un timeout scade al ricevente, che decreta la perdita di un messaggio (negative ack)

Schemi per l’invio dei messaggi ack

  • Nello schema con positive ack, un messaggio viene ritrasmesso se non viene ricevuta una conferma al mittente entro un timeout predefinito.
    • La failure viene individuata più rapidamente in caso di traffico sporadico.

Schemi per l’invio dei messaggi ack

  • Nello schema con negative acks, il ricevente richiede una ritrasmissione inviando un ack negativo
    • Minimizza il traffico di rete ma richiede l’implementazione di uno dei seguenti meccanismi:
      • Numerazione dei messaggi, in maniera tale da poter richiedere la ritrasmissione di un particolare messaggio (se ad esempio viene ricevuto il messaggio i ma non il messaggio i-1)
      • Una strategia time-triggered in maniera tale che il ricevente sappia quando deve ricevere un messaggio.

Livelli di affidabilità

  • Livelli di affidabilità in comunicazioni multicast:
    • Unreliable multicast – Nessuno sforzo per superare failures dei canali di comunicazione; il multicast è affidabile se lo sono i canali e il mittente.
    • Best-effort multicast – Il mittente compie qualche azione per assicurare la consegna del messaggio, come ad esempio ritrasmettere lo stesso, ma non ci sono garanzie
    • Reliable multicast – I partecipanti (membri del gruppo) si coordinano per garantire che il messaggio venga consegnato a tutti i destinatari corretti.

Basic Multicast

  • 2 primitive: B-multicast e B-deliver
  • Garantiscono che un processo corretto prima o poi riceverà il messaggio, a patto che il mittente non fallisca
  • La primitiva di B-multicast può essere implementata utilizzato una primitiva per la comunicazione punto-punto su canale affidabile:
    • B-multicast(g,m): for each process p Σ g, send(p,m)
    • B-receive(m) at p: B-deliver(m) at p
  • Soffre del problema dell’ack-implosion
  • Spreca larghezza di banda
  • … e comunque il mittente può fallire in ogni istante durante l’esecuzione del B-multicast!

Reliable Multicast

  • Hadzilacos e Toueg (1994), Chandra e Toueg (1996)
  • Soddisfa le seguenti proprietà:
    • Integrityun processo corretto p riceve m al più una volta. Inoltre, p Σ group(m) e m è stato inviato via multicast da sender(m)
    • Validity se un processo corretto p invia m in multicast, prima o poi riceverà m
    • Agreement – se un processo corretto riceve m, allora tutti i processi corretti in group(m) prima o poi riceveranno m

Uniform reliable multicast

  • Le definizioni delle proprietà del reliable multicast fanno riferimento a processi corretti (cioè che non falliscono mai).
  • Una proprietà valida a prescindere dal fatto che i processi siano corretti o meno si dice uniforme.
  • In particolare si ha:
    • Uniform agreement – se un processo (corretto o meno) riceve m, allora tutti i processi corretti in group(m) prima o poi riceveranno m

Implementazione del Reliable Multicast con B-multicast


Implementazione del Reliable Multicast con B-multicast

L’implementazione soddisfa le proprietà del reliable multicast:

Integrità: discende dall’integrità dei canali di comunicazione.

Validità: è evidente che un processo corretto prima o poi fa il B-deliver a sé stesso.

Accordo: discende dal fatto che ogni processo corretto esegue B-multicast dopo B-deliver. Se dunque un processo corretto non effettua R-deliver, ciò può essere dovuto solo al fatto che non ha fatto B-deliver; ciò può sussistere solo se nessun altro processo corretto ha fatto il B-deliver: in tal caso nessuno farà R-deliver.

  • Questa implementazione è corretta in un sistema asincrono, ma inefficiente (il messaggio è inviato |g| volte a ciascun processo)

Implementazione del Reliable Multicast con B-multicast

L’implementazione soddisfa anche la proprietà di uniform agreement.
Se ad esempio un processo non è corretto e va in crash dopo aver effettuato R-deliver, poiché in precedenza ha sicuramente effettuato B-deliver, nondimeno dunque tutti i processi corretti riceveranno il messaggio.

N.B.: Se si invertono le istruzioni ‘R-deliver m’ e ‘if(q≠p) then B-multicast(g,m) endif’, l’implementazione non soddisfa più la proprietà di uniform agreement.

Ordinamento FIFO

  • Se un processo corretto invia in multicast m e poi m’, allora ogni processo corretto che riceverà m’ avrà già ricevuto m
  • Versione uniforme: idem senza ‘corretto’

Ordinamento causale

  • Se multicast(g,m) → multicast(g,m’) , dove è la relazione happened-before nell’ambito del gruppo g, allora ogni processo corretto che riceverà m’ avrà già ricevuto m.
  • Versione uniforme: idem senza ‘corretto’.

Ordinamento causale

  • L’ordinamento causale implica quello FIFO, poiché gli invii di uno stesso processo sono in relazione HB
  • L’ordinamento causale estende l’ordinamento FIFO con l’ordinamento della ricezione dei messaggi che, pur inviati da processi diversi, sono in relazione di potenziale causalità
    • Se un processo p invia in multicast un messaggio m ed un processo p’≠p riceve m prima di inviare in multicast m’, allora nessun processo corretto riceve m’ a meno che non abbia già ricevuto m

Ordinamento totale

  • Se un processo corretto riceve i messaggi m e poi m’, allora ogni altro processo corretto che riceve m’ avrà già ricevuto m.
  • Uniform Version: idem senza ‘corretto’.
  • L’ordinamento totale non implica quello FIFO né quello causale.

Confronto degli ordinamenti

Nell’esempio i messaggi TO sono ricevuti nell’ordine opposto rispetto all’invio: la definizione di TOM richiede infatti che l’ordine sia lo stesso per tutti, ma può essere arbitrario.


Un approccio modulare ai protocolli di multicast


Esempio: bulletin board

Un gruppo per argomento; gli utenti si sottoscrivono agli argomenti di interesse.
Un utente invia un messaggio su un argomento → broadcast al gruppo.
Serve la semantica del reliable multicast se si vuole garanzia che tutti gli iscritti ricevano i messaggi.
Serve la semantica dell’ordinamento FIFO se si vuole che tutti i messaggi inviati da uno stesso utente siano ricevuti nell’ordine di invio.

Serve la semantica dell’ordinamento causale se si vuole, ad es., che il messaggio “Re: Microkernels” sia ricevuto dopo il messaggio “Microkernels” cui si riferisce.Serve la semantica dell’ordinamento totale se si vuole che la numerazione dei messaggi sia la stessa per tutti gli utenti.


Implementazione dell’ordinamento FIFO

  • L’ordinamento si realizza mediante l’utilizzo di numeri di sequenza
  • Assunzione: i gruppi non si sovrappongono
  • Sp – contatore dei messaggi inviati dal processo p al gruppo g
  • Rq - numero di sequenza dell’ultimo messaggio delivered da p, inviato a g da q.
  • Hold-Back-Queue(p) coda dei messaggi fuori sequenza in attesa di essere ricevuti da p

Implementazione del FIFO Reliable Multicast

Si può usare la stessa implementazione del FIFO multicast, usando R-multicast al posto di B-multicast.


Implementazione dell’ordinamento causale

  • L’implementazione tiene conto solo delle relazioni HB tra i messaggi multicast, non di quelle tra messaggi diretti (one-to-one) scambiati tra i processi
  • Si può far uso di orologi vettoriali (Vector Clocks)
    • l’elemento i-esimo conta il numero di messaggi inviati dal processo i-esimo in relazione HB con il prossimo messaggio
  • Assunzione: gruppi chiusi non sovrapposti
  • Per effettuare il CO-multicast, un processo incrementa il “proprio” elemento nel vettore ed esegue B-multicast al gruppo g del messaggio marcato col vector clock.

Implementazione dell’ordinamento causale

  • Quando pi fa il B-deliver di un messaggio inviato da pj, prima di effettuare il CO-deliver deve inserirlo nella hold-back queue CO-deliver finché non ha fatto il CO-deliver di tutti i messaggi in relazione HB con esso
  • Pideve perciò verificare di aver fatto:
    • il CO-deliver di tutti i messaggi precedenti inviati da pj, e:
    • il CO-deliver di tutti i messaggi di cui pjaveva fatto il CO-deliver prima di inviare il messaggio in questione
  • Queste condizioni possono essere verificate esaminando i vector timestamps dei messaggi ricevuti.

Implementazione dell’ordinamento causale


Implementazione di Causal Reliable Multicast

Il multicast con ordinamento causale affidabile può essere implementato a partire dalla implementazione del Causal Multicast, usando R-multicast al posto di B-multicast.

Implementazione dell’ordinamento totale

  • Basata sulla marcatura dei messaggi con identificatori totalmente ordinati, in modo che tutti i processi possano prendere le stesse decisioni
  • Il delivery è come per l’ordinamento FIFO, ma i numeri di sequenza si riferiscono al gruppo, non al processo
  • Primo metodo: implementazione mediante processo sequenziatore
    • un messaggio m è inviato sia a g sia a sequencer(g), etichettato con un id univoco id(m)
    • sequencer(g) può coincidere con un membro di g
    • sequencer(g) gestisce un numero di sequenza per il gruppo sg, con cui marca i messaggi di cui effettua B-deliver
    • sequencer(g) annuncia i numeri di sequenza inviando messaggi di ordinamento a g tramite B-multicast
    • un messaggio resta nella hold-back queue finché non può esserne effettuato il TO-deliver, in base al suo numero di sequenza

Implementazione dell’ordinamento totale


Implementazione dell’ordinamento totale

  • Secondo metodo: Algoritmo ISIS (Birman, 1987), valido per gruppi aperti o chiusi.
  • I processi concordano collettivamente sui numeri di sequenza, con un algoritmo distribuito.

Ogni ricevente propone il numero di sequenza al multicaster che genera il numero “agreed

Ogni processo q di g possiede:

Aqg: il più alto numero di sequenza finora convenuto

Pqg: il più alto numero di sequenza finora proposto dallo stesso q


Implementazione dell’ordinamento totale

Ogni ricevente propone:
Pqg:=Max(Aqg,, Pqg)+1
e assegna temporaneamente al messaggio il numero proposto, inserendolo nella hold back queue; questa è ordinata con il valore più piccolo in testa.

Il multicaster raccoglie le proposte e seleziona il valore maggiore a, quindi effettua B-multicast<i,a> (i è l’id univoco con cui il multicaster ha etichettato m).

Ogni ricevente assegna:
Aqg:=Max(Aqg, a)
e associa il valore a al messaggio, quindi riordina la hold-back queue se il valore convenuto è diverso da quello proposto.
Quando al messaggio in testa alla coda viene assegnato lo stesso numero proposto, viene inserito in una delivery queue.

Implementazione del Causal Total Multicast

  • Se si combina l’algoritmo per l’ordinamento causale (CO) con quello per il multicast totalmente ordinato (TO) basato sul sequencersi ottiene un ordinamento che è ordinato sia causalmente sia totalmente (C&TO)
    • il sequenziatore deve fare il delivery secondo l’ordinamento causale, e il multicast dei numeri di sequenza dei messaggi nell’ordine con cui li riceve.
    • i processi nel gruppo di destinazione non effettuano il deliver prima di aver ricevuto un messaggio order dal sequenziatore e il messaggio è il prossimo nella sequenza
    • in tal modo, poiché il sequencer effettua il deliver in ordine causale, e tutti gli altri processi lo effettuano nell’ordine del sequencer, l’ordinamento è sia totale sia causale.

I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design, Cap. 12 §4 eccetto “Reliable multicast over IP multicast”, IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion