XORs in the Air: Practical Wireless Network Coding

Like the previous paper, this one is also about taking advantage of the broadcast nature of wireless to improve throughput. However, the approach here is more elegant and more practical. The idea is that different nodes know the contents of different packets, either because they originally sent them, or because they happen to have heard them. If a sender with multiple packets to forward knows which receivers have which packets, it may be able to send a sum of the packets (XOR) such that each receiver can "solve" for their own packet from it. This is shown to actually improve throughput noticeably in real networks. Unlike the previous paper, end applications don't need to be modified, there is no need for batching, and the scheme works well with multiple flows - in fact, that's the whole point of the scheme. This makes the scheme applicable in real 802.11 networks. The paper is well-presented and interesting to read.

Note that COPE takes advantage of the wireless medium in a fundamentally different way from ExOR. ExOR is about taking advantage of multiple relay nodes when we send from a single source to a single destination and links are lossy. COPE is about conserving spectrum when multiple flows pass through the same set of nodes, and does not worry overly much about loss. The approach in COPE seems more useful in real wireless network deployments, whereas ExOR is sort of a "theoretical" result that, if you had to send from one node to another over a lossy channel and there happened to be several idle nodes in-between you and your destination, you should utilize all of them rather than trying to find one single best path.

I also found it interesting that COPE could improve throughput by reducing the sizes of router queues. This is a nice unanticipated effect.

My main concern about the paper is whether the potential reordering of packets, or the wait for the nodes to put them back in order, can increase jitter and confuse TCP's estimation of round-trip time or confuse real-time applications. It would have been nice to see some latency results.