Vai a: navigazione, ricerca

Indice 1 Premessa 2 Pacchetti e percorsi 3 Network Coding – la soluzione? 4 Internet codificato 5 La codifica Random Linear 6 Realizzazioni 7 Benefici e applicazioni 8 Conclusione 9 Riferimenti

Premessa

Nel leggere la rivista on line Network World del 30 luglio scorso, mi sono imbattuto in un articolo il cui titolo mi ha colpito: Why TCP/IP is on the way out (Perché il TCP/IP sta per andarsene). Ora, chiunque abbia a che fare con le reti sa che il TCP/IP è in realtà una coppia di protocolli, che fa parte della "suite TCP/IP" su cui si basa tutta l’Internet. Pensare che la loro fine sia vicina stimola una certa curiosità verso ciò che dovrebbe sostituirli.

Sono andato a leggere un po’ in giro per la rete e mi sono reso conto che quel titolo è un po’ ingannevole: il TCP/IP, almeno in un primo tempo, verrà solo "aiutato" da una tecnica di codifica dei pacchetti, detta Network Coding (NC), che dovrebbe essere implementata nei nodi della rete, i quali diventerebbero più “smart” e contribuirebbero così al miglioramento delle trasmissioni. Laddove la Teoria dell’informazione è centrata sul livello fisico, il NC è applicabile a tutti i livelli OSI superiori a quello fisico. Attingendo largamente a un video illustrativo recitato dal prof. Fiztek, Università di Aalborg (Danimarca) e ad altre fonti reperibili in rete, riporto qui alcune notizie su questa nuova tecnologia, i cui primi studi risalgono circa al 2000, a partire dal modello di flusso cosiddetto "Butterfly", in cui si vede in forma elementare che il nodo centrale in basso contiene sia in ingresso che in uscita la somma dei segnali A+B e quindi non è "spiabile".

La prima formulazione del RLNC, ossia la versione random del network coding, compare anni dopo, nel 2013, con lavori svolti dalla succitata università danese in collaborazione con il prestigioso MIT (Massachusets Institute of Technology) e il Caltech (California Institute of Technology). L’argomento è abbastanza complesso e spiegarne i vari perché in profondità è certamente al di là dei miei scopi. Mi accontento di fornire un quadro generale di quello che potrebbe diventare un tema “caldo” in un futuro non lontano.

Pacchetti e percorsi

Si sa che su internet i dati vengono inviati in "pacchetti". Il formato dei pacchetti e le procedure per la loro consegna a destinazione sono descritti da una suite di protocolli conosciuti come TCP/IP, o “suite dei protocolli internet”, progettata nei primi anni ‘70.

In breve tempo la suddetta suite, nata in ambito militare con obiettivi di agilità e flessibilità nell’interconnettere un grande numero di computer diversi (flessibilità che sembra cozzare contro il concetto di “militare”) ha prodotto un enorme balzo in avanti nelle concezioni sulle reti, rivoluzionando il nostro paradigma per la trasmissione di informazioni digitali. Straordinariamente, 40 anni dopo, questa suite forma ancora la spina dorsale dell’internet. Tuttavia, dice Fiztek, nonostante tutti i suoi meriti, sarebbe difficile sostenere che è particolarmente efficiente, sicura o dinamica.

Ad esempio, affinché una trasmissione di dati TCP abbia successo, il destinatario deve raccogliere i pacchetti nell'ordine esatto in cui sono stati inviati. Se per qualsiasi motivo anche un singolo pacchetto viene perso, il protocollo interpreta questo evento come un segno che la rete è congestionata e quindi, a causa della richiesta di ritrasmissione, la velocità di trasmissione viene dimezzata immediatamente; dopodichè la velocità risale, ma molto lentamente. Questo è ideale in alcune situazioni e terribilmente inefficiente in altre. Il problema è che il protocollo non ha l'intelligenza necessaria per decidere qual è la cosa giusta da fare a seconda della situazione contingente.

Inoltre, sebbene i pacchetti potrebbero prendere un numero teoricamente infinito di percorsi per viaggiare tra il punto A e punto B in una rete, frammentandosi in una molteplicità di modi, si scopre che i dati in una connessione TCP viaggiano sempre lungo lo stesso percorso, ciò che rende abbastanza facile spiare la comunicazione e non sfrutta le possibilità di percorsi più efficienti.

Network Coding – la soluzione?

Un'interessante proposta che potrebbe offrire la soluzione a questi – e ad altri - problemi è appunto il NC, che mira a rendere ogni nodo della rete molto più intelligente di quanto sia attualmente. Con il TCP/IP, i nodi della rete, oltre a provvedere al routing (instradamento), nei riguardi dei dati sono semplici switch che possono solo memorizzare i pacchetti per poi trasmetterli al nodo successivo, lungo un percorso predeterminato; al contrario, con il NC ogni nodo può compiere operazioni sui pacchetti, per esempio la codifica.

