Prioritize efficiently: Layer selection in network coding

• Published in: Computer communications 2019-08, Vol.144, p.100-111
• Main Authors: Naumann, Roman, Schaeffer, Marie, Dietzel, Stefan, Scheuermann, Björn
• Format: Article
• Language: English
• ISSN: 0140-3664; 1873-703X
• DOI: 10.1016/j.comcom.2019.05.008

Network coding simplifies routing decisions, improves throughput, and increases tolerance against packet loss. A fundamental limitation, however, is delay: decoding requires as many independent linear combinations as data blocks. Prioritized network coding reduces this delay problem by introducing a hierarchy of prioritization layers. What remains is the problem of choosing a layer to approach two often-contradicting goals: reduce delay until prioritized layers can be decoded and keep the total number of transmissions low. In this paper, we propose an algorithm for this problem that – based on limited feedback – primarily minimizes per-layer delay but identifies opportunities to reduce the required transmissions when per-layer delay is unaffected. Our evaluation shows that our algorithm improves per-layer delay compared to hierarchical network coding and is close to the theoretical optimum number of total transmissions. Moreover, we demonstrate how the proposed algorithm can benefit smart-factory applications that operationalize delay-sensitive information from the production process.