We study the broadcast transmission of a single file to an arbitrary number of receivers using Random Linear Network Coding (RLNC) in a network with unreliable channels. Due to the increased computational complexity of the decoding process (especially for large files), we apply chunked RLNC (i.e., RLNC is applied within non-overlapping subsets of the file). In our work, we show the optimality of the Least Received (LR) batch scheduling policy with regards to the expected file transfer completion time. The LR policy strives to keep the receiver queues balanced. This is done by transmitting packets (corresponding to encoded batches) that are needed by the receivers with the shortest queues of successfully received packets. Furthermore, we provide formulas for the expected time for the file transmission to all receivers using the LR batch scheduling policy and the minimum achievable coding window size in the case of a pre-defined delay constraint. Moreover, we evaluate through simulations a modification of the LR policy in a more realistic system setting with reduced feedback from the receivers. Finally, we provide an initial analysis and further modifications to the LR policy for time-correlated channels and asymmetric channels.

Additional Metadata
Keywords Asymmetric channels, Broadcast, Chunked random linear network coding, Optimal batch scheduling policy, Sample path analysis, Time-correlated channels, Wireless channels
Persistent URL dx.doi.org/10.1145/3340242
Journal ACM Transactions on Modeling and Performance Evaluation of Computing Systems
Citation
Skevakis, E. (Emmanouil), Lambadaris, I, & Halabian, H. (Hassan). (2019). Scheduling for optimal file-Transfer delay using chunked random linear network coding broadcast. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 4(3). doi:10.1145/3340242