On The Capacity of Immediately-Decodable Coding Schemes for Wireless Stored-Video Broadcast with Hard Deadline Constraints

Multimedia streaming applications have stringent Quality-of-Service (QoS) requirements. Typically, each packet is associated with a packet delivery deadline. This work models and considers streaming broadcast of stored video over the downlink of a single cell. We first generalize the existing class of immediately-decodable network coding (IDNC) schemes to take into account the deadline constraints. The performance analysis of IDNC schemes are significantly complicated by the packet deadline constraints (from the application layer) and the immediate-decodability requirement (from the network layer). Despite this difficulty, we prove that for independent channels, the IDNC schemes are asymptotically throughput-optimal subject to the deadline constraints when there are no more than three users and when the video file size is sufficiently large. The deadline-constrained throughput gain of IDNC schemes over non-coding scheme is also explicitly quantified. Numerical results show that IDNC schemes strictly outperform the non-coding scheme not only in the asymptotic regime of large files but also for small files. Our results show that the IDNC schemes do not suffer from the substantial decoding delay that is inherent to existing generation-based network coding protocols.