Aggiungere intelligenza a livello del nodo può essere un cambiamento veramente dirompente, perché permette di ottenere una flessibilità senza precedenti nel modo in cui le informazioni vengono gestite. Per esempio, si può approfittare del multipath TCP (già implementato in iOS 7 ma poco diffuso per il suo basso rapporto benefici/complessità) e, su di esso, aggiungere un meccanismo di codifica che aumenta ulteriormente la sicurezza e la velocità, e addirittura permette l’archiviazione dei dati proprio nei nodi della rete.

In un recente studio, un team di ricercatori delle tre università americane citate sopra ha documentato un'implementazione di tale meccanismo di codifica, detto appunto network coding, mostrando un impressionante aumento nella velocità di trasporto, da cinque a dieci volte. "E questa tecnologia può essere utilizzata in tutte le comunicazioni, quelle satellitari, quelle della rete mobile nonché quelle internet dal computer," dice il professor Frank Fiztek, che ha diretto lo studio.

Internet codificato

Secondo lui il NC dovrebbe caratterizzare il passaggio alla quinta generazione delle comunicazioni, o 5G, passaggio che dovrebbe costituire una rivoluzione e non solo una evoluzione, così come è stato quando la commutazione di circuito è diventata commutazione di pacchetto.

Con il NC il percorso unico dell’attuale TCP/IP può diventare una molteplicità di percorsi, e, grazie alle elaborazioni svolte nei singoli nodi della rete, risultare in un salto qualitativo nella comunicazione digitale. “Noi cambiamo da store and forward, un modo molto stupido per ricevere i pacchetti - inviare i pacchetti, a compute and forward”, continua Fitzek. Un punto su cui insiste molto è che il network diventa così anche un mezzo di storage.

Secondo lui la 5G deve intervenire migliorando decisamente i seguenti aspetti:

• Throughput
• Affidabilità
• Ritardo di trasmissione
• Sicurezza
• Complessità

Sui primi quattro aspetti non ci sono dubbi, mentre il quinto caratterizza il fatto che la trasmissione di informazioni si svolge in modalità sempre più varie, interattive e altamente dinamiche, ossia imprevedibili.

La codifica Random Linear

Cosa viene fatto in realtà sui pacchetti? Niente altro che una trasformazione lineare. Un pacchetto P_i viene considerato come un numero o, se si preferisce come un polinomio. Tenere insieme un gruppo di pacchetti {P_i} è come tenere insieme un gruppo di polinomi, al quale si può applicare una trasformazione lineare attraverso la moltiplicazione per una matrice di coefficienti, ottenendo un altro gruppo di pacchetti {C_i}. E’ come costruire quello che a scuola è stato chiamato “un sistema lineare di n equazioni in n incognite”.

Mentre in tutti gli altri casi si studia con molta cura come determinare i coefficienti del codice, qui la matrice viene riempita addirittura con numeri casuali. In altre parole si costruisce una sorta di codice a caso! Da cui RLNC (Random Linear Network Coding). Un nodo quindi trasmetterà i pacchetti trasformati, insieme alla matrice dei coefficienti, tramite la quale il nodo ricevente potrà riscostruire i pacchetti originali (risolvendo il sistema di equazioni lineari). Vengono quindi aggiunti i bit della matrice, che sono però solo n², se il pacchetti del gruppo sono n. Sembrerà strano, ma questo “codice casuale” si rivela pieno di virtù. Non stupisce che, maggiore è l’ampiezza della matrice (e quindi il numero dei pacchetti del gruppo), maggiore è la performance del codice; ma maggiore è anche la sua complicatezza, che occorre in qualche modo fronteggiare.

Sappiamo dalle tecniche di comunicazione che la codifica di sorgente toglie ridondanza, mentre la codifica di canale aggiunge ridondanza in modo controllato. Nello RNLC non si toglie nè si aggiunge niente. “Noi non facciamo niente altro che una diversa rappresentazione dei pacchetti, e il numero dei bit di ciascun pacchetto resta invariato” dice Fiztek. “Mentre quasi tutto è end to end, questa codifica è o può essere node to node perché, insieme all’informazione, trasportiamo anche i coefficienti del codice. Ogni volta che è necessario si può fare anche una ricodifica on the fly (al volo) senza bisogno di decodificare prima”. Ossia ogni codifica può essere sovrapposta alla precedente.

La complicatezza risultante dalla codifica può venire ridotta attraverso il cosiddetto metodo di eliminazione di Gauss-Jordan, che comunque richiede una quantità di operazioni proporzionale espressa da un polinomio che contiene un fattore cubico, uno quadratico e uno lineare. Inserendo molti zeri nella matrice dei coefficienti si riesce a ridurre l’impatto del fattore cubico e a limitare molto le dimensioni di quello quadratico. Insomma casuale sì, ma con giudizio...

