Locally Recoverable Streaming Codes for Packet-Erasure Recovery
Vinayak Ramkumar, Myna Vajha, P. Vijay Kumar · 2021
Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a $[{\tau}+1, {\tau}+1-{a}]$ Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from a arbitrary packet erasures, under a strict decoding delay constraint ${\tau}$. Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of a erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from ${a}\gt 1$ arbitrary packet erasures under a decoding delay ${\tau}$, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay ${r}\lt {\tau}$. We term these codes as $({a},{\tau},{r})$ locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters $\{{a},{\tau},{r}\}$. Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our (${a},{\tau}={a}({r}+1)-1,{r})$ LRSC construction provides the additional guarantee of recovery from the erasure of ${h}, 1\leq {h}\leq {a}$, packets, with delay ${h}({r}+1)-1$. The construction thus offers graceful degradation in decoding delay with increasing number of erasures. A full version of this paper is accessible at [1].