A Multi-Threaded Approach to Encoding with Random Linear Network Coding

Abstract:
Cloud and distributed storage applications require processing of large fragments of data. This poses memory, delay, and processing speed challenges for systems using erasure codes to reduce the cost of storage and/or increase the reliability of the system. To address these, this paper proposes and deploys designs that exploit current multi-threading capabilities of microprocessors to accelerate the encoding and decoding process of erasure codes, focusing on the case of Random Linear Network Coding (RLNC). More specifically, we propose a strategy for parallel computation based on splitting symbols into significantly smaller fragments and reordering data to speed up computation and decreasing the potential for thread blocking. We implement the strategy in C++ and carry out benchmark experiments and compare them with the single threaded state-of-the-art block RLNC encoders. We show a reduction of processing time by a factor of three by using our strategies for files of 32 MB or more as well as reducing memory usage drastically in the system. We also show that our approach provides a better scaling than the single-threaded option when increasing the number of fragments that a file is broken into. In other words, distributed storage systems can split files or data into a larger number of fragments without experiencing a speed penalty.