La codifica RLNC può essere “a blocchi”, come avviene per il codice Reed Solomon, oppure di tipo "convoluzionale", in cui ogni pacchetto è codificato sulla base dei precedenti e introduce così un ritardo molto contenuto. Codificando in questo modo i pacchetti TCP si guadagna dal doppio a dieci volte in velocità. Ciò è dovuto soprattutto al fatto che i percorsi possono essere multipli e che non c’è la rigidità del richiedere una ritrasmissione del pacchetto ogni volta che viene rivelato un errore, cosa che introduce ritardi considerevoli.

Non solo. La trasmissione diventa assai resistente agli errori, ossia il codice è a correzione d’errore ed è anche molto più efficace del diffuso Reed Solomon. La spiegazione di questo fenomeno non è facile e non possiamo riportarla qui. Un altro vantaggio notevole del RLNC è la sua compatibilità con i sistemi esistenti, privi di codifica. Il passaggio al RLNC può essere graduale quanto si vuole e, al limite, indolore.

Ho parlato del TCP e tuttavia la ricodifica può essere fatta non solo al livello OSI “transport” ma a tutti gli altri livelli. E il bello è che non è necessaria alcuna segnalazione (signalling), quella successione di segnali di servizio di “domande” e “risposte” (ACK) che assicurano lo stabilirsi del collegamento, come in una telefonata. E’ come il traffico in autostrada, con le auto che si muovono ad alta velocità: non ci può essere segnalazione, le auto devono trovare un modo per gestire il loro movimento basandosi solo su una loro reciprocità. Lo trovano, perché a guidarle c’è un’intelligenza, umana o non umana. Nel RLNC l’intelligenza sta nell’algebra lineare impiegata. La quale, per inciso, è anche alla base della regolazione del movimento di molti droni.

Realizzazioni

Cosa dire sul piano realizzativo? C’è già qualche implementazione sul mercato che sembra funzionare bene. Dal canto suo il MIT e l’università danese di Aalborg hanno realizzato del software prototipale, da usare per studio e come base di partenza.

Dice ancora Fiztek: “Noi abbiamo fatto la libreria KODO che può funzionare su tutte le piattaforme. Originalmente scritta in C++ può essere riscritta in Java o in Python, un linguaggio è molto facile. Stiamo lavorando per rendere la codifica più efficiente: aumentando il numero degli zeri nella matrice dei coefficienti si guadagna molto in velocità.”

Fiztek vuole enfatizzare molto il fatto che con RLNC la rete diventa, oltre che un mezzo di trasporto, anche un modo per fare storage. Si ottengono cioè le due funzioni, trasporto e storage, usando lo stesso codice e a differenti livelli di complessità, dal sensore al server.

Si incrementa molto anche la sicurezza, sia come protezione dall’hacking, sia come rimedio agli errori di rete.

Il RLNC consente di ottenere una grande resilienza, specie usando molti cloud contemporaneamente, con risultati superiori a quelli di una batteria di dischi in modalità Raid-5, tanto per fare un esempio con una tecnologia diversa e ormai vecchiotta.

La sequenza delle tre figure soprastanti mostra come in confronto con l’assenza di codifica e con la codifica Reed Solomon, il RLNC mostra una formidabile resistenza al crescere del tasso d’errore in rete.

Benefici e applicazioni

I benefici ottenibili dal RLNC sono molteplici:

Tra i campi di applicazioni vengono citati i seguenti.

Ci sono oggi vari tentativi di usare il multipath TCP/IP (RFC 6824) ma questo implica scegliere il miglior percorso tra tutti, che va anche schedulato. Ne segue che il beneficio che ne deriva risulta essere molto piccolo. Ciò non accade applicando al multipath il RLNC, che non necessita di schedulazione.

Conclusione

Tenendo conto che oltre al modello client server c’è quello peer to peer che, con il diffondersi della condivisione di file, verrà sempre più usato, Fiztek è portato a concludere quanto segue:

• Le reti future devono fronteggiare trasmissioni molto più dinamiche e sempre meno prevedibili.
• Lo storage non sarà più nella dorsale, ma nei “bordi” (leggi: nodi) della rete
• Il Network Coding è una strada percorribile per risolvere, usando un unico codice, sia i problemi della rete che quelli dello storage.

Riferimenti

http://www.networkworld.com/article/2459286/why-tcp/why-tcp/ip-is-on-the-way-out.html?source=NWWNLE_nlt_daily_pm_2014-07-30#tk.rss_all

http://thedasforum.org/wp-content/uploads/2013/02/Medards-PCIA-Network-Coding-Presentation.pdf

http://www.mit.edu/~medard/page2/papers08/lima-medard-barros.pdf