  This paper studies the complicated interplay of the completion time (as a
measure of throughput) and the decoding delay performance in instantly
decodable network coded (IDNC) systems over wireless broadcast erasure channels
with memory, and proposes two new algorithms that improve the balance between
the completion time and decoding delay of broadcasting a block of packets. We
first formulate the IDNC packet selection problem that provides joint control
of the completion time and decoding delay as a statistical shortest path (SSP)
problem. However, since finding the optimal packet selection policy using the
SSP technique is computationally complex, we employ its geometric structure to
find some guidelines and use them to propose two heuristic packet selection
algorithms that can efficiently improve the balance between the completion time
and decoding delay for broadcast erasure channels with a wide range of memory
conditions. It is shown that each one of the two proposed algorithms is
superior for a specific range of memory conditions. Furthermore, we show that
the proposed algorithms achieve an improved fairness in terms of the decoding
delay across all receivers.
