Universit` a degli Studi di Roma
“La Sapienza”
Facolt` a di Ingegneria
Tesi di Laurea in Ingegneria Informatica
sessione estiva - Settembre 2007
Valutazione delle prestazioni su scala geografica
di middleware publish-subscribe
Stefania Della Bina
Relatore: Prof. Roberto Baldoni
Co-relatore: Sirio Scipioni
Indice
Introduzione 1
1 Modello Publish/Subscribe 3
1.1 Altri paradigmi di comunicazione . . . 4
1.2 Qualit`a del servizio . . . 7
1.3 Modelli di sottoscrizione . . . 9
1.4 Modello architetturale . . . 10
1.4.1 Protocolli di rete (Network Protocols) . . . 11
1.4.2 Infrastruttura di overlay (Overlay Infrastructure) . . . 12
1.4.3 Indirizzamento degli eventi (Event Routing) . . . 13
1.4.4 Controllo degli eventi (Matching Algorithm) . . . 16
2 RTI DDS 17 2.1 Introduzione al Middleware . . . 17
2.1.1 Tipi e funzionalit`a del Middleware . . . 18
2.2 DDS . . . 20
2.2.1 QoS . . . 21
2.2.2 Architettura . . . 23
2.3 Real Time Innovations Data Distribution Service . . . 27
2.3.1 QoS supportate . . . 29
2.3.2 Discovery . . . 31
2.4 Note sugli ambienti supportati . . . 31
3 ORTE RTPS 33 3.1 Protocollo RTPS . . . 33
3.1.1 Architettura . . . 35
3.2 ORTE . . . 37
3.2.1 Manager e Managed Application . . . 37
3.2.2 Comunicazioni tra nodi . . . 39
3.2.3 QoS Supportate . . . 40
4 PlanetLab 41 4.1 Ambienti di test . . . 42
4.1.1 Simulatori/Emulatori . . . 42
4.1.2 Real testbed . . . 42
4.2 PlanetLab . . . 43
4.2.1 Servizi . . . 43 iii
4.2.2 Elementi base di PlanetLab . . . 45
4.3 Architettura dei nodi PlanetLab . . . 45
4.4 Slice . . . 46
4.5 Utilizzo di PlanetLab . . . 47
5 Test RTI 49 5.1 Modalit`a di comunicazione . . . 50
5.2 Programma di test . . . 54
5.2.1 Utilizzo del software . . . 56
5.3 Ambiente di test . . . 58
5.4 Test Best-Effort . . . 59
5.5 Test strict reliable . . . 63
5.6 Test reliable . . . 68
6 Test ORTE 75 6.1 Protocolli di comunicazione . . . 75
6.2 Programma test . . . 77
6.3 Utilizzo del software . . . 77
6.4 Test Best-Effort . . . 78
6.5 Test reliable . . . 81
7 Confronto tra middleware 89 7.1 Conclusioni . . . 94
Elenco delle figure
1.1 Space decoupling. . . 4
1.2 Time decoupling. . . 4
1.3 Syncronization decoupling. . . 4
1.4 Semplice sistema Pub/Sub. . . 5
1.5 Interazione Message Passing. . . 5
1.6 Interazione RPC. . . 6
1.7 Interazione Notification. . . 6
1.8 Iterazione Shared spaces. . . 7
1.9 Iterazione Message queue. . . 7
1.10 Architettura a livelli di un sistema Publish/Subscribe. . . 10
2.1 Struttura a livelli per applicazioni di rete distribuite. . . 18
2.2 Genealogia del Middleware. . . 20
2.3 Schema concettuale del DCPS. . . 24
2.4 Modello del DCPS. . . 25
2.5 Moduli DCPS. . . 26
2.6 Architettura di un’applicazione sviluppata su RTI DDS. . . 28
3.1 Moduli struttura PIM, del protocollo RTPS. . . 36
3.2 Componenti del “modulo strcture” di RTPS, in relazione ai componenti del DDS. 36 3.3 Struttura interna di ORTE. . . 38
3.4 Esempio di comunicazione tra nodi . . . 39
4.1 Distribuzione geografica dei nodi PlanetLab . . . 41
4.2 Architettura di un nodo . . . 46
4.3 Aquisizione di una slice. . . 47
5.1 Scambio di messaggi del protocollo reliable. . . 52
5.2 Andamento publisher e subscriber in modalit`a Best-Effort nazionale. . . 60
5.3 Andamento del throughput in trasmissione e media dei throughput in ricezione con trasmissioni best-effort, su scala nazionale. . . 60
5.4 Andamento del throughput in trasmissione e media dei throughput in ricezione con trasmissioni best-effort, su scala europea. . . 61
5.5 Andamento del subscriber migliore e peggiore, con comunicazioni best-effort su scala europea. . . 61
5.6 Confronto su scala nazionale ed europea del throughput in trasmissione, con comunicazioni best-effort. . . 62
v
5.7 Andamento del throughput in trasmissione e ricezione per comunicazioni strict reliable. . . 64 5.8 Andamento del throughput in trasmissione per le comunicazioni reliable e best-
effort, su scala nazionale. . . 64 5.9 Andamento throughput in trasmissione con comunicazioni strict reliable e throu-
ghput in ricezione con canali best-effort, su scala nazionale. . . 65 5.10 Andamento del throughput in trasmissione delle diverse trasmissioni reliable
testate su scala europea. . . 66 5.11 Andamento del throughput in trasmissione, con comunicazione strict reliable, su
scala nazionale ed europea. . . 67 5.12 Andamento del throughput in trasmissione su scala europea, di comunicazioni
best-effort e strict-reliable. . . 67 5.13 Andamento del throughput in trasmissione e ricezione, con comunicazioni relia-
ble, su scala nazionale. . . 69 5.14 Confronto del throughput in trasmissione e ricezione, tra comunicazione reliable
ed best-effort. . . 69 5.15 Confronto del throughput in trasmissione e ricezione, tra comunicazioni reliable
e strict reliable. . . 70 5.16 Andamento del throughput in trasmissione e ricezione, com comunicazioni relia-
ble su scala europea. . . 71 5.17 Andamento del throughput in trasmissione e ricezione con comunicazione relia-
ble, su scala europea e nazionale. . . 72 5.18 Confronto del throughput in trasmissione e ricezione su scala europea, con co-
municazioni reliable e strict reliable. . . 72 5.19 Confronto del throughput in trasmissione e ricezione su scala europea, con co-
municazioni reliable e best-effort. . . 73 6.1 Andamento del throughput in trasmissione e ricezione per le comunicazioni best-
effort, su scala nazionale. . . 79 6.2 Andamento del throughput in trasmissione e media dei throughput in ricezione
dei vari subscriber. . . 79 6.3 Andamento del throughput in trasmissione, su scala nazionale ed europea, con
comunicazioni best-effort. . . 80 6.4 Andamento del throughput in ricezione, su scala nazionale ed europea, con
comunicazione best-effort. . . 80 6.5 Anadamento del throughput in trasmissione e ricezione, su scala nazionale con
comunicazione reliable QoS Ins. 1. . . 82 6.6 Andamento del throughput in trasmissione e ricezione, su scala nazionale con
comunicazione reliable QoS Ins. 2. . . 82 6.7 Andamento del throughput in trasmissione e ricezione, su scala nazionale con
comunicazione reliable QoS Ins. 3. . . 83 6.8 Andamento del throughput in ricezione e trasmissione, su scala europea con
comunicazioni reliable QoS Ins. 1. . . 84 6.9 Andamento del throughput in ricezione e trasmissione, su scala europea con
comunicazioni reliable QoS Ins. 2. . . 85 6.10 Confronto su scala del throughput in trasmissione e ricezione, con comunicazione
reliable. . . 85
ELENCO DELLE FIGURE vii 6.11 Confronto del throughput in trasmissione tra comunicazioni best-effort e reliable,
su scala europea. . . 86 6.12 Confronto del throughput in ricezione tra comunicazioni best-effort e reliable, su
scala europea. . . 86 7.1 Confronto del throughput in trasmissione su scala nazionale, con comunicazioni
best-effort, tra RTI DDS e ORTE. . . 89 7.2 Confronto del throughput in ricezione su scala nazionale, con comunicazioni best-
effort, tra RTI DDS e ORTE. . . 90 7.3 Confronto del throughput in trasmissione su scala europea, con comunicazioni
best-effort, tra RTI DDS e ORTE. . . 90 7.4 Confronto del throughput in ricezione su scala europea, con comunicazioni best-
effort, tra RTI DDS e ORTE. . . 91 7.5 Confronto del throughput in trasmissione con comunicazioni reliable, su scala
nazionale. . . 92 7.6 Confronto del throughput in ricezione con comunicazione reliable, su scala na-
zionale. . . 92 7.7 Confronto del throughput in trasmissione con comuncazione reliable, su scala
europea. . . 93 7.8 Confronto del throughput in ricezione con comunicazione reliable, su scala europea. 93
Introduzione
L’esigenza di avere applicazioni distibuite in ambienti di larga scala, scalabili e affidabili, ha portato alla creazione di nuovi paradigmi di comunicazione. L’unico in grado di fornire la disseminazione delle informazioni in forma anonima, in maniera asincrona, garantendo il to- tale disaccoppiamento dei partecipanti `e il paradigma publish/subscriber. Tali carateristiche permettono di ottenere una distribuzione delle informazioni scalabile e affidabile, in quanto i partecipanti non devono conoscersi reciprocamente, l’operazione di invio e ricezione non devono essere sincronizzate e non richiede che le entit`a interessate siano “attive” nello stesso tempo.
Questo paradigma di comunicazione, grazie a queste caratteristiche, nell’ultimo decennio si `e guadagnato un ruolo centrale nello sviluppo di applicazioni su larga scala; esempi di applica- zione sono il controllo del traffico aereo, il controllo dei processi industriali, lo scambio delle quotazioni finanziarie. A seconda del campo di applicazione, la diffusione delle informazioni deve seguire regole e rispettare vincoli pi`u o meno restrittivi: si pensi per esempio a quanto ritardo sia accettabile tra l’invio del comando “Fuoco” e la ricezione dello stesso da parte di un dispositivo remoto in una missione militare, o a quanto sia tollerabile la perdita di una transazione finanziaria (“real-time”).
Per cui le problematiche che un sistema di diffusione delle informazioni si trova ad affrontare sono molteplici: l’ormai crescente mole di dati che si vuole trasmettere ad un numero sempre maggiore di partecipanti interessati, i quali possono essere dislocati su una rete geograficamente vasta, `e un altro aspetto da tenere bene in considerazione, come pure la diversit`a delle architet- ture usate per i singoli partecipanti. Senza contare aspetti dinamici delle reti, guasti, il churn1 dei partecipanti, inaffidabilit`a dei canali, aspetti che appaiono evidenti, e maggiormente critici, se si pensa ad una rete di dispositivi mobili.
Poich´e tali problematiche sono comuni a molti e diversi campi d’applicazione, si `e pensato di creare uno strato software che si occupasse di esse. Uno strato che forma una “terra di mezzo”
tra applicazione e sistema sottostante e per questo chiamato middleware. L’idea `e dunque di demandare al middleware la gestione delle problematiche, mentre l’applicazione dovr`a occuparsi solo della propria logica: inviare un dato per l’applicazione si tradurr`a in un’istruzione al middleware sottostante, inviarlo affidabilmente potr`a essere la stessa istruzione con parametri di affidabilit`a. Il resto del gioco `e intrapreso dal middleware, il cui apporto migliorer`a sia l’interoperabilit`a con i vari sistemi che l’efficienza delle applicazioni.
Contributo
Oggetto di questa tesi `e lo studio di due particolari implementazione di middleware pub/sub orientati alla diffusione delle informazioni: RTI DDS della Real Time Innovations.Inc[5] e OR- TE, sviluppato all’interno del progetto europeo OCERA[6]. Lo scopo `e analizzare il compor-
1Per churn si intende il continuo entrare ed uscire di partecipanti dalla comunicazione
1
tamento di tali software in ambiente WAN, in condizioni di stress dovute alla dimensione degli eventi inviati, al numero di partecipanti alla comunicazione ed infine alla distanza geografica tra di essi.
Questi aspetti sono particolarmente importanti in quanto il software RTI DDS `e nato per essere utilizzato in ambiente LAN e solo di recente si `e pensato di adattare il prodotto ad un ambiente pi`u dinamico e di larga scala.
Per consentire una stima delle performance in un’ambiente WAN `e stata utilizzata la rete PlanetLab[7]; questa rete `e costituita da molti nodi sparsi in 35 paesi.
PlanetLab permette agli utenti di usufruire su ogni nodo di una macchina virtuale; in questo modo `e stato possibile far funzionare il software sui nodi interessati, in condizioni di canali condivisi e latenze imprevedibili.
I test hanno permesso di evidenziare eventuali criticit`a e debolezze di tali prodotti software in ambiente WAN, permettendo una valutazione delle soluzioni implementate nei middleware pub/sub RTI DDS e ORTE.
Capitolo 1
Modello Publish/Subscribe
Il modello Publish/Subscribe `e una tecnologia chiave per lo sviluppo di applicazioni distribuite, permettendo la propagazione dell’informazione tra pi`u partecipanti. In sostanza ogni parteci- pante alla comunicazione pu`o scegliere il ruolo di Publisher o di Subscriber delle informazioni.
I primi producono i dati sotto forma di “eventi” che sono consumati dai secondi qualora essi abbiano interesse nel riceverli; tale interesse viene manifestato tramite la sottoscrizione. Ci`o che caratterizza un sistema Publish/Subscribe `e, per l’appunto, come i dati fluiscono dai Publi- shers ai Subscribers: i destinatari, non sono reperiti direttamente tramite il loro indirizzo, ma in maniera semantica tramite il contenuto degli eventi sottoscritti. Per esempio in un sistema Publish/Subscribe topic-based il publisher produrr`a eventi appartenenti ad un certo topic, senza curarsi di sapere l’indirizzo di chi sia interessato a tali eventi. Dall’altro lato i subscribers inte- ressati a quel tipo di evento comunicheranno la propria volont`a di ricevere dati da quel topic, senza la necessit`a di sapere l’indirizzo di chi genera gli eventi. Grazie a questo anonimato, i partecipanti si scambiano informazioni senza doversi conoscere l’un l’altro direttamente, ren- dendo quindi possibile e relativamente semplice l’espansione della comunicazione a reti di larga scala (space decoupling, fig. 1.2) [8].
Un’altra caratteristica molto importante `e il disaccoppiamento temporale tra il publisher ed i subscriber, infatti non si ha la necessit`a che entrambe siano attivi contemporaneamente per far si che l’evento venga consegnato (time decoupling, fig. 1.2) [8]. Infatti la consegna dell’evento avviene anche se il publisher pubblica un evento mentre i subscriber sono disconnessi e si pu`o avere una consegna di eventi ai subscriber mentre i publisher sono disconnessi.
L’operazione di publicazione e notifica degli eventi sono operazioni non bloccanti, cio´e non alterano il normale flusso delle operazioni nel publisher e nel subscriber (synchronization decoupling, fig. 1.3) [8].
Esistono diversi modelli di sottoscrizione che influenzano il modo in cui un subscriber specifica quali sono gli eventi di interesse: Topic-based e Type-based.
L’interazione tra i Publishers ed i Subscribers `e mediata dal Pub/Sub System, che in generale
`e costituito da un insieme di nodi che si coordinano tra loro per far s`ı che le informazioni arrivino a tutti, e possibilmente, solo ai partecipanti interessati. Il Pub/Sub System pu`o essere decomposto in tre livelli funzionali, che sono: Overlay infrastrutture, Event routing, Matching.
Come precedentemente esposto i nodi che compongono il Pub/Sub system sono distribuiti sulla rete di comunicazione, ed i clienti del sistema sono divisi in due gruppi, in base al ruolo svolto nei confronti degli eventi (produttori, consumatori).
Lo scambio di informazioni tra un cliente ed il Pub/Sub system avviene tramite un insieme 3
Figura 1.1: Space decoupling. Figura 1.2: Time decoupling.
Figura 1.3: Syncronization decoupling.
di primitive con le quali il publisher sottomette un evento al sistema con l’operazione di pu- blish(e), ed un subscribe manifesta il suo interesse verso uno specifico evento con l’operazione di subscribe(o). Dove o `e un filtro applicato agli eventi, espresso tramite una costruzione che dipende dal linguaggio usato per la sottoscrizione. Per rimuovere una sottoscrizione si utilizza l’operazione unsubscribe(o); come raffigurato in figura 1.4.
1.1 Altri paradigmi di comunicazione
Esistono altri paradigmi di comunicazione oltre al paradigma Publish/Subscribe appena intro- dotto. Tali paradigmi sono Message passing, remote invocations, notifications, shared spaces e message queuing. Tali paradigmi si differenziano tra loro per livello di astrazione, per tale motivo non `e facile effettuare un’analisi comparativa. Tutti questi modelli non disaccoppiano la comunicazione tra i partecipanti come avviene nel modello Publish/Subscribe, e presentano, un limitato supporto nel tempo e nello spazio.
Message Passing: Il message passing rappresenta una comunicazione distribuita a basso li- vello, dove i partecipanti comunicano tramite l’invio e la ricezione di messaggi (Fig. 1.5).
Il produttore invia i messaggi in modo asincrono attraverso un canale di comunicazione ed il consumatore riceve tali messaggio ascoltando in modo sincrono il canale. Il produttore ed il consumatore devono essere accoppiati temporalmente e spazialmente, in quanto devono essere contemporaneamente attivi, e devono conoscersi reciprocamente. Questo paradigma `e attualmente poco usato.
RPC: La Remote Procedure Call [9, 10] `e la pi`u diffusa forma d’interazione distribuita; la quale `e stata poi rafforzata applicandola al contesto object-oriented nella forma di Re- mote Method Invocations, un esempio `e Java RMI [11]. Tale popolarit`a deriva dalla sua
1.1. ALTRI PARADIGMI DI COMUNICAZIONE 5
Figura 1.4: Semplice sistema Pub/Sub.
semplicit`a nell’utilizzo, infatti l’interazione remota appare allo sviluppatore software allo stesso modo di una interazione locale (Fig.1.6). La distribuzione non pu`o essere effettua- ta in modo completamente trasparente all’applicazione, in quanto l’applicazione si trova a dover gestire potenziali fallimenti che possono derivare da problemi di trasmissione o fallimenti remoti. Risulta presente un accoppiamento spaziale (consumatore e produttore si devono conoscere) e temporale (il consumatore effettua chiamate bloccanti). Per ovvia- re a ci`o sono state sviluppate due soluzioni, la prima nota come one-way [12] (consente invocazioni asincrone di metodi remoti, senza valori di ritorno), la seconda nota come wait-by-necessity [13, 14] (consente invocazioni asincrone con valori di risposta).
Notification: Questo paradigma consente l’invocazione remota di metodi in modalit`a asin- crona. Per consentire ci`o si `e divisa l’invocazione sincrona in due comunicazioni distinte asincrone. Nella prima comunicazione il cliente invia al server gli argomenti dell’invoca- zione ed un riferimento di callback necessario al cliente per gestire il valore di ritorno. La seconda comunicazione inviata dal server verso il cliente per restituire il valore di ritorno.
Questo schema `e attualmente usato per garantire la consistenza nella web caches [15].
Questa implementazione `e una limitat`a forma di publish/subscribe, dove il subscriber `e il
Figura 1.5: Interazione Message Passing.
Figura 1.6: Interazione RPC.
Web proxy, ed il publisher `e il Web server. Visto che la comunicazione avviene in modo diretto tra cliente e server si ha il fenomeno dell’accoppiamento spaziale.
Figura 1.7: Interazione Notification.
Shared Spaces: Il paradigma distributed shared memory (DSM) [16, 17] prevede che pi`u host in un sistema distribuito vedano un’area di memoria condivisa, distaccata dal loro spazio di indirizzamento locale. La comunicazione tra host viene effettuata tramite l’inserimento e rimozione di tuple dal tuple space [18] (collezione ordinata di tuple accessibili da tutti gli host del sistema). Questo modello d’interazione consente il disaccoppiamento spaziale e temporale, in quanto gli host consumatori e produttori possono non conoscersi recipro- camente. L’operazione di prelievo di una tupla `e un’operazione sincrona; per tale motivo
`e presente il problema della sincronizzazione, che limita la scalabilit´a del modello.
Message Queuing: Il Message queuing [19] `e una recente alternativa per le interazioni di- stribuite; questo paradigma di comunicazione `e fortemente legato al paradigma publi- sh/subscribe, perch´e usualmente ne utilizza alcune forme. A livello di interazione la coda di messaggi assomiglia molto al tuple space visto precedentemente; in quanto la coda pu`o essere vista come uno spazio globale in cui sono memorizzati i messaggi dal produtto- re. Dal punto di vista funzionale il sistema a code di messaggi garantisce le propriet`a transazionali e di ordinamento. Produttore e consumatore sono disaccoppiati temporal- mente e spazialmente, e si ha sincronizzazione nella fase di prelevamento dei messaggi.
Sono stati sviluppati sistemi che supportano una consegna asincrona dei messaggi, ma, tali sistemi non supportano un gran numero di consumatori.
1.2. QUALIT `A DEL SERVIZIO 7
Figura 1.8: Iterazione Shared spaces.
Figura 1.9: Iterazione Message queue.
Nella tabella 1.1 viene riportato scematicamente il disaccopiamento effettuato da ogni paradigma di comunicazione.
1.2 Qualit` a del servizio
Nei sistemi publish/subscribe quando si considerano le qualit`a del servizio del sistema si trova una certa difficolta nella definizione e nell’attuazione di tali politiche a causa del disaccopia- mento presente tra produttori e consumatori. Infatti il disaccopiamento introduce un compor- tamento non deterministico, il che significa che l’esatto comportamento del sistema `e difficile da specificare, applicare e controllare. Ora analizzer`o tre qualit`a del servizio fondamentali dei sistemi Pub/Sub.
Reliable deliverey: Effettuare la reliable delivery di un evento richiede la determinazione di tutti i subscriber che devono ricevere tale evento e la consegna dell’evento a tutti loro.
Elaborare un evento in una infrastruttura Pub/Sub richiede che l’evento attraversi molti nodi della rete che possono essere sorgenti di non-determinismo. Il non-determinismo pu`o essere dovuto alla trasmissione su canali asincroni WAN oppure al sovraccarico di alcuni nodi. Il non-determinismo impatta sul tempo di publicazione, il quale cresce indefiniti- vamente, ed impatta negativamente sulla probabilit`a di consegna dell’evento di notifica a
Space Time Syncronization Abstraction decoupling decoupling decoupling
Message Passing No No Producer-side
RPC/RMI No No Producer-side
Asyncronous RPC/RMI No No Yes
Future RPC/RMI No No Yes
Notifications No No Yes
Tuple spaces Yes Yes Producer side
Message queuing Yes Yes Producer side
Publish/subscribe Yes Yes Yes
Tabella 1.1: Decoupling presente nei diversi paradigmi di comunicazione.
tutti i subscriber interessati (notification loss [20]). Per contrastare tale impatto negativo occorre introdurre il concetto di persistenza degli eventi, durabilit`a della sottoscrizione e ritrasmissione di eventi, questi concetti aiutano a ridurre l’effetto non-deterministico, permettendo di ottenere un elevato reliable delivery. In generale pi`u un evento rimane nel sistema, minore sar`a l’effetto non deterministico, al costo di un elevata occupazione di memoria. Nel caso in cui l’informazione `e ritrasmessa un numero infinito di volte, il non-determinismo `e assente;
Timeliness: Applicazioni Real-Time richiedono spesso uno stretto controllo sul tempo im- piegato da un evento per raggiungere tutti i suoi sottoscrittori. Queste applicazioni ti- picamente sono sviluppate su infrastrutture dedicate oppure in ambienti in cui la con- segna di messaggi sincroni pu`o essere assunta con sicurezza. Anche in questi ambienti completamente gestiti, una infrastruttura publish/subscribe pu`o introdurre fattori non- deterministici a causa del disaccopiamento, in quanto si possono avere ritardi di elabora- zione non prevedibili su ogni nodo o processi anomali. Quando la propriet`a di timeliness devono essere applicate si dovranno privileggiare comunicazioni punto-punto in cui il di- saccopiamento `e limitato o totalmente assente. L’inconveniente di tale scelta risiede nel mancato disaccopiamento, quindi nella limitata scalabilit`a dovuta all’infrastruttura richie- sta. Infatti il publisher dovrebbe conoscere tutti i subscriber e determinare i destinatari per ogni evento. Si stanno studiando meccanismi per garantire la timeliness e sistemi scalabili;
Security: Nei sistemi publish/subscribe la sicurezza `e un problema, infatti deve garantire l’ac- cesso al sistema solo ai partecipanti autorizzati e la fiducia tra publisher e subscriber.
Infatti un subscriber vuole fidarsi dell’autenticit`a degli eventi ricevuti dal sistema, in quanto generati da un fidato publisher e con un contenuto non corrotto. Al tempo stesso i publisher devono fidarsi dei subscriber per quanto concerne la sottoscrizione generata.
Poich´e un messaggio attraversa molti nodi dell’infrastruttura, occore far si che tali nodi non corrompano tali messagi e le identit`a dei partecipanti. Progettare misure di sicureza implica la conoscenza certa delle identit`a degli altri partecipanti, questo `e in chiaro con- trasto con l’anonimato che `e alla base del sistema publish/subscribe. Sotto l’assunzione di fiducia il disaccopiamento pu`o essere preservato utilizzando una soluzione nella quale la fiducia tra un publisher ed un subscriber `e applicata attraverso una catena di relazioni di fiducia tra tutti i nodi dell’infrastruttura, in particolare quelli incontrati lungo il percorso seguito dall’evento [21]. In altre parole quando propago un messagio, sia una sottoscrizio- ne o un evento, un nodo dell’infrastruttura oltre a propagare tale messaggio deve rilasciare
1.3. MODELLI DI SOTTOSCRIZIONE 9 la relazione di fiducia relativa al messaggio stesso, con lo scopo di garantire l’integrit`a del messaggio. Nel caso generale in cui non si pu`o assumere che la completa infrastruttura sia fidata, occorre prendere in considerazione l’eventualit`a che un evento attraversi po- tenziali nodi maliziosi. Per ovviare a tale inconveniente si pu`o pensare di utilizzare dei gruppi di fiducia, cio´e dei domini logici all’interno dell’infrastruttura publish/subscribe [22]. I domini logici limitano la visibilit`a degli eventi e sottoscrizioni all’interno di uno stesso dominio logico, ci`o permettere ad od ogni dominio logico di essere indipendente.
All’interno di un dominio logico si ha una infrastruttura fidata; se si vuole aggiungere un nuovo nodo al dominio logico e tale nodo `e raggiungibile tramite uno o pi`u nodi non fidati occorre utilizare una modalit`a tunnel per scambiarsi informazioni in modalit`a codificata.
1.3 Modelli di sottoscrizione
Esistono diversi modi per specificare quali eventi siano di interesse, e, ad ognuno di essi, corri- sponde una variante del paradigma Publish/Subscribe. Ci`o che fondamentalmente caratterizza tali modelli `e la loro “potenza espressiva”, maggiore espressivit`a implica la possibilit`a per un subscriber di selezionare con maggiore precisione gli eventi ai quali `e interessato. I seguenti sono i modelli di sottoscrizione pi`u popolari:
Topic-based Model: Gli eventi sono raggruppati in topics (letteralmente “argomenti”). Un subscriber dichiara il proprio interesse in un determinato topic e ricever`a tutti gli eventi ad esso correlati. Il topic pu`o essere visto come un canale logico che connette ogni pos- sibile publisher di quel topic ad ogni subscriber interessato. Il principale svantaggio di questo modello risiede nella poca espressivit`a offerta ai subscribers. Infatti un subscriber interessato solo ad un sottoinsieme di eventi correlati ad uno specifico topic ricever`a anche tutti gli altri che fanno parte di esso. Nelle varie implementazioni questo problema `e stato risolto usando un sistema a gerarchie di topic, ovvero creando topic che sono sottosezioni di altri [23, 24].
Content-based Model: I subscribers esprimono il proprio interesse specificando condizioni sul contenuto degli eventi che si vogliono ricevere. In altre parole si filtra il contenuto dei messaggi e si accettano solo quelli che soddisfano i criteri imposti su determinati attributi.
A seconda del tipo degli attributi e del linguaggio usato (alcuni linguaggi permettono l’
uso delle espressioni regolari e di operatori logici [25, 26]) si possono creare filtri pi`u o meno espressivi. Il topic-based model pu`o essere emulato con il Content-based Model con un vincolo di uguaglianza preso su un attributo che gioca il ruolo del topic. La complessit`a del linguaggio influenza la complessit`a delle operazioni di ricerca dei subscriber. Non esiste pi`u l’idea di un canale logico tra i publishers ed i subscribers mentre la corrispondenza tra di essi `e del tutto orientata all’evento stesso. Il vantaggio `e l’alto potere espressivo, mentre lo svantaggio risiede nella complessit`a di calcolo richiesta per calcolare l’insieme dei subscribers interessati, analizzando il contenuto di ogni evento, il che richiede un grande dispendio di risorse. Una descrizione completa di questo modello `e disponibile in [27].
Type-based Model: In questo tipo di modello, gli eventi sono in realt`a oggetti, nei quali possono essere incapsulati attributi e metodi [28, 29]. Per cui un subscriber decider`a il tipo di oggetti da ricevere ed il middleware sottostante fornir`a all’applicazione le istanze degli oggetti ricevuti. Per cui la correttezza dell’oggetto `e affidata al sistema Pub/Sub e non all’applicazione. Il Type-based Model `e una sorta di “terra di mezzo” tra il Topic-based ed il Content-based: impone agli eventi una struttura rigida come un Topic-based e vincoli
complessi possono essere espressi sugli attributi e sui metodi (approccio Object-Oriented), come nel Content-based.
Concept-based: In questo modello di sottoscrizione si presuppone che i partecipanti siano informati della struttura degli eventi prodotti, sia dal punto di vista semantico che sin- tattico. Questo modello consente di descrivere uno schema di evento ad alto livello di astrazione usando delle ontologie1 [30].
Location-awareness: Questo modello `e usato per la comunicazione con dispositivi mobili, quando il subscriber mobile si trova in prossimit`a dei nodi del Pub/Sub sistem pu`o rice- vere messaggi di notifica. In questo tipo di modello `e importante che il sistema Publi- sh/Subscribe sia in grado di monitorare la mobilit`a dei clienti che vogliono accedere ai servizi. Una descrizione pi`u dettagliata `e riportata in [31, 32].
1.4 Modello architetturale
Come sopra accennato, un sistema Publish/Subscribe `e composto da tre livelli, in figura 1.10 viene riportato anche il livello dei protocolli di rete.
Figura 1.10: Architettura a livelli di un sistema Publish/Subscribe.
Per la diffusione scalabile delle informazioni, i livelli funzionali sono:
1schema concettuale esaustivo e rigoroso nell’ambito di un dato dominio, si tratta generalmente di una struttura dati gerarchica che contiene tutte le entit`a rilevanti, le relazioni esistenti fra di esse, le regole, gli assiomi, ed i vincoli specifici del dominio.
1.4. MODELLO ARCHITETTURALE 11 l’ overlay Infrastructure, l’event routing (indirizzamento degli eventi) e l’algoritmo per il matching fra eventi e sottoscrizioni. L’ Overlay Infrastructure rappresenta l’organizzazione delle diverse entit`a che compongono il sistema (per esempio una rete di server dedicati o una overlay peer-to-peer strutturata), mentre per “Event Routing” si intende il meccanismo per la disseminazione delle informazioni dai publishers ai subscribers. Esso sfrutta l’infrastruttura di overlay e vi integra le proprie informazioni di routing per ottenere una spedizione degli eventi scalabile. Spesso, nelle implementazioni, questi due livelli si confondono l’un l’altro, non distinguendo chiaramente le loro dipendenze e rendendo difficile il confronto con le altre implementazioni. Infine l’ “Algoritmo di Matching” filtra gli eventi prodotti dai publisher e fa in modo che al subscriber giungano solo quelli che soddisfano determinati criteri previsti dal modello di sottoscrizione.
Segue una breve panoramica sui livelli, le loro funzioni e implementazioni.
1.4.1 Protocolli di rete (Network Protocols)
Formano lo strato che `ancora il sistema Pub/Sub alla rete sottostante, consentendo la comu- nicazione e la trasmissione dati fra i vari componenti del Pub/Sub System. Poich´e un sistema Pub/Sub pu`o sorgere su reti eterogenee (LANs2, WANs3, mobile networks . . . ) esso pu`o impie- gare pi`u di un singolo protocollo di rete per far fronte a differenti condizioni hardware/software che si possono presentare su parte della rete o per rendere massime le performance.
E possibile differenziare i sistemi Pub/Sub in base al tipo di protocollo che adottano:` Transport level: I sistemi Pub/Sub di questo tipo sfruttano le funzionalit`a offerte dai proto-
colli di livello transport, ad esempio comunicando direttamente attraverso TCP o UDP oppure interfacciandosi ad essi usando dei protocolli specifici di middleware (quali IIOP4 e SOAP5). Questa scelta rende il sistema molto flessibile e facile da estendere anche a si- stemi in cui sono presenti degli impedimenti dovuti alla presenza di firewall o reti private, casi in cui serve l’intervento di un amministratore per la configurazione.
Network level Multicast: Utilizzando direttamente le primitive di broadcast e multicast del- la rete si ottiene un modo pi`u efficiente per diffondere i dati tra molti nodi partecipanti. In questo modo le latenze sono minori e il throughput aumenta, in quanto l’onere di imple- mentare il protocollo di routing `e svolto dagli apparati di rete. Ad esempio IP Multicast pu`o essere usato direttamente in un ambiente Topic-based, in quanto ad ogni topic si pu`o far corrispondere esattamente un gruppo multicast. Non `e invece cos`ı immediato per un Content-based dove non `e possibile mappare i subscribers in gruppi multicast. Tuttavia IP Multicast non `e una soluzione sufficientemente flessibile per una WAN ([33, 34]), inoltre orienta l’espressivit`a dalla conoscenza del topic (e della sua semantica), alla conoscenza di un indirizzo di Multicast IP (che di per s´e non `e espressivo).
Mobile Networks: Esistono due varianti, una che considera tutti i dispositivi come mobili [35, 36], l’altra che considera parte dei nodi ferma e costituente l’infrastruttura fissa e solo i client si muovono rimanendo sempre ad un hop6 di distanza da almeno un nodo fisso [37, 38]. In entrambi i casi si pu`o usare un Transport e/o un Network protocol che utilizzi il protocollo di livello data link della rete mobile (per esempio 802.11g) oppure
2LAN - Local Area Network, una rete di dimensioni geografiche limitate ad un edificio o campus
3WAN - Wide Area Network, una rete geografica molto estesa, anche planetaria
4IIOP - Internet Inter-Orb Protocol in sostanza CORBA orientato al web
5SOAP - Simple Object Access Protocol, una specifica XML per le transazioni sincrone e asincrone sul web
6Letteralmente “salto”, indica quanti nodi deve attraversare il dato prima di giungere al client.
direttamente il protocollo di livello data link stesso, senza trascurare che la mobilit`a dei dispositivi introduce vincoli sulle risorse, consumo di batteria, larghezza di banda limitata oltre a temporanee disconnessioni e indisponibilit`a dei nodi. Tutte caratteristiche che il middleware deve considerare insieme alla location-awareness prima citata, che deve essere tipicamente supportata.
1.4.2 Infrastruttura di overlay (Overlay Infrastructure)
Generalmente un sistema Publish/Subscribe si basa su una overlay network di livello applicativo.
Diverse possibilit`a si presentano nel modo in cui i nodi della rete sono organizzati, e nel ruolo che ricoprono.
Broker Overlay: Per coprire una rete quale l’intera internet, le applicazioni distribuite che si avvalgono del Pub/Sub system richiedono che questo sia implementato come un insieme di server indipendenti e comunicanti. In questo contesto, ogni singolo server `e chiamato broker. I broker server formano quindi una rete di overlay comunicante con i protocolli di network citati prima. Un cliente che intende connettersi e partecipare alla comunicazione pu`o accedere al sistema tramite un qualsiasi broker, che in genere memorizza solo un sottoinsieme delle sottoscrizioni. Le connessioni sono puramente logiche e astratte, non rispecchiano gli effettivi link internet che sfruttano, il che implica che una broker network sia statica; ossia varia solo raramente in caso di aggiunta di un nuovo broker o di guasto su uno esistente. Per questo si assume che la topologia sia gestita da un amministratore ed i nodi connessi a formare il “vicinato” (neighborhood) siano determinati in base a relazioni di conoscenza (staticamente). Le topologie usate sono per lo pi`u di due tipi : gerarchica e flat. Nel primo caso i punti d’accesso dei publisher risiedono alla radice e quelli dei subscriber alle foglie (o viceversa) e gli eventi viaggiano solo attraverso i livelli interessati [39, 40]; nel secondo caso invece non ci sono limitazioni alla connessione, il che, ha il vantaggio di non sovraccaricare i nodi radice [41].
Peer-to-peer Structured Overlay: Una overlay network peer-to-peer structured `e una rete di livello applicazione composta da un insieme di nodi che si autogestiscono, formanti un grafo strutturato su uno spazio di chiavi virtuali, dove ad ogni chiave `e associato un nodo. La presenza di questa struttura delle chiavi imposta al grafo, permette l’efficiente rilevazione dei partecipanti e dei dati da trasmettere, nonch´e la comunicazione attraverso i nodi. Il fatto che la overlay sia strutturata garantisce quindi che vi sia sempre corrispon- denza tra un qualsiasi indirizzo ed un nodo attivo anche in presenza di nodi che entrano ed escono dalla rete (churn) e di guasti sui nodi. A differenza della broker overlay ine- rentemente statica, una p2p7 Structured Overlay gestisce bene gli aspetti dinamici della comunicazione, per cui `e pi`u adatta ad ambienti decentralizzati e di larga scala, dove l’intervento umano non pu`o essere considerato una soluzione fattibile. Alcuni esempi di sistemi che sono stati sviluppati sono: Pastry [42], Chord [43], CAN [44];
Peer-to-peer Unstructured Overlay: La rete si sforza di organizzare i nodi in una strut- tura gerarchica o flat in un piccolo raggio di copertura di rete, contro guasti dei nodi e frequenza di churn (ingresso/uscita di nodi). Differentemente da una broker overlay, non si suppone che i nodi siano server dedicati, ma possono includere anche workstations, por- tatili, dispositivi mobili e cos`ı via, ed essi possono agire sia come clienti che come parte del
7E il diffusissomo acronimo per i sistemi peer-to-peer`
1.4. MODELLO ARCHITETTURALE 13 pub/sub system. Inoltre, ovviamente, la topologia non deve essere gestita da un ammini- startore umano, i nodi sono in grado di autogestirsi. Poich´e non vi `e una struttura, per reperire i nodi ed i dati esse sfruttano tecniche di flooding, gossiping o cammini casuali attraverso il grafo per diffondere e ricevere informazioni associate ai nodi. Il vantaggio risiede nella facilit`a con cui vengono gestiti i “join” e “leave” (unione e rilascio) dei nodi.
In ogni caso, a differenza delle reti strutturate, non v’`e garanzia che ad ogni indirizzo sia associato un nodo attivo.
Unstructured Overlays over Mobile Networks: In un ambiente formato da dispositivi mobili, il cambiamento di topologia `e una caratteristica imprescindibile, dovuta al churn, allo spostamento dei dispositivi nonch´e ai guasti. `E impossibile in questo caso, agire creando strutture gerarchiche o flat a piccoli raggi in quanto i nodi sono mobili e questo ne rende difficile l’ottimizzazione. Inoltre sono necessari algoritmi che mantengano con- nettivit`a e consistenza delle strutture dati per il routing, altrimenti il routing degli eventi stesso non pu`o avvenire correttamente [35, 36]. Creare alberi ricoprenti richiede algoritmi costosi dal punto di vista energetico, a causa della limitata energia di tali dispositivi e della scarsa capacit`a di calcolo a loro disposizione; algoritmi che creano overlay struttura- te non sono adatti a questo tipo di ambienti. Soluzioni tipiche per questo ambiente sono basate su overlay non strutturate e contando sul livello MAC (Medium Access Controll per esempio 802.11b/g/n); sfruttandone le sue caratteristiche di broadcast e il suo sistema di segnalazione [45].
1.4.3 Indirizzamento degli eventi (Event Routing)
Il cuore di un sistema Pub/Sub distribuito risiede nel meccanismo di Event Routing. In poche parole `e il processo di consegna degli eventi a tutti i subscribers che abbiano manifestato la volont`a di sottoscrivere una pubblicazione. Questo implica una visita dei nodi da parte del Notification Service8al fine di trovare, per ogni evento pubblicato, tutti i client la cui sottoscri- zione registrata `e presente nel sistema al momento della pubblicazione. Tuttavia, l’impossibilit`a di definire un ordine temporale globale tra una sottoscrizione ed una pubblicazione accadute su due nodi diversi (e quindi con clock generalmente diverso) rende ambigua questa definizione di event routing. Il problema principale dell’event routing `e la scalabilit`a. Le performan- ce dovrebbero degradarsi il meno possibile all’aumentare dei nodi, delle sottoscrizioni e delle pubblicazioni. A tal fine occorre regolare le pubblicazioni in modo che la propagazione degli eventi coinvolga quanto pi`u possibile solo i brokers che contengono delle sottoscrizioni per essi (Message overhead). D’altro canto, ridurre la quantit`a di informazioni di routing da mantenere sui brokers al fine di permettere flessibili cambiamenti delle sottoscrizioni (Memory overhead ).
Questi due aspetti sono in evidente contrapposizione, bilanciarli `e uno dei primi compiti del progettista di un sistema Pub/Sub.
Esistono tre categorie di routing e sono: flooding algorithm, selective algorithm, event gossiping algorithm.
Flooding algorithm: Gli algoritmi di flooding sono basati su una deterministica e completa disseminazione degli eventi sull’intero sistema. Una soluzione banale consiste nel propa- gare ogni evento dal publisher verso tutti i nodi del sistema (tramite un’operazione di broadcast oppure ogni nodo invia l’evento a tutti i processi conosciuti). Il vantaggio di questo algoritmo `e: l’assenza di limitazioni sulle sottoscrizioni, i linguaggi utilizzati nelle
8E un servizio offerto dal Middleware`
sottoscrizioni, l’applicabilit`a ad ogni architettura, non richiede la memorizzazione di in- formazioni di routing; lo svantaggio principale `e il sovraccarico di messaggi scambiati al crescere della rete quindi la non scalabilit`a. Per diminuire il message overhead si `e creato il subscription flooding, in cui ogni sottoscrizione `e inviata a tutti i brokers, i quali hanno la conoscenza dell’intero sistema. In questo modo ogni subscriber pu`o essere raggiunto in un singolo hop ed gli eventi non di interesse possono essere scartati immediatamente.
Questo approccio non pu`o essere considerata una soluzione flessibile se i sottoscrittori cambiano ad un alto rate, in quanto i cambiamenti devono essere inviati a tutta la rete [41, 25].
Selective algorithm: Gli algoritmi selettivi tendono a ridurre la disseminazione dell’infor- mazione degli algoritmi di flooding con l’uso di strutture deterministiche costruite sulle sottoscrizioni. Ci`o `e possibile solo se un sottoinsieme dei nodi di broker memorizzi ogni sottoscrizione ed un sottoinsieme dei nodi di broker sia visibile da ogni evento. Questi algoritmi ottimizzano particolarmente le risorse quando un evento deve essere trasmesso solo ad una porzione di sottoscrittori. Nel caso in cui molti eventi sono di interesse per un gran numero di sottoscrittori, il flooding pu`o essere considerata un’opzione concorrente poich´e essa evita di memorizzare ed aggiornare informazioni relative ad eventi di routing [46]. Il Filtering-based routing ed il Rendezvous-based routing sono due algoritmi selettivi.
Filtering-based routing: L’algoritmo riduce il message overlay inoltrando un evento solo ai nodi che si trovano su un percorso che collega il publisher ai vari subscriber.
Identificando il prima possibile gli eventi non di interesse per alcuni nodi si blocca il prima possibile il loro inoltro [47]. L’algoritmo richiede la memorizzazione, la co- struzione e l’aggiornamento dei diversi path, quindi si introduce memory overhead.
Ogni broker deve memorizzare la routing information associata ad ogni vicino nel- l’overlay e riguardante l’insieme di sottoscrittori raggiungibili attraverso quel broker.
Queste informazioni consentono di costruire path di sottoscrizione. Ogni volta che si genera una sottoscrizione, tale informazione viene diffusa verso ogni publisher di tale evento. Nel caso in cui tutti i nodi possono aggire da puglisher per tutte le sottoscrizioni, si ha il flooding della rete; in tale situazione l’algoritmo di flooding risulta conveniente in quanto non occorre gestire routing information. In questo algo- ritmo possono essere imposti limiti sul contenuto delle sottoscrizioni. L’architettura naturale per i broker `e quella di grafo aciclico o albero, in quanto la presenza di cicli richiede la gestione della ridondanza dei messaggi inondati nella rete. L’uso di questo algoritmo su overlay non strutturate soffre dell’impossibilit`a della tipologia aciclica e la dinamicit`a della rete causa frequenti aggiornamenti delle informazioni di routing. Le prestazioni sono fortemente influenzate dalla funzione di associazio- ne evento-sottoscrittore (matching) e dalla tipologia dell rete di overlay, in particola modo dal diametro della rete e memory overhead. Il diametro della rete `e una misura dipendente dalla lunghezza dei path tra publish e subscribe, questo parametro incide sul notification latency. Per diminuire tale valore occorre incrementare il numero di vicini di un nodo, ma tale valore incide sul memory overhead aumentandolo. Non sono presenti limiti sul linguaggio di sottoscrizione.
Rendezvous-based routing: Questo algoritmo ottimizza le prestazioni raggruppando tutte le sottoscrizioni di un determinato evento in uno stesso nodo, evitando l’e- secuzione delle operazioni di matching su pi`u nodi. Ci`o viene effettuato definendo due funzioni SN, EN che associano rispettinameste sottoscrittori e eventi ai nodi del sistema pub/sub. In particolare sia o una sottoscrizione, SN(o) restituisce l’insieme
1.4. MODELLO ARCHITETTURALE 15
Type Name Routing Filtering Nodes Nodes handling
storins Subs Events
Flooding Event flooding Det. Subscribers No Tutti
Subs Flooding Det. Publishers Tutti No
Selective Filter-Based Det. Intermediaries sottoinsieme sottoinsieme Rendezvous-based Det. Intermediaries sottoinsieme sottoinsieme
Gossiping Basic gossiping Prob. Subscribers No tutti
Informed gossiping Prob. Intermediaries sottoinsieme sottoinsieme Tabella 1.2: Classificazione algoritmi di routing.
dei nodi responsabili della memorizzazione di o e di effettuare la consegna a tutti i sottoscrittori di o (detti nodi rendezvous di o ). Mentre EN(e) ritorna l’insieme dei nodi responsabili di inoltrare e ai sottoscrittori registrati nel sistema (detti no- di rendezvous di e). Questo algoritmo funziona solo se `e verificata la propriet`a di Mapping interaction [48], che afferma: l’insieme dei nodi rendezvous di e devono memorizzare tutte le sottoscrizioni collegate ad e. Un publisher quando invia un evento e, inoltra tale evento ai nodo rendezvous di e, i quali effettuano l’operazione di matching tra e ed tutti i sottoscrittori del nodo. La definizione delle funzioni EN, SN che rispettino la mapping interaction `e non banale in quanto implica la defini- zione di un raggruppamento dello spazio delle sottoscrizioni, con assegnamento ad un singolo nodo. Questo algoritmo non si adatta bene ad ambienti con elevata dina- micit`a, in quanto la rimozione o l’inserimento di un nuovo nodo del sistema richiede una revisione dell’intero sistema di raggruppamento. Le reti non strutturate non sono adatte a questo algoritmo a causa della dinamicit`a e delle dimensioni ignote.
Lo svantaggio principale sono le restrizioni imposte al linguaggio di sottoscrizione, in quanto non sempre `e possibile effettuare una segmentazione dei sottoscrittori, si pensi ad esempio al caso di sottoscrizioni su spazi multi-dimensionali. Le prestazioni inerenti il memory overheard dipendono dalla funzione di mapping usata.
Event gossiping: Gli algoritmi di gossiping sono algoritmi probabilistici, che non usano rou- ting strutturati. Risultano particolarmente adatti in reti con elevato dinamismo dei nodi.
Nel basic gossiping ogni nodo scambia informazioni con uno o pochi nodi vicini nella rete, selezionati in modo casuale. In questo modo la disseminazione dell’informazione assomiglia molto alla disseminazione epidemiologica, la quale sotto certe condizioni porta alla generazione di una diffusione robusta e auto-stabilizzante [49]. Questo algoritmo non richiede la memorizazione di informazioni d’instradamento ed informazione rigurdante le sottoscrizioni, lo svantaggio `e rappresentato da una moderata ridondanza dei messaggi scambiati. Questo algoritmo utilizza un approccio totalmente distribuito, e consente di avere una elavata stabilit`a con reti ad elevato dinamismo. In Informed gossip protocol si ha un basic gossiping algorithm nel quale la scelta dei nodi vicini a cui inoltrare l’evento viene eseguita in base alle conoscenze acquisite dal nodo durante la sua esistenza. Con questo approccio si tenta di inoltrare l’evento solo ai nodi interessati. Ogni nodo mantiene informazioni riguardanti le sottoscrizioni dei suoi vicini, quindi si introduce un overheard di memoria, a vantaggio di un minor overheard di messaggi.
Nella tab. 1.2 riporto la classificazione degli algoritmi di routing.
1.4.4 Controllo degli eventi (Matching Algorithm)
Con Matching si indica il processo di controllo di un evento che sia adatto ad una sottoscrizione.
Il matching `e eseguito dal sistema Pub/Sub al fine di determinare se un evento debba essere consegnato ad un subscriber o meno. Esso si interfaccia anche con l’agoritmo di routing, in quanto spesso decisioni di routing sono prese in base al matching degli eventi delle sottoscri- zioni. Nel contesto di sistemi di larga scala `e desiderabile da un lato avere un un numero di sottoscrizioni elevato e dall’altro avere alte velocit`a di elaborazione degli eventi. Ne segue che in generale il processo di matching viene eseguito spesso e su grandi quantit`a di dati. Questo non
`e un gran problema in un sistema Topic-based, dove il matching si riduce ad un semplice lookup in tabelle, ma in un sistema Content-based `e un grande scoglio per le performance generali, per cui l’efficienza dell’algoritmo di matching gioca un ruolo fondamentale.
Capitolo 2
RTI DDS
Visto il crescente interesse nei confronti del paradigma di comunicazione Publish/Subscribe e la mancanza di supporto alla qualit`a del servizio offerto dai prodotti sviluppati, l’OMG (Object Management Service) ha deciso di redigere uno standard per la comunicazione publish/subscribe che contenga, come elemento caratterizzante, un forte supporto alla qualit`a del servizio. Tale standard prende il nome di Data Distribution Service for Real Time System (DDS). Attual- mente questo standard `e seguito da molti produttori software, i quali oltre alle funzionalit`a previste dallo stesso, n´e implementano delle nuove. Lo standard OMG non prevede specifiche riguardanti l’integrazione tra i diversi prodotti software, quindi, attualmente non `e possibile avere interoperabilit`a tra le varie implementazioni del DDS. Per sopperire a tale mancanza si sta lavorando per redigere uno standard di interoperabilit`a tra diverse implementazioni. Diverse aziende hanno deciso di implementare tale standard, tra cui Real-Time Innovation (RTI) [5]; il prodotto software utilizzato nello sviluppo di questa tesi.
Prima di analizzare la specifica fornita dall’OMG ed l’implementazione di RTI, occorre per`o introdurre, con una breve excursus il concetto di Middleware.
2.1 Introduzione al Middleware
Il Middleware[50] `e uno strato di software che si interpone tra le applicazioni ed il sistema ope- rativo, isolando le applicazioni dall’architettura usata. Nel Network Middleware (Figura 2.1) si ha l’isolamento dalla particolare pila protocollare usata per la rete: l’applicazione semplice- mente non necessita di sapere che stack usare (TCP/IP, IPX . . . ) altres`ı non ha bisogno di creare strutture apposite (per esempio socket), bens`ı si rivolge a questo strato per ottenere tali funzionalit`a.
L’utilizzo di uno strato software aggiuntivo, il middleware appunto, consente di ottenere un elevato livello di servizio per gli utenti, ed un elevato livello di astrazione per i programmatori.
Consente di facilitare la manutenzione, la stesura e l’integrazione di applicazioni. Tale ruolo `e, per certi versi, un’evoluzione del ruolo del middleware, che in partenza era limitato a ricercare l’efficienza e l’interoperabilit`a nel sistema.
Pi`u precisamente un Middleware si pu`o definire come
un software di connessione che consiste in un insieme di servizi e/o di ambienti di sviluppo di applicazioni distribuite che permettono a pi`u entit`a (processi, oggetti, ecc), residenti su uno o pi`u elaboratori, di interagire attraverso una rete di inter-
17
connessione a dispetto di differenze nei protocolli di comunicazione, architetture dei sistemi locali, sistemi operativi, ecc.
Il suo principale obiettivo `e fornire la “visione” di un’applicazione distribuita come un in- sieme di entit`a cooperanti al di sopra di OS1 eterogenei. A tale scopo devono essere forniti servizi per la localizzazione di una entit`a, servizi per la scoperta delle operazioni eseguibili da una entit`a, servizi per la sincronizzazione temporale e per la sicurezza , ecc. .
Figura 2.1: Struttura a livelli per applicazioni di rete distribuite.
.
2.1.1 Tipi e funzionalit` a del Middleware
Un Middleware ha la caratteristica di fornire un ben preciso modello di programmazione per lo sviluppo di applicazioni distribuite, che consente al programmatore di non occuparsi di tutti i dettagli di basso livello della comunicazione e dello scambio di messaggi tra processi distribuiti.
Le principali specifiche e propriet`a che un generico middleware deve fornire sono:
Marshalling e Unmarshalling: i dati prodotti dalle applicazioni devono essere formattati per garantire l’indipendenza hardware/software dell’host di provenienza, il Marshalling (letteralmente “impastamento”), effettuato in fase di trasmissione, prevede la suddivi- sione dei dati in pi`u messaggi, la codifica in caratteri universali ASCII, la conversione little-endian e big-endian, ecc.; l’Unmarshalling, effettuato in fase di ricezione, opera esattamente al contrario riportando i dati in uno stato comprensibile a quel particolare host;
Data Representation and Codification: per poter effettuare il marshalling e unmarshal- ling, il protocollo di middleware deve definire tutti i tipi di dato che le applicazioni possono utilizzare per comunicare (es. string, float, enumerated ecc.); in tal modo il programma- tore potr`a tralasciare i dettagli dei processi di comunicazione, a patto di lavorare, in fase di programmazione, con i tipi messi a disposizione dal protocollo che sta impiegando;
1Operating System - sistema operativo
2.1. INTRODUZIONE AL MIDDLEWARE 19 Invocazioni Remote: i moderni middleware, con la nascita della programmazione a oggetti distribuiti, devono permettere l’invocazione remota di processi e metodi per garantire un’interazione efficiente tra le applicazioni, l’invocatio remote consente cio;
Garanzia della Location Transparency: gli applicativi che costituiscono il sistema distri- buito devono poter comunicare senza preoccuparsi della loro posizione fisica n´e dei loro indirizzi logici, sar`a il Middleware Layer a occuparsi dei dettagli di basso livello;
Totale trasparenza di utilizzo per l’utente finale: l’utente dell’applicazione programma- ta col supporto middleware non deve “accorgersi” della presenza dello stesso e quindi non deve occuparsi di coordinarne il funzionamento dello stesso, in quanto sar`a del tutto integrato nel codice dell’applicazione;
Un Middleware pu`o essere catalogato in base ai servizi offerti, in base a tale principio si ha la seguente classificazione:
RPC-based system: rappresenta la forma pi`u semplice di middleware, prevede le infrastrut- ture necessarie per effettuare le RPC2 in modo trasparente al programma, ed in modo uniforme rispetto ai protocolli sottostanti;
TP Monitor: i middleware di questo tipo sono in grado di supportare transactional RPC cio´e transazioni distribuite con propriet`a ACIDE con dati distribuiti su pi`u sistemi eterogenei;
Object-Broker: estendono il paradigma RPC nel mondo object-oriented, con l’aggiunt`a di nu- merosi servizi che semplificano lo sviluppo di applicazioni distribuite Object-Oriented. In questo modello si ha l’introduzione di concetti come eredit`a e polimorfismo. Uno standard specitico per tale applicazione `e CORBA (Common Object Request Broker Architecture) [1];
Object monitor: nasce dall’unione di due tipi di middleware il TP Monitoe e l’Object Broker, questo prodotto nasce a causa di esigenze di mercato, infatti non si ha l’introduzione di innovazioni;
Message-oriented: (MOM) sono middleware in grado di supportare l’interoperabilit`a message- based, basata su scambio di messaggi. Per messaggio si intende un insieme di dati strut- turati, caratterizzati da un tipo ed un’insieme di parametri del messaggio. Una delle pi`u importati astrazioni generate `e quella di MESSAGE QUEUING. Un esempio di tale implementazione `e il JMS (Java Message Sistem) [3]. La limitazione principale di questo middleware `e l’indirizzamento punto-punto;
Message-brokers: questo middleware supera i limiti del MOM eliminando lo schema di in- dirizzamento punto-punto ma spostando l’indirizzamento al contenuto dei messaggi. Il paradigma pi`u noto `e il Publish/Subscribe;
Nella Fig. 2.2 viene rappresentata la genealogia dei middleware appena descritti.
2Remote Procedure Call.
Figura 2.2: Genealogia del Middleware.
2.2 DDS
L’obbiettivo del DDS `e di agevolare la distribuzione efficiente dei dati in sistemi distribuiti, e ha come oggetto i sistemi real-time; per tale motivo `e stata sviluppata un’architettura com- pletamente decentralizzata ed sono state previsto un ricco insieme di qualit`a del servizio che consentono di bilanciare l’efficienza e le prestazioni del software.
Ia specifica del DDS `e basata sull’astrazione di un Global Data Space GDS, in cui i publisher producono dati ed i subscriber consumano dati, tale spazio pu`o essere caratterizzato dal concetto di topic, Publisher, Subscriber, Subscription e Quality of Service;
Quality of Service: con le QoS si indica un concetto generale, utilizzato per specificare il comportamento del servzio fornito. Infatti con le QoS il protocollo spiega “cosa” ci si puo attendere da una applicazione e non il “come” si ottiene. La QoS caratterizza il DDS dagli altri midleware Pub/Sub, in quanto fornisce un’ampia ricchezza di QoS supportate.
Per implementare tali caratteristiche il DDS prevede la capacit`a di controllare e limitare l’uso di risorse come la memoria, la banda di rete, e molte propriet`a non funzionali dei topic.
Topic: definisce un tipo di dato che pu`o essere scritto nel GDS. Nello standard attuale devono essere utilizzati dei tipi non ricorsivi e devono essere definiti tramite l’OMG IDL ,Interface Definition Languafe. Il DDS fornisce anche la capacit`a di distinguere topic di uno stesso
2.2. DDS 21 tipo tramite l’uso di semplici chiavi. Ad ogni topic si possono associare specifiche qualit`a del servizio (QoS). Da un punto di vista applicativo i topic sono utilizzati per definire l’Application Information Model, cio´e il tipo di informazioni scambiate nel modello. Il DDS fornisce inoltre le capacit`a per eseguire semplici aggregazioni di topic, ed il content- based filtering;
Publisher: definisce una sorgente dati, pu`o dichiarare l’interesse di generare dati con determi- nate caratteristiche di qualit`a del servizio associate e scrivere il dato nel GDS. Le qualit`a definite devono essere compatibili con quelle dichiarate dal topic di interesse. In figura 2.4 si pu`o notare come il DDS si affidi ad una specifica di topic inglobata in DataWriter, la quale definisce un tipo scritto nel GDS; il publisher incapsula la responsabilit`a legata alla disseminazione dei dati in accordo con le QoS richieste;
Subscriber: leggono topic in GDS, per i quali esiste una sottoscrizione correlata. Il DDS conta su uno specifico DataReade che serve come tipo letto dal GDS. Il Subscriber incapsula la responsabilit`a associate alla ricezione dei dati in accordo alle QoS richieste.
Subscription: operazione logica che consente di legare insieme un subscriber ai publish inte- ressati. La sottoscrizione deve soddisfare due tipi di condizioni. Un tipo di condizioni sono relative alle caratteristiche concrete del topic, come tipo, nome del contenuto e . L’altro insieme di condizioni sono relative alle QoS. Per le QoS si segue un modello di richiesta/offerta, nel quale le QoS richieste devono essere le stesse o pi`u deboli di quelle offerte. Il DDS prevede uno schema di sottoscrizione pi`u generale del tipico Topic-Based Model, lo schema consente una sottoscrizione Content-Based. Per specificare il filtro della sottoscrizione si utilizza un sottoinsieme di Struct Query Language SQL.
Una caratteristica chiave alla base del DDS `e il servizio di discovery. Tale servizio ha il compito di scoprire e comunicare le propriet`a dei partecipanti al GDS. Infatti le informazioni necessarie per stabilire una sottoscrizione sono completamente distribuite e vengono scoperte automaticamente.
2.2.1 QoS
Il DDS implementa un insieme molto ricco di QoS, ora fornir`o una breve panoramica delle QoS pi`u interessanti, tali caratteristiche vengono catalogate in base all’aspetto che permettono di controllare.
Risorse: queste QoS consentono di controllare le risorse usate nella disseminazione dati, le pi`u rilevanti politiche che consentono di controllare le risorse di calcolo e le risorse di rete sono la RESOURCE LIMITY e la TIME BASED FILTERED. La RESOURCE LIMITY permette di controllare la quantit`a di messagi memorizati in una implementazione del DDS. La TIME BASED FILTERED permette alle applicazioni di specificare l’intervallo temporale minimo tra due messagi di dato; i messagi prodotti ad una velocita maggiore non sono consegnati. Questa politica consente di controllare la larghezza di banda utilizata nella connessione, memoria e potenza di calcolo dei subscriber connessi, i quali possono avere una limitat`a capacita di calcolo.
Data Timeliness: il DDS prevede un insieme di politiche che consentono di controllare la propriet`a di timeliness della distribuzione dati. Le QoS supportate sono DEADLINE e LATENCY BUDGET. La DEADLINE permette ad una applicazione di definire il massi- mo intervallo di tempo tra i dati; se trascorre tale intervallo senza l’arrivo di un messaggio
viene effettuata una notifica tramite LISTENER. Il LATENCY BUDGET consente ad una applicazione di fornire al middleware il livello d’urgenza associato ad un dato comu- nicato. In particolare specifica il massimo ammontare di tempo che dovrebbe trascorrere dall’istante in cui il dato `e scritto, all’istante in cui viene posto nella coda di ricezione del ricevente.
Data Availability: per controllare la data availability posso usare le politiche di , LIFESPAN e HISTORY. La DURABILITY fornisce un controllo sul tempo di vit`a di un dato scritto nel GDS. Questa caratteristica consente al dato di essere volatile e dall’altro permette al dato di avere persistenza. `E utile notare che dati transienti e persistenti consentono di fare Time Decoupling tra lo scrittore ed il lettore; rendendo il dato disponibile per i successivi lettori inscritti, nel caso di dati transienti oppure dopo che lo scrittore ha lasciato il GDS, nel caso di dati persistenti. Il LIFESPAN permette di controllare l’intervallo di tempo nel quale il dato `e considerato valido, il valore di default `e infinito. La HISTORY fornisce un modo per controllare il numero di dati, cio´e la sottosequenza scritta nello stesso topic e tenuta disponibile per il lettore; i possibili valori attribuibili sono gli ultimi, gli ultimi N oppure tutti i samples.
Data Delivery: permette di controllare come il dato `e consegnato, ed a chi `e consentito scri- vere su uno specifico topic. Le politiche che si possono usare sono la RELIABILITY, DESTINATION ORDER e OWNERSHIP. La RELIABILITY permette di controllare il livello di reliability associato alla diffusione dati, le possibili scelte sono reliable e best- effort. La DESTINATION ORDER consente di definire l’ordine dei cambiamenti eseguiti dal publisher sulla stessa istanza di un dato topic. Il DDS consente di ordinare i vari cambiamenti in accordo ai time-stamp della sorgente o della destinazione. La politica di OWNERSHIP consente di controllare il numero di scrittori permessi per un dato topic.
Se configurato come esclusivo si indica che il topic pu`o essere posseduto e quindi scritto da un singolo scrittore. `E possibile inoltre associare una nuova politica, detta OWNER- SHIP STRENGTH che consente di associare un valore numerico di forza ad ogni scrittore, in questo caso il topic `e posseduto da colui che ha un valore di owneship strength pi`u alto.
Un valore di OWNERSHIP STRENGTH `e shared, con questo valore si possono avere pi`u scrittori che sovrascrivono un topic. I vari cambiamenti devono essere ordinati in accordo al valore settato nella politica di DESTINATION ORDER.
Oltre alle politiche appena definite il DDS fornisce alcuni modi per definire e distribuire infor- mazioni di bootstrapping, tramite il significato di USER DATA, TOPIC DATA e GROUP DATA.
La USER DATA permette all’aplicazione di associare informazioni aggiuntive all’oggetto entit`a creato, tale informazione pu`o essere utilizzata dalle applicazioni remote per uno scopo apposito, ad esempio attribuire credenziali di sicurezza.
Il TOPIC DATA consente di aggiungere informazioni aggiuntive ad un topic creato, tale informazione pu`o essere prelevata da applicazioni remote.
Il GROUP DATA associa informazioni aggiuntive al Publisher e Subscriber creati, tale va- lore `e disponibile alle applicazioni nelle entita DataReader e DataWriter, tale valore viene propagato tramite il topic creato.
Un’altra politica di QoS prevista `e la LIVELINESS, la quale consente di settare i parametri utilizzati nella determinazione di entita considerate “vive”. Questa politica ha molti settaggi per consentire una modellazione pi`u consona per le possibili situazioni. Il settaggio AUTOMATIC consente di determinare i fallimenti al livello di processo ma non determina i fallimenti a livello logico di processo, questa modalit`a richiede poco overheard. Il settagio MANUAL consente di determinare fallimenti logici, richiede l’esecuzione dell’operzione di ASSERT-LIVENESS.
2.2. DDS 23 La politica di PARTITION consente l’introduzione di una partizione logica nella partizione fisica indotta dal dominio, questa partizione non crea un vero isolamento tra i partecipanti come un dominio. Questa policy pu`o essere modificata, ci`o causa una modifica delle relazioni esistente tra i DataReader ed i DataWriter del dominio, creando nuove relazioni o rompendo relazioni esistenti.
2.2.2 Architettura
La specifica del DDS definisce due livelli di interface, il DCPS (Data Centric Publish-Subscribe) ed il DLRL (Data Local Reconstruct Layer ).
DCPS: Prevede le funzionalit`a richieste per pubblicare e ricevere data-object, in modo effi- ciente;
DLRL: Livello opzionale che permette una semplice integrazione di servizi al livello applicativo;
Di seguito effettuer`o un analisi del DCPS.
Il DCPS deve essere altamente competivo ed efficiente nell’uso delle risorse. Per tale mo- tivo `e importante che le interfacce siano progettate in modo da consentire al middleware di pre-assegnare le risorse, evitare l’uso di risorse illimitate o difficili da predire, minimizzare la necessit`a di fare copie di dati. Le interfacce definite hanno il vantaggio di essere semplici da usare, sicure ed efficienti.
Le funzionalit`a del DCPS sono:
- Identificazione dei dati che un publisher intende pubblicare e tipi di valori previsti per tali dati;
- Identificazione dei dati di interesse per un subscriber e come accedere a tali dati;
- Applicazioni per definire topic, per associare vari tipi di dato al topic, per creare publisher e subscriber e per associare caratteristiche di QoS a tali entit`a.
Per descrivere un DCPS si usano due specifiche, il PIM Platform Independent Model ed il PSM Platform Specific Model per le piattaforme basate su PIM; Noi ora analizzeremo il PIM.
Nel DCPS la comunicazione `e effettuata con l’aiuto delle seguenti entit`a: DomainPar- ticipant, DataWriter, DataReader, Publisher, Subscriber e topic. Lo schema con- cettuale del DCPS viene rappresentato in figure 2.3, nel quale viene rappresentato il flusso dell’informazione tra le varie entit`a.
Il Publisher ed il DataWriter risiedono nel mittente, mentre Subscriber ed Data Rea- der risiedono nel ricevente. Un Publisher `e responsabile della distribuzione dei dati, egli pu`o publicare dati di diverso tipo. Un DataWriter `e l’oggetto dell’applicazione usato dal publi- sher per comunicare l’esistenza di una nuova istanza di dato per uno specifico tipo di dato, ed
`e associato ad un singolo tipo di dato. Una volta comunicata l’esistenza di un nuovo dato o un cambiamento con DataWriter(s) `e compito del Publisher determinare quando `e appropriato generare il messagio corrispondente ed eseguire realmente la pubblicazione. Tutto ci`o dovra essere fatto in accordo alle QoS associate al Publisher ed al DataWriter corrispondente.
Un Subscriber `e l’oggetto responsabile della ricezione di dati pubblicati, e della fornitura di tale dato alle applicazioni interessate, si possono ricevere vari tipi di dati, rispettando le QoS richieste. Per accedere ai dati ricevuti l’applicazione usa il modulo DataReader collegato alla sottoscrizione del dato, con tale modulo si esprime l’interesse dell’applicazione nei confronti dei dati relativi al DataReader.
Figura 2.3: Schema concettuale del DCPS.
Il Topic `e un oggetto concettuale che si interpone tra le publicazioni (oggetti DataWriter ) e le sottoscrizioni (oggetti DataReader ), con l’obbiettivo di crere un’associazione tra un nome (unico nel sistema), un tipo di dato e le QoS associate al dato stesso. La definizione del tipo di dato deve fornire le informazioni necessarie per il servizio di gestione dei dati, come serializza- zione e deserializzazione del dato in/da uno adatto alla trasmissione. La definizione pu`o essere fatta per mezzo di un linguaggio testuale oppure per mezzo di un “plugin” operazionale che fornisce i metodi necessari. Il DCPS pu`o anche supportare sottoscrizioni CONTENT-BASED con l’uso di un filtro, questa `e una caratteristica opzionale, in quanto il filtro pu`o essere com- putazionalmente intensivo e quindi introdurre un ritardo difficile da predire; comunque recenti ricerche hanno dimostrato che esistono efficienti algoritmi per affrontare questo problema. Il DDS differisce dai sistemi publisher/subscriber “enterprise”, come il sistema Rendezvous, nel binding tra topic e tipi di dato, in quanto il topic `e pi`u di una etichetta, ma tale disaccoppia- mento presente nel DDS permette di associare delle aggiuntive QoS, di effettuare ottimizzazioni come la pre-allocazione delle risorse necessarie al topic.
Il modello concettuale del DCPS viene rappresentato in figua 2.4. Nel modello si nota che tutte le classi appena analizzate estendono il DCPSEntity, ogni specializzazione ha una corrispondente specifica Listener ed un insieme di valori di QoS specifici.
Nel modello concettuale troviamo anche le QoSPolicy, Listener, DomainParticipant e StatusCondition.
Le QoSPolicy costituiscono l’insieme delle propriet`a di QoS previste, viene previsto un meccanismo generale che permette alle applicazioni di controllare i servizi e modellarli per le loro necessit`a. Ogni Entity supporta specifici tipi di QoS.
Il Listener prevede un meccanismo generico che consente al middleware di informare l’ap- plicazione dell’accadimento di eventi asincroni importanti, come l’arrivo di un dato o la viola- zione di una specifica propriet`a di QoS. Dalla figura si evince che `e stata effettuata la sceta di
2.2. DDS 25
Figura 2.4: Modello del DCPS.
