  Random Linear Network Coding (RLNC) has emerged as a powerful tool for robust
high-throughput multicast. Projection analysis - a recently introduced
technique - shows that the distributed packetized RLNC protocol achieves
(order) optimal and perfectly pipelined information dissemination in many
settings. In the original approach to RNLC intermediate nodes code together all
available information. This requires intermediate nodes to keep considerable
data available for coding. Moreover, it results in a coding complexity that
grows linearly with the size of this data. While this has been identified as a
problem, approaches that combine queuing theory and network coding have
heretofore not provided a succinct representation of the memory needs of
network coding at intermediates nodes.
  This paper shows the surprising result that, in all settings with a
continuous stream of data, network coding continues to perform optimally even
if only one packet per node is kept in active memory and used for computations.
This leads to an extremely simple RLNC protocol variant with drastically
reduced requirements on computational and memory resources. By extending the
projection analysis, we show that in all settings in which the RLNC protocol
was proven to be optimal its finite memory variant performs equally well. In
the same way as the original projection analysis, our technique applies in a
wide variety of network models, including highly dynamic topologies that can
change completely at any time in an adversarial fashion.
