Realizzazione di un co/decodificatore Raptor per servizi multimediali

2 Introduzione
poi fruiti su richiesta, dando così l’illusione di una trasmissione istantanea),
servizi di broadcast locale (ad esempio informazioni all’interno di un museo),
ecc.
Affinchè tutto ciò si realizzi devono però essere risolti alcuni problemi di
carattere tecnico, ma anche commerciale. Tralasciando gli aspetti commer-
ciali, che vanno al di là degli scopi di tale dissertazione, ci soffermeremo sugli
aspetti più prettamente tecnici.
La fruizione di contenuti video su terminali mobili pone sfide tecnologiche
diverse rispetto a quelle relative alla televisione terrestre. Per rispondere a
queste sfide sono state ad oggi sviluppate tre principali famiglie di tecnologie
radio:
• Il sistema S-DMB (Satellite Digital Multimedia Broadcast), una tec-
nologia ibrida che impiega un satellite geo-stazionario ed una rete co-
locata con le “mobile stations” della rate cellulare per fornire una coper-
tura urbana indoor non ottenibile tramite il solo utilizzo del satellite.
• Il DVB-H, sostanzialmente una risposta del DVB Forum all’UMTS.
Tale tecnologia fa largo riuso del DVB-T (il riferimento per il Digitale
Terrestre in Italia) e cerca di risolvere le problematiche di consumo
delle batterie e di progettazione d’antenna che il DVB-T pone ad un
terminale mobile.
• L’MBMS (Multimedia Broadcast/Multicast Service), definito in ambito
3GPP. Si tratta di un servizio in grado di ottimizzare la trasmissione
di contenuti di tipo streaming e download in modalità Broadcast o
Multicast sia per l’accesso GSM/EDGE che per quello UMTS.
È dunque questo lo scenario delle tecnologie a disposizione per consentire la
fruizione di contenuti video su terminali mobili ed è questo lo scenario che
costituisce lo sfondo di questa dissertazione. In particolare l’argomento di
studio principale affrontato per realizzare questo lavoro è stato il codificato-
re e decodificatore FEC (Forward Error Correction) previsto dalla specifica
ETSI che definisce l’MBMS. É utile quindi, prima di scendere nel dettaglio
3del lavoro realizzato, dare una descrizione a grandi linee del sistema MBMS.
Rispetto alle modalità tradizionali di trasmissione su una rete radio,
l’MBMS introduce una nuova modalità: il Multicasting, cioè la gestione del-
l’invio del contenuto ad un gruppo di utenti in mobilità . Il mondo Internet,
attraverso il protocollo TCP/IP, prevede già delle tecniche per l’ottimizza-
zione dell’invio di contenuti a gruppi di ricevitori. L’MBMS ha adattato le
idee ed i relativi protocolli d’utente alle esigenze delle reti 3GPP. In sintesi,
dunque, seguendo la definizione data dalla specifica ETSI, l’MBMS è un ser-
vizio punto-multi-punto nel quale i dati sono trasmessi da una singola entità
sorgente ad una molteplicità di ricevitori. I modi offerti da tale servizio sono
quindi quello Broadcast e quello Multicast.
Ovviamente questo tipo di trasmissione richiede alcune caratteristiche
fondamentali, tra le quali l’affidabilità, il basso overhead di rete e la possi-
bilità di supportare diversi ricevitori con caratteristiche eterogenee. Per ga-
rantire queste proprietà è necessario adottare delle opportune contromisure:
in questo ambito si inserisce lo scopo di questa dissertazione. Tra le specifi-
che richieste dall’MBMS c’è infatti l’utilizzo di un codice FEC necessario per
riuscire a recuperare le inevitabili perdite di dati (“erasures”) introdotte dal
canale di trasmissione.
Partendo quindi dalla teoria generale della codifica di pacchetto, sono sta-
te studiate diverse soluzioni fino ad arrivare al codice utilizzato dallo stan-
dard ETSI per l’MBMS: il codice Raptor di tipo sistematico. L’obiettivo
principale della tesi è stato proprio la realizzazione di un co-decodificatore
Raptor sistematico. Per far ciò è stato implementato un software utilizzan-
do il linguaggio di programmazione C/C++. In ultimo, una campagna di
simulazioni ha consentito di valutare le prestazioni del codec realizzato.
Capitolo 1
Tecniche di codifica avanzate a
livello di pacchetto
La trasmissione broadcast o multicast deve possedere delle caratteristi-
che fondamentali: deve essere completamente affidabile, richiedere un basso
overhead di rete, supportare un vasto numero di utenti con caratteristiche
eterogenee. In questo capitolo tratteremo delle tecniche di codifica avan-
zate Forward Error Correction (FEC) che agiscono a livello di pacchetto.
Introdurremo i concetti e la terminologia che riguardano l’affidabilità a livel-
lo di trasporto ed i diversi approcci utilizzati per ottenere una trasmissione
affidabile [1].
1.1 L’affidabilità nelle trasmissioni Multicast
I servizi Multicast sono generalmente implementati sulla rete IP, rete
adatta a gestire una comunicazione punto-multi-punto, ma che non garan-
tisce assolutamente l’affidabilità della trasmissione, essendo basata su un
protocollo best-effort [2]. In una rete multicast, le perdite di dati (erasures)
sono imputabili a diversi motivi, che vanno dalla congestione della rete a
problemi propagativi dovuti al canale radio (ad esempio in un collegamento
satellitare).
6 Tecniche di codifica avanzate a livello di pacchetto
Nell’approccio seguito in [1] il progetto di un protocollo multicast affida-
bile coinvolge non solo i livelli più bassi definiti nello struttura ISO/OSI, ma
si spinge fino ai livelli di rete, trasporto e applicazione. Nel seguente paragra-
fo vengono discussi quindi i principali meccanismi di recupero delle perdite
che riguardano il livello di trasporto (livello 4 della struttura ISO/OSI).
1.1.1 Tecniche di recupero a livello di trasporto
Il protocollo Automatic Repeat reQuest (ARQ) è sicuramente uno dei me-
todi più diffusi per il recupero degli errori [3]. Con tale protocollo, ciascun
ricevitore ha un canale di ritorno (feedback channel ), che utilizza per chiede-
re al trasmettitore la ritrasmissione dei pacchetti persi. I vantaggi dell’ARQ
sono evidenti nel caso di protocolli uno-a-uno (basti pensare al successo del
TCP/IP), mentre nelle applicazioni uno-a-molti presentano diversi problemi.
In una rete eterogenea, infatti, sono presenti nello stesso istante ricevitori
con caratteristiche molto diverse tra loro: se essi sono collegati con un nodo
ad alta capacità, i ricevitori con collegamenti di banda inferiore limitano la
possibilità del nodo di sfruttare al massimo la banda. Si può osservare così
il problema del “crying baby”: in un gruppo di ricevitori, uno o più membri
non possono raggiungere il ritmo di trasmissione della connessione e così per-
dono continuamente dati. In questo modo essi richiedono continuamente la
ritrasmissione dei pacchetti persi, riducendo così la banda utilizzabile dagli
altri membri che riceveranno una gran quantità di pacchetti replicati [4].
Quando l’ARQ è troppo costoso o impossibile da implementare perchè
il canale di ritorno è troppo piccolo o non esiste (come nella trasmissione
satellitare unidirezionale), vengono impiegati diversi approcci per garantire
l’affidabilità. Una opzione è l’utilizzo del Data Carousel [5]. Tale tecnica pre-
vede l’invio ciclico da parte del trasmettitore dei dati. Il ricevitore continua a
ricevere pacchetti fin quando non ha ricevuto una copia di ciascun pacchetto.
Il Data Carousel non richiede un canale di ritorno. Se un ricevitore perde
un pacchetto, deve aspettare la fine dell’intero giro prima di poter tentare di
recuperare il pacchetto perso. Ciò comporta un evidente spreco di banda dal
1.1 L’affidabilità nelle trasmissioni Multicast 7
momento che il trasmettitore ritrasmette i dati fin quando tutti i ricevitori
hanno ricevuto tutti i pacchetti.
Un altro metodo per garantire l’affidabiltà è l’utilizzo di codici FEC (For-
ward Error Correction) [1], [6], [7]. Gli ingressi di un codificatore FEC sono
K pacchetti sorgenti di uguale lunghezza (source packets). Il codificatore ge-
nera N pacchetti codificati encoding packets della stessa lunghezza con una
piccola intestazione che contiene le informazioni necessarie al decoder. Il co-
dice è sistematico se i pacchetti sorgente sono trasmessi tra quelli codificati.
Dal lato del ricevitore il decodificatore utilizza i pacchetti codificati per rico-
struire una copia esatta dei K pacchetti sorgente. Un codice è poi chiamato
Minimum-Distance-Separable (MSD) se può ricreare una esatta copia dei dati
originali da qualunque gruppo di K simboli codificati (in seguito tale codice
verrà chiamato anche codice perfetto o ideale). É evidente che tali tecniche
introducono ridondanza (data dal rapporto N/K) ed essa è tanto più grande
quanto più grande è il numero dei ricevitori, quanto più ampio è il grado di
eterogeneità e quanto più bassa è l’affidabilità del canale radio. I codici FEC
a livello di pacchetto possono poi essere suddivisi in due categorie: proattivi
e reattivi. Nel primo caso il trasmettitore decide a priori quanti encoding
packets devono essere generati (FEC a ritmo fisso); la seconda classe prevede
che il trasmettitore invii dapprima solo i dati originali e poi utilizzi il canale
di feedback per stimare il numero di perdite e decidere quanti pacchetti di
parità generare (FEC con ritmo adattivo). I due diversi approcci possono poi
essere combinati per creare soluzioni ibride. Comunque, dal momento che la
soluzione reattiva richiede un canale di ritorno, d’ora in avanti ci riferiremo
a schemi FEC proattivi, assumendo che l’esistenza del feedback channel non
sia garantita.
Per scegliere la strategia di recupero più appropiata, è necessario fare
delle considerazioni sulle caratteristiche e sulle esigenze delle tecniche sopra-
citate. Il protocollo ARQ garantisce completa affidabilità ma dimostra una
scarsa scalabilità soprattutto quando centinaia di migliaia o milioni di utenti
devono essere serviti. Ed è per di più irrealizzabile quando il canale di ritorno
8 Tecniche di codifica avanzate a livello di pacchetto
non è disponibile. Il Data Carousel e il metodo tramite FEC possono esse-
re applicati anche senza feedback channel, ma garantisco un’affidabilità solo
parziale. É evidente poi che l’utilizzo di pacchetti di parità per il recupero
dei dati persi (FEC) è vantaggioso rispetto al protocollo ARQ e al Carousel
in termini di efficienza di trasmissione e scalabilità. Infatti basti pensare,
parlando di efficienza, che un pacchetto di recupero (repair packet) può esse-
re utilizzato per riparare la perdita di ciascun pacchetto di dati appartenente
allo stesso blocco codificato. In altri termini, un pacchetto di parità può
recuperare la perdita di diversi pacchetti in diversi ricevitori. Infine, per quel
che concerne la scalabilità, usando repair packets il trasmettitore necessita
soltanto di una stima del caso peggiore per quel che riguarda le perdite e non
di conoscere il numero esatto di pacchetti da ritrasmettere.
1.1.2 Tipologie di codici FEC
Seguendo [7] i codici FEC possono essere distinti in base a due importanti
caratteristiche:
• la lunghezza K del blocco che può essere codificato (lunghezza del
blocco piccola o grande);
• la capacità di generare un numero arbitrario di pacchetti di parità (o
di recupero). Avremo quindi codici con un ritmo finito o privi di ritmo
(rateless).
Esistono diverse alternative di codifica FEC. Una descrizione esaustiva può
essere trovata in [1]. Qui vengono citati tre nuovi tipi di codice, i codici a
blocco Multi-Dimensional (codici M-D), gli LDGM e i codici di tipo Digital
Fountain.
Codici FEC Multidimensionali (M-D)
Questi tipi di codici sono basati su due concetti: la codifica concatena-
ta e la decodifica iterativa, concetti alla base dei turbo codici. I codici con
1.1 L’affidabilità nelle trasmissioni Multicast 9
lunghezza del blocco lunga sono preferibili rispetto a quelli con blocchi più
piccoli perchè le diverse parole di codice hanno una distanza minima maggio-
re e conseguentemente delle prestazioni superiori. Tuttavia poichè è difficile
implementare codificatori che lavorino su blocchi con lunghezza K molto ele-
vata, si preferisce concatenare diversi codificatori che agiscono su blocchi di
lunghezza inferiore. I blocchi di uscita sono organizzati in un array bidi-
mensionale (una matrice). Il codice esterno solitamente effettua una codifica
lungo le righe dell’array, quello interno lavora per colonne (ecco perchè codi-
fica bidimensionale). La tecnica classica di decodifica per i codici concatenati
prevede dapprima la decodifica del codice interno, poi la codifica di quello
esterno; l’intero processo viene ripetuto in modo iterativo fino a quando non
è soddisfatto un particolare criterio d’arresto che dipende dall’algoritmo FEC
M-D utilizzato. Dal momento che tali codici fanno uso di controlli di parità
extra (quelli che si ottengono dall’incrocio delle due dimensioni), essi hanno
dei vantaggi rispetto ai codici monodimensionali. In particolare, per un dato
ritmo, il codice ottenuto dal prodotto di due codici 1D ha una capacità di
recupero degli errori superiore a quella di un codice 1D [9]. Inoltre, fissata la
probabilità di fallire la decodifica, il codice concatenato può usare un ritmo
di codifica superiore rispetto al codice monodimensionale [10].
I codici LDGM
I Low Density Generator Matrix code sono stati presentati in [11]: gli
autori descrivono il progetto e l’implementazione di questo caso particolare
di codici LDPC (Low Density Parity Check, vedi paragrafo 2.2) in grado di
operare su blocchi sorgenti lunghi parecchie decine di megabytes. Gli LDGM
sono codici a blocco lineari con una matrice di controllo di parità H molto
sparsa. Tale matrice può anche essere descritta tramite un grafo bipartito
tra nodi di sinistra chiamati message nodes, nodi di destra chiamati check
nodes. I K pacchetti sorgenti formano i primi K message nodes, mentre
pacchetti di parità formano i rimanenti N − K message nodes. É presente
un edge nel grafo tra un nodo sorgente ed un check node se e solo se c’è un
10 Tecniche di codifica avanzate a livello di pacchetto
’1’ nella corrispondente posizione della matrice H (colonna, riga). Gli edges
rappresentano i vincoli presenti da tra i vari message nodes. La differenza
con i codici LDPC classici è che, mentre in questi ultimi la matrice H, di
dimensione (N − K) × N , e il conseguente grafo bipartito, coprono tutti i
nodi di sinistra (nodi sorgente e di parità), nei codici LDGM la matrice H,
di dimensione (N−K)×K, copre solo i primi K nodi sorgente ed è associata
ad una matrice identità di dimensione (N − K) × (N − K). Il risultato è
una matrice, anche essa matrice generatrice (ecco il Generator Matrix), così
fatta:
[H|IN−K ] (1.1.1)
Ciascun nodo di parità è collegato esattamente ad un check node. Un codice
LDGM dove tutti i nodi sorgente hanno lo stesso grado e tutti i check nodes
hanno lo stesso grado, è detto regolare. In tal caso, i gradi di sinistra e di
destra nel grafo sono collegati ai parametri (K,N) dall’equazione:
K × gradodisinistra = (N −K)× gradodidestra (1.1.2)
In questa equazione gli edge da check nodes a parity nodes non sono consi-
derati nei gradi di destra e sinistra. La matrice H è costruita essenzialmente
in modo random imponendo i vincoli sui gradi. Viene poi applicata un’otti-
mizzazione per evitare la presenza nel grafo di cicli di lunghezza quattro (cio
avviene quando due nodi sorgenti sono connessi agli stessi due check nodes),
perchè essi rendono la decodifica subottima.
Codici di tipo Digital Fountain
Questi codici sono di tipo rateless, cioè privi di ritmo. I codici Digi-
tal Fountain sono l’oggetto fondamentale di questa dissertazione e saranno
trattati in maniera esaustiva nel capitolo successivo. Come vedremo poi nel
capitolo 4 è proprio un codice di tipo digital fountain (codice Raptor siste-
matico) ad essere stato adottato dalle specifiche ETSI/3GPP per la codifica
FEC nell’architettura MBMS [13].