I'm thinking of Network Coding Meets TCP. Though that doesn't give a great background. I've experimented with my own implementation, but had to shelve it due to lack of time. I'll try to quickly summarise the core idea;
You have packets [p1, .. pn] in your stream's transmission window.
Randomly pick coefficients [x1, ..., xn] and calculate a new packet = x1*p1 + x2*p2 + , .... (in a galois number field, so '+' is an XOR and '*' is a pre-computed lookup table). Sending the coefficients in the packet header.
The receiver collects the packets, and attempts to combine pairs of packets to reduce the complexity of the coefficients. Basically like solving simultaneous equations. That sounds complicated, but the algorithm isn't too hard;
- Keep the current set of packets, sorted by their coefficients. When you receive an incoming packet, you attempt to subtract each of your existing packets which have a smaller coefficient set (again, galois field math). If you're left with nothing, this packet didn't give you any new information, so throw it away.
- Attempt to subtract this new packet from each of the existing packets in your set. Insert your new packet into the list.
When you have a packet with a most significant coefficient of 1. You know you will be able to decode that packet eventually. And you know that you can eliminate that coefficient from any other incoming packet. So you can send an acknowledgement to the sender and they can advance their transmit window. Once you have eliminated all other coefficients you can deliver the packet to the application. Keep each packet in memory until the sender has advanced their window and stopped sending it.
Each incoming packet may eliminate a coefficient from the packets in your list, while at the same time introducing a new one. If you don't send extra redundant packets you may never be able to decode anything. Consider the worst case where every packet is the XOR of two neighbouring packets in the stream, you can't decode anything until you receive a single packet by itself. Sending more redundant packets will reduce the latency to decode the stream while adding to the number of useless packets received.