Computer Science > Information Theory
[Submitted on 7 Sep 2021]
Title:Locally Recoverable Streaming Codes for Packet-Erasure Recovery
View PDFAbstract: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>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<\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.
Current browse context:
cs.IT
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.