XORs in The Air: Practical Wireless Network Coding

[paper]

This paper uses the idea of network coding to improve throughput on wireless networks in the form of COPE. The introductory example they give is Alice and Bob each sending each other packets through 1 router. This takes 4 transmissions. Instead, the router XORs the two packets together and then broadcasts the XOR value. This is 3 transmissions. Basically, their idea is to reduce the number of packets sent by doing opportunistic coding so that end points can "figure out" what the message is without actually needing to see the message. The goal is to combine as many packets as possible into one transmission. Other approaches try to minimize the number of broadcasts to raise throughput; they instead capitalize on the idea of broadcasts as a way to minimize the overall number of transmissions. XOR is a quick, cheap operation with hardware support.

Something that was not immediately clear to me is how this works with hidden terminals. I think the solution to this is by learning neighbor state with "reception reports", and so the encoder does not assume that 2 nodes it can communicate with can also see each other's transmissions. It still seems to me though that they are going to have hidden terminal issues.

To decode, each node has a packet pool with packets it has recently received or sent; the packets are hashed and keyed by packet ID. When it receives an encoded packet, it gets the relevant packets from the packet pool if they have not yet been garbage collected. Also, they do hop-by-hop acks and retransmissions.

Their results from different toy topologies are a 1.1-1.3 throughput gain for Alice-and-Bob and X-topologies with long-lived TCP flows, and 1.35-1.5 throughput gain for the cross topology. They do a lot better with UDP flows -- 1.58-2 for Alice-and-Bob, 1.5-1.75 for X-topology, and 2-4 for cross. All of these throughput gains are less than the theoretical Coding+MAC gains because of header overhead. In a 20-node wireless ad hoc network, TCP didn't have much improvement with coding (2-3%) because of TCP backoff after a collision loss. This is a hidden terminal problem. When they bring all the nodes closer together and remove hidden terminals, they get a 38% improvement. They get a 3-4x improvement for UDP when congestion is high.

-----------------

Class notes:
-- topology matters - wheel is best
-- symmetry also matters -- need symmetry to do coding
-- hosts need to cache for long enough, and the sending proxy needs to keep track of cached state correctly