Optimality of Network Coding with Buffers
The authors analyze distributed and Packetized implementations of random linear Network Coding (PNC) with buffers. In these protocols, nodes store received packets to later produce coded packets that reflect this information. They show the optimality of PNC for any buffer size; i.e., they show that PNC performs at least as good as any protocols with the same buffer size. In other words, a multicast task completes at exactly the first time in which in hindsight it was possible to route information from the sources to each receiver individually given the buffer constraint, i.e., that the buffer used at each node never exceeds its buffer size.