XORs in the Air

This paper extends the idea of using the broadcast nature of the wireless medium by adding another source of optimization: routers can encode packets if they know that the next hop can decode the packets; a router can know this by listening in on other transmissions. This basically allows the algorithm to increase the theoretical capacity of the wireless links, since in some cases multiple packets destined for several next hops can be sent as a single packet, given knowledge of what each destination has heard.

The routing algorithm, called COPE, eavesdrops on neighboring transmissions. Each transmission contains information about what packets that node has heard, as well as acknowledgements for packets it has received, along with the packet(s) it is transmitting (some XORed together). In some cases, it aggressively encodes packets without knowing for sure that the receivers can decode them; this utilizes ETX to figure out the forward probability of each link. One interesting thing here is that unlike ExOR, it seems all packets are sent this way and none use traditional routing (there is no arbitrary 90% metric of where to go from one regime to another).

COPE utilizes bitmaps in a number of cases to reduce the overhead of the routing algorithm. One place this occurs is in the ACKing mechanism; there is an independent link-layer ACK algorithm for COPE, necessary because the aggressive encoding may be too aggressive (and, of course, the links are shared/unreliable).

COPE for UDP increases throughput, sometimes by large amounts, depending on the particular topology. However, the major problem with COPE is that it interacts badly with TCP due to to TCP's problems with hidden nodes; COPE cannot help throughput because hidden nodes combined with congestion control gives small queues and little opportunity for coding. This weakness is pretty major, but I think that some obvious refinements may change this. For example, having TCP-awareness in the link algorithm (as in a previous paper we read) could make the ACKing mechanism of the link layer work better with TCP ACKs to avoid unnecessary congestion control.