In this paper, we propose a practical Random Network Coding (RNC) scheme for data distribution in a peer-to-peer (P2P) overlay network. The use of RNC incurs a significant computational cost that, till present, has limited its deployment in practical applications. In this study, it is shown that RNC complexity can be lowered by using Luby Transform (LT) codes to pre-encode the data and by letting intermediate nodes use RNC in a low-order Galois Field, i.e. GF(2). Moreover, we exploit a recently proposed variant of the Gaussian Elimination algorithm (OFG) to improve further both the creation of random combinations for RNC and the final decoding of the content. Our analysis is based on both analytical modeling and simulations over P2P overlay networks generated from random graphs and real snapshots of the PPLive streaming application. The results point out that using LT codes and RNC in GF(2) one is able to significantly improve the overall performance in terms of both delay and bandwidth utilization at a reasonable computational cost. Finally, the RNC strategies we propose do not require any prior knowledge of the overlay network topology thus making them very general.

A practical Random Network Coding scheme for data distribution on peer-to-peer networks using rateless codes

GRANGETTO, Marco;GAETA, Rossano;SERENO, Matteo
2013

Abstract

In this paper, we propose a practical Random Network Coding (RNC) scheme for data distribution in a peer-to-peer (P2P) overlay network. The use of RNC incurs a significant computational cost that, till present, has limited its deployment in practical applications. In this study, it is shown that RNC complexity can be lowered by using Luby Transform (LT) codes to pre-encode the data and by letting intermediate nodes use RNC in a low-order Galois Field, i.e. GF(2). Moreover, we exploit a recently proposed variant of the Gaussian Elimination algorithm (OFG) to improve further both the creation of random combinations for RNC and the final decoding of the content. Our analysis is based on both analytical modeling and simulations over P2P overlay networks generated from random graphs and real snapshots of the PPLive streaming application. The results point out that using LT codes and RNC in GF(2) one is able to significantly improve the overall performance in terms of both delay and bandwidth utilization at a reasonable computational cost. Finally, the RNC strategies we propose do not require any prior knowledge of the overlay network topology thus making them very general.
70
1
13
http://www.sciencedirect.com/science/article/pii/S0166531612000909
Valerio Bioglio; Marco Grangetto; Rossano Gaeta; Matteo Sereno
File in questo prodotto:
File Dimensione Formato  
final_4aperto.pdf

Accesso aperto

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 305.21 kB
Formato Adobe PDF
305.21 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/130116
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact