  Random linear network coding (RLNC) has been shown to efficiently improve the
network performance in terms of reducing transmission delays and increasing the
throughput in broadcast and multicast communications. However, it can result in
increased storage and computational complexity at the receivers end. In our
previous work we considered the broadcast transmission of large file to N
receivers. We showed that the storage and complexity requirements at the
receivers end can be greatly reduced when segmenting the file into smaller
blocks and applying RLNC to these blocks. To that purpose, we proposed a packet
scheduling policy, namely the Least Received. In this work we will prove the
optimality of our previously proposed policy, in terms of file transfer
completion time, when N = 2. We will model our system as a Markov Decision
Process and prove the optimality of the policy using Dynamic Programming. Our
intuition is that the Least Received policy may be optimal regardless of the
number of receivers. Towards that end, we will provide experimental results
that verify that ntuition.
