Practical random linear network coding on GPUs

Xiaowen CHU*, Kaiyong Zhao, Mea Wang

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

6 Citations (Scopus)


Recently, random linear network coding has been widely applied in peer-to-peer network applications. Instead of sharing the raw data with each other, peers in the network produce and send encoded data to each other. As a result, the communication protocols have been greatly simplified, and the applications experience higher end-to-end throughput and better robustness to network churns. Since it is difficult to verify the integrity of the encoded data, such systems can suffer from the famous pollution attack, in which a malicious node can send bad encoded blocks that consist of bogus data. Consequently, the bogus data will be propagated into the whole network at an exponential rate. Homomorphic hash functions (HHFs) have been designed to defend systems from such pollution attacks, but with a new challenge: HHFs require that network coding must be performed in GF(q), where q is a very large prime number. This greatly increases the computational cost of network coding, in addition to the already computational expensive HHFs. This paper exploits the potential of the huge computing power of Graphic Processing Units (GPUs) to reduce the computational cost of network coding and homomorphic hashing. With our network coding and HHF implementation on GPU, we observed significant computational speedup in comparison with the best CPU implementation. This implementation can lead to a practical solution for defending against the pollution attacks in distributed systems.

Original languageEnglish
Title of host publicationNETWORKING 2009 - 8th International IFIP-TC 6 Networking Conference, Proceedings
Number of pages13
Publication statusPublished - 2009
Event8th International IFIP-TC 6 Networking Conference, NETWORKING 2009 - Aachen, Germany
Duration: 11 May 200915 May 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5550 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International IFIP-TC 6 Networking Conference, NETWORKING 2009

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Applications and services
  • GPU computing
  • Network coding
  • Pollution attack


Dive into the research topics of 'Practical random linear network coding on GPUs'. Together they form a unique fingerprint.

Cite this