Title: Approximating Throughput and Packet Decoding Delay in Linear Network Coded Wireless Broadcast,
Abstract: In this paper, we study a wireless packet broadcast system that uses linear
network coding (LNC) to help receivers recover data packets that are missing
due to packet erasures. We study two intertwined performance metrics, namely
throughput and average packet decoding delay (APDD) and establish strong/weak
approximation relations based on whether the approximation holds for the
performance of every receiver (strong) or for the average performance across
all receivers (weak). We prove an equivalence between strong throughput
approximation and strong APDD approximation. We prove that throughput-optimal
LNC techniques can strongly approximate APDD, and partition-based LNC
techniques may weakly approximate throughput. We also prove that memoryless LNC
techniques, including instantly decodable network coding techniques, are not
strong throughput and APDD approximation nor weak throughput approximation
techniques.