Samuele Salti

Reti di Calcolatori LSAA 2005-2006

Realizzazione di un Supporto alla Coordinazione in una MANET:

Servizi di Discovery

2

LINDA – Gelernter (1985)

Linguaggio di CoordinazioneSpazi di tuple come multiset di tuple idealmente illimitati

Nello spazio – memoriaNel tempo - persistenza

Operazioni di scrittura e di lettura/cancellazione basata su pattern matching

Bloccanti: rd(p)/in(p)Non bloccanti out(t) e rdp(p)/inp(p)Di gruppo: outg(t[]) e rdg(p)/ing(p).

Memoria associativa con selezione non deterministica.Modello fortemente disaccoppiato e con semantica forte

nello spazio -> Ts accessibile globalmentenel tempo-> Ts persistente.

3

MANET

Nodi mobili che collaborano per fornirsi servizi

Connettività basata sulla vicinanza reciproca

Topologia dinamicaComunicazione unreliableProbabili partizionamenti e ricongiungimenti

Dispositivi con capacità diverse

Interessante disporre di un modello dicoordinazione con una semantica chiara

e fortemente disaccoppiato

4

Linda in una MANET

Realizzazioni distribuite classiche di LindaPer ovviare a limiti di memoriaPer garantire fault tolerance, load balancing...

Assunzioni forti di Disconnesioni rarePossibilità di schemi di replicazione...

Da rivedere in una MANETNessuna assunzione sull'effettiva consegna dei dati inviatiNessuna possibilità di replicazione a causa alla mobilitàNessuna possibilità di coordinazione per ottenere atomicità...

5

Linda in una MANET

Abbandonare l'idea di uno spazio di tuple persistente,globalmente accessibile e modificato in

modo atomico

Spazi di tuple in una MANET comeGlobal Virtual Data Structure.

6

Global Virtual Data Structure

Una struttura dati condivisa la cui vista locale ad ogni nodo è basata su regole ben definite, tipicamente dovute alla connettività.La ricostruzione completa può avvenire solo in presenza di connettività totale -> Virtual

Trasparente all'allocazione - GVDS percepita da ogni nodo come struttura dati locale dinamicaDistribuita - Ogni partecipante possiede una parte dell'intera strutturaDinamica – Vista locale limitata alla combinazione dei dati presenti sui device in visibilitàAccesso uniforme – Ogni partecipante ha lo stesso set di operazioni

7

Spazi di tuple come GVDS

Spostamento deciso della semantica verso il best effortLimitata accessibilità del tsLimitata durata nel tempo del tsSemantica operazioni più lasca

Due sottosistemi principali da considerareMeccanismi dei membri in visibilità per realizzare la GVDS Meccanismi di ingresso o di ritorno di nuove entità in una località

Principi seguitiEconomia del numero di messaggiMinimizzare situazioni di incosistenzaAccettare solo situazioni di inconsistenza per eccesso

8

Protocollo GVDS

Prima ricerca in locale, poi nella GVDSOgni operazione sul TS crea la sua vista della GVDS

Due strutture dati locali per mantenere informazioni sulle operazioni di lettura / cancellazione pendentiInsieme alle tuple locali, stato globale distribuito della GVDS.

B A CIN(p) IN(p)

RESPONSE(t)

COMMIT(C) COMMIT(C)

9

Servizi di Discovery - Motivazioni

Parte imprescindibile di una GVDSEsigenza fondamentale da risolvere:

Caso opposto: informare della risoluzione di pendenze

...in(p)...

...out(t)

...

t

A

waiting(p)

B

...in(p)...

...work

...

t waiting(p) t

A B

a)

b)

10

Servizi di Discovery – Scelte progettuali

A chi assegnare la responsabilità di informare un nuovo arrivato sulla situazione attuale della GVDS?

A chiunque la conosce e vede il nuovo arrivatoSoluzione molto distribuita, maGrande quantità di messaggi, molti inutili

Protocollo di Elezione di un coordinatore non adatto per elevata dinamicità

A chi ha richiesto originariamente la rd/inSoluzione centralizzata, maLocalizza in modo preciso le responsabilitàLimita numero messaggi a quelli necessari

Scelta una politica di aggiornamento push per l'originatoreConsente di limitare il numero di messaggi, in presenza di

un supporto che fornisca già una vista della località

11

Servizi di Discovery – Scelte progettuali

Come comunicare informazioni “negative” come le pendenze risolte?

Informazioni “costose”: non più presenti nella GVDS, necessità di memorizzarle separatamente

Soluzione: non comunicarle!All'atto della perdità di connettività, un partecipante non è più interessato alle pendenze della sottorete non più raggiungibilePuò scartarle

Ad ogni riconnessione necessità di comunicare solo pendenze presenti nella GVDS aggiornata

12

Servizi di Discovery – Scelte Progettuali

Risoluzione delle asimmetrie

Supporto a casi di inconsistenza

A RESPONSE(t) verso BIl messaggio si perdeB mantiene la pendenzaA rialloca la tuplaINCONSITENZA

A

B

Servizio di Refresh Globale Periodico(Inconsistenza Temporanea)

13

Ambiente di Implementazione - AGAPE

Middleware per la comunicazione di gruppo basato su contestiSpecificatamente progettato per le MANETComunicazioni tra membri di uno stesso gruppo co-locatiBasata su contesti e profili

Anycast Context Based CommunicationMulticast Context Based Communication

14

Spazio di tuple - Implementazione

Aggiunta ad AGAPE di uno strato per la gestione del TSTupleSpace Service – gestione protocollo in visibilitàTupleSpace Discovery Service – gestione servizi di Discovery

15

TS Discovery Service

Opera in sinergia con il TS ServiceGestisce una DiscoveryTable

Una entry per ogni rd/in pendente del proprio device-> responsabilità dell'originatoreAd ogni entry agganciato un elemento attivo, un Notifier ->

politica push dell'originatoreA regime

Il TSDS aggiorna le entry collaborando con il VMSProfili nella vista attuale già notificatiProfili nella vista attuale nuovi arrivati

Ogni notifier, sulla base di queste informazioni, notifica i nuovi arrivati con la situazione attuale delle proprie pendenze

Ad intervalli regolari,il notifier esegue il refresh a tutti i presenti.

16

Conclusioni e Future Work

Realizzazione per il middleware AGAPE di un supporto alla coordinazione ispirato a Linda.Necessario un rilassamento del modello

Semantica molto più best effortDisaccoppiamento molto più ridottoGarantite comunque alcune proprietà più deboli

Possibili sviluppi:Dare più flessibilità nelle politiche di updating

Molto dipendenti dal contesto applicativoAndare nella direzione di LIME

Comunicazioni di disconnessione (?)