Locally Recoverable Streaming Codes for Packet-Erasure Recovery

Abstract

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 [τ+1,τ+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 τ. 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>1 arbitrary packet erasures under a decoding delay τ, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay r<τ. We term these codes as (a,τ,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,τ,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,τ=a(r+1)-1,r) LRSC construction provides the additional guarantee of recovery from the erasure of h, 1 ≤ h ≤ a, packets, with delay h(r+1)-1. The construction thus offers graceful degradation in decoding delay with increasing number of erasures.