  In this paper, we consider the packet-level forward error correction (FEC)
code design, without feedback or with delayed feedback, for achieving the
minimum end-to-end latency, i.e., the latency between the time when packet is
generated at the source and its \emph{in-order delivery} to the application
layer of the destination. We first show that the minimum-latency FEC design
problem can be modeled as a partially observable Markov decision process
(POMDP), and hence the optimal code construction can be obtained by solving the
corresponding POMDP. However, solving the POMDP optimally is in general
difficult unless the size is very small. To this end, we propose an efficient
heuristic algorithm, namely the majority vote policy, for obtaining a high
quality approximate solution. We also derive the tight lower and upper bounds
of the optimal state values of this POMDP, based on which a more sophisticated
D-step search algorithm is implemented for obtaining near-optimal solutions.
The simulation results show that the proposed code designs via solving the
POMDP, either with the majority vote policy or the D-step search algorithm,
strictly outperform the existing schemes, in both cases, without or with only
delayed feedback.
