Storm: Rateless MDS erasure codes

Thumbnail Image
Date
2015
Authors
Pedro Miguel Silva
Jaime Dias
Manuel Ricardo
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Erasure codes have been employed in a wide range of applications to increase content availability, improve channel reliability, or to reduce downloading time. For several applications, such as P2P file sharing, MDS erasure codes are more suitable as the network is typically the most constrained resource, not the CPU. Rateless MDS erasure codes also enable to adjust encoding and decoding algorithms as function of dynamic variables to maximize erasure coding gains. State-of-the-art MDS erasure codes are either fixed-rate or have practical limitations. We propose Storm erasure codes, a rateless MDS construction of Reed- Solomon codes over the finite field (formula presented), where p is a Mersenne prime. To the best of our knowledge, we are the first to propose a rateless construction (n can be increased in steps of k) with (formula presented) encoding time complexity and min (formula presented) upper bound for decoding time complexity. We provide the complexity analysis of encoding and decoding algorithms and evaluate Storm’s performance.
Description
Keywords
Citation