Optimality of Network Coding in Packet Networks
The authors resolve the question of optimality for a well studied packetized implementation of random linear network coding, called PNC. In PNC, in contrast to the classical memory-less setting, nodes store received information in memory to later produce coded packets that reflect this information. PNC is known to achieve order optimal stopping times for the many-to-all multicast problem in many settings. They give a reduction that captures exactly how PNC and other network coding protocols use the memory of the nodes. More precisely, they show that any such protocol implementation induces a transformation which maps an execution of the protocol to an instance of the classical memory-less setting.