@inproceedings{948750aafe944cbd993994c6bab37842,
title = "Approximating throughput and packet decoding delay in linear network coded wireless broadcast",
abstract = "We study the interplay between the throughput and average packet decoding delay (APDD) of linear network coded (LNC) wireless broadcast systems through studying the approximation of throughput and APDD. We first define strong and weak approximations (based on whether the approximation holds for every receiver or not). We then prove that LNC techniques that strongly approximate throughput can also strongly approximate APDD, but those that weakly approximate throughput do not necessarily weakly approximate APDD. We prove that all throughput-optimal LNC techniques, including random linear network coding, strongly approximate APDD with a ratio between 4/3 and 2. We also prove that all memoryless LNC techniques, including instantly decodable network coding techniques, cannot strongly or weakly approximate throughput, nor strongly approximate APDD.",
keywords = "Approximation, Decoding delay, Network coding, Throughput, Wireless broadcast",
author = "Mingchao Yu and Parastoo Sadeghi",
note = "Publisher Copyright: {\textcopyright} 2018 IEEE Information Theory Workshop, ITW 2018. All rights reserved.; 2018 IEEE Information Theory Workshop, ITW 2018 ; Conference date: 25-11-2018 Through 29-11-2018",
year = "2018",
month = jul,
day = "2",
doi = "10.1109/ITW.2018.8613407",
language = "English",
series = "2018 IEEE Information Theory Workshop, ITW 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2018 IEEE Information Theory Workshop, ITW 2018",
address = "United States",
}