Tecniche per l`affidabilità delle comunicazioni basate su codici FEC

Facoltà di Ingegneria
Corso di Studi in Ingegneria Informatica
tesi di laurea specialistica
Tecniche per l’affidabilità delle
comunicazioni basate su codici FEC in
piattaforme middleware OMG DDS
Anno Accademico 2007/2008
Relatore
Ch.mo prof. Stefano Russo
correlatori
Ing. Christiancarmine Esposito
Ing. Generoso Paolillo
candidato
Angelo Gentile
matr. 885/156
Alla mia famiglia
Non cercare di diventare un uomo di successo,
ma piuttosto un uomo di valore.
Albert Einstein
Indice
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme middleware
OMG DDS ............................................................................................................................................I Indice............................................................................................................................................... V Introduzione ..................................................................................................................................... 7 Capitolo 1 ....................................................................................................................................... 13 Meccanismi di comunicazione affidabile e stato dell’arte dei protocolli multicast........ 13 1.1 I requisiti di un protocollo di comunicazione affidabile e i sistemi mission-critical ........... 13 1.2 Schemi per la realizzazione di una comunicazione affidabile ............................................. 15 1.2.1 Affidabilità basata sul sender ........................................................................................ 20 1.2.2 Affidabilità basata sul receiver ..................................................................................... 21 1.3 I protocolli multicast affidabili ............................................................................................ 24 1.3.1 RMDP:un semplice protocollo basato su FEC ............................................................. 24 1.3.2 Digital Fountain: affidabilità sender-based mediante uso di Tornado Codes ............... 28 1.3.3 EC-SRM:un approccio ibrido NAK + FEC .................................................................. 30 1.3.4 Slingshot:un esempio di affidabilità mediante receiver-based FEC ............................. 34 1.3.5 Ricochet: la Lateral Error Correction............................................................................ 38 Capitolo 2 ....................................................................................................................................... 45 Tecniche di affidabilità basate su Erasure Codes in piattaforme DDS........................... 45 2.1 Introduzione ......................................................................................................................... 45 2.2 Gli Erasure Codes ................................................................................................................ 46 2.2.1 Concetti di base ............................................................................................................. 47 2.2.2 Codici Reed-Solomon ................................................................................................... 50 2.2.3 Codici LDPC ................................................................................................................ 52 2.3 I middleware di tipo publish/subscribe e l’OMG Data Distribution Service ....................... 57 2.3.1 Il modello di comunicazione publish/subscribe ............................................................ 57 2.3.2 Introduzione allo standard OMG DDS ......................................................................... 61 2.3.4 Modello di programmazione del DDS ......................................................................... 63 2.3.4 Le politiche di QoS del DDS ........................................................................................ 65 2.3.5 Le problematiche nell’utilizzo del DDS nel contesto dei MCS .................................... 69 2.3.6 Una possibile soluzione: l’utilizzo di FEC ................................................................... 70 V
Capitolo 3 ....................................................................................................................................... 72 Erasure Codes a livello applicativo e realizzazione di un protocollo di trasporto
affidabile in OpenDDS ......................................................................................................... 72 3.1 Integrazione degli Erasure Codes in piattaforme DDS ........................................................ 72 3.2 Erasure Codes a livello applicativo...................................................................................... 74 3.2.1 La piattaforma RTI DDS............................................................................................... 74 3.2.2 Libreria Jerasure per codici Reed-Solomon .................................................................. 80 3.2.3 L’applicazione benchmark ............................................................................................ 83 3.3 La campagna sperimentale ................................................................................................... 85 3.3.1 Descrizione del testbed ................................................................................................. 85 3.3.2 Caratterizzazione del comportamento di rete................................................................ 86 3.3.3 Emulazione di rete:il modello di Gilbert....................................................................... 89 3.3.4 Risultati e valutazione delle prestazioni........................................................................ 91 3.3.5 Considerazioni .............................................................................................................. 98 3.4 Erasure Codes a livello trasporto ......................................................................................... 98 3.4.1 La piattaforma OpenDDS ............................................................................................. 99 3.4.2 Il Pluggable Transport Layer di OpenDDS................................................................. 101 3.5 Il prototipo di un protocollo di trasporto FEC-based per OpenDDS ................................. 106 3.5.1 Scelte di progetto ........................................................................................................ 106 3.5.2 Architettura complessiva............................................................................................. 107 3.5.3 Integrazione in OpenDDS ........................................................................................... 112 Conclusioni e sviluppi futuri ........................................................................................................ 115 Appendice A ................................................................................................................................ 118 Realizzazione di un plug-in di trasporto in OpenDDS ................................................... 118 A.1 Utilizzo del Transport Framework di OpenDDS .......................................................... 118 Ringraziamenti ............................................................................................................................. 136 Bibliografia .................................................................................................................................. 140 VI
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Introduzione
I sistemi per la distribuzione dei dati hanno subito in anni recenti una profonda
trasformazione che si è tradotta in una enorme crescita in termini di complessità e
dimensioni. Essi sono oramai distribuiti su scala geografica, costituiscono cioè vere e
proprie federazioni di sistemi i cui sottosistemi componenti sono spesso situati a distanze
tali da dover interagire attraverso reti di tipo WAN e/o attraverso la Internet.
La nuova generazione di tali sistemi prende il nome di Ultra Large Scale (ULS) Systems
proprio ad indicare tali caratteristiche.
L’estensione su scala geografica dei sistemi ULS e l’elevato numero di parti che in essi
intervengono pongono delle serie problematiche di affidabilità e scalabilità. Data la
vastità delle reti di interconnessione è infatti elevatissima la probabilità che qualche
componente hardware si guasti o che si verifichi una congestione, provocando la perdita
dei dati inviati. I sistemi ULS devono pertanto essere in grado di funzionare anche in
presenza di un certo numero di guasti di rete, necessitano cioè di appositi meccanismi di
fault-tolerance.
In questo contesto si può dunque definire come affidabile un servizio di distribuzione dei
dati se esso garantisce la consegna anche in presenza di guasti di rete.
La scalabilità è un altro requisito fondamentale per tali sistemi. Gli ULS hanno moltissimi
utenti ed utilizzano grosse quantità di risorse data la vastità della scala di distribuzione, ed
7
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
è molto probabile che il numero di utenti aumenti durante il ciclo di vita degli ULS, con
conseguente aumento delle risorse richieste. È pertanto necessario saper gestire la crescita
delle dimensioni
in modo che non
provochi un peggioramento eccessivo delle
prestazioni. Un sistema è infatti scalabile se le sue prestazioni degradano linearmente al
crescere della dimensione del sistema stesso.
Nel dominio dei sistemi orientati alla distribuzione dei dati esiste la classe dei sistemi
mission-critical, per la quale ai requisiti concernenti l’affidabilità e la scalabilità se ne
aggiungono altri riguardanti la celerità nella consegna dei dati stessi. Si è cioè di fronte
alla necessità di offrire un servizio di distribuzione affidabile dei dati nel rispetto di
determinati vincoli temporali.
Esempi di sistemi mission-critical sono i sistemi di controllo del traffico aerero (ATC-Air
Traffic Control) dislocati su scala continentale.
Oggetto del presente lavoro di tesi è lo studio di tecniche innovative per la realizzazione
di comunicazioni affidabili in sistemi mission-critical che effettuano distribuzione di
dati.
I due classici approcci alla realizzazione di una comunicazione affidabile prevedono
l’utilizzo di:
• Tecniche di Automatic Repeat reQuest (ARQ) che raggiungono l’affidabilità
mediante richieste (esplicite o meno) di ritrasmissione dei dati persi;
• Tecniche di Forward Error Correction (FEC) che consentono di rimediare alle
eventuali perdite e/o corruzioni dei dati mediante codici rivelatori e correttori
d’errore.
8
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Le tecniche di tipo ARQ hanno il pregio della semplicità implementativa, soffrendo
peraltro di problemi inerenti alla proliferazione delle richieste di ritrasmissione e
all’elevata latenza in fase di scoperta e recupero perdite.
Le tecniche di tipo FEC, pur presentando un carico computazionale aggiuntivo dovuto alle
fasi di codifica e decodifica, permettono di superare le limitazioni degli schemi ARQ
offrendo in generale una maggiore prevedibilità dei tempi di recupero dei pacchetti persi.
Non esiste tuttavia uno schema in assoluto migliore di un altro e l’efficacia di ognuno di
essi dipende dal contesto in cui operano e dai requisiti dell’applicazione.
Una soluzione architetturale interessante per la realizzazione di applicazioni orientate alla
distribuzione dei dati in tali sistemi è costituita dai sistemi middleware di tipo
publish/subscribe . Il modello Publish/Subscribe risulta particolarmente adatto alla
realizzazione di applicazioni distribuite aventi come task principale la distribuzione dei
dati.
I middleware basati sul modello Publish/Subscribe offrono infatti un elevato grado di
disaccoppiamento tra le entità comunicanti, rendendo
particolarmente agevole la
realizzazione di schemi di comunicazione molti-a-molti (anche con requisiti di tempo
stringenti,come nel caso di sistemi real-time e mission critical appunto) ed offrendo un
elevato grado di scalabilità al crescere dei partecipanti alla comunicazione.
In particolare in tali contesti è ampiamente utilizzato un particolare tipo di middleware di
tipo publish/subscribe – l’OMG DDS (Data Distribution Service)– che oltre alle proprietà
comuni ai sistemi basati su tale modello, offre un ampio supporto alle politiche di QoS
(Quality of Service)
Fissato l’obiettivo di realizzare uno schema di affidabilità innovativo per i servizi di
distribuzione dei dati e partendo dalla constatazione che, allo stato attuale, le piattaforme
9
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
DDS esistenti offrono meccanismi di affidabilità basati esclusivamente su schemi ARQ, in
questo lavoro di tesi si è:
• Studiata sperimentalmente la realizzazione di meccanismi che, mediante uso di
codici di protezione (Erasure Codes) integrati nel DDS, introducano
determinismo nella consegna dei dati;
• iniziata la realizzazione di un protocollo di trasporto affidabile per piattaforme
DDS integrante Erasure Codes.
In una prima fase di studio si è utilizzata un’applicazione benchmark per estrarre dati
sperimentali che permettessero di confermare la validità dell’approccio.
In particolare si è messo a confronto l’utilizzo del servizio di consegna affidabile della
piattaforma DDS stessa, basato su soli meccanismi di ritrasmissione, con l’utilizzo di un
schema FEC realizzato a livello applicativo, cioè “poggiato” sul servizio best-effort del
DDS.
Le sperimentazioni effettuate in laboratorio mediante emulatori WAN confermano che
sotto certe ipotesi è possibile realizzare una consegna certa dei dati con il solo utilizzo di
FEC, senza dover ricorrere necessariamente al servizio di consegna affidabile fornito dalla
piattaforma DDS.
Alla luce dei risultati ottenuti si è tuttavia compresa la necessità di un cambio di
approccio,stante la dipendenza della soluzione iniziale dal DDS stesso.
Per realizzare un meccanismo che non fosse vincolato al DDS, ci si è dunque concentrati
sulla possibilità di realizzare uno strato di trasporto affidabile da integrare in una
piattaforma DDS. In particolare si è lavorato su un’implementazione open-source dello
standard DDS, OpenDDS.
Partendo dal transport framework di OpenDDS e da un protocollo multicast UDP-like
(cioè non affidabile) si è realizzato un primo prototipo di un semplice protocollo
integrante Erasure Codes. Tale prototipo, pur essendo estremamente semplice, costituisce
10
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
una piattaforma iniziale per la costruzione di un protocollo di trasporto complesso per
DDS basato su schemi di tipo FEC.
11
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
12
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Capitolo 1
Meccanismi di comunicazione affidabile e stato dell’arte dei
protocolli multicast
1.1 I requisiti di un protocollo di comunicazione affidabile e i sistemi missioncritical
Un protocollo di comunicazione può essere definito affidabile se garantisce la
consegna dei messaggi anche in presenza di guasti di rete. La consegna certa è un requisito
particolarmente laborioso da raggiungere in alcuni contesti applicativi.
L’affidabilità della comunicazione in sistemi mission-critical (MCS-Mission
Critical Systems) operanti su scala geografica è l’oggetto del presente lavoro di tesi.
I MCS di nuova generazione sono definiti come federazioni di sistemi autonomi
interconnessi da reti a estensione geografica.
I suddetti sistemi presentano un’elevata criticità temporale: dati inviati oltre fissati limiti
possono condurre a instabilità del sistema con conseguenti rischi per persone o cose.
La loro natura mission critical sottintende inoltre la capacità di far fronte ad errori e guasti
che inevitabilmente si presentano in fase operativa.
Infine,rappresentando una classe di sistemi ULS (Ultra Large Scale)[25] sono caratterizzati
da una grande quantità di dati scambiati,diversi e numerosi utenti umani e,come già detto,
13
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dall’utilizzo di reti di telecomunicazione ad estensione geografica (reti WAN- Wide Area
Network).
Figura 1 - Esempio di sistema mission critical su scala geografica: controllo del traffico aereo
Tali reti sono caratterizzate da:
•
elevata imprevedibilità dei patterns di perdita dei pacchetti
•
elevata variabilità della latenza di rete (definita come l’intervallo di tempo
intercorrente tra l’invio del dato da parte del mittente e l’effettiva ricezione
dello stesso da parte del ricevente.)
•
guasti di rete frequenti ,non prevedibili e spesso correlati tra loro,con
conseguenti perdite di messaggi ,isolate (raramente) o a burst .
14
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Le caratteristiche di tali sistemi e delle reti su cui operano impongono requisiti
particolarmente stringenti alla consegna dei messaggi (e più in generale,di qualunque tipo
di dato scambiato tra i partecipanti) e dunque ai protocolli utilizzati.
Schematizzando,si possono identificare i seguenti requisiti per l’infrastruttura di
comunicazione dei MCS.:
•
Consegna dei dati entro fissati limiti temporali (prevedibilità);
•
Tolleranza ai guasti di rete;
•
Scalabilità: degrado lineare delle prestazioni al crescere delle entità
comunicanti.
Ai requisiti sopra elencati va ovviamente aggiunto il requisito di consegna certa dei dati
inviati, senza il quale è impossibile definire un meccanismo di comunicazione come
affidabile.
1.2 Schemi per la realizzazione di una comunicazione affidabile
Il recupero dei messaggi da corruzione1 e/o perdita può essere raggiunto
sostanzialmente mediante due tecniche. Esse possono essere nella pratica declinate in
varie forme allo scopo di realizzare schemi flessibili ed adatti ai contesti specifici.
Tali tecniche sono[10]:
¾ ARQ – Automatic Repeat reQuest: (lett. “richiesta di ritrasmissione
automatica”) si basa sulla ritrasmissione dei pacchetti corrotti o mancanti
11
nel contesto considerato la corruzione del pacchetto provoca lo scarto dello stesso,dunque è equivalente alla perdita
15
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
attivata da un implicito o esplicito riscontro positivo o negativo (ACK
/NAK) inviato dai riceventi.
Figura 2 - Funzionamento di un tipico schema ARQ
Essendo le perdite spesso correlate possono esser necessarie più
ritrasmissioni per assicurare la consegna di un determinato pacchetto ad un
determinato receiver2. Tuttavia in media il numero di ritrasmissioni per ogni
pacchetto è 1/(1-p) con p pari al tasso di perdita dei pacchetti(PLR,packet
loss rate)[10].
Le tecniche ARQ sono di norma utilizzate in protocolli multicast per la
semplicità di implementazione e per la loro efficacia,pur presentando alcune
limitazioni quali:
•
necessità di un canale di ritorno,
•
latenza di recovery di un pacchetto perso dipendente dal RTT e dal
pattern di perdita dei pacchetti (e quindi dalla lunghezza dei bursts)
2
•
ridotta scalabilità
•
sender quale bottleneck della comunicazione
Se un pacchetto è andato perso potrebbe cioè capitare che anche alcune sue ritrasmissioni si perdano
16
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Gli schemi ARQ non godono di una buona scalabilità se utilizzati in
protocolli multicast .Infatti la probabilità di perdite incorrelate cresce con la
dimensione del gruppo multicast richiedendo la ritrasmissione della
maggioranza dei pacchetti[10] ,mentre l’invio continuato dei riscontri
(positivi) da parte dei singoli receiver può provocare un fenomeno noto in
letteratura come ACK implosion [9,11],in cui il sender è letteralmente
sommerso da messaggi di riscontro.
Inoltre la dipendenza della latenza di recovery dal RTT rende tali schemi
inadatti al loro utilizzo in contesti real time [10,11]. La dipendenza della
stessa dai patterns di perdita dei pacchetti,che sono in generale diversi per
ogni receiver,li rende inadatti anche all’utilizzo su canali con capacità di
banda limitata(o comunque in contesti in cui è da evitare lo spreco di
banda),in quanto essa provoca ritrasmissioni di pacchetti spesso non
necessari alla maggioranza dei receivers[17].
È chiaro inoltre che l’utilizzo di schemi ARQ in reti ad estensione geografica
comporterebbe un’elevata imprevedibilità della latenza di recovery:
•
in tali reti è infatti impossibile ottenere una stima precisa dell’RTT a
causa della variabilità della latenza di rete;
•
l’imprevedibilità dei patterns di perdita dei pacchetti non permette
invece di stimare con precisione le lunghezze dei bursts da cui
dipende direttamente la latenza dell’ARQ.
Tutto questo si traduce nell’impossibilità di offrire dei limiti superiori ed
inferiori alla latenza di recovery .
Gli schemi ARQ si rivelano pertanto sostanzialmente inadatti all’utilizzo in
MCS.
17
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
¾ FEC –Forward Error Correction: (lett.” Correzione degli errori in
avanti”)si basa sull’utilizzo di codici che permettono di ricostruire i pacchetti
persi tramite l’aggiunta di dati ridondanti .La comunicazione si arricchisce
dunque di una fase di codifica lato sender,con costruzione di pacchetti di
ridondanza da inviare insieme ai dati originari, e di una fase di decodifica
lato receiver,dove i dati vengono ricostruiti dai pacchetti ricevuti(cfr. figura
seguente).
Figura 3 - Funzionamento di uno schema FEC
Gli svantaggi di tali schemi sono sostanzialmente relativi all’aumento del
carico computazionale dovuto alla codifica/decodifica dei dati,che tuttavia
è
bilanciato
dalla
superiore
scalabilità
e
dalla
ridotta,nonché
maggiormente predicibile, latenza della fase di discovery e recovery
perdite rispetto a schemi di tipo ARQ. La maggiore scalabilità dipende dal
fatto che negli schemi FEC la fase di recupero è a carico dei destinatari. La
latenza di scoperta e recupero perdite si riduce perché non è più necessario
attendere una comunicazione dal destinatario al sender per ottenere il dato.
Inoltre essa diventa maggiormente predicibile in quanto la codifica rende i
18
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dati indipendenti dal pattern di perdita dei pacchetti: lo schema funziona
finchè le perdite sono in numero minore o uguale a quello massimo assunto.
Gli schemi FEC costituiscono pertanto una soluzione valida per garantire
l’affidabilità in protocolli di comunicazione multicast.
FEC si fonda su assunzioni di tipo statistico sul numero massimo di perdite itrodotte
dal canale pertanto nei casi in cui il numero di perdite reale sia maggiore di quello atteso,
meccanismi di FEC “puri” possono non garantire da soli la consegna certa dei
dati,rendendo necessaria talvolta l’introduzione di uno schema misto FEC+ARQ[10] per
rimediare con le ritrasmissioni ai casi in cui FEC fallisca.
Schemi FEC puri restano comunque una soluzione attraente in contesti applicativi in cui il
ritardo introdotto da soluzioni ARQ è inaccettabile oppure in cui ricontattare il sender per i
pacchetti persi è impossibile o da evitare [11].
La suddivisione in schemi ARQ e FEC costituisce una prima possibile classificazione
delle tecniche di affidabilità. È tuttavia possibile un’ulteriore suddivisione in due classi
[11] che distingue gli schemi in base alla responsabilità della reliability della
comunicazione :
•
Affidabilità basata sul sender (sender-based reliability)
•
Affidabilità basata sul receiver (receiver-based reliability)
19
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
1.2.1 Affidabilità basata sul sender
Negli schemi ad affidabilità basata sul sender è l’entità che trasmette in multicast a
dover assicurare la consegna certa dei dati.
Tali schemi possono essere sia basati su tecniche ARQ che FEC (oppure su approcci
ibridi) che possono a loro volta essere così classificati[9,11]:
•
ACK/timeout:in questo approccio i receivers inviano dei riscontri positivi
(ACKs) al sender quando ricevono un pacchetto entro un certo intervallo di
tempo( si rende quindi necessario l’utilizzo di timeout);è un meccanismo che
in comunicazioni multicast ad elevata frequenza di invio messaggi
porta,specialmente con un elevato numero di receivers,al già citato problema
dell’ ACK implosion. Una delle soluzioni proposte per aggirare il problema e
rendere lo schema parzialmente scalabile in contesti multicast è quello
dell’uso di ACK trees,cioè di aggregazioni gerarchiche di riscontri in modo
da ridurne il numero e dunque il carico sul sender.
Tale soluzione non è tuttavia utilizzabile in applicazioni ad elevata criticità
temporale in quanto una qualsiasi struttura gerarchica(quale è l’albero di
ACKs) introduce un ritardo spesso inaccettabile nel processo di scoperta dei
pacchetti persi [9,11].
Altro rimedio contro l’ACK implosion è l’utilizzo di riscontri negativi
(NAKs,cfr 1.2.2) che prevede la segnalazione da parte dei receivers dei soli
pacchetti mancanti,riducendo quindi drasticamente il numero di messaggi
complessivamente inviati al sender.
•
Sender-based FEC:è l’applicazione più immediata dello schema FEC: la
codifica è a carico del sender che genera un certo numero c di pacchetti di
ridondanza per ogni r pacchetti-dato.
20
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Tale schema gode di una certa flessibilità in quanto il numero di pacchetti
ridondanti può essere scelto in base alle esigenze specifiche. Sono possibili
soluzioni miste in cui ad un approccio FEC di base si affiancano schemi
ARQ per assicurare l’affidabilità anche in quelle situazioni in cui il solo FEC
non abbia consentito la ricostruzione del dato.
Nell’approccio sender-based l’efficienza temporale dello schema FEC
dipende fortemente dalla frequenza di invio del sender stesso e dal codice
usato per la protezione. Tale soluzione è comunque adatta soprattutto ad
applicazioni in cui è presente un unico sender che trasmette ad tasso elevato
e costante ad un singolo gruppo(in modo da poter scegliere in maniera
opportuna il numero di pacchetti ridondanti)[9,11].
In generale i meccanismi sender-based presentano alcuni svantaggi[11]:
•
in molti casi il sender sarà probabilmente impegnato ed una richiesta di
ritrasmissione potrebbe sovraccaricarlo;
•
il RTT introduce una latenza non necessaria nel processo di recupero dei
pacchetti (si potrebbero infatti recuperare i dati da altri receiver “vicini”
molto meno impegnati del sender;cfr.par.succ).
•
infine, il sender costituisce un single-point-of-failure per cui in assenza di
meccanismi di replicazione un crash del sender si traduce nella perdita
definitiva dei messaggi non ancora ricevuti.
1.2.2 Affidabilità basata sul receiver
In questi schemi la responsabilità della fase di scoperta delle perdite ed il loro
recupero è a carico dei receivers della comunicazione (si considera il caso di
comunicazioni multicast).
21
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Come nel caso di affidabilità basata sul sender è possibile realizzare sia schemi basati su
ARQ che su FEC [9]:
•
NAK/sender-based sequencing: il sender numera i messaggi multicast
inviati ad un certo gruppo ed i receivers scoprono eventuali perdite quando
arriva un messaggio successivo a quello atteso. Per effettuare il recovery
inviano un riscontro negativo (NAK) al sender stesso o ad altri receivers
ottenendo la ritrasmissione3(il NAK può essere inviato in unicast al sender o
in multicast all’intero gruppo[11]).
La latenza associata alla scoperta della perdita è dunque proporzionale al
tempo che intercorre tra due invii successivi da parte del sender al gruppo,e
dunque dipende anche in questo caso dal tasso di invio del sender stesso.
Approcci misti prevedono l’invio di pacchetti di ridondanza codificati con
tecniche FEC all’atto della ritrasmissione anziché dell’intero dato
originario(cfr. par.1.3.3).
•
Receiver-based FEC: tra gli schemi illustrati precedentemente ,quelli basati
su ACK sono intrinsecamente inadatti ad applicazioni multicast multisender
mentre quelli basati su NAK con sender sequencing e FEC sender-based
vincolano la latenza della scoperta delle perdite all’intervallo tra due invii
successivi. Idealmente,la latenza dovrebbe essere indipendente da tale
intervallo di tempo e si vorrebbe ottenere un meccanismo scalabile che però
non perda la flessibilità del FEC.Tale combinazione è fornita dagli schemi
FEC basati sui receivers: i receivers generano pacchetti FEC dai dati in
ingresso e li scambiano con altri receivers scelti casualmente. Poiché i
pacchetti codificati sono generati da dati in ingresso al receiver la latenza per
3
A rigore,il meccanismo NAK con sender sequencing si può considerare uno schema di affidabilità receiver-based nel
caso in cui siano i receivers ad effettuare le ritrasmissioni,cioè se l’onere della fase di recovery non è a carico del
sender.
22
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
il recupero delle perdite non dipenderà più dal tasso di invio del sender ma
dal tasso di invio dell’intero gruppo multicast[9],cioè dalla velocità con cui i
receivers scambiano informazioni tra loro,consentendo una maggiore
scalabilità rispetto al numero di sender per gruppo.
Gli schemi qui brevemente descritti costituiscono una classificazione comunque
grossolana delle alternative possibili ma consentono di inquadrare con più chiarezza le
soluzioni implementate nei protocolli multicast descritti nel seguito.
23
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
1.3 I protocolli multicast affidabili
La proliferazione di applicazioni che necessitano di una distribuzione affidabile di
dati ad un numero più o meno ampio di clients autonomi è stata la spinta principale allo
sviluppo di nuovi protocolli multicast e broadcast[10,13].
La varietà di tali applicazioni e le diverse condizioni in cui esse operano (reti,numero ed
eterogeneità dei componenti ,differenti requisiti temporali etc.)
hanno portato alla
progettazione,nel corso del decennio 1997-2007,di soluzioni più o meno valide in
determinati contesti applicativi.
Nel seguito si passano brevemente in rassegna le caratteristiche di alcuni di questi
protocolli che costituiscono lo stato dell’arte delle comunicazioni affidabili. Di essi si
analizzeranno i meccanismi di reliability (con riferimento alle classificazioni presentate
nel paragrafo 1.2) ,il funzionamento complessivo e le principali scelte implementative
operate dagli autori.
Si consideri comunque che tipicamente un protocollo multicast affidabile è strutturato in 3
fasi logiche [9]:
1. Trasmissione dei pacchetti
2. Scoperta dei pacchetti persi
3. Recupero dei pacchetti persi
1.3.1 RMDP:un semplice protocollo basato su FEC
Il Reliable Multicast data Distribution Protocol (RMDP) è il primo lavoro
innovativo nell’ambito dei protocolli multicast basati su tecniche FEC per assicurare
l’affidabilità[10].
24
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Esso si presenta come protocollo per la distribuzione di files in multicast in una varietà di
contesti (applicazioni operanti su LAN,applicazioni mobili/wireless).
L’approccio FEC è del tipo sender-based con utilizzo di Erasure Codes di tipo ReedSolomon(cfr. cap 2) e con un limitato utilizzo di NAKs(approccio ibrido). Le assunzioni
di base sono le seguenti:
•
La comunicazione avviene secondo un modello client-server
•
I dati da inviare hanno una dimensione nota e finita e sono suddivisi in L
pacchetti di dimensione s
•
I clients hanno differenti velocità di ricezione,subiscono perdite differenti ed
iniziano a ricevere pacchetti in momenti differenti
Il principio di funzionamento è semplice: i dati vengono codificati con un ‘elevata
ridondanza,utilizzando un (n,k)-codice (cfr.cap 2) con n>>k;la trasmissione dei dati inizia
all’atto della richiesta del primo client e continua con un tasso fisso finchè ci sono clients
attivi. In una prospettiva ideale k=L in modo che ,sfruttando le proprietà degli erasure
codes, basti ricevere k pacchetti qualsiasi per ricostruire il dato. Questo significa che le
perdite eventualmente occorse possono essere compensate semplicemente attendendo
l’arrivo di ulteriori pacchetti in modo da arrivare a k.
Il protocollo opera come segue:
1. Un client contatta il server richiedendo un file e specificando i parametri per
il trasferimento (tasso di invio dati,dimensione blocchi)
2. Il server risponde con un set di parametri da utilizzare per ottenere il file
richiesto:una session key,l’indirizzo utilizzato per inviare i pacchetti dato,la
dimensione del file ed altre informazioni utili per il client.
25
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3. Il server trasmette un numero sufficiente di pacchetti per consentire la
ricezione
del
file
anche
in
presenza
di
un
certo
numero
di
perdite(cioè,trasmette gli n pacchetti in cui sono stati codificati i k del dato)
4. Nel caso in cui il client rilevi un’interruzione nel flusso dei dati prima che la
ricezione sia completa,è inviata al sender una richiesta di ulteriori
pacchetti(continuation request,costituisce una sorta di NAK).
Le prime due fasi del protocollo possono essere ripetute se una richiesta va persa in quanto
sono entrambe idem potenti. L’ultima fase (che realizza in pratica un meccanismo ARQ
mediante NAKs) spesso non è necessaria o perché la ridondanza iniziale consente la
ricostruzione del dato oppure perché richieste parzialmente sovrapposte hanno provocato
una maggiore durata del tempo di trasmissione del dato richiesto.
Pur essendo il principio di funzionamento di RMDP molto semplice,gli autori sottolineano
come siano importanti,in ottica implementativa, i parametri caratterizzanti il protocollo e
di come si debba trovare un compromesso tra essi per costruire un’implementazione
efficiente.
Un primo parametro da dimensionare correttamente è la dimensione dei blocchi di
codifica k :in un’implementazione reale k non può essere eccessivamente grande in quanto
i tempi di codifica e decodifica rischiano di diventare eccessivi,tuttavia un valore elevato
di k migliora le prestazioni in termini di protezione dagli errori. Inoltre k non dovrebbe
essere fissato una volta per tutte ma dipendere dalla dimensione del file da inviare pur
essendo più efficiente uno schema con k costante
Una soluzione di compromesso proposta è la seguente:detta L la dimensione del file in
numero di pacchetti,fissato k ad un valore tale da garantire un overhead di
codifica/decodifica accettabile (“accettabile” secondo parametri che variano da contesto a
26
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
contesto) ,si suddivide il dato da inviare in B gruppi di k pacchetti ciascuno (con B= [L/k])
e poi si applica un (n,k)-codice ad ogni gruppo di k pacchetti. Infine,i gruppi vengono
trasmessi in maniera interlacciata,un pacchetto per gruppo alla volta,come mostrato nella
figura seguente:
Figura 4 -Distribuzione dei dati nei gruppi ed ordine di invio del sender (RMDP)
Questo adattamento rende il costo di codifica/decodifica indipendente dalla dimensione
del file anche se introduce una condizione di ricostruzione leggermente più stringente: è
necessario infatti ricevere non solo L differenti pacchetti ma essi devono includere almeno
k pacchetti per gruppo;inoltre l’efficienza di codifica è in qualche modo ridotta,essendo
pari ad 1 solo per k=L.
L’implementazione di RMDP presentata dagli autori [10] si presenta come
protocollo da utilizzare in aggiunta al multicast fornito da IP in reti wide-area per il
trasferimento di files di media dimensione senza particolari requisiti temporali. Tuttavia
nella fase iniziale del protocollo è possibile scegliere se utilizzare IP in unicast o in
multicast,sia per garantirne l’usabilità anche in reti dove il multicast IP non è
supportato,sia per consentire una superiore scalabilità del protocollo in contesti dove un
client è interessato a ricevere un file senza avere un server preferenziale.
Altro aspetto importante di RMDP è il limitatissimo utilizzo delle continuation
requests da parte dei clients,che costituiscono la componente ARQ del protocollo. Tali
messaggi vengono infatti utilizzati solo nel caso in cui una trasmissione sia interrotta. Il
27
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
limitato ricorso a tale meccanismo riduce sensibilmente il rischio di ACK implosion al
sender.
I limiti del protocollo RMDP sono da ricercarsi essenzialmente:
• nella totale assenza di un meccanismo di controllo della congestione di rete, che può
avere conseguenze drammatiche sulla perdita di pacchetti;
• nella scarsa efficienza del codice Reed-Solomon utilizzato,che ne limita le
performance in termini di codifica e decodifica di file di grosse dimensioni.
1.3.2 Digital Fountain: affidabilità sender-based mediante uso di Tornado Codes
Il protocollo presentato in questo paragrafo utilizza un approccio FEC sender-based
per assicurare la consegna certa dei dati[13].
Concepito per operare nel contesto della distribuzione in Internet di software e di
contenuti multimediali, sfrutta le potenzialità di una particolare classe di codici (Tornado
Codes,cfr. [13,15]) per risolvere problemi di overhead di codifica e decodifica (tipici dei
codici Reed-Solomon utilizzati anche in RMDP) ed ottenere buone prestazioni
complessive.
L’idea alla base è quella di realizzare una “fontana digitale” mediante uso di un
codice di protezione : i dati richiesti possono essere ricostruiti da un qualsiasi sottoinsieme
di pacchetti codificati che abbia una dimensione totale pari alla dimensione del file
richiesto.
Dal punto di vista strettamente matematico questo è possibile mediante utilizzo di Erasure
Codes (cfr.cap 2) che tuttavia consentono solo idealmente di realizzare tale astrazione.
28
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
I codici Reed-Solomon ,costituenti la classe standard di Erasure Codes,consentono infatti
di codificare i k pacchetti contenenti i dati originari su n pacchetti-codice,con la possibilità
di poter ricostruire i dati da un qualunque sottoinsieme di k pacchetti estratto dagli n totali.
Pur sembrando questa una strada percorribile per la realizzazione di una “fontana digitale”
non è ,dal punto di vista prestazionale, una soluzione valida: i codici Reed-Solomon
soffrono di elevato overhead di codifica/decodifica dovuto alla densità del sistema lineare
che definisce i codici stessi (cfr.par 2.2.2) ,overhead che diventa proibitivo anche per
valori moderati di k ed n.
La soluzione proposta in questo protocollo è dunque quella dell’approssimazione di
una fontana digitale mediante utilizzo di Tornado Codes,una particolare classe di codici
LDPC(cfr.par 2.2.3).
Dal punto di vista implementativo il protocollo si presenta come livello sovrapposto
al multicast IP. Per motivare questa scelta, gli autori sottolineano che l’obiettivo del
protocollo è quello di dimostrare che l’utilizzo dei codici permette di ottenere benefici in
sistemi reali (come appunto quello del multicast IP), non quello di realizzare un protocollo
multicast funzionalmente completo da distribuire.
Il protocollo aggiunge inoltre un controllo di congestione operato mediante layered
multicast( per approfondimenti cfr [15]) .Questo approccio consente la convivenza di
differenti gruppi multicast caratterizzati da diverse velocità di ricezione e si basa sulle due
seguenti idee,qui brevemente riportate:
• Il controllo di congestione avviene mediante Synchronization Points(SPs) che sono
pacchetti speciali del flusso dati. Un receiver può sottoscrivere un diverso layer
(cioè un diverso tasso di invio dati)solo subito dopo tali SP,ed ai receivers dei
livelli più bassi è consentito più spesso di sottoscrivere i livelli più alti;
• Invece di utilizzare sottoscrizioni esplicite il sender genera dei burst periodici in cui
trasmette a velocità doppia per ogni livello. In tal modo si simula in pratica un
29
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
sorta
di
congestione:
eventi,sperimentano
se
perdite
i
receivers,
di
mediante
pacchetti,allora
un
meccanismo
resteranno
al
ad
layer
corrente,altrimenti sottoscriveranno automaticamente il layer immediatamente
superiore (la sottoscrizione avviene comunque al successivo SP);
Altra fase fondamentale del protocollo è la ricostruzione dei dati da parte dei receivers,
che segue un approccio molto semplice:anziché iniziare operazioni di decodifica
preventiva ,che pure sarebbero parzialmente sovrapposte alla fase di ricezione dei
pacchetti seguenti, si preferisce attendere che arrivi il numero di pacchetti necessario alla
decodifica completa. Le operazioni preventive potrebbero infatti risultare inutili (i
pacchetti decodificati preventivamente potrebbero poi arrivare intatti).
Tale numero non è pari a k ma è leggermente superiore per via dell’inefficienza di
codifica(cfr. par.2.2.3). Nell’implementazione finale del protocollo presentata dagli autori
[13] è necessario attendere 1.055k pacchetti per decodificare il dato richiesto.
In esecuzione il protocollo utilizza due threads lato server:uno per gestire un canale UDP
unicast per l’invio di informazioni di controllo,l’altro per l’invio in multicast dei dati; i
clients sui receiver richiedono prima le informazioni al porto UDP (noto) ed alla ricezione
delle stesse effettuano la sottoscrizione al gruppo multicast appropriato.
Tale protocollo ha il pregio di mostrare come soluzioni FEC sender-based possano
comunque risultare valide in determinati contesti a patto di utilizzare codici che
garantiscano buone prestazioni in termini di codifica e decodifica.
1.3.3 EC-SRM:un approccio ibrido NAK + FEC
Uno dei primi protocolli multicast affidabili ad utilizzare tecniche FEC è stato
ECSRM [16].Tale protocollo è stato realizzato mediante FEC enhancement
del
preesistente protocollo affidabile SRM (Scalable Reliable Multicast).
30
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In questa sede si introdurranno solo gli aspetti principali del protocollo SRM,per
una descrizione più dettagliata cfr.[18].
SRM realizza un meccanismo di recovery di tipo ARQ receiver-based con utilizzo di
NAKs. SRM cerca però di ridurre il traffico dovuto alle fase di recovery mediante una
tecnica detta duplicate avoidance,illustrata nel seguito.
In SRM, tutti i receiver possono inviare un NAK in multicast all’intero gruppo multicast e
rispondere ad un NAK con una ritrasmissione in multicast del pacchetto perso. Prima di
trasmettere un NAK o effettuare una ritrasmissione, il sender resta in attesa per un certo
intervallo di tempo durante il quale può decidere di sopprimere la trasmissione prevista se
ne arriva una identica(cioè se arriva un NAK per lo stesso pacchetto o il pacchetto stesso
ritrasmesso). L’intervallo di attesa è una funzione randomizzata del round trip time (RTT)
misurato tra la sorgente del dato ed il sender del NAK(o della ritrasmissione).
Questo processo di soppressione delle ritrasmissioni e dei NAKs va sotto il nome di
duplicate avoidance (DA)[8].
Nonostante questo accorgimento SRM soffre comunque di[16]:
1. Ridotta scalabilità al crescere della dimensione del gruppo multicast
2. Mancanza di un meccanismo di controllo del traffico in ingresso ai nodi
La scarsa scalabilità dipende da vari fattori. SRM ha necessità di stimare il RTT per
applicare la DA e con n nodi nel gruppo sono necessari O(n2) messaggi[16]. Il calcolo
dell’intervallo di attesa della DA inoltre è puramente basato su tale stima dell’RTT e non
tiene conto della dimensione del gruppo. Se il gruppo cresce senza un corrispondente
aumento del tempo di attesa,prima o poi si verificherà una implosione dei messaggi
inviati[16]. Non è comunque possibile aumentare oltre un certo limite tale ritardo in quanto
influenza ovviamente la latenza della fase di recovery.
31
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
SRM non esegue alcun controllo sul traffico in ingresso ad un nodo. In un certo istante
alcuni nodi staranno inviando NAKs,altri ritrasmettendo pacchetti,altri ancora inviando
nuovi dati. Anche imponendo ad ogni sender dei limiti al tasso di invio di dati nuovi le
ritrasmissioni ed i NAKs possono condurre ad una quantità di traffico aggregato che
potrebbe non essere gestibile per qualche nodo[16].
EC-SRM (Erasure Correcting SRM) cerca di superare i limiti di SRM.
ECSRM mantiene la soppressione dei NAKs ed aggiunge una forma di controllo del
traffico,consentendo solo ai sender di effettuare le ritrasmissioni. Il tasso di invio
complessivo di ogni sender (comprensivo cioè di dati nuovi e ritrasmissioni) è limitato ad
un certo valore. Restano comunque i NAKs,ma grazie alla loro ridotta dimensione ed al
meccanismo di soppressione il loro impatto sul traffico è limitato[16].
Inoltre,essendo solo il sender ad effettuare ritrasmissioni ,rispetto ad SRM si elimina anche
il traffico necessario alla stima del RTT4 che influenzava pesantemente la scalabilità. Il
protocollo utilizza comunque un meccanismo di DA,impostando il ritardo di attesa in base a
due parametri i cui valori vanno specificati per ogni sessione multicast(cfr.[16]).
Un’altra modifica importante è dovuta chiaramente all’inserimento dei FEC. SRM
rispondeva ad un NAK con la ritrasmissione del pacchetto perso. ECSRM invece manda un
pacchetto di ridondanza generato tramite un opportuno (n,k)-codice (cfr.cap2).
In ECSRM i NAKs indicano il numero di pacchetti persi per ogni gruppo di trasmissione5
ed il sender invia tanti pacchetti di ridondanza quanti sono quelli segnalati dal NAK.
ECSRM opera la soppressione delle ritrasmissioni basandosi sul numero di pacchetti
persi all’interno di un gruppo. Potrebbe infatti capitare di ricevere più NAKs relativi allo
4
In SRM ogni nodo stima l’RTT verso gli altri nodi per poter dimensionare il tempo di attesa della DA per l’eventuale
ritrasmissione;in ECSRM è necessario solo un meccanismo di soppressione dei NAKs
5
Un gruppo di trasmissione (EC-group) in ECSRM è un gruppo di k pacchetti-dato sottoposti a codifica;i pacchetti
sono identificati nell’EC-group mediante un indice.
32
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
stesso gruppo di trasmissione a breve distanza di tempo . Senza alcun meccanismo
aggiuntivo questo comporterebbe l’invio di pacchetti di ridondanza già inviati poco prima.
In ECSRM si adotta allora il seguente approccio:
1. Il sender memorizza l’istante di invio degli ultimi k pacchetti dei gruppi di
trasmissione;
2. Quando il sender riceve un NAK che segnala m pacchetti persi per un certo
gruppo,controlla se l’invio degli ultimi m pacchetti di quel gruppo è avvenuto entro
la soglia di soppressione(cioè il tempo di attesa della DA);
3. Per ognuno dei pacchetti inviati entro la soglia,il sender decrementa di 1 il valore
m,ritrasmettendo poi un numero di pacchetti pari al valore residuo.
Supponiamo ad esempio arrivi al sender un NAK con m=3 al quale esso risponde
ritrasmettendo 3 pacchetti. Se entro la soglia di soppressione arriva un nuovo NAK con
m=5 il sender ritrasmetterà soltanto altri 2 pacchetti.
L’assunzione alla base è che il sender riceva NAKs solo per gruppi inviati per intero.
Sono tuttavia possibili scenari in cui un NAK arrivi prima che sia conclusa la trasmissione
dell’intero gruppo. In tal caso il sender attende per un breve periodo che arrivino almeno k
pacchetti al receiver che ha inviato il NAK. Se dopo tale periodo il gruppo non è ancora
completo,allora effettua la ritrasmissione dei pacchetti mancanti.
In conclusione,ECSRM è una modifica di SRM operata per incrementare la scalabilità. Il
principale accorgimento adottato a tal fine è l’invio di pacchetti ridondanti in risposta ai
NAKs. Questo provoca una riduzione del traffico di NAK e del traffico dovuto alle
ritrasmissioni.
Il primo diminuisce sia per il meccanismo di soppressione dei NAKs sia per la differente
natura dei NAK stessi. In SRM un NAK è relativo al singolo pacchetto di cui si richiede la
33
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
ritrasmissione,mentre in ECSRM un NAK è relativo al numero di pacchetti necessario per
raggiungere il valore k utile alla decodifica.
La seconda componente di traffico diminuisce per il meccanismo di soppressione
precedentemente analizzato. Anche in questo caso è l’aggiunta dello schema FEC ad essere
decisiva: ogni pacchetto ritrasmesso può infatti rimpiazzare un qualunque pacchetto perso.
Pur risolvendo molti problemi di SRM, ECSRM presenta alcuni limiti. Gli autori infatti
assumono che le applicazioni che utilizzano ECSRM possano permettersi un compromesso
tra latenza di recovery e scalabilità. I meccanismi con cui ECSRM raggiunge affidabilità e
scalabilità sono infatti affetti da una elevata latenza intrinseca. L’utilizzo di un ritardo per
garantire la soppressione di traffico di ritrasmissione è un limite spesso insuperabile in
contesti real-time e/o time-critical.
1.3.4 Slingshot:un esempio di affidabilità mediante receiver-based FEC
Il protocollo Slingshot [11] presenta un approccio innovativo nel contesto dei
protocolli affidabili basati su tecniche FEC. Esso propone per la prima volta uno schema
receiver-based con l’obiettivo di ridurre i tempi di recupero delle perdite.
Il contesto applicativo di riferimento per Slingshot è quello del trasferimento dati
nei moderni datacenters,costituiti da diverse migliaia di componenti soggetti a fallimenti
ed interconnessi da canali di comunicazione LAN e ad elevata banda trasmissiva. In tali
datacenters le applicazioni ad elevata criticità temporale convivono con applicazioni con
requisiti di consegna meno stringenti, e quindi protocolli real-time si affiancano a
protocolli meno soggetti a vincoli temporali.
34
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
I protocolli real-time tuttavia,pur garantendo la consegna certa in presenza del numero
massimo di fallimenti previsti, per raggiungere tale obiettivo rallentano la consegna nel
caso medio (cfr.[13]).
L’obiettivo degli autori di Slingshot è dunque quello di realizzare un protocollo multicast
che,in una prima fase, consegni la maggior parte dei dati molto velocemente,offrendo
delle prestazioni che peggiorano gradatamente al crescere del numero dei fallimenti
incontrati ed offrendo ,in una seconda fase, dei meccanismi opzionali di recupero dei dati
mancanti con una latenza superiore a quella sperimentata nella prima fase.
L’idea di base per assicurare la protezione dei dati dai fallimenti è quella di ricorrere ad un
approccio FEC basato sui receivers: i dati ricevuti dai receivers di un certo gruppo
multicast vengono codificati in pacchetti FEC e successivamente scambiati tra i receivers
stessi per ricostruire i pacchetti mancanti.
In pratica le due fasi del protocollo si possono brevemente descrivere come segue:
1. I dati sono inviati inizialmente mediante un servizio multicast best-effort (es.
multicast IP).
2. I receivers effettuano delle comunicazioni unicast per scambiare i pacchetti
FEC da essi stessi costruiti a partire dai dati ricevuti e ricostruiscono i dati
mancanti mediante i pacchetti FEC ottenuti dagli altri receivers.
La seconda fase si compone a sua volta di due sottofasi:
I.
I receivers costruiscono e scambiano velocemente tra loro i pacchetti
FEC,realizzando una rapida scoperta dei pacchetti mancanti ed il recupero
della maggior parte di essi.
35
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
II.
I receivers opzionalmente inviano esplicite richieste ad altri receivers per
ottenere i pacchetti mancanti effettuando un recupero completo dei dati
mancanti.
Le due sottofasi sono evidenziate in grigio nella figura seguente.
Figura 5 - Funzionamento di Slingshot
(NB: q ed r sono receivers,p è sia sender che receiver: Slingshot è infatti concepito
come algoritmo distribuito simmetrico,per cui il sender opera anche da receiver,inviando i
dati in multicast anche a sé stesso e partecipando poi alla fase di recupero dalle perdite).
Dal punto di vista implementativo, Slingshot utilizza due tipi di pacchetti, data
packets contenenti i dati inviati in multicast ed identificati da un ID del tipo
(sender,numero di sequenza),e repair packets contenenti informazioni utili al recupero dei
dati mancanti.
36
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Nella sottofase I i receivers generano un repair packet ogni r data packets ricevuti
in multicast e lo inviano in unicast a c receivers selezionati casualmente. Slingshot utilizza
la forma più semplice e veloce di FEC,cioè le funzioni XOR binarie,che consentono ad un
singolo repair packet di permettere la decofica di diversi data packets.
Per facilitare il recupero dei data packets a partire dai repair packets ogni nodo che esegue
Slingshot utilizza un buffer dati dove conserva i data packets:
all’atto della ricezione di un repair packet il nodo controlla se esso è utile alla decodifica
dei data packets che non ha ancora ricevuto;se solo uno di questi pacchetti non ricevuti è
decodificabile grazie al repair packet appena ricevuto,il nodo recupera dal buffer gli altri
r-1 data packets che hanno contribuito alla costruzione del repair packet in questione e
combinandoli con le XOR contenute in tale pacchetto opera la ricostruzione del pacchetto
mancante.
La natura probabilistica della sottofase I ha come conseguenza una percentuale di
pacchetti persi non recuperati. Un nodo può quindi scegliere se attendere ulteriormente
l’arrivo di altri pacchetti di riparazione oppure far partire la sottofase II di richiesta
esplicita dei pacchetti mancanti.
Per la sottofase II le realizzazioni possibili sono due: si può inviare la richiesta esplicita a
qualche receivers arbitrario oppure al sender ,che deve dunque gestire un buffer dei
pacchetti inviati.
Slingshot è in pratica un protocollo configurabile che può operare sia garantendo
una consegna certa di tutti i pacchetti( a prezzo di un degrado prestazionale imposto dalla
fase di recupero esplicito)sia come protocollo real-time con garanzie di consegna offerte
su base probabilistica.
37
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
1.3.5 Ricochet: la Lateral Error Correction
Ricochet [9] è un protocollo multicast affidabile a bassa latenza concepito per
applicazioni time-critical distribuite operanti su clusters.
I protocolli di reliable multicast esistenti,che costituiscono il meccanismo di
comunicazione principale in tali contesti, non offrono adeguate prestazioni in termini di
scalabilità e criticità temporale ed è dunque obiettivo degli autori di Ricochet realizzare un
protocollo che ,pur offrendo adeguate garanzie in termini di celerità di consegna, fornisca
anche scalabilità al crescere dei gruppi di comunicazione multicast( ovvero ,in situazioni
multisender e multigroup).
Ricochet utilizza un innovativo schema di FEC receiver-based che va sotto il nome di
LEC (Lateral Error Correction) .Tale schema sfrutta la sovrapposizione parziale di
diversi gruppi di comunicazione multicast per rendere i tempi di latenza della fase di
recupero perdite indipendenti dalla velocità di trasmissione del particolare gruppo.
L’utilizzo di FEC lato receiver non è un’idea nuova (cfr.Slingshot ,par.prec),tuttavia è
nuova l’idea di sfruttare la presenza di più gruppi di comunicazione per incrementarne le
prestazioni.
Le caratteristiche principali Ricochet si possono riassumere nei seguenti punti:
• In Ricochet ogni nodo appartiene a più gruppi multicast e riceve dati da tutti i
gruppi;
• Ricochet utilizza due tipi di pacchetti,data packets e repair packets (come già visto
in Slingshot,cfr. par. prec.),i primi contenenti i dati effettivi ed i secondi la
ridondanza di codifica;
• Ricochet utilizza come operazione di codifica la XOR binaria dei data packets
ricevuti da un nodo (anche questo è già visto in Slingshot:la differenza è che in
38
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Ricochet i pacchetti che vanno a comporre il repair packets possono essere
associati a differenti gruppi multicast,cfr.nel seguito).
La seguente immagine mostra la struttura dei pacchetti utilizzati da Ricochet:
Figura 6 - Strutttura pacchetti Ricochet
La differenza principale tra la tecnica LEC ed una normale tecnica FEC receiver-based sta
nella costruzione del repair packet:
• come già visto in Slingshot,un repair packet è costruito dalla XOR di r data
packets(di cui contiene gli IDs) e rende possibile la ricostruzione di un data packet
mancante al receiver se esso ha già a disposizione gli altri r-1 data packets inclusi
nel repair packet.Tale pacchetto è inviato a c destinatari selezionati casualmente.
• Il principio operativo alla base della LEC(nonché differenza fondamentale rispetto
alle tecniche già viste) è che un repair packet inviato da un nodo ad un altro può
essere costruito a partire dai dati inviati a qualunque gruppo multicast in comune
tra i due nodi.
39
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Questo permette di velocizzare la fase di recupero dei pacchetti persi in quanto non si è
più vincolati al tasso di invio verso il singolo gruppo multicast.
Dati ad esempio due gruppi A e B costituiti dai nodi n1,n2,n3,n4 (situazione rappresentata
nella figura seguente)
Figura 7 - LEC in 2 gruppi multicast
con i nodi n1 ed n2 appartenenti ad entrambi i gruppi,è chiaro ,per quanto detto, che
ognuno di essi potrà inviare all’altro repair packets composti dai dati provienti sia da A
che da B,indifferentemente.Detto ad esempio r=5 ,n1 dovrà attendere solo 5 pacchetti in
totale (indirizzati ad A o a B) prima di costruire il pacchetto da inviare ad n2.
40
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il seguente schema permette di comprendere come questa soluzione consenta un recupero
più veloce dalle perdite rispetto all’approccio basato sul singolo gruppo:
Figura 8 - LEC(a destra) vs FEC receiver-based in singolo gruppo
A parità di data packets ricevuti (identificati in figura da A1,A2… B1,B2… etc) n1
riesce a costruire con molto anticipo un repair packet da inviare ad n2,che può così iniziare
il recupero dei dati molto prima che nel caso di FEC receiver-based in un singolo gruppo.
Dal punto di vista algoritmico Ricochet si presenta come algoritmo simmetrico
distribuito(cioè il medesimo algoritmo è eseguito in contemporanea da tutti i nodi)e si
può quindi analizzare il suo comportamento dal punto di vista di un singolo nodo,nel
seguito indicato con n1.
La prima operazione che lo schema LEC prevede è la suddivisione dei vicini di n1 (un
vicino di n1 è un nodo appartenente ad almeno uno dei gruppi di cui fa parte anche n1) in
41
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
regioni 6,utilizzando poi queste informazioni per la costruzione e distribuzione dei repair
packets .
Nell’esempio rappresentato nella figura seguente, n1 appartiene ai gruppi A,B e C e ne
consegue la suddivisione nelle regioni abc,ab,bc,a,b e c (il gruppo D è ignorato da n1).
Figura 9 - n1 appartiene ad A,B e C ;le regioni individuate sono abc,ab,ac,bc,a,b,c
Le uniche regioni di interesse sono quelle derivanti dalle intersezioni non vuote (questo
limita il numero massimo di regioni individuabili al numero di nodi presenti nel sistema).
All’atto dell’invio di un repair packet lo schema LEC prevede la selezione casuale dei
destinatari non dall’intero gruppo ,ma da ogni regione, in modo che:
1. Il numero di destinatari selezionati da una singola regione sia proporzionale alla
dimensione di tale regione;
2. Il numero totale di destinatari selezionati tra tutte le regioni sia pari al numero c di
destinatari previsti per quel gruppo.
Per un dato gruppo A caratterizzato da un numero totale di destinatari cA il numero di
destinatari selezionati da una certa regione di A sarà pari a cA *|x|/|A|, con |x| pari al
numero di nodi nella regione in questione ed |A| pari al numero totale di nodi nel gruppo.
6
le regioni non sono altro che le intersezioni disgiunte dei gruppi a cui appartiene n1
42
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La seguente immagine mostra la selezione dei destinatari per l’invio di un repair packet
verso il gruppo A:
Figura 10 - selezione dei destinatari dalle regioni di A
(NB: cAx indica il numero di destinatari selezionati per la regione x)
La selezione dei destinatari dalle regioni piuttosto che dai gruppi permette di costruire i
repair packets a partire dai dati di più gruppi multicast: poiché il nodo n1 sa che i nodi
della regione ab ricevono dati sia per il gruppo A che per il gruppo B,ad essi potrà inviare
repair packets composti di dati inviati verso i due gruppi.
La LEC è una declinazione innovativa delle tecniche FEC receiver-based ma è necessario
settare opportunamente i parametri caratterizzanti il meccanismo ( r e c principalmente)
per ottenere prestazioni adeguate ai requisiti richiesti dall’applicazione in termini di
percentuale di recupero pacchetti persi e di overhead computazionale. Come osservato
43
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
sperimentalmente dagli autori di Ricochet, al crescere di c (numero di destinatari repair
packets) per r fissato cresce la percentuale di recupero (tendendo al 100%) ma cresce
corrispondentemente l’overhead computazionale al nodo.
Il meccanismo LEC da solo non consente un recupero totale delle perdite per via della sua
natura probabilistica (analogamente a quanto visto per gli schemi receiver-based in un
singolo gruppo,cfr.par .prec.) e gli autori hanno dunque previsto un layer aggiuntivo al
protocollo di base che implementa un meccanismo ARQ con riscontri negativi (NAKs).
Così come visto in Slingshot[11], se dopo la fase di recupero LEC qualche pacchetto
risultasse ancora mancante ,è possibile richiedere esplicitamente la ritrasmissione di tali
pacchetti al sender.
Questo meccanismo NAK ha il pregio di non allungare eccessivamente i tempi di
recupero: la scoperta delle perdite avviene quasi per intero nella fase LEC,pertanto il
ritardo tipico degli meccanismi ARQ “classici”(dovuto soprattutto alla latenza della
scoperta) non è qui presente.
Tale layer aggiuntivo è inoltre utilizzato opzionalmente (così come già visto in Slinghot)in
quanto le applicazioni che utilizzano il protocollo possono anche ritenere sufficienti le
garanzie (espresse in termini probabilistici) offerte dallo schema LEC di base.
In definitiva il protocollo Ricochet raggiunge l’affidabilità con uno schema FEC
innovativo che migliora le prestazioni in fase di rilevazione e recupero delle perdite
Tuttavia il recupero completo è garantito al 100% solo con un layer NAK aggiuntivo.
È inoltre necessario settare opportunamente i parametri della LEC per non incorrere in un
eccessivo overhead.
44
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Capitolo 2
Tecniche di affidabilità basate su Erasure Codes in piattaforme
DDS
2.1 Introduzione
Nella prima parte di questo capitolo sarà presentata una classe di codici correttori
d’errore, detti Erasure Codes, particolarmente adatti al recupero dei dati persi per
cancellazione. Di essi si analizzeranno i principi di funzionamento e le caratteristiche
principali delle due famiglie di codici più diffuse
La trattazione qui presentata degli Erasure Codes ha il solo scopo di fornire gli
elementi utili a comprendere i risvolti pratici derivanti dall’utilizzo di tali codici nel
contesto delle comunicazioni affidabili.. Tale trattazione non ha dunque pretese di rigore
matematico e non esaurisce la tematica.
Approcci più rigorosi possono essere reperiti in [19][20] dove gli Erasure Codes vengono
presentati nel contesto della Teoria dei Codici.
Nella seconda parte del capitolo sarà introdotto uno schema di comunicazione affidabile
per middleware DDS basato su tali codici. Dopo una breve introduzione degli aspetti
fondamentali dello standard OMG, saranno analizzati i vantaggi e gli svantaggi derivanti
45
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dall’utilizzo del DDS nel contesto dei MCS e, successivamente, le considerazioni da cui è
scaturita l’idea di utilizzare gli EC per realizzare un meccanismo alternativo di recupero
dei dati persi.
2.2 Gli Erasure Codes
Gli Erasure Codes - EC nel seguito - offrono un sistema di protezione dei dati dalle
cancellazioni7 (da cui l’Erasure del nome). Secondo la classificazione presentata nel
capitolo 1 essi si inseriscono dunque nell’insieme delle tecniche FEC.
Gli EC sono stati tuttavia già stati utilizzati con successo in una varietà di contesti,quali
sistemi RAID fault-tolerant, sistemi di storage distribuiti,applicazioni peer-to-peer e
distribuzione di contenuti multimediali[23][24][13].
Allo stato attuale le famiglie di EC più utilizzate sono :
1. Codici di Reed-Solomon
2. Low Density Parity Check (LDPC) Codes (lett.”codici a controllo di parità a bassa
densità”).
Esse presentano differenti modalità di costruzione dei codici e differenti caratteristiche
prestazionali,pur operando secondo gli stessi meccanismi fondamentali.
Dopo aver introdotto i concetti alla base del funzionamento degli EC si analizzeranno le
caratteristiche specifiche delle due famiglie suddette .
7
Nel contesto delle telecomunicazioni , si definisce cancellazione la perdita di un pacchetto causata dal comportamento
fallimentare di componenti di rete o dalla congestione della rete stessa.
46
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
2.2.1 Concetti di base
L’idea alla base degli Erasure Codes è quella di codificare k blocchi8 di dati sorgenti
generando n blocchi di dati codificati9, in modo che sia possibile ricostruire i dati sorgenti
a partire da un qualunque sottoinsieme di blocchi di cardinalità k [22].
Un codice che presenta tali caratteristiche prende il nome di (n,k)-codice[19] e permette di
ricostruire i dati sorgente nell’ipotesi in cui siano avvenute al massimo n-k cancellazioni in
un gruppo di n blocchi codificati.
Il rapporto k/n prende il nome di code rate e rappresenta una misura dell’efficienza
del codice.
La seguente figura[22] schematizza il processo di codifica/decodifica negli (n,k)-codici:
Figura 11 - Rappresentazione grafica del processo di codifica/decodifica FEC
Esempi notevoli sono costituiti da[19][21] :
• Codici a ripetizione:cioè (n,1)-codici,in cui il dato sorgente viene semplicemente
ripetuto n volte;permettono di recuperare fino ad n-1 perdite ma soffrono di scarsa
efficienza.
8
9
Un blocco è qui inteso come un insieme di bit di dati sorgente
n>k
47
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
• Codici a controllo di parità: cioè (k+1,k)-codici,in cui c’è un solo blocco di
ridondanza calcolato come somma10 dei
k
blocchi sorgenti;permettono di
recuperare una sola perdita ma hanno un elevato code rate;
I due semplici codici appena presentati sembrano essere stati costruiti senza
particolari basi teoriche. Tuttavia è facilmente dimostrabile che essi esibiscono il
comportamento atteso[21].Per costruire codici con valori arbitrari di n e k è però
necessario un approccio più sistematico.
Da questo punto di vista un’interessante classe di EC è la classe degli EC lineari che
possono essere analizzati tramite le proprietà dell’algebra lineare.
Detto x=x0…xk-1 il vettore dei blocchi dato e detta G una matrice nxk tale che ogni sua
sottomatrice G’ di dimensioni kxk risulti invertibile, un (n,k)-codice lineare si può
rappresentare come:
y=Gx
Un codice lineare può cioè essere assegnato nella forma di un sistema di equazioni lineari.
Se al receiver giungono almeno k componenti del vettore y ,i dati sorgenti possono essere
ricostruiti usando le k equazioni corrispondenti alle componenti note di y. Detta G’ la
matrice kxk rappresentativa di tali equazioni ,è possibile ricostruire i dati risolvendo il
sistema:
y’=G’x
→
x=G’-1y
10
La somma può essere definita in diversi modi a seconda di quale sia l’insieme dei simboli rappresentati dai
blocchi;può essere una semplice XOR binaria così come una somma su un particolare campo.
48
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Nel caso in cui la matrice G includa una matrice identità di ordine k ,il codice risultante
sarà un codice sistematico . Un codice sistematico permette una decodifica veloce dei dati
in quanto inserisce una copia dei dati non codificati accanto ai blocchi di codifica[19][21].
Il processo di codifica e decodifica si può ora rappresentare anche in forma matriciale:
Figura 12 - Rappresentazione matriciale di codifica e decodifica per un codice
sistematico (y' e G' sono identificati dalle aree in grigio sulla destra)
I codici Reed-Solomon ed i codici LDPC appartengono alla classe degli EC lineari e
molte delle loro caratteristiche (e differenze) dipendono da quelle dei sistemi di equazioni
lineari che li definiscono.
49
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
2.2.2 Codici Reed-Solomon
I codici di Reed-Solomon costituiscono la classe di EC canonici. Essi prendono il
nome dai due studiosi che nel 1960 pensarono ad una efficiente tecnica di codificadecodifica per una classe di codici lineari a blocco. I codici RS sono stati utilizzati già da
tempo per realizzare meccanismi di fault-tolerance in una varietà di contesti,quali sistemi
RAID,file systems distribuiti,p2p etc.[23][26][38].
Dal punto di vista algebrico, i codici Reed-Solomon operano sugli elementi del
campo finito esteso di Galois GF(2L). I blocchi sono cioè rappresentati come interi in
[0,…,2 L-1], quindi il generico elemento è composto da L bit di informazione[19][20][26].
La codifica avviene in due fasi:
1. I blocchi dato sono partizionati in words di dimensione fissata L ed un
insieme di k words forma un vettore.
2. Gli m blocchi di codifica vengono generati mediante prodotto11 tabulare tra il
vettore di blocchi dato ed una matrice di distribuzione B .Complessivamente
saranno trasmessi n=k+m blocchi.
La fase di decodifica è concettualmente semplice:
1. dati almeno k blocchi di codifica si deriva da essi una matrice di decodifica
B’ analogamente a quanto visto nel paragrafo precedente;
2. si effettua l’inversione di tale matrice e si esegue il prodotto tabulare tra la
matrice invertita ed il vettore dei k blocchi ricevuti.
11
Il prodotto è eseguito in GF(2L)
50
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La seguente immagine riassume il processo di codifica/decodifica sopra descritto:
Figura 13 - Il processo di codifica (in alto) e le due fasi di decodifica (in basso)
dei codici Reed-Solomon
La codifica/decodifica nei codici RS risulta essere particolarmente onerosa per una
varietà di ragioni[24]:
1. il calcolo degli m blocchi di codifica richiede m prodotti che coinvolgono un
vettore di k elementi. Con dimensioni dei blocchi pari ad L la complessità di
tale operazione risulta pari a O(Lmk).
2. La decodifica include una inversione di una matrice di ordine k,cioè
un’operazione di complessità O(k3) .
3. La decodifica prevede ,per ogni blocco da decodificare, anche un prodotto
tabulare tra la matrice di decodifica ed il vettore dei k blocchi ricevuti. Tale
operazione ha una complessità pari a O(k2L).
4. I prodotti sono eseguiti in GF(2L) e sono molto più dispendiosi rispetto ai
prodotti tra semplici interi.
51
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Per queste ragioni, i codici RS si utilizzano in applicazioni in cui i valori di k ed m restano
relativamente bassi ed in cui anche la dimensione L dei blocchi stessi è contenuta.
Al crescere di tali parametri, infatti, i tempi di codifica/decodifica dei dati possono
diventare insostenibili e si pone pertanto la necessità di trovare un’alternativa valida ai
codici RS nelle situazioni in cui essi non sono utilizzabili.
Esistono comunque decoder ad alte prestazioni per codici RS basati su architetture VLSI
ed algoritmi specifici [38].
2.2.3 Codici LDPC
I codici LDPC (Low Density Parity Check) [27][28] costituiscono un’importante
alternativa ai codici RS. I LDPC Codes sono codici lineari caratterizzati da una matrice
generatrice con pochi elementi non nulli rispetto al numero di elementi nulli (da qui il
nome). Grazie a tale caratteristica per essi è possibile realizzare schemi di decodifica che
non necessitano di costose operazioni matriciali (decodifica iterativa).
I LDPC furono introdotti da Gallagher nel 1960 nella sua tesi di dottorato. Tuttavia,
a causa della difficoltà dell’epoca nell’implementare un codificatore efficiente e della
successiva introduzione dei codici RS, essi sono stati ignorati fino alla metà degli anni ’90.
Le differenze principali tra i LDPC e i codici Reed-Solomon sono le seguenti[13]:
•
I Reed-Solomon operano mediante l’algebra dei campi finiti mentre i LDPC
utilizzano semplici XOR (OR esclusivo) binari;
•
I Reed-Solomon sono caratterizzati da un sistema di equazioni denso mentre
le equazioni dei LDPC sono costruite con un numero di variabili di solito
molto piccolo dando luogo ad un sistema sparso;
•
L’efficienza di decodifica dei LDPC è leggermente inferiore rispetto a quella
dei Reed-Solomon, essendo necessari (1+ε) k pacchetti per ricostruire un
52
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dato originariamente suddiviso in k pacchetti (ε maggiore di zero e di solito
dipendente dal pattern di perdita dei pacchetti e dalle scelte operate per la
costruzione delle equazioni).
I codici LDPC possono essere rappresentati in due modi:
1. In forma matriciale (perché codici lineari).
2. Su grafo bipartito.
Le due rappresentazioni sono equivalenti dal punto di vista algebrico, in quanto
rappresentative dello stesso sistema di equazioni lineari. Tuttavia i grafi bipartiti aiutano a
comprendere meglio sia il grado di densità sia il processo di decodifica iterativa.
Nella rappresentazione su grafo bipartito i nodi dato costituiscono l’insieme dei nodi a
sinistra mentre i nodi per il controllo di parità sono sulla destra12.
Gli archi che connettono i due sottoinsiemi di nodi rappresentano operazioni di XOR
binario (cfr. FIG seguente).
Figura 14 - Grafo bipartito per codice LDPC con k=4 e m=3.
(il simbolo + indica la XOR binaria)
12
In questa sede si prendono in considerazione LDPC binari,per cui ogni nodo rappresenta un bit-dato o un bit di parità.
53
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La densità del codice può dunque essere valutata dal numero complessivo di archi del
grafo.
Un’ulteriore rappresentazione su grafo si ricava dalla precedente ponendo nodi dato e nodi
di parità sulla sinistra e ricavando i vincoli sulla destra. Un grafo di questo tipo prende il
nome di Grafo di Tanner.
Figura 15 - Rappresentazione LDPC su grafo di Tanner.
I grafi di Tanner permettono di analizzare il processo di decodifica e comprendere
perché per i LDPC Codes possano essere necessari più di k blocchi per effettuare la
decodifica completa.
Per comprendere il meccanismo di decodifica è utile un esempio completo. Con
riferimento al codice rappresentato nel grafo di Tanner della figura precedente:
1. i vincoli sono posti a zero;
2. ricevuto il bit #2 con valore 1;calcolo del nuovo valore dei vincoli ;
3. ricevuto il bit #7 con valore 1;calcolo del nuovo valore dei vincoli;
4. ricevuto il bit #4 con valore 0;calcolo del nuovo valore dei vincoli;
5. calcolo del bit #3 dal vincolo #3; il valore è 0;
6. ricevuto il bit #5 con valore 1;calcolo del nuovo valore dei vincoli;
54
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
7. calcolo del bit #1 dal vincolo 1;il valore è 1;
8. infine,calcolo del bit #6 a valore 0;
Graficamente :
1
2
3
4
5
6
7
8
Figura 14: Esempio di decodifica LDPC su grafo di Tanner
55
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Nell’esempio appena presentato la decodifica completa risulta possibile dopo la
ricezione di k=4 bit (al passo 7 i nodi dato sono infatti tutti noti),così come avviene nei
codici RS. Tuttavia si è sottolineato come in generale per i LDPC Codes siano necessari
più di k blocchi codice per effettuare la decodifica completa.
Non è detto infatti che i k elementi ricevuti permettano di risolvere le equazioni da cui
dipendono i nodi dato.
Una situazione di questo tipo è visualizzata in figura:
Figura 16:LDP - decodifica impossibile con k bit
Il codice rappresentato è strutturato in maniera tale che ricevuti i bit 1,5,6 e 7 non sia
possibile risolvere alcuna equazione vincolare. Non è possibile in definitiva effettuare la
decodifica con k elementi ed è necessario attendere un ulteriore blocco.
Nonostante questa piccola inefficienza di codifica ,i codici LDPC costituiscono
un’alternativa importante ai codici RS nelle situazioni in cui i RS non forniscano
prestazioni adeguate.
Come tuttavia evidenziato in [24], in termini di codifica/decodifica i LDPC offrono
prestazioni sensibilmente migliori rispetto ai RS soltanto quando k ed m assumono valori
nell’ordine di 102. La scelta tra LDPC e RS dipende quindi dalle necessità specifiche.
56
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La classe di LDPC che offre le migliori prestazioni complessive è quella dei Tornado
Codes. Tali codici sono strutturati in maniera tale che l’arrivo di un singolo blocco
inneschi la risoluzione di un elevato numero di equazioni (da qui il Tornado del nome).
I Tornado Codes,introdotti nel 1997 [15], offrono le migliori prestazioni complessive in
termini di codifica/decodifica, arrivando ad essere anche 10,000 volte più veloci dei codici
RS per dati di grosse dimensioni.
L’utilizzo dei Tornado Codes è tuttavia vincolato alle concessioni degli autori che ne
detengono il brevetto.
2.3 I middleware di tipo publish/subscribe e l’OMG Data Distribution Service
Dopo un’introduzione degli aspetti fondamentali dei middleware di tipo
publish/subscribe ed in particolare del DDS, si analizzano i problemi derivanti
dall’utilizzo di tali middleware nel contesto dei MCS considerato e, successivamente, si
propone l’idea per uno schema di affidabilità alternativo basato su EC.
Come accennato in precedenza, gli EC sono normalmente utilizzati per garantire
protezione da cancellazioni dei dati in diversi contesti. In questo paragrafo sarà presentato
invece un uso alternativo degli EC nel contesto delle tecniche FEC per la comunicazione
affidabile.
2.3.1 Il modello di comunicazione publish/subscribe
Il modello di comunicazione publish/subscribe [29][30][40] sta ricevendo negli
ultimi anni un’attenzione crescente da parte degli sviluppatori in quanto gode di proprietà
che facilitano la realizzazione di applicazioni dinamiche e distribuite su larga scala.
57
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
I componenti principali di un sistema basato sul modello publish/subscibe sono:
¾ il publisher: è il “produttore” dei messaggi di comunicazione
¾ il subscriber: riceve i messaggi a cui è interessato, comunicando il suo
interesse mediante sottoscrizioni;
¾ Un Event Service : il modello di comunicazione publish/subscribe è ad
eventi e l’Event Service è l’intermediario tra le parti.
Il publisher invia messaggi (in questo modello dette pubblicazioni) all’event service mentre
il subscriber comunica il suo interesse ad una determinata categoria di messaggi mediante
un meccanismo di sottoscrizione. Quando un messaggio risulta disponibile presso l’event
service, esso informa i subscribers interessati a quel particolare tipo di messaggio mediante
notifiche.
La seguente immagine schematizza l’interazione tra le parti :
Figura 17 Interazione in un sistema Publish/Subscribe
58
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il modello publish/subscribe offre dunque uno schema di interazione asincrono con
un elevato grado di disaccoppiamento tra le parti. La potenza dei sistemi basati su tale
modello risiede proprio nelle tre forme di disaccoppiamento che esso introduce[30]:
¾ Disaccoppiamento nello spazio
¾ Disaccoppiamento nel tempo
¾ Disaccoppiamento nella sincronizzazione
Le tre forme di disaccoppiamento sono schematizzate in figura:
Figura 18 - Forme di disaccoppiamento tra le parti nel modello publish/subscribe
Analizziamo nel dettaglio ciascuna di esse:
• Disaccoppiamento nello spazio: le parti della comunicazione non hanno bisogno di
conoscersi in quanto l’interazione avviene solo tramite l’event service. Il publisher
59
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
non ha riferimenti dei subscribers e non ha informazioni sul numero di subscribers
coinvolti nella comunicazione. Il subscriber, allo stesso modo, non ha alcun
riferimento del publisher e non sa quanti pusblisher stiano intervenendo nella
comunicazione. In altre parole, il modello publish/subscribe è intrinsecamente
basato su uno schema di comunicazione di tipo molti-a-molti.
• Disaccoppiamento nel tempo: le entità interagenti non devono necessariamente
partecipare attivamente alla comunicazione negli stessi istanti di tempo. In
particolare, il publisher potrebbe effettuare qualche pubblicazione mentre il
subscriber è disconnesso oppure, viceversa, il subscriber potrebbe ricevere una
notifica circa l’avvenuta pubblicazione di un evento di interesse mentre il publisher
che l’ha pubblicata non è più attivo.
• . Disaccoppiamento della sincronizzazione: i flussi di esecuzione delle parti sono
disaccoppiati. I publishers non sono bloccati dopo l’invio di una pubblicazione ed i
subscribers ricevono le notifiche in maniera asincrona mediante una callback
mentre stanno effettuando altre elaborazioni. In effetti la produzione e la ricezione
dei messaggi non avvengono nel flusso di controllo principale di publisher e
subscriber, e pertanto non sono eventi sincroni.
Disaccoppiare la produzione e l’utilizzo delle informazioni introduce un elevata
scalabilità in quanto le dipendenze esplicite tra le entità partecipanti sono rimosse.
Rimuovere tali dipendenze riduce la necessità di coordinazione e sincronizzazione tra le
parti, e rende i
sistemi publish/subscribe l’infrastruttura di comunicazione adatta ad
ambienti distribuiti che sono asincroni per natura e che richiedono un pattern di
comunicazione di tipo molti-a-molti, come ad esempio quello delle comunicazioni mobili
o della distribuzione di dati.
60
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In contesti in cui è necessario garantire anche un’elevata affidabilità della comunicazione,
e dunque anche recupero dalle perdite, la scalabilità di tali sistemi risulta in qualche modo
ridotta in quanto sorge la necessità di memorizzare gli eventi per poterne eventualmente
effettuare la ritrasmissione[30].
2.3.2 Introduzione allo standard OMG DDS
Lo standard OMG Data Distribution Service[5] è una specifica per sistemi di
distribuzione dei dati basati su un modello di comunicazione publish-subscribe topicbased13. Lo scopo di tale specifica è fornire un interfaccia comune di livello applicativo
che definisca chiaramente il servizio di distribuzione dei dati . La specifica utilizza il
linguaggio UML per descrivere il servizio, fornendo quindi un modello indipendente dalle
particolari piattaforme hardware
e dai particolari linguaggi di programmazione. Il
modello può essere quindi istanziato su una qualunque piattaforma reale ed implementato
in un qualunque linguaggio di programmazione.
Lo standard fornisce altresì una definizione formale delle politiche di QoS(Quality
of Service) che è possibile usare per configurare il servizio.
In definitiva,l’obiettivo del DDS è di facilitare la distribuzione efficiente dei dati in
sistemi distribuiti[4].
Le applicazioni distribuite basate sul modello publish-subscribe(descritto nel dettaglio nel
paragrafo successivo) sono composte da processi ,detti “participants”,che possono
ricoprire i ruoli sia di pulisher che di subscriber. Tali processi usando il DDS possono
effettuare semplici operazioni di ‘read’ e ‘write’ in maniera efficiente e con un interfaccia
tipizzata, e sarà poi il middleware DDS sottostante a distribuire i dati in modo che ogni
participant possa accedere al valore più recente del dato.
13
Un sistema pub/sub è Topic-based quando i partecipanti pubblicano e sottoscrivono eventi individuali
61
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In pratica il servizio crea uno spazio globale dei dati (global data space) che può essere
letto e scritto da tutti i processi(comunicazione data-centrica,cfr fig seg.).
Figura 19 - Il Global Data Space
Per realizzare questa astrazione lo standard definisce due livelli di interfacce[4] :
1. Un livello inferiore,il DCPS (Data-Centric Publish-Subscribe) che è
orientato alla distribuzione efficiente delle informazioni ai richiedenti le
stesse;
2. Un livello superiore,facoltativo,il DLRL (Data-Local Reconstruction Layer)
che consente una più semplice integrazione nel livello applicativo.
Figura 20 - Livelli Interfacce OMG DDS
Non tutte le implementazioni conformi allo standard implementano entrambi i livelli di
interfacce. Tuttavia
per assicurare conformità ed interoperabilità è obbligatoria la
62
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
realizzazione di un sottoinsieme di DCPS che prevede l’implementazione delle entità
principali previste dallo standard (Minimum profile,crf[5]).
2.3.4 Modello di programmazione del DDS
Il modello di programmazione del DDS è mostrato nella figura seguente:
Figura 21 - Modello di programmazione del DDS
[4]Le classi principali attraverso le quali si realizza la comunicazione sono:
DomainParticipant,DataWriter,DataReader,Publisher,Subscriber e Topic.
63
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Tutte queste classi derivano dalla classe base Entity il che evidenzia la loro capacità di
essere configurate attraverso politiche di QoS (cfr.par succ.),ricevere notifiche di eventi
attraverso dei listeners e supportare condizioni di attesa dell’applicazione.
Il Publisher è l’oggetto responsabile della pubblicazione dei dati. Un DataWriter è un
interfaccia tipizzata del Publisher: i participants utilizzano i DataWriters per comunicare il
valore di un certo tipo di dato o il cambiamento del valore del tipo stesso. Una volta che il
dato è stato comunicato al Publisher, è sua responsabilità decidere quando inviare il
corrispondente messaggio di pubblicazione.
Il Subscriber riceve i dati pubblicati e li rende disponibili al participant che lo contiene.
Un subscriber può ricevere dati di differenti tipi e per accedere a tali dati il participant deve
usare un DataReader, che è l’interfaccia tipizzata attaccata al subscriber.
L’associazione di un oggetto DataWriter (che rappresenta una pubblicazione) con oggetti
DataReader è realizzata per mezzo del Topic. Un Topic associa un nome (unico nel
sistema), un tipo di dato e politiche di QoS al dato stesso.
La seguente immagine mostra gli le entità ora introdotte nell’architettura tipica di
un’applicazione DDS:
Figura 22 - Architettura di una tipica applicazione DDS
64
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il “dominio DDS” è formato in questa immagine da tre DomainParticipants che
comunicano su tre diversi Topics. Il primo participant contiene un Subscriber (contentente
a sua volta un DataReader), ed un Publisher (contenente due DataWriter). Il secondo
participant contiene un singolo subscriber che contiene a sua volta due DataReader
associati a differenti Topics. Infine il terzo participant contiene un singolo Publisher con
un singolo DataWriter.
2.3.4 Le politiche di QoS del DDS
Il Data Distribution Service adotta una serie di politiche di qualità del servizio (QoS) in
modo da poter adattare il servizio alle caratteristiche e ai requisiti dell’applicazione. Le
QoS policies sono un insieme di proprietà che guidano il comportamento del servizio e
sono realizzate a partire da una QoS Policy predefinita che viene specializzata per definire
i diversi aspetti del funzionamento del servizio.
In questa sezione vengono descritte le policies principali mentre per una descrizione
esaustiva si rimanda alla specifica DDS [5].
Una QoS Policy può essere associata a ciascuna delle DCPSEntities descritte in
precedenza(cfr.fig 20). Per realizzare un disaccoppiamento lasco tra Publisher e
Subscriber, il livello DCPS prevede un meccanismo per stabilire quando le policy offerte
tra le entità di pubblicazione e sottoscrizione sono ammissibili. In tal senso viene
realizzato un pattern noto come RxO ( Requested versus Offered). Il Data Reader setta
un valore “richiesto” per una particolare policy di QoS. Il Data Writer setta un valore
“offerto” per quella policy di QoS. Quando il DDS realizza un associazione tra Data
Reader e Data Writer, si stabilisce se le policy di QoS sono compatibili, ovvero se tutti i
valori richiesti sono supportati da quelli offerti. Se ciò non avviene il Servizio DDS non
65
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
realizza l’associazione e solleva un’eccezione del tipo INCOMPATIBLE_QOS a ciascun
lato della comunicazione. Di seguito sono descritte le QoS Policy rilevanti ai fini della
costruzione del modello del sistema nei capitoli successivi.
• Deadline: Questa policy è utilizzata se un Topic deve essere aggiornato
periodicamente. Lato Publisher si stabilisce un contratto che l’applicazione dovrà
rispettare. Lato Subscriber si stabilisce un requisito minimo di frequenza di
aggiornamento. Identificato un DataWriter che corrisponda al DataReader, il
servizio controlla se risulta OfferedDeadlinePeriod ≤ RequestedDeadlinePeriod.
Se questo non accade i due endpoint vengono informati dell’incompatibilità
creatasi attraverso i meccanismi di listener o condition. In caso di compatibilità il
servizio opera comunque un controllo costante ed informa l’applicazione di
qualsiasi violazione del contratto che possa essersi verificata.
• Lifespan: Lo scopo di questa policy è di evitare la possibilità di consegnare
all’applicazione dati ormai non più validi. Ciascun campione di dato verrà quindi
marcato con un expiration time, oltre il quale verrà scartato e mai consegnato
all’applicazione. L’istante di scadenza del dato viene calcolato aggiungendo il
valore della lifespan al timestamp di sorgente, automaticamente settato dal servizio
o
fornito
dall’applicazione
write_w_timestamp.
Questa
sorgente
politica
attraverso
di
QoS
una
specifica
naturalmente
primitiva
prevede
una
sincronizzazione tra i clock di sorgente e destinazione. Se ciò non fosse vero il
servizio usare l’istante di ricezione piuttosto che il timestamp di sorgente per
calcolare la scadenza.
• Reliability: Indica il livello di affidabilità richiesta da un DataReader o offerta da un
DataWriter. Sono possibili due livelli di servizio, best-effort e reliable. Un’offerta
66
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
di servizio reliable implicitamente comprende anche inferiore best-effort. Se la
politica scelta è reliable i campioni di dato prodotti da un singolo DataWriter non
saranno consegnati all’applicazione fino a che i campioni precedentemente
originati non saranno stati consegnati. Il servizio naturalmente si farà carico di
ritrasmettere eventuali campioni andati perduti. Nel caso best-effort questa
limitazione non è presente, il campione più aggiornato verrà sempre consegnato
all’applicazione `e non si effettua un recupero di campioni eventualmente persi.
• Liveliness: Questa policy controlla il meccanismo ed i parametri usati dal servizio
per assicurare che una data entità sia ancora viva. Ha diverse possibili
combinazioni di valori che si adattano sia al caso di data-object aggiornati
periodicamente che in modo aperiodico. Consente anche un minimo di
personalizzazione per adattarsi a requisiti differenti in termini di tipologie di
fallimento che si vogliono identificare. Il livello automatic è utile per applicazioni
che necessitano solo un controllo a livello di processo, ma non consente di
identificare problemi che riguardano la logica dell’applicazione. Se necessario è
opportuno adottare una soluzione
In questo caso la liveliness
assert liveliness o
manuale per identificare guasti e fallimenti.
può essere dichiarata esplicitamente con la primitiva
implicitamente pubblicando nuovi dati. E’ infine possibile
specificare la granularità di questo processo, dalla più fine, ossia per ciascun topic,
alla più grossa, un qualsiasi topic pubblicato garantisce la liveliness dell’intero
partecipante.
• Ownership: serve ad arbitrare l’aggiornamento dei DataReader in presenza di più
DataWriter coinvolti nella pubblicazione di valori per lo stesso data-object. Sono
possibili due tipi di ownership: shared ed exclusive. Nel caso di un possesso
67
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
shared, il servizio accetterà modifiche da ciascun DataWriter. Nel caso exclusive
invece il servizio dovrà garantire che in ogni istante di tempo sia unico il
DataWriter abilitato a realizzare aggiornamenti del data-object. Il possesso della
risorsa si determina attraverso il valore di un’altra policy, OwnershipStrength. Essa
da un valore di Ownership a ciascun DataWriter e la risorsa viene affidata al
DataWriter con il valore più elevato, che sia vivo (come specificato dalla
Liveliness Policy) e non abbia mancato la deadline (come specificato dalla
Deadline Policy). Il possesso può quindi cambiare nei seguenti casi:
¾ nel sistema esiste un DataWriter con Ownership Strength
più elevata;
¾ si verifica un cambiamento della Ownership Strength del
possessore;
¾ si verifica un cambiamento nella Liveliness del possessore;
¾ il DataWriter possessore manca una deadline.
E’ bene osservare che la determinazione del possesso viene operata in maniera
indipendente da ciascun DataReader. Non è considerato un requisito l’agreement
tra i DataReader riguardo al DataWriter che possiede l’istanza, come non è
considerato un requisito che il DataWriter sia cosciente di possedere o meno la
risorsa. Questa scelta è motivata dall’obiettivo di preservare il disaccoppiamento
tra le entità e di consentire che questa politica sia implementata in maniera
efficiente. E’ infine possibile che più DataWriter abbiano lo stesso valore di
Ownership Strength, e in questo caso la specifica non fornisce indicazione sul
criterio di scelta, impone però che questo debba dare risultato uguale per tutti i
DataReader e non cambi a meno che non si verifichi uno dei casi precedenti
(cambio nella Strength, nella Liveliness, mancata deadline).
68
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
2.3.5 Le problematiche nell’utilizzo del DDS nel contesto dei MCS
I sistemi MCS, come evidenziato nel capitolo1, operano distribuzione di dati su reti WAN
(Wide Area Network). Una soluzione architetturale interessante per la realizzazione di
applicazioni orientate alla distribuzione dei dati in tali sistemi è costituita proprio dai
sistemi publish/subscribe per le proprietà di scalabilità offerte. Il paradigma
publish/subscribe offre infatti un elevato disaccoppiamento ed un naturale pattern di
comunicazione molti-a-molti(cfr.par 2.3.1). Tra i sistemi publish/subscribe esistenti,il
DDS rappresenta quello con le caratteristiche più adatte al contesto dei MCS. Diversi studi
dimostrano infatti che i middleware DDS mostrano prestazioni superiori in termini di
celerità di consegna rispetto ad altri sistemi basati sullo stesso paradigma.
I middleware DDS inoltre offrono delle politiche di QoS configurabili secondo le esigenze
specifiche delle applicazioni, con politiche specifiche per garantire opportuni upperbounds dei tempi di consegna e politiche atte a garantire la consegna certa dei
messsaggi(cfr. par.2.3.4).
Tuttavia i middleware DDS utilizzano soltanto soluzioni basate su schemi ARQ (cfr.par
1.2) per assicurare l'affidabilità nella consegna dei messaggi. Queste soluzioni offrono
prestazioni dipendenti dal tasso di perdita dei pacchetti e dalla lunghezza media dei
bursts di perdita(cfr.par.1.2).
In reti ad estensione geografica, a causa della variabilità di tali parametri, questa
dipendenza si traduce nell’impossibilità di offrire dei limiti superiori ed inferiori alla
latenza di recovery.
È chiaro quindi, come già osservato nel capitolo1, che schemi di tipo ARQ non
risultano adatti al loro utilizzo in contesti mission critical su rete ad estensione geografica.
69
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
2.3.6 Una possibile soluzione: l’utilizzo di FEC
Le tecniche FEC rappresentano una valida alternativa alle tecniche ARQ. Esse
presentano le dipendenze dai patterns di perdita che affliggono gli ARQ
non
e questo
comporta in generale una maggiore prevedibilità dei tempi di recupero (cfr. cap 1).
Nel contesto considerato i guasti di rete si traducono in perdite dei pacchetti, cioè in
cancellazioni degli stessi. Pertanto è logico considerare come strumento per la
realizzazione di uno schema di affidabilità FEC gli Erasure Codes introdotti all’inizio di
questo capitolo .
Volendo quindi realizzare un servizio di distribuzione dei dati che rispetti al tempo stesso i
requisiti di scalabilità, prevedibilità e tolleranza ai guasti (cioè,recupero dalle perdite) si è
pensato di introdurre un meccanismo di codifica basato su EC in middleware di tipo
DDS.
L’utilizzo di FEC per la realizzazione di meccanismi affidabilità non è nuova. In
letteratura esistono differenti protocolli multicast, alcuni dei quali presentati nel capitolo 1,
che realizzano una consegna certa dei dati attraverso schemi FEC [13,12,10,11,9,16].
Tuttavia tali protocolli (ed i relativi schemi FEC) sono stati progettati con l’obiettivo di
soddisfare requisiti di sistemi operanti in contesti differenti da quello in esame, pertanto
ottengono prestazioni buone in termini di affidabilità e celerità della consegna in ipotesi
differenti da quelle valide nel contesto dei sistemi mission-critical operanti su reti ad
estensione geografica.
È dunque necessario operare una valutazione sperimentale di schemi FEC nel contesto dei
in esame per poterne confermare l’efficacia. È inoltre opportuno valutare anche
l’opportunità di utilizzare una tecnica ibrida FEC+ARQ in quanto la difficoltà nella stima
70
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dei parametri caratteristici delle reti wide-area potrebbe rendere impossibile la
realizzazione di una consegna certa con uno schema FEC puro.
Nel capitolo successivo sarà presentato lo studio sperimentale di tali soluzioni condotto a
partire da un’applicazione DDS di benchmark modificata per integrare uno schema FEC
ed uno schema FEC+ARQ.
Successivamente si è passati ad un approccio di livello trasporto, iniziando la realizzazione
di un protocollo integrato nel DDS che realizzi schemi di affidabilità FEC.
I due approcci sono schematizzati nella figura seguente:
Figura 23 - Integrazione di FEC in piattaforme DDS: i due approcci utilizzati
71
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Capitolo 3
Erasure Codes a livello applicativo e realizzazione di un
protocollo di trasporto affidabile in OpenDDS
3.1 Integrazione degli Erasure Codes in piattaforme DDS
L’introduzione degli EC in middleware DDS può avvenire in diversi modi. In questa
sede si è inizialmente adottato un approccio di livello applicativo. Un blocco FEC si pone
idealmente al di sopra del DDS fornendo all’applicazione dei servizi (opzionali) di
protezione dei dati dalle perdite. Tale approccio è schematizzato in figura:
Figura 24 - Inserimento FEC a livello applicativo
72
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La codifica avviene mediante opportune librerie EC nel publisher dell’applicazione.
Il publisher invia poi i messaggi ai subscribers tramite il DDS. La decodifica avviene lato
subsciber sempre a livello applicativo. Ricevuti i messaggi codificati dal DDS, il decoder
ricostruisce i messaggi originari e li passa all’applicazione subscriber.
Questo approccio, per quanto semplice dal punto di vista implementativo, ha
evidenziato in fase sperimentale dei limiti importanti.
Il problema principale è che in tale approccio si è fortemente dipendenti dal DDS
sottostante. In determinate condizioni questa dipendenza può manifestarsi in un
comportamento inatteso dell’applicazione e del meccanismo di affidabilità, provocando
perdite inattese e prestazioni inadeguate.
Si è quindi reso necessario un cambio di approccio. L’inserimento degli EC avviene
a livello trasporto, andandosi ad integrare ai meccanismi di trasmissione sottostanti il
DDS. La seguente figura schematizza il nuovo approccio:
Figura 25 - Inserimento FEC a livello trasporto
73
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In questo modo è possibile realizzare un meccanismo di affidabilità in maniera
completamente indipendente dalle problematiche del DDS. Questo approccio in linea
teorica è quello vincente, tuttavia sono necessarie ulteriori sperimentazioni a conferma di
ciò.
3.2 Erasure Codes a livello applicativo
In questo paragrafo si presenta l’approccio di livello applicativo da un punto di vista
implementativo, analizzando tutte le componenti che sono intervenute nella realizzazione
dello schema.
I FEC sono stati introdotti mediante una libreria di codici Reed-Solomon scritta in
linguaggio C. La scelta dei codici Reed-Solomon è dettata dai risultati sperimentali
presentati in [24].
La libreria è stata utilizzata per la realizzazione di strutture ad oggetti che si
occupassero della codifica e della decodifica dei messaggi da pubblicare.
Il middleware DDS utilizzato è la distribuzione commerciale RTI DDS, versione
4.1d. Tale middleware è stato scelto perché la soluzione ARQ da esso adottato per
garantire la ritrasmissione è molto efficiente e presenta un buon termine di paragone per la
soluzione proposta.
3.2.1 La piattaforma RTI DDS
RTI DDS[1] è un’implementazione commerciale dello standard OMG per applicazioni
real-time distribuite.
In questo paragrafo si illustreranno gli aspetti della piattaforma RTI DDS di
interesse per la comprensione dei test successivi. In particolare si illustrerà il protocollo
affidabile realizzato da RTI DDS per garantire il recupero dalla perdite.
74
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
RTI DDS utilizza come servizio di consegna di default il best-effort:i DataReader settati
con questa configurazione ignorano i messaggi persi.
L’applicazione riceve soltanto una notifica se non riceve un nuovo messaggio entro un
certo periodo di tempo( periodo settato tramite la policy DEADLINE).
Il modello di consegna affidabile realizzato nel middleware RTI DDS garantisce invece la
consegna certa ed in ordine dei messaggi inviati tra i partecipanti della specifica
applicazione.
In sostanza,il middleware realizza questo servizio mediante l’utilizzo di un protocollo di
tipo ARQ con utilizzo di riscontri sia positivi che negativi . Esso inoltre si avvale
dell’ausilio di due code di messaggi ,una per il DataWriter – send queue – ed una per il
DataReader –receive queue - della pubblicazione in questione,fornendo ai primi le risorse
necessarie a memorizzare gli ultimi X messaggi inviati ed ai secondi le risorse necessarie a
memorizzare X messaggi consecutivi attesi(cioè a memorizzare messaggi giunti out-oforder in attesa di quelli mancanti).
Il DDS rimuove i messaggi dalla send queue solo quando è certo che siano stati consegnati
a tutti i subscribers interessati alla pubblicazione,mentre la rimozione dei messaggi dalla
receive queue avviene solo quando è possibile effettuare la consegna ordinata degli
stessi,cioè quando siano arrivati i messaggi mancanti (rispetto alla sequenza attesa).
Il protocollo affidabile di RTI DDS utilizza 4 tipi diversi di messaggi :
ƒ DATA e NOKEY_DATA:tali messaggi,inviati dal DataWriter, contengono il
valore effettivo del dato inviato ed associano a tale valore un numero di sequenza
progressivo usato dal DDS per reperire il dato all’interno della send queue
associata a quel particolare DataWriter.Il numero di sequenza è generato
automaticamente dal DataWriter ogni volta che l’applicazione invoca una write()
75
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
sul DDS.(NOKEY_DATA si usa nel caso in cui il tipo di dato non abbia una
chiave)
ƒ ACKNACK:come accennato in precedenza,RTI utilizza dei risconti positivi o
negativi per comunicare al DataWriter che il DataReader interessato ha
effettivamente ricevuto il dato e che il dato è stato salvato nella coda di
ricezione,oppure per comunicare i dati mancanti rispetto alla sequenza attesa. Per
questi scopi si utilizza un unico tipo di messaggio,ACKNACK appunto,che ha la
seguente semantica:
o ACKNACK(<first_missing>) : indica che tutti i messaggi con numero di
sequenza minore (strettamente) di first_missing sono stati ricevuti con
successo e consegnati all’applicazione in ordine(cioè,ack positivo dei
messaggi fino a first_missing-1),e dunque il prossimo atteso è
first_missing(ack negativo del messaggio first_missing);
o ACKNACK(<first_missing>-<last_missing>):
indica
l’intervallo
di
messaggi mancanti ,dunque nel senso di ack negativi;
ƒ HB:messaggio di HeartBeat;è utilizzato dal DataWriter per segnalare al DataReader
che dovrebbe aver ricevuto i dati contrassegnati dai numeri di sequenza indicati
come intervallo nel messaggio,e può opzionalmente richiedere un riscontro a
questa segnalazione;
I messaggi di cui sopra non devono necessariamente essere inviati in singoli pacchetti di
rete,bensì è possibile (e consigliabile per migliorare le prestazioni superiori)inserirne più
d’uno in un singolo pacchetto(piggyback).
Il comportamento del protocollo può essere meglio compreso mediante l’analisi di uno
scenario elementare così caratterizzato:
abbiamo:
• Perdita messaggio dati
76
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
• Nessuna perdita messaggio di riscontro
In breve lo scenario prevede l’invio di 3 messaggi dati contrassegnati da numeri di
sequenza 1,2 e 3 con perdita del messaggio numero 1;il diagramma è il seguente:
Figura 26 - Protocollo affidabile di RTI DDS
Lo scenario evolve come segue:
1) lato Publisher l’applicazione invoca una write(A) sul DDS tramite l’oggetto
DataWriter per inviare il dato A;il DataWriter associa il numero di sequenza ‘1’ a
tale dato prima di inviarlo e lo memorizza nella send queue(cache(A,1));
2) il protocollo invia due messaggi insieme(piggyback),un DATA(A,1) ed un
HB(1),cioè effettua l’invio effettivo del dato e segnala (con l’HeartBeat) che il
DataReader dovrebbe aver ricevuto tale dato;la coppia di messaggi si perde;
3) il Publisher invoca una nuova write per l’invio del secondo dato,B,contrassegnato
dal numero di sequenza 2,insieme all’HeartBeat per i messaggi da 1 a 2;prima
77
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
dell’invio effettivo si salva il dato nella send queue:cache(B,2);DATA(B,2);HB(12);
(si noti che a questo punto ,non avendo ancora ricevuto alcun ACKNACK dal
DataReader, entrambi i dati A e B sono contrassegnati come non eliminabili nella
send queue);
4) ricevuto il dato (B,2) il DataReader effettua la memorizzazione nella receive queue
(cache(B,2)),ma poiché manca il dato con numero di sequenza 1 riserva ad esso un
posto nella coda e salva B;entrambi i messaggi vengono segnalati come non
disponibili(X) per la read o la take sul DataReader(mancando (A,1) non è possibile
una consegna ordinata);
5) avendo ricevuto l’HB(1-2) ed avendo riscontrato la perdita del messaggio 1,il
DataReader invia l’ACKNACK(1),richiedendo in pratica la ritrasmissione del
messaggio (A,1);
6) ricevuto l’ACKNACK(1)(che significa che i dati fino ad 1 ESCLUSO sono stati
ricevuti,ovvero che 1 si è perso) il DataWriter inizia la fase di ritrasmissione,prima
recuperando il dato dalla send queue ( get(1) ),poi reinviando il dato
mancante(DATA(A,1));(NB:l’Heartbeat NON viene reinviato!)
7) ricevuto il dato (A,1) il DataReader può contrassegnare come disponibili per la read
o take entrambi i dati in coda;
8) il DataWriter effettua l’invio del terzo dato (DATA(C,3)) insieme ad un HeartBeat
da 1 a 3(da 1 a 3 perché ha inviato i dati contrassegnati da questi numeri di
sequenza);i dati salvati finora nella send queue sono ancora impossibili da eliminare
in quanto non sono stati ricevuti ACKNACK con numeri di sequenza superiori ad
1(cioè nessun messaggio,dal punto di vista del Publisher) è stato memorizzato nella
receive queue;
78
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
9) ricevuto il terzo dato lo memorizza in coda e lo segnala come disponibile(avendo
già ricevuto 1 e 2) e poiché ha ricevuto l’HB(1-3) il DataReader effettua il controllo
sui dati ricevuti e trovandoli tutti in coda può inviare l’ACKNACK(4),che segnala al
DataWriter l’avvenuta memorizzazione dei messaggi fino a 3 e l’attesa del quarto;
10) ricevuto tale ACKNACK(4) il DataWriter può finalmente contrassegnare come
eliminabili i dati fino a 3(incluso)e proseguire con le altre eventuali operazioni.
Una sottile ma importante caratteristica del protocolo che è opportuno segnalare è la
seguente: i messaggi ACKNACK sono inviati dai DataReader esclusivamente in risposta
diretta ai messaggi di HeartBeat.Questo permette ai DataWriter di controllare in qualche
modo l’overhead dovuto a tali messaggi di servizio,ad esempio inviando un unico HB per
una lunga sequenza di DATA() ,e ricevendo pertanto un unico ACKNACK per tutta la
sequenza.
79
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.2.2 Libreria Jerasure per codici Reed-Solomon
Jerasure è una libreria in C/C++ è una implementazione degli Erasure Code: ReedSolomon (RS) e Liberation. Tratteremo solo i primi, per i codici Liberation si rimanda al
riferimento [32] dove è disponibile la libreria e la relativa documentazione.
Jerasure si compone dei seguenti file:
¾ galois.h e galois.c: contengono procedure per l’aritmetica nel campo di
Galois (2w ) GF per 1 δ w δ 32
¾ jerasure.h e jerasure.c: contengono procedure di codifica/decodifica e procedure di
supporto a queste
¾ reed-sol.h e reed-sol.c: implementano procedure per la generazione di matrici di
distribuzione di Vandermonde [19] e routine per i codici Reed-Solomon ottimizzati
per RAID-6 [15], tecnica nella quali i blocchi ridondanza sono al massimo due (m
=2)
¾ cauchy.h e cauchy.c: implementano procedure per la generazione di matrici di
distribuzione di Cauchy e routine di supporto a queste
Vengono presentate adesso le routine di generazione delle matrici di distribuzione e di
codifica messe a disposizione dalla libreria Jerasure.
Routine di generazione delle matrici di distribuzione:
¾ galois_single_divide(): Effettua una divisione fra elementi singoli di (2w ) GF , ma
usata opportunamente serve a generare una matrice di Cauchy
¾ galois_single_multiply(): Effettua una moltiplicazione fra elementi singoli
80
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
di (2w ) GF , ma usata opportunamente serve a creare delle matrici RAID-6
¾ reed_sol_vandermonde_coding_matrix(): Genera una matrice di Vandermonde
¾ reed_sol_r6_coding_matrix(): Genera una matrice per RAID-6
¾ cauchy_original_coding_matrix(): Genera una matrice di Cauchy
¾ cauchy_good_general_coding_matrix(): Genera una buona matrice. A seconda dei
parametri che gli vengono passati, genera una matrice ottimale per RAID-6,
altrimenti genera una buona matrice chiamando rispettivamente
¾ cauchy_original_coding_matrix()
e
cauchy_improve_coding_matrix()
che
migliorala matrice con un metodo euristico
Routine di codifica:
¾ jerasure_matrix_encode(): effettua la codifica sfruttando una delle matrici generate
dalle routine di generazione delle matrici di distribuzione
¾ reed_sol_r6_encode(): può essere usata solo nel caso m = 2 ed effettua una codifica
ottimizzata, non necessita di matrice di distribuzione poiché implicita
¾ jerasure_bitmatrix_encode(): effettua la codifica sfruttando una delle matrici
generate dalla routine di generazione delle matrici di distribuzione estesa secondo
l’isomorfismo fra il campo di Galois (2w ) GF e lo spazio delle matrici binarie L
⋅ L. La matrice viene estesa mediante la routine jerasure_matrix_to_bitmatrix()
¾ jerasure_schedule_encode(): effettua la codifica sfruttando una schedule che è una
struttura derivata dalla bitmatrix atta a rappresentare le operazioni di codifica.
Queste ultime vengono infatti pre-elaborate anziché fatte scorrendo ogni volta la
bitmatrix aumentando l’efficienza. La bitmatrix viene convertita in una schedule
tramite
jerasure_dumb_bitmatrix_to_schedule()
o
meglio
jerasure_smart_bitmatrix_to_schedule()[32].
81
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Si noti che per la decodifica esistono funzioni complementari a quelle di codifica qui
introdotte, pertanto esse non verranno presentate esplicitamente. Per approfondimenti si
rimanda al riferimento [32].
La libreria Jerasure è stata utilizzata per la realizzazione delle fasi di codifica e decodifica
nell’applicazione benchmark. In particolare sono state utilizzate le seguenti funzioni:
¾ cauchy_original_coding_matrix(): per la generazione della matrice di Cauchy
¾ jerasure_matrix_to_bitmatrix():per la conversione della matrice di Cauchy in
matrice binaria
¾ jerasure_bitmatrix_encode(): per la codifica dei dati in ingresso mediante la
matrice binaria
¾ jerasure_bitmatrix_edecode(): per la decodifica dei dati ricevuti mediante la
matrice binaria
82
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.2.3 L’applicazione benchmark
L’applicazione benchmark utilizzata è stata realizzata a partire da un’applicazione di
test scritta in linguaggio C++ inclusa nella distribuzione commerciale di RTI DDS
versione 4.1d.
Le funzioni della libreria Jerasure per la codifica/decodifica sono wrappate
all’interno di una gerarchia di classi che gestisce i messaggi da codificare e decodificare
mediante una struttura dati linkata. Il diagramma UML è il seguente:
Figura 27 – Classi del layer FEC introdotto tra applicazione e DDS
83
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
L’applicazione opera come segue:
¾ un publisher emette un certo numero di pubblicazioni di dimensione scelta
da riga di comando all’atto dell’avvio dell’applicazione;
¾ le pubblicazioni vengono suddivise in k blocchi (con k dipendente dalla
dimensione totale del messaggio) che vengono poi codificati con il grado di
ridondanza indicato da riga di comando
¾ per ogni blocco così ottenuto si inserisce un timestamp associato alla
pubblicazione e lo si invia tramite il DDS configurato in modalità best-effort
¾ lato subscriber,appena si ricevono almeno k blocchi per una pubblicazione si
tenta la decodifica;appena
¾ nella versione del benchmark che realizza lo schema misto FEC+ARQ, se il
subscriber riceve meno di k blocchi per una certa pubblicazione,provvede ad
effettuare la richiesta di ritrasmissione indicando i blocchi mancanti per
arrivare a k
Per ogni pubblicazione si registrano,lato publisher, il timestamp di invio del messaggio ed
il tempo di arrivo dell’echo,calcolando in pratica la latenza di messaggio come RTT/2.
84
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.3 La campagna sperimentale
Per valutare le prestazioni della soluzione FEC ed operare un confronto con la
soluzioni FEC+ARQ ed ARQ del DDS in modalità reliable è stata condotta una campagna
sperimentale in ambiente controllato, allo scopo di ottenere risultati che fossero
riproducibili.
3.3.1 Descrizione del testbed
L’approccio scelto per operare i test è quello della network emulation. Un publisher
ed un subscriber sono stati istanziati su due macchine fisiche differenti collegate ad un
emulatore di rete (Shunra Virtual Enterprise). Tale emulatore ha permesso di simulare il
comportamento della rete reale in base a specifici parametri estratti sperimentalmente e ad
un opportuno modello matematico.
Figura 28 - Il simulatore di rete utilizzato
L’emulazione, rispetto alla simulazione, si presenta come uno schema ibrido[37] in
cui, accanto ad elementi simulati in base a modelli matematici governati da opportuni
parametri (in questo caso è la rete ad essere simulata mediante modello), si utilizzano
anche elementi reali, come sono le due macchine fisiche collegate all’emulatore utilizzate
in questa campagna. La differenza principale tra simulazione ed emulazione è la seguente:
mentre la prima utilizza una dimensione temporale virtuale (cioè,anche il tempo è
85
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
simulato), la seconda deve avvenire in una dimensione temporale reale, data la presenza di
elementi reali.
Figura 29 - Il testbed utilizzato per le sperimentazioni
3.3.2 Caratterizzazione del comportamento di rete
Per valutare correttamente le prestazioni degli schemi FEC e FEC+ARQ è
necessario modellare il comportamento della rete nella maniera più realistica possibile.
Lo studio di Internet mediante un suo modello consiste nel semplificare e ridurre la rete ad
un prototipo in scala che ne riproduca le caratteristiche essenziali e ne restituisca una
rappresentazione semplice anche se non completamente corrispondente alla rete reale. In
quest’ottica sono stati utilizzati parametri precedentemente estratti da sperimentazioni
effettuate su alcuni paths europei. I dati sperimentali hanno permesso una
caratterizzazione di tali paths in termini di :
¾ latenza di rete (Delay)
¾ percentuale pacchetti persi( PLR-Packet Loss Rate)
¾ n.medio pacchetti perdi di fila (ABL- Average Burst Length)
86
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 30 - I paths presi in esame per simulare la Internet
I risultati mostrano un andamento del PLR dipendente dall’intervallo di
pubblicazione dei messaggi, mente l’ABL si mostra sostanzialmente dipendente dal path:
Figura 31 - Andamento dell'Average Burst Length nei paths esaminati
87
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 32 - L'andamento del Packet Loss Rate nei paths esaminati
Tra i sei paths totali sono stati selezionati, in base ai dati a disposizione, i seguenti 3
scenari:
Figura 33 - I parametri degli scenari selezionati
Gli scenari sono stati selezionati in modo da garantire una caratterizzazione di rete che
fosse statisticamente significativa. I tre scenari presentano pertanto differenti ritardi
introdotti, sono caratterizzati da dispersioni statistiche dei ritardi differenti (la dispersione
statistica è misurata in termini di IQR) e differenti percentuali di perdita dei pacchetti
(PLR). I valori di ABL medi risultano compresi tra un minimo di 1,26 ed un massimo di
1,59.
88
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.3.3 Emulazione di rete: il modello di Gilbert
Simulare un canale con perdite mediante emulatore di rete comporta la scelta di un
modello matematico che permetta all’emulatore, attraverso parametri rappresentativi della
rete, di ricrearne il comportamento in maniera realistica.
La rete da simulare in questo contesto è Internet, con le caratteristiche di variabilità
della latenza e, soprattutto, della correlazione tra le perdite. Per testare correttamente
l’affidabilità degli schemi in esame, è infatti necessario che il modello delle perdite sia
simulato nella maniera più prossima possibile a quanto avviene sulla rete reale.
È intuitivo che per simulare una rete con tali caratteristiche ( o almeno, scenari
rappresentativi tale rete) non è sufficiente un modello semplicistico di canale con perdite,
come ad esempio un canale BEC (Binary Erasure Channel) in quanto privo di
informazioni di stato. Non è ovviamente possibile simulare delle perdite correlate
mediante un modello che non abbia memoria dell’esito dell’invio del dato precedente.
Figura 34 - Binary Erasure Channel (BEC)
89
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In un canale BEC il dato (binario) è inviato correttamente oppure cancellato, ed ogni
invio è indipendente dal precedente e dal successivo. La probabilità di cancellazione è cioè
sempre la stessa per ogni invio.
È dunque necessario utilizzare un altro modello, che tenga memoria dell’andamento
degli invii precedenti. La scelta è caduta sul modello di Gilbert[36].
Il modello di Gilbert è basato su una catena di Markov a due stati ed aggiunge
quindi memoria rispetto ad un canale BEC. In breve, la memoria della catena di Markov
permette di definire una probabilità che un pacchetto venga perso se è stato perso anche
quello precedente e di generare quindi perdite a burst. Il modello si presenta come segue:
Figura 35 - Rappresentazione del modello di Gilbert
Esso consiste di due stati del canale: LOSS e NON-LOSSI. Le probabilità di
transizione da uno stato ad un altro sono p e q. Una transizione dallo stato NON-LOSS
allo stato LOSS avviene con probabilità p mentre la transizione opposta con probabilità q.
Nello stato NON-LOSS la probabilità di perdite è nulla,mentre nello stato LOSS è pari ad
1. Le probabilità di restare nei due stati sono rispettivamente 1-p ed 1-q.
Il modello è dunque completamente caratterizzato dai due parametri p e q, e tali
parametri possono essere calcolati, ai fini della simulazione, a partire dai dati estratti
sperimentalmente dai paths da simulare secondo le seguenti formule:
90
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.3.4 Risultati e valutazione delle prestazioni
I parametri dei test eseguiti sono:
¾ Dimensione messaggi : 100 KB
¾ Periodo di pubblicazione : 20 msec
¾ Numero di pubblicazioni : 200
¾ Numero di pacchetti di ridondanza: m= {1,….,12}
I test sono stati eseguiti sia per lo schema FEC che per FEC+ARQ. Essi miravano a
valutare l’affidabilità degli schemi, misurata in termini di percentuale di pacchetti
correttamente giunti a destinazione, e la prevedibilità degli stessi, misurata in termini di
InterQuartileRange(IQR) sulla latenza di consegna.
I grafici seguenti mostrano l’andamento della percentuale di consegna al variare di m nei
tre scenari. FEC+ARQ mostra una affidabilità superiore rispetto a FEC fin dai primi livelli
di ridondanza grazie alle ritrasmissioni. Tuttavia FEC mostra una consegna pari al 100%
nel primo scenario per m=8 (FEC+ARQ raggiunge il 100% per m=4).
L’andamento di entrambi gli schemi diventa comunque decrescente da un certo valore di
m in poi in quanto la codifica e la decodifica dei messaggi tendono a diventare maggiori
del periodo di pubblicazione, portando alla saturazione delle code del DDS ed al
conseguente drop dei messaggi.
91
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 36 - Percentuale di successo per FEC+ARQ al variare di m nei 3 scenari
Figura 37 - Percentuale di successo di FEC al variare di m nei 3 scenari
92
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il grafico successivo mostra invece l’andamento di FEC sovrapposto a quello di
FEC+ARQ nel primo scenario in modo da poter operare un confronto immediato
Figura 38 - Confronto tra le percentuali di successo di FEC e FEC+ARQ nel primo scenario
Il grado di ridondanza m influenza non solo il grado di affidabilità, ma anche le
prestazioni degli schemi in termini di latenza. Come osservabile nei grafici successivi,
relativi al primo scenario, FEC mostra un andamento crescente della latenza con m,
mentre FEC+ARQ presenta un grado elevato di latenza con valori piccoli di m (che
provocano aumento delle ritrasmissioni)
decrescente con m fino ad un certo punto,
quando poi l’aumento di m provoca un aumento complessivo dei pacchetti inviati soggetti
a perdite, provocando l’aumento del numero di ritrasmissioni necessarie.
Inoltre già in questo scenario si nota come la variabilità dello schema FEC molto inferiore
rispetto a quella dello schema FEC+ARQ.
93
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 39 - Andamento della latenza di FEC e FEC+ARQ nel primo scenario al variare di m
Figura 40 - IQR della latenza nel primo scenario
94
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Le osservazioni relative alla latenza del primo scenario si estendono anche agli altri,
come mostrato dai grafici che seguono (tali grafici sono normalizzati rispetto ai valori del
primo scenario):
Figura 41 - Latenza mediana dei 3 scenari con valori ottimali di m
Figura 42 - IQR della latenza nei 3 scenari con valori ottimali di m
95
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
I grafici precedenti mostrano l’andamento della latenza degli schemi FEC e
FEC+ARQ nei 3 scenari
con il valore di m ottimale determinato negli esperimenti
precedenti. Inoltre si è operato in questi grafici un confronto con l’ARQ del DDS sia in
termini di latenza mediana che di variabilità della latenza stessa.
I risultati mostrano chiaramente che FEC e FEC+ARQ esibiscono la stessa latenza
mediana nei 3 scenari (esattamente gli stessi valori in tutti e tre i casi) mentre la
variabilità, e dunque l’imprevedibilità dello schema, è molto superiore per FEC+ARQ.
Tale variabilità dipende dal numero di ritrasmissioni variabile che tende a far
aumentare la dispersione della latenza. Questo fenomeno è illustrato nell’immagine
seguente che mostra l’andamento della latenza degli schemi FEC e FEC+ARQ nel primo
scenario al variare delle pubblicazioni.
Figura 43 - Andamento della latenza nel primo scenario al variare delle pubblicazioni
I picchi presenti nell’andamento di FEC+ARQ provocano l’aumento della
dispersione statistica dei tempi di latenza, cioè una maggiore imprevedibilità.
96
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Un ulteriore test mirava a valutare la stabilità dell’ARQ del DDS al variare del
periodo di pubblicazione. I risultati di tale test sono mostrati nel grafico che segue:
Figura 44 - Instabilità del meccanismo di ritrasmissione del DDS
al variare del periodo di pubblicazione
Il DDS mostra un andamento della latenza crescente quando il periodo di
pubblicazione diventa troppo breve. La coda di invio del publisher cresce indefinitamente
al crescere delle pubblicazioni diventando instabile e provocando ritardi nella trasmissione
(e ritrasmissione dei messaggi).
97
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.3.5 Considerazioni
Nonostante i risultati della campagna mostrino la sostanziale efficacia dello schema
FEC in termini sia di prevedibilità che di affidabilità della consegna, l’approccio
complessivo si è mostrato troppo dipendente dal DDS sottostante.
Nel prosieguo del lavoro si è dunque adottato un cambio di approccio, passando allo
sviluppo di uno schema FEC operante a livello trasporto. Con lo spostamento del layer
FEC/FEC+ARQ al di sotto del DDS l’idea è di ottenere un maggiore disaccoppiamento
tra il middleware e lo schema di affidabilità, favorendo nel contempo l’integrazione nella
piattaforma stessa.
Lo svantaggio di tale approccio è la maggiore complessità: operare al livello
trasporto implica la sostanziale ridefinizione di tutti i meccanismi ed algoritmi di invio e
ricezione dei messaggi che nell’approccio al livello applicativo erano offerti dal DDS
sottostante.
3.4 Erasure Codes a livello trasporto
Il cambio di approccio operato a valle delle considerazioni sui risultati della fase
sperimentale ha comportato anche un cambio della piattaforma middleware utilizzata.
Si è passati dall’utilizzo di RTI DDS ad OpenDDS [2][3]. La scelta di OpenDDS è
stata dettata da vari fattori:
¾ è open-source:il codice C++ è liberamente consultabile e modificabile
secondo le esigenze;
¾ è portabile: OpenDDS è realizzato sulla piattaforma ACE (Adaptive
Communication Environment [33]) che si occupa della comunicazione e del
controllo;
98
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
¾ offre un pluggable transport framework che consente la realizzazione di
protocolli di trasporto adatti alle proprie esigenze
Realizzando dunque uno schema di affidabilità FEC nel contesto di un protocollo di
trasporto, è possibile poi effettuarne il plug-in nella piattaforma, in maniera trasparente al
DDS stesso ed alle applicazioni che interagiscono solo con il transport layer.
3.4.1 La piattaforma OpenDDS
OpenDDS è, come detto, una implementazione OpenSource dello standard OMG
DDS. Allo stato attuale implementa solo il livello DCPS dello standard.
Dal punto di vista architetturale si presenta come in figura seguente:
Figura 45 - L'architettura di OpenDDS
OpenDDS è realizzato al di sopra di ACE [33] per assicurare la portabilità della
piattaforma ed utilizza anche alcune funzionalità del middleware CORBA TAO quali ad
esempio le funzionalità del compilatore idl e come base per il DCPSInfoRepository.
Le entità DCPS accedono alle funzionalità del trasporto mediante il transport layer
che assicura trasparenza alle applicazioni rispetto al protocollo utilizzato. Le applicazioni
99
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
accedono alle funzioni offerte dall’interfaccia del layer e le implementazioni specifiche
dei protocolli restano nascoste. Allo stato attuale OpenDDS include 4 protocolli di
trasporto built-in: una implementazione UDP,una TCP,un multicast affidabile ed un
multicast non affidabile.
Dal punto di vista implementativo OpenDDS utilizza un thread per la
comunicazione con l’ORB mentre le comunicazioni di I/O non dirette verso l’ORB
avvengono in threads separati.
OpenDDS utilizza inoltre il DCPSInfoRepository come processo separato che
gestisce la comunicazione nei domini DDS. Tutti i partecipanti devono interagire
attraverso il DCPSInfoRepository (istanziato su un determinato nodo) che tuttavia resta al
di fuori del flusso dei dati.
Figura 46 - OpenDDS : DCPSInfoRepository
100
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.4.2 Il Pluggable Transport Layer di OpenDDS
OpenDDS utilizza il Pluggable Transport Layer come “collante” tra le applicazioni DDS
ed il particolare protocollo di trasporto scelto per l'applicazione stessa.
Questo permette di utilizzare il servizio di distribuzione dei dati con una varietà di
protocolli di trasporto senza apportare modifiche all'applicazione poichè essa “vede” solo
il Pluggable Transport Layer.
Figura 47 - Pluggable transport layer di OpenDDS
Allo stato attuale OpenDDS fornisce delle semplici implementazioni del protocollo
TCP,del protocollo UDP e di due protocolli di trasporto multicast,uno reliable ed uno non
reliable.
Il Pluggable Transport Layer consente agli sviluppatori di applicazioni di realizzare i
propri protocolli di trasporto personalizzati. L'implementazione di un protocollo
personalizzato consiste in breve nella specializzazione di un insieme di classi definite nella
101
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
cartella del Transport Framework,$DDS_ROOT/dds/DCPS/transport/framework.
Come è possibile intuire anche dall'immagine precendente,i protocolli di Trasporto (cioè
gli oggetti che permettono di accedere alle funzionalità protocolli di trasporto) sono
generati da un oggetto factory e vengono successivamente associati ai publishers ed ai
subscribers.
Il Pluggable transport layer ( o meglio,il transport framework) fornisce, come detto in
precedenza, l'insieme di classi da specializzare per la realizzazione di un
proprio
protocollo di trasporto in OpenDDS.
Il TransportFramework di OpenDDS non è standard in quanto allo stato attuale non è stata
effettuata alcuna richiesta di standardizzazione da parte degli sviluppatori di OpenDDS.
Questo ha tuttavia un impatto minimo sugli sviluppatori di applicazioni DDS poiché le
problematiche di trasporto risultano trasparenti ad essi.
Si è inoltre accennato al fatto che i protocolli di trasporto siano generati da un oggetto
Factory che si occupa di istanziare gli oggetti che forniscono accesso ai servizi del
particolare protocollo di trasporto usato.
All'interno del framework è dunque presente una particolare classe astratta,la
TransportImplFactory, specializzando la quale è possibile definire delle factory concrete
preposte alla creazione delle istanze dei propri oggetti di protocollo.
Il codice delle applicazioni utilizzerà poi i metodi forniti da questi ultimi per accedere alle
funzionalità del protocollo.
In realtà le applicazioni sono trasparenti ai differenti protocolli di trasporto in quanto esse
fanno riferimento,per l'utilizzo dei servizi di trasporto, ad un' interfaccia unica definita
anch'essa nel transport framework mediante la classe astratta TransportImpl. Da essa
infatti devono derivare i particolari protocolli realizzati, cioè gli oggetti concreti che la
factory dovrà istanziare.
102
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Di fatto quindi la realizzazione di un nuovo protocollo in OpenDDS avviene mediante un
Abstract Factory pattern ,cioè mediante un particolare schema di programmazione
secondo il quale un certo oggetto(concreto),derivante da un oggetto astratto che fa da
interfaccia, viene creato dalla corrispondente Factory che a sua volta deriva dalla Factory
astratta:
Figura 48 - Abstract Factory Pattern
Nel caso del framework di OpenDDS il diagramma presentato nella figura precedente si
particolarizza come segue:
103
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 49 - Abstract Transport Factory in OpenDDS
L'mmagine precedente riporta come classi concrete d'esempio le implementazioni di TCP
e di UDP presenti in OpenDDS;le corrispondenti Factory sono istanziate mediante una
classe concreta del framework,la TransportFactory.
In pratica nel file TheTransportFactory.h del framework è definito un oggetto di tipo
TransportFactory(chiamato “TheTransportFactory” )mediante il metodo statico instance();
tale oggetto costituisce il punto di accesso dell'applicazione alle funzionalità di creazione
degli oggetti concreti di TransportImplFactory e TranportImpl:
...............
namespace OpenDDS
{
namespace DCPS
{
104
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
#define TheTransportFactory OpenDDS::DCPS::TransportFactory::instance()
} /* namespace DCPS */
} /* namespace OpenDDS */
.................................................................
Qualora un publisher (o un subscriber) voglia ad esempio istanziare un proprio oggetto di
trasporto procederà come segue:
Figura 50 - Creazione di un oggetto concreto di trasporto
Il primo metodo invocato è un metodo di TheTransportFactory, create_transport_impl();le
operazioni successive sono invocate al suo interno e permettono di restituire al chiamante
un oggetto di tipo astratto TranportImpl associato però ad una particolare
implementazione
concreta
che
deve
essere
stata
precedentemente
realizzata.
105
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
3.5 Il prototipo di un protocollo di trasporto FEC-based per OpenDDS
In questo paragrafo sarà presentata il prototipo del protocollo di trasporto di cui si è
iniziata la realizzazione. Tale prototipo ha lo scopo principale di aprire una direzione di
sviluppo nuova per lo studio di schemi FEC in piattaforme DDS e non è, allo stato attuale,
un protocollo completo in ogni sua parte.
3.5.1 Scelte di progetto
Il prototipo è stato concepito come strato FEC sovrapposto al multicast non
affidabile dello stack TCP/IP (overlay FEC). Tale scelta è stata dettata dalla volontà di
utilizzare come supporto all’invio ed alla ricezione dei messaggi un’infrastruttura di rete
reale. Il prototipo è orientato al suo utilizzo su rete Internet, e non su una infrastruttura
dedicata, pertanto ha senso utilizzare un protocollo realmente implementato dai dispositivi
di rete come il protocollo IP multicast. Soluzioni analoghe sono state adottate da protocolli
precedentemente analizzati per le stesse motivazioni[13].
La stratificazione risultante è la seguente :
Figura 51 - FEC sovrapposto al multicast IP
106
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il prototipo è scritto in linguaggio di programmazione C++ e compilato come
librerie a collegamento dinamico (shared object in ambiente Linux[34]) alla stregua degli
altri protocolli di OpenDDS. Il collegamento dinamico permette alle applicazioni che
utilizzano i protocollo di non includere all’interno del proprio eseguibile il file oggetto
della libreria, ma solo un riferimento ad essa. La libreria(cioè il file oggetto della libreria)
sarà poi caricata dinamicamente durante l’esecuzione dell’applicazione[34].
Lo schema di funzionamento di base prevede che la codifica avvenga prelevando la
sequenza di bytes componenti la pubblicazione dalla struttura dati restituita dalle classi del
transport layer di OpenDDS. La codifica avviene immediatamente prima dell’invio su rete
in multicast IP.
Calcolata la dimensione in byte dei dati della pubblicazione, essi vengono suddivisi
in k blocchi (il valore di k dipende dalla dimensione complessiva dei dati e dai parametri
di codifica impostati). Ad essi è applicato un Erasure Code di tipo Reed-Solomon (lo
stesso utilizzato nel benchmark) con grado di ridondanza selezionato in precedenza.
In fase di ricezione, una volta ricevuti nel buffer dati almeno k blocchi si effettua la
decodifica. Se
3.5.2 Architettura complessiva
Nella sua versione definitiva, il prototipo dovrebbe presentare come punto di
accesso alle funzionalità di invio e ricezione la classe ErasureProtocolIF:
Figura 52 - Classe ErasureProtocolIF
107
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Tale classe dovrà offrire due semplici primitive, send() e receive, che nascondano
all’applicazione utente la complessità del protocollo. In pratica la realizzazione sarebbe
quella di un pattern façade. Le classi derivate dalla classe EventHandler,attualmente clase
astratta, dovrebbero poi definire delle specifiche logiche di invio e ricezione lato publisher
e lato subscriber. Allo stato attuale tali classi risultano non implementate o astratte.
108
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 53 - Il diagramma delle classi del prototipo
109
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
In questa versione del prototipo la logica di invio è gestita dalla sola classe
ErasureProtocolSocket, in cui avvengono anche le fasi di codifica e decodifica dei dati,
rispettivamente nei metodi send_bytes() e receive_bytes().
La classe che incapsula i meccanismi di codifica e decodifica è la classe Packet, il
cui diagramma è mostrato nell’immagine seguente:
Figura 54 - classe Packet per la gestione della codifica e decodifica dei dati
Il costruttore della classe Packet crea un oggetto che si occupa della codifica del
blocco di byte, inizializzando tutti i parametri necessari alla codifica e decodifica. In base
ai parametri inseriti come parametri all’atto della creazione dell’oggetto, il costruttore
alloca delle aree di memoria i cui verranno memorizzati i blocchi dato ed i blocchi di
codifica. Il costruttore lavora su un buffer di dati linearizzati che deve essere
110
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
opportunamente riempito dal blocco di byte dei dati da codificare mediante il metodo
addStream(). Esso costruisce inoltre le matrici che saranno utilizzate per la codifica e la
decodifica.
La classe Packet utilizza le funzioni delle libreria Jerasure analizzata in precedenza
per realizzare i metodi encode() e decode(). Il metodo encode() utilizza la matrice binaria
generata dal costruttore tramite la funzione di libreria apposita. Esso genera k+m blocchi
di dati codificati che vengono memorizzati separatamente in due array, uno di dimensione
k contenente i dati originari (il codice utilizzato è un codice sistematico) e l’altro di
dimensione m contente i blocchi di parità. Il metodo decode() suppone di avere a
disposizione almeno k blocchi disponibili nella struttura dati tra blocchi dato e blocchi di
parità. Nel caso in cui siano disponibili meno di k blocchi risulterà impossibile realizzare
la decodifica. Il metodo canDecode() si occupa di verificare questa condizione.
I metodi getData() e getCoding() sono utilizzati nella fase post-codifica per il
prelievo dei blocchi da inviare sulla rete, mentre i metodi addData() e addCoding() sono
utilizzati successivamente alla ricezione lato subscriber per effettuare poi la decodifica.
La classe che incapsula le logiche di invio e ricezione (nonché le fasi di codifica e
decodifica dei dati) è, come detto, ErasureProtocolSocket.
La classe ErasureProtocolSocket presenta nella struttura dati un oggetto di tipo
Ace_Sock_Dgram fornito dalla piattaforma ACE che mette a disposizione metodi di invio
e ricezione tipici delle socket di sistema[34](è sostanzialmente un wrapper). La
realizzazione del FEC overlay sul multicast IP avviene proprio in questa classe : la fase di
codifica, gestita mediante un oggetto di classe Packet, è immediatamente precedente
all’invio dei dati sulla socket a datagrammi, cui sarà passato come indirizzo di rete quello
del gruppo multicast utilizzato. Viceversa la fase di decodifica è immediatamente
successiva alla ricezione dei dati dalla socket da parte del subscriber.
111
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Il metodo send_bytes() elabora la struttura dati iovec iov[] (è l’array di puntatori ai
buffer dati contenenti i bytes della pubblicazione passato dal livello applicativo)
effettuando il conteggio dei bytes, inserendoli nella struttura dati di un oggetto Packet ed
applicando poi la codifica Reed-Solomon. I blocchi dato ed i blocchi codice vengono poi
utilizzati per riempire una struttura di tipo iovec che sarà inviata mediante il metodo send()
della ACE_Dgram_Socket_Mcast all’indirizzo IP multicast settato da file di
configurazione (NB:anche il numero di porto è settato tramite il medesimo file di
configurazione).
Il metodo receive_bytes() effettua la ricezione dei dati dalla socket multicast tramite
un buffer dati. Il contenuto di questo buffer è successivamente elaborato per estrarre i
pacchetti dato ed i pacchetti codice che saranno utilizzati per riempire la struttura dati di
un oggetto di classe Packet. Se sono stati ricevuti almeno k blocchi in totale, è possibile
effettuare la decodifica. Una volta decodificati i dati, essi vengono inseriti nella struttura
iovec iov[] data come parametro di ingresso/uscita alla funzione receive_bytes: tale
struttura permette di passare i dati alla classe del frame work TransportReceiveStrategy
che poi effettuerà una call-back sull’oggetto di trasporto per segnalare la ricezione di un
messaggio di cui effettuare il delivery (metodo delivery_sample() di TransportImpl)
3.5.3 Integrazione in OpenDDS
Oltre alle classi che includono la logica specifica del protocollo è stato necessario
definire un insieme di classi derivate da classi del transport framework di OpenDDS per
realizzare l’operazione di plug-in nella piattaforma.
112
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Le classi realizzate sono mostrate nel diagramma in fig. 53 e sono essenzialmente
quelle indicate nell’appendice, A dove è descritto il procedimento generale per la
realizzazione di un plug-in di trasporto.
Le classi sono :
¾ ErasureProtocolConfiguration: si occupa della configurazione dell’oggetto
protocollo mediante lettura dei parametri dai files di configurazione di
publisher e subscriber; nella sua versione definitiva si occuperà
dell’inizializzazione di tutti i parametri dei codici e degli indirizzi di rete;
¾ ErasureProtocolLoader: definisce l’oggetto preposto al caricamento della
libreria di trasporto da parte delle applicazioni;
¾ ErasureProtocolFactory: è la factory specializzata allo scopo di istanziare
oggetti di trasporto di tipo ErasureProtocolTransport;
¾ ErasureProtocolTransport: deriva dal TransportImpl e definisce un oggetto
concreto di trasporto che utilizza gli oggetti DataLink per l’invio e la
ricezione dei dati;esso si occupa inoltre di recuperare i parametri
¾ ErasureProtocolDataLink:si occupa di gestire il set di link dell’applicazione
che usa il protocollo mediante gli oggetti di Send e ReceiveStrategy;
¾ ErasureProtocolSendStrategy/ReceiveStrategy:
derivano
dalle
classi
astratte del framework con lo stesso nome e ne implementano i metodi
astratti di send_bytes e receive_bytes
meccanismo
di
trasporto;includono
necessari al funzionamento del
un
puntatore
alla
classe
ErasureProtocolSocket;
¾ ErasureProtocolSocket: in questa versione del prototipo l’EventHandler
preposto alla gestione degli eventi di invio e ricezione è realizzato da questa
113
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
classe derivata da ACE_Event_Handler[34] che realizza i metodi di
send_bytes e receive_bytes utilizzati dalle classi Send e Receive Strategy.
In particolare, in questa versione iniziale del prototipo l’EventHandler inizialmente
concepito è stato momentaneamente accantonato, realizzando una logica di invio più
semplice basata su una socket a datagrammi.
114
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Conclusioni e sviluppi futuri
I risultati ottenuti in sede sperimentale circa l’utilizzo di schemi di affidabilità FEC
in middleware di tipo DDS mostrano come tali schemi, in determinate condizioni di
funzionamento della rete, possano fornire una tolleranza alle perdite ed una prevedibilità
dei tempi di consegna in grado di soddisfare i requisiti dei sistemi mission-critical operanti
su scala geografica.
La prevedibilità dello schema FEC si è mostrata superiore sia a quella della
soluzione ibrida che a quella del protocollo basato su ARQ utilizzato dal DDS.
L’approccio inizialmente utilizzato prevedeva l’utilizzo dei FEC a livello
applicativo, sovrapposti cioè allo strato del DDS. Tale approccio, pur offrendo il pregio
della semplicità implementativa, ha esibito una elevata dipendenza dal DDS stesso.
Inoltre, operando al di sopra dello strato DDS non è stato possibile realizzare una reale
integrazione della soluzione FEC con il middleware.
Si è dunque operato un cambio di approccio, iniziando la realizzazione di un
protocollo di trasporto integrante schemi FEC per garantire l’affidabilità.
Operando al livello trasporto è possibile definire l’algoritmo di recupero dalle
perdite in maniera completamente indipendente dal DDS.
115
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Utilizzando il supporto offerto dalla piattaforma OpenDDS è stato possibile
realizzare un plug-in per l’integrazione del prototipo nella piattaforma stessa.
Le evoluzioni future del presente lavoro riguardano lo sviluppo del prototipo del
protocollo che dovrebbe portare alla realizzazione di un protocollo di trasporto completo
FEC-based per middleware DDS.
In tale protocollo dovrebbero inoltre essere integrate differenti librerie di codici FEC
(es. ReedSolomon,LDPC) per offrire capacità di adattamento alle necessità delle differenti
applicazioni. Resta inoltre da testare la scalabilità della soluzione FEC al crescere del
numero dei subscriber, avendo effettuato in questa sede test basati su un unico publisher
ed un unico subscriber.
116
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
117
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Appendice A
Realizzazione di un plug-in di trasporto in OpenDDS
A.1 Utilizzo del Transport Framework di OpenDDS
In questo paragrafo si illustreranno i passaggi fondamentali per la realizzazione di
un plug-in per un protocollo di trasporto mediante le classi fornite dal transport
framework. A tal scopo saranno utilizzati gli esempi del protocollo Simple Udp di Open
DDS e del plugin C++ per il protocollo Ricochet[9].
La classe astratta TransportImpl definisce le funzionalità che un oggetto concreto di
trasporto deve offrire alle applicazioni. Il diagramma della classe è il seguente:
118
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 55 - La classe TransportImpl
La classe include metodi per l'invio e la ricezione dei dati,la configurazione del trasporto,la
gestione dei datalinks e delle associazioni tra oggetti locali e remoti.
I metodi astratti fondamentali che devono essere implementati dalle classi derivate
allo scopo di realizzare un oggetto trasporto concreto sono:
z
find_or_create_datalink(): é un metodo protetto richiamato dal metodo pubblico
reserve_datalink,il quale restituisce un puntatore ad un oggetto DataLink(si
anticipa brevemente che gli oggetti DataLink sono gli oggetti che incapsulano le
logiche di invio e ricezione dei messaggi e che si fanno carico di stabilire la
119
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
connessione tra le entità remote dell'applicazione);tale metodo deve reperire(parte
find del metodo)un datalink esistente oppure,se necessario,crearne uno(parte
create)
tenendo
presente
il
valore
del
paramentro
di
ingresso
connect_as_publisher: se tale parametro ha valore '1' allora sarà necessario creare
una connessione attiva per conto di un publisher verso un subscriber
remoto,mentre se ha valore '0' sarà necessario creare una connessione passiva lato
subscriber .
(Es:per Ricochet e SimpleTcp la parte find è realizzata mediante il metodo
find(ACE_INET_Addr) richiamato sulla struttura dati AddrLinkMap che altro non
è che una tabella hash che utilizza come chiave l'ACE_INET_Addr associato al
particolare DataLink,che costituisce dunque il value della struttura hash).
(NB : si noti che nella parte create(),che viene eseguita solo se la parte find non
restituisce DataLinks , dopo la creazione del DataLink bisogna effettuare il binding
con l'indirizzo IP-nel caso di Ricochet ad esempio è l'indirizzo del gruppo-tramite
il metodo bind(key,value) invocato sulla struttura hash)
z
configure_i():è
un
metodo
protetto
invocato
dal
metodo
pubblico
configure();consente di effetturare delle operazioni aggiuntive all'atto della
configurazione del protocollo(si noti che non è possibile eseguire l'attachment di
alcun oggetto di trasporto non configurato da parte di publishers o
subscribers,dunque l'operazione di configurazione è da invocare appena dopo la
creazione dell'oggetto di trasporto concreto).
z
shutdown_i/connection_info_i/release_datalink_i: sono metodi invocati dai
quasi-omonimi (non presentano la “i”) metodi pubblici che permettono allo
sviluppatore di aggiungere ulteriori operazioni ritenute necessarie.
Un oggetto fornente un servizio di trasporto deve dunque derivare da questa
classe,TransportImpl,
deve
implementarne
i
metodi
astratti(principalmente
120
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
find_or_create_datalink) e può poi fornire ulteriori metodi specifici del protocollo
implementato. Ad esempio,il plug-in del protocollo Ricochet per OpenDDS aggiunge il
metodo
deliver_sample per gestire i dati in arrivo dalla rete.
Le applicazioni utilizzano poi i servizi di trasporto senza tener conto delle particolari
implementazioni poiché accedono ad oggetti della classe base. Inoltre è necessario
eseguire l'attachment dell'oggetto di trasporto ad un oggetto di tipo TransportInterface.
Tale classe definisce i metodi effettivamente
accedere ai servizi del livello trasporto e costituisce il
usati dalle entità del DCPS per
meccanismo
attraverso il quale l'applicazione invia i dati ai sottoscrittori e
principale
gestisce le associazioni
tra pubblicazioni e sottoscrizioni. La classe fornisce metodi per eseguire l'attachment ed il
detachment degli oggetti concreti
di
protocollo(attach_trasport
è
quello
invocato
dall'applicazione per collegare il trasporto alla particolare entità DCPS) , metodi per
gestire l'invio di data samples e di messaggi di controllo( send() e send_control() ) e per
gestire pubblicazioni e sottoscrizioni(add_subscriptions()/add_publications()).
Figura 56 - La classe TransportInterface
121
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Vale la pena notare che in OpenDDS le implementazioni delle entità DCPS
Publisher e Subscriber,definite nello standard DDS mediante le omonime interfacce,
derivano anche da
TransportInterface,ed è dunque tramite esse che si effettua
l'attachment del protocollo di trasporto all'applicazione.
Figura 57 - Publisher, Subscriber e TransportInterface
All'interno dell'oggetto di trasporto è necessario implementare una classe derivata da
DataLink,classe del framework che incapsula le logiche di invio e ricezione dei messaggi
,definite
a
loro
volta
tramite
le
classi
TransportSendStrategy
e
TransportReceiveStrategy.
Gli oggetti di tipo DataLink delegano in sostanza l'invio dei data samples agli
oggetti di tipo TransportSendStrategy e la loro ricezione, nonché il delivery dei messaggi
all'applicazione, agli oggetti di tipo TransportReceiveStrategy.
122
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Un oggetto DataLink è sempre creato da un oggetto di tipo TransportImpl il cui
puntatore è passato come argomento al costruttore del DataLink.
Figura 58 - Classe DataLink
L'oggetto
derivato
da
DataLink
costituisce,
accanto
agli
oggetti
TransportSendStrategy e TransportReceiveStrategy, il “cuore” della logica di qualsiasi
protocollo di trasporto: è in queste classi che vanno definite le dinamiche comportamentali
del
protocollo
rispetto
all'invio
e
la
ricezione
dei
messaggi,alla
eventuale
ritrasmissione,alla eventuale necessità di effettuare una connessione (Es: il plug-in per
TCP di OpenDDS utilizza un oggetto SimpleTcpConnection per gestire la connessione e
123
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
le disconnessioni,tale oggetto inoltre concettualmente sostituisce l'astrazione della Socket;
Ricochet incapsula l’oggetto RicochetIF, che è l’interfaccia reale del protocollo,
all’interno del RicochetDataLink).
Le classi derivate utilizzeranno il metodo protetto start() della classe base DataLink
per comunicare alla classe base che l'oggetto datalink concreto è ora “connesso” e per
invocare l'attivazione delle strategie di invio e ricezione.
Normalmente l'invocazione del metodo start (i cui argomenti sono proprio i
puntatori alle strategie di invio e ricezione)avviene all'interno di un metodo connect()
opportunamente definito dalla classe derivata.
Ad es. nel caso di Ricochet:
int
OpenDDS::DCPS::RicochetDataLink::connect(bool is_publisher)
{......................................
start (this->send_strategy_,
this->receive_strategy_);
……………
}
(NB:RicochetDataLink deriva ovviamente da DataLink).
Anche i protocolli TCP ed UDP implementati in OpenDDS aggiungono una funzione
connect() alle proprie implementazioni del DataLink per effettuare l'attivazione della Send
e Receive Strategy.
Oltre al già citato connect, i metodi fondamentali degli oggetti di tipo DataLink sono:
z
make_reservation(): questo metodo,esistente in due versioni diverse a seconda sia
il publisher o il subscriber ad essere remoto,è invocato dagli oggetti TransportImpl
per assegnare un certo DataLink ad una coppia publisher-subscriber;
z
send_start(),send(),send_stop():
questi
metodi
sono
invocati
dall'oggetto
124
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
TransportInterface che referenzia il particolare DataLink per inviare un data
sample o un messaggio di controllo ;
z
remove_sample(): è una sorta di undo_send() in quanto rimuove dal DataLink ogni
traccia del messaggio passato come primo argomento;
Per definire le strategie di invio e ricezione dei messaggi è necessario effettuare
l'overriding
di
alcuni
metodi
delle
classi
TransportSendStrategy
e
TransportReceiveStrategy.
Definita
una
classe
derivata
da
TransportReceiveStrategy
(ad
es.,
SimpleUdpReceiveStrategy) ridefiniamo:
z
receive_bytes (): metodo da definire per prelevare i bytes in ingresso.
z
deliver_sample (): metodo di call-back invocato per effettuare la consegna dei
messaggi all’oggetto TransportImpl.
z
start_i (): metodo per attivare la ricezione dei dati.
z
stop_i (): metodo per fermare la ricezione dei dati.
Definita
una
classe
derivata
da
TransportSendStrategy(Ad
es,SimpleUdpSendStrategy),ridefiniamo:
z
stop_i (): metodo per arrestare l'invio dei dati.
z
send_bytes () :metodo da implementare per gestire l'invio dei dati.
z
get_handle () :metodo che restituisce un handle
z
send_bytes_i (): metodo invocato da send_bytes() : effettua il lavoro reale di
invio dei bytes.
É inoltre necessario implementare una classe del tipo MySocket(Ad es.
125
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
SimpleUdpSocket) che derivi da ACE_Event_Handler [33](cioè un gestore degli
eventi) e che offra i seguenti metodi:
z
get_handle (): metodo di cui effettuare l'ovverride perchè ritorni un handle
appropriato del gestore eventi
z
handle_input ():metodo di cui effettuare l'ovverride per passare il controllo
alla receive strategy
z
handle_close ():metodo di cui effettuare l'override per gestire la chiusura della
socket
z
set_receive_strategy ():aggiunta di questo metodo per settare la receive
strategy.
z
remove_receive_strategy ():aggiunta di questo metodo per rimuovere la
receive strategy
z
open_socket ():aggiunta di questo metodo per aprire la socket
z
close_socket ():aggiunta di questo metodo per chiudere la socket
z
send_bytes():aggiunta di questo metodo per l'invio dei bytes dei dati.
Inoltre l'oggetto MySocket normalmente conterrà nella struttura dati una socket vera
e propria fornita dall'ACE sottostante(ad es,SimpleUdpSocket ha una variabile membro
private del tipo ACE_SOCK_Dgram,cioè una socket a datagrammi incapsulata in una
struttura ad oggetti dell'orb). Più in generale, è necessario implementare un gestore degli
eventi di invio e ricezione dei bytes di dati che fornisca tali servizi ai metodi receive_bytes
e send_bytes delle Receive e Send Strategy.
Le relazioni tra le classi si possono così schematizzare(anche se sono possibili variazioni
di questo schema ):
126
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 59 - DataLink,SendStrategy ,ReceiveStrategy e Socket
L'implementazione dei suddetti metodi dipende dal protocollo che si
intende
realizzare.
Ad esempio, il SimpleUDP di OpenDDS implementa il metodo send_bytes() della
SendStrategy
semplicemente
richiamando
il
metodo
della
TransportSendStrategy non_blocking_send()(il quale a sua volta richiama il
classe
base
metodo
send_bytes_i(),da implementare nella classe derivata,e che risulta essere quindi ,in ultima
istanza,l'unico metodo che realizza l'invio effettivo dei dati;esso infatti è invocato da tutti
i metodi di invio definiti nella TransportSendStrategy):
ssize_t
OpenDDS::DCPS::SimpleUnreliableDgramSendStrategy::send_bytes(const iovec iov[], int
n, int& bp)
{
............................
return this->non_blocking_send (iov, n, bp);
}
127
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Mentre la send_bytes_i() è implementata semplicemente richiamando il metodo di
invio dell'oggetto SimpleUdpSocket:
ssize_t
OpenDDS::DCPS::SimpleUnreliableDgramSendStrategy::send_bytes_i (const iovec iov[],
int n)
{
//socket_
è
il
puntatore
all'oggetto
SimpleUdpSocket
contenuto
nell'oggetto
SimpleUnrealiableDgramSendStrategy
return this->socket_->send_bytes(iov, n, this->remote_address_);
}
La send_bytes della socket è in sostanza una send() richiamata sull'oggetto
ACE_SOCK_Dgram incapsulato dalla SimpleUdpSocket(ACE_SOCK_Dgram è in
sostanza la struttura dell'orb ACE sottostante che wrappa la socket del sistema operativo):
ACE_INLINE ssize_t
OpenDDS::DCPS::SimpleUdpSocket::send_bytes(const iovec iov[],
int n,
const ACE_INET_Addr& remote_address)
{
........................................
return this->socket_.send(iov,n,remote_address);
}
La struttura iovec iov[] passata come parametro di ingresso contiene i riferimenti all’array
di buffer istanziati dalla classe astratta del framework TransportSendStrategy e
contengono la sequenza di bytes dei dati della pubblicazione dell’applicazione publisher.
128
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Nel
caso
del
protocollo
Ricochet
invece
la
send_bytes
della
RicochetSendStrategy
non utilizza la RicochetSocket(,utilizza invece il metodo di
invio definito dall'oggetto
RicochetIF ,che
all'algoritmo di trasporto
implementato da Ricochet:
rappresenta
il
punto
di
accesso
ssize_t
OpenDDS::DCPS::RicochetSendStrategy::send_bytes(const iovec iov[],
int n,
int& bp)
{..........................
this->ricochet_->send (byte_ptr,
bytes_len);
.....................
}
Dove “ricochet” è il puntatore
all'oggetto di tipo RicochetIF utilizzato dalla
RicochetSendStrategy;
Quindi il diagramma delle classi di cui sopra nel caso del protocollo Ricochet è
leggermente diverso,includendo anche la classe RicochetIF che effettua le reali operazioni
di invio e ricezione secondo la logica definita dall'algoritmo:
Figura 60 - Ricochet :classi per l'invio e la ricezione dei dati
129
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Le RicochetSocket non vengono dunque utilizzate in quanto l'invio e la ricezione
dei messaggi sono gestiti tramite l'oggetto RicochetIF(NB:nella libreria che implementa
l’algoritmo di Ricochet è comunque presente un gestore degli eventi di invio e ricezione
che è funzionalmente analogo agli EventHandler degli altri protocolli).
L'invio avviene ,come detto in precedenza, tramite il metodo send() dell'oggetto
RicochetIF usato dalla RicochetSendStrategy,mentre per la ricezione ed il delivery dei
messaggi si utilizza un meccanismo di callback:
1. la RicochetReceiveStrategy invoca il metodo join() di RicochetIF per inserire nel
gruppo multicast di Ricochet l'oggetto RicochetCallback a cui è associato(tale
oggetto è un MessageHandler) ;
2. Quando ci sarà un messaggio di cui effettuare il delivery,RicochetReceiveStrategy
invocherà il deliverSample() dell'oggetto RicochetCallback che attiverà le
operazioni di ricezione e delivery da parte dell'oggetto RicochetReceiveStrategy
cui è associato.
Riepilogando,un oggetto concreto che fornisca un servizio di trasporto per OpenDDS deve
essere un oggetto di una classe derivata da TransportImpl,la quale necessita a sua volta di
oggetti DataLink ,Receive e Send Strategy e gestori degli eventi ( opportunamente
specializzati a seconda del protocollo.
Resta da chiarire come avvenga il passaggio dei dati dall’applicazione DDS al livello di
trasporto. Il diagramma di sequenza illustrato nella figura 62 ricostruisce tale passaggio.
L’interazione tra le classi avviene nelle seguenti fasi:
130
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
1) All’atto della pubblicazione l’applicazione publisher invoca una write() sull’oggetto
DataWriter specializzato per il particolare Topic passando come argomento di
ingresso un puntatore all’oggetto che rappresenta la publlicazione; tale DataWriter
è generato automaticamente dalla pubblicazione del file .idl in cui si definisce la
struttura dati della pubblicazione.
2) Il DataWriter utilizza il metodo dds_marshal() per costruire un oggetto di tipo
DataSample a partire dall’oggetto della pubblicazione passato come parametro di
ingresso(NB: il DataSample è un alias che individua un Ace_Message_Block, la
classe per la gestione dei messaggi in ACE)
3) Il DataWriter invoca poi una write() sull’oggetto di tipo DataWriterImpl
(implementazione dell’interfaccia DataWriter dello standard DDS) in esso
incapsulato passando un puntatore all’oggetto DataSample creato al passaggio
precedente;
4) Il DataWriterImpl invoca il proprio metodo create_sample_data_message() per
creare un oggetto DataSample a partire dai dati individuati dal riferimento avuto in
ingresso al passaggio precedente;
5) Il DataWriterImpl accoda l’oggetto appena creato alla struttura dati dell’oggetto
WriterDataContainer (oggetto contenuto nel DataWriterImpl che gestisce le
strutture dati dei samples inviati e da inviare)mediante invocazione del metodo
enqueue();
6) Il DataWriterImpl segnala la disponibilità di un nuovo sample al livello di
trasporto,invocando il metodo data_available() dell’oggetto TransportInterface
(NB: poiché, come visto, in OpenDDS le entità DCPS Publisher e Subscriber
derivano anche da TransportInterface, tale invocazione avviene sull’oggetto
Publisher che contiene il DataWriter stesso che invoca il metodo);
131
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
7) L’oggetto TransportInterface richiede il DataSample segnalato all’oggetto
DataWriterImpl che ne ha segnalato la disponibilità mediante il metodo
get_unsent_data();
8) Il
DataWriterImpl
a
sua
volta
recupera
tale
DataSample
dall’oggetto
WriterDataContainer invocando il metodo omonimo e lo restituisce all’oggetto
TransportInterface (NB: la restituzione del DataSanoke non è raffigurata per non
appesantire eccessivamente il diagramma);
9) L’oggetto TransportInterface invoca il proprio metodo protetto send() per effettuare
l’invio del DataSample;
10) Il metodo send() a sua volta invoca il metodo send() dell’oggetto DataLink riferito
da TransportInterface;
11) Il DataLink, come detto in precedenza, delega l’invio dei dati alla classe
TransportSendStrategy, di cui invoca il metodo send(), passando come argomento
di ingresso il DataSample contenente i dati della pubblicazione;
12) Nel metodo send() di TransportSendStrategy viene aggiunto un header di livello
trasporto al DataSample ed invocato il metodo send_packet() della classe stessa;
13) Il metodo send_packet() costruisce una struttura dati di tipo iovec* contenente i
dati del DataSample ricevuto in ingresso rappresentati mediante un semplice array
di bytes;esso invoca successivamente per l’invio di tale array il metodo
send_bytes() della classe TransportSendStrategy passando la struttura iovec appena
creata come paramentro di ingresso;
14) come
visto
in
precedenza,il
metodo
send_bytes()
della
classe
TransportSendStrategy invoca il metodo omonimo della classe derivata dello
specifico protocollo, nel quale devono essere implementati i meccanismi di invio
effettivo dei dati al destinatario.
132
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
La ricezione dei messaggi avviene con una sequenza di operazioni analoga, partendo dalla
ricezione dei dati come sequenza di bytes acquisiti dalla rete, risalendo fino alle classi di
livello trasporto ed applicativo.
133
Tecniche per l’affidabilità delle comunicazioni basate su codici FEC in piattaforme
middleware OMG DDS
Figura 62 - Passaggio dei dati dall'applicazione al trasporto
134
135
Ringraziamenti
Questo è per me il paragrafo più bello ed insieme difficile da scrivere. In questi
lunghi anni di università (adesso non stiamo lì a contare quanti…) la mia vita ha incrociato
quella di numerosissime persone, così tante che sarebbe un’impresa davvero ardua
ricordarle tutte e descrivere nello spazio di poche righe il significato dei momenti che con
esse ho condiviso ed il contributo che esse hanno realmente dato alla crescita dell’uomo
Angelo prima che dello studente Angelo.
Altrettanto arduo sarebbe evitare di stilare una sorta di graduatoria, una classifica
che renda più merito a qualcuno piuttosto che ad altri, magari basata sul numero di parole
da me spese per ognuno. Pertanto, non troverete tanti nomi tra queste parole, e sono sicuro
che le poche eccezioni mi saranno perdonate dai numerosissimi “assenti”.
Sono altrettanto sicuro del fatto che, pur non trovando il proprio nome, le persone
che leggeranno queste parole riusciranno a ritrovarsi in esse, nel modo più intimo
possibile, come piace a me.
Un ringraziamento particolare va ad un’eccezione, la mia famiglia, cui questo lavoro
è dedicato. In questi anni mio padre, mia madre, Maria e Luciano sono stati un punto di
riferimento insostituibile, un sostegno continuo sia dal punto di vista economico
(principalmente mamma e papà :-) ) che morale. Difficilmente sarei arrivato a questo
136
risultato senza anche uno soltanto di loro, nonostante in questi anni non abbia fatto troppo
per dimostrare l’importanza che per me hanno avuto durante questo percorso.
Molto di quel che sono ora (e che sembra piacere!) è merito loro, e questo è un
contributo che nessuna dedica o nessun ringraziamento potrà mai ripagare abbastanza.
Ovviamente anche il resto della mia famiglia rientra in questi ringraziamenti, ma
nonni, zii, cugini e tutti i familiari che mi hanno sempre stimato e appoggiato durante le
mie avventure/sventure universitarie costituiscono, per numero, una sorta di grande tribù
che non riuscirei mai ad incastrare in queste poche pagine. Grazie, a tutti voi.
Come ulteriore eccezione, vorrei ringraziare chi mi ha seguito da vicino nello
sviluppo di questo lavoro, i miei correlatori Ing. Christian Esposito e Ing. Generoso
Paolillo, per me semplicemente Chris e Gene, per la fiducia che hanno continuato a
mostrarmi fino alla fine, per il sostegno offertomi e per il contributo finale che hanno dato
alla mia crescita come studente.
Mi preme poi ricordare i due docenti che più hanno contribuito alla mia formazione.
Ringrazio dunque il prof. Cotroneo per la stima incondizionata mostratami in questi anni
e per aver reso, con la sua simpatia, più sopportabili le lunghe giornate trascorse in
laboratorio durante il lavoro di tesi.
Un ringraziamento sentito va al prof. Russo, soprattutto per aver aiutato quella
matricola un po’ spaesata che iniziò questa avventura a capire che il corso di studi scelto
poteva esser quello giusto, e per aver contribuito in maniera decisiva, nel corso degli anni
successivi, alla mia maturazione come studente.
Un pensiero va poi a tutti coloro che, conosciuti all’università, hanno affrontato
insieme a me almeno una parte del mio percorso di studente. Tra questi è incluso anche
chi con me ha soltanto preso un caffè, scambiato una chiacchiera, giocato a pallone o in
altro modo contribuito a rendere più piacevole questo percorso di per sé denso di
137
difficoltà, regalandomi momenti di allegria e di confronto intellettuale. Durante questi
anni ho spesso dato l’impressione, a tanti, di non dare importanza eccessiva a tutto questo,
e mi piace pensare che qualcuno potrà finalmente avere il riconoscimento che merita
leggendo queste parole.
Allo stesso modo mi hanno aiutato tutti gli extra-ingegneri (mi metto anche ad
inventare parole ora…), alcuni dei quali fanno parte della mia vita da tempo immemore, e
che hanno avuto il merito unico di tenere sempre vive parti di me importanti quanto la
“parte ingegnera”. Sarebbe per me impossibile immaginare la mia vita senza di voi, siete
importanti già ora e posso ben sperare che lo sarete anche in futuro. Qualcuno di voi forse
storcerà un po’ il naso all’inizio non leggendo il proprio nome, ma conto, come ho fatto in
tutti questi anni (e per qualcuno, soprattutto negli ultimi mesi ;-) ), sulla vostra capacità di
sopportare il mio carattere particolare.
Un pensiero agrodolce va infine a tutte le persone che hanno fatto parte della mia
vita anche solo per brevi periodi e che ora, per un motivo o per un altro, sono su binari
paralleli. Probabilmente esse non leggeranno mai queste parole, ma so bene che senza
alcune di loro non sarei qui ora e non sarei la persona che sono. Grazie.
138
139
Bibliografia
[1]
RTI 2006 “RTI Data Distribution Service - The Real-Time Publish-Subscribe
Middleware User’s Manual”
[2]
Object Computing Inc. 2007 “TAO Developers guide Excerpt : chapter 31-Data
Distribution Service ”
[3]
OCIWeb 2008 www.opendds.org
[4]
G. Pardo-Castellote 2003 “OMG Data-Distribution Service:Architectural
Overview”,In Proceedings of the 23rd International Conference on Distributed
Computing System,5 2003
[5]
Object Management Group 2007 “Data Distribution Service for Real Time
Systems”,OMG Specification version 1.2,
http://www.omg.org/technology/documents/dds_spec_catalog.htm
[6]
A.Corsaro,L.Querzoni,S,Scipioni,S.Tucci Piergiovanni e A.Virgillito, 2006 “Quality
of service in Publish/Subscribe Middleware”. Global Data Management , 5 2006, .
[7]
L.Rizzo, 1997 “Effective Erasure Codes for Reliable Communication Protocols”.
140
ACM SIGCOMM Computer Communication Review, 27(2):24–36, Aprile 1997
[8]
D.Li e D.R.Cheriton 1999 “Evaluating the Utility of FEC with Reliable Multicast”
In Proceedings of Seventh International Conference on Network Protocols (ICNP),
pp. 97-105, Ottobre-Novembre, 1999.
[9]
M. Balakrishnan, K.P. Birman, A.Phanishayee, S.Pleisch 2007 “Ricochet: Lateral
Error Correction for Time-Critical Multicast”. In NSDI 2007: Fourth Usenix
Symposium on Networked Systems Design and Implementation, 2007.
[10] L.Rizzo,L. Vicisano 1997 “A Reliable Multicast data Distribution Protocol based on
software FEC techniques (RMDP)”,ACM SIGMOBILE Mobile Computing and
Communications Review, 2(2):23–31, Aprile 1998
[11] M. Balakrishnan, S. Pleisch, K. Birman. 2005 ” Slingshot: Time-critical multicast for
clustered applications.” In IEEE Network Computing and Applications
[12] J. Nonnenmacher, E. Biersack, and D. Towsley. 1997 “Paritybased loss recovery for
reliable multicast transmission”. In Proceedings of the ACM SIGCOMM ’97
conference, pg. 289–300, New York, NY, USA, 1997. ACM Press.
[13] J. W. Byers, M. Luby, M. Mitzenmacher, A. Rege. 1998 “A digital fountain
approach to reliable distribution of bulk data”. In ACM SIGCOMM ’98 Conference,
pp. 56–67,New York, NY, USA,1998. ACM Press
[14] M. Luby,M. Mitzenmacher,M. A. Shokrollahi, D. Spielman, V. Stemann, 1997
“Practical loss-resilient codes,” in Proc. 29th Annu. ACM Symp. Theory of
Computing, 1997, pp. 150–159.,
141
[15] L. Vicisano, L. Rizzo, J. Crowcroft. 1998 “TCP-like congestion control for layered
multicast data transfer.” In Proc. of INFOCOM ’98, San Francisco, Aprile 1998
[16] Jim Gemmell 1997, “Scalable Reliable Multicast Using Erasure-Correcting Resends”, Microsoft Research Technical Report, MSR-TR-97-20, 30 giugno 1997.
[17] M. Luby, L. Vicisano, J. Gemmell, L. Rizzo, M. Handley, J. Crowcroft.2002” The
Use of Forward Error Correction (FEC) in Reliable Multicast”. RFC Editor ref:RFC3453,
2002.
[18] S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, 1997 "A Reliable Multicast
Framework for Light-weight Sessions and Application Level Framing", IEEE/ACM
Transaction on Networking, Dic.1997 vol.5 no.6 p.784-803
[19] L.Berardi 1994 “Algebra e teoria dei codici correttori”,Franco Angeli ed.
[20] J.H. van Lint 1992 “Introduction to Coding Theory”,2nd ed. Springer-Verlag
[21] L.Rizzo 1997 “On the feasibility of software FEC”,DEIT Technical Report LR970131
[22] L. Rizzo. 1997 “Effective Erasure Codes for Reliable Computer Communication
Protocols”. ACM SIGCOMM Computer Communication Review, 27(2):24–36,
Aprile1997
[23] J.S. Plank and Y. Ding. 2005 “Note: Correction to the 1997 tutorial on ReedSolomon Coding”. Software Practice & Experience, 35(2):189194,Febbraio 2005
142
[24] R.L. Collins and J.S. Plank. 2005 “Assessing the Performance of Erasure Codes in
the Wide-Area”. Proceedings of the IEEE International Conference on Dependable
Systems and Networks (DSN 2005), pp. 182–187, Giugno-Luglio 2005.
[25] Northrop, L., Feiler, P., Gabriel, R. P., Goodenough, J., Linger, R., Longstaff, T., et
al. 2006 “Ultra-Large-Scale Systems: The Software Challenge of the Future”.
Pittsburgh, PA: Software Engineering Institute, Carnegie Mellon University.
http://www.sei.cmu.edu/uls/uls.pdf
[26] J. S. Plank. 1997 “A tutorial on Reed-Solomon coding for fault-tolerance in RAID-l
ike systems.” Software – Practice & Experience, 27(9):995–1012, Settembre 1997.
[27] Bernhard M. J. Leiner 2005 "LDPC codes - a Brief Tutorial", Aprile 2005.
[28] Gordon McDonald 2006 “Low Density Parity Check Codes”,21 Aprile 2006
[29] R. Baldoni, R. Beraldi, S. Tucci Piergiovanni, A. Virgillito 2004
“Measuring
notification loss in publish/subscribe communication systems” In Proceedings of the
10th International Symposium Pacific Rim Dependable Computing (PRDC ’04)
[30] P.Th. Eugster, P. A. Felber, R. Guerraoui, and A. Kermarrec. 2003 “The many faces
of publish/subscribe.” ACM Computing Surveys (CSUR), 35(2):114–131, Gennaio
2003.
[31] R. Joshi , G. Pardo-Castellote 2006 “OMG's Data Distribution Service Standard:
An overview for real-time systems”, http://www.ddj.com/architect/194900002
143
[32] J.S. Plank 2007 “Jerasure: A Library in C/C++ Facilitating Erasure Coding for
Storage Applications.” Technical Report UT-CS-07-603, Department of Computer
Science,University of Tennessee, Settembre 2007,
http:/www.cs.utk.edu/~plank/plank/papers/CS-07-603.html
[33] D. Schmidt, ACE – the Adaptive Communication
Environment
http://www.cse.wustl.edu/~schmidt/ACE.html
[34] M. Mitchell, J. Oldham, Alex Samuel 2001 “Advanced Linux
Programming”,
ed. Sams Publishing
[35] D.C. Schmidt, S.D. Huston 2002 “C++ Network Programming:
Mastering
Complexity Using ACE and Patterns”, ed. Addison-Wesley Longman
[36] E. N. Gilbert, 1960 “Capacity of a Burst-Noise Channel,” Bell System Technical J
Journal, vol. 39, pp. 1253–265,Sep 1960.
[37] S.Guruprasad, R. Ricci, J. Lepreau 2005 “Integrated Network Experimentation
using Simulation and Emulation”, In Proceedings of the First International
Conference on Testbeds and Research Infrastructures for the DEvelopment of
NeTworks and COMmunities (TRIDENTCOM’05)
[38] Dilip V. Sarwate, Naresh R. Shanbhag 2001 “High-Speed Architectures for Reed–
Solomon Decoders”,In IEEE Transactions on Very Large ScaleIintegration (VLSI)
systems, vol. 9, no. 5, Ottobre 2001
144
[39] J. P. Macker 1997 “Reliable multicast transport and integrated erasure-based
forward error correction”, In Proceedings IEEE MILCOM, p. 973-7 vol.2,
Novembre 1997
[40] G. Coulouris, J. Dollimore , T. Kindberg 2005 "Distributed Systems: Concept and
Design" 4th ed.
145