COPE

This paper describes COPE, which is a way of increasing throughput by XORing various packets together. The basic idea is that you can take advantage of the broadcast nature of wireless to transmit multiple packets at once to multiple destinations. The easiest way to do this is to XOR several packets together, which you can do if you know that the destinations have all but one of the packets you are about to send. This is made possible by a combination of eavesdropping on packets and storing them for a short duration.

An important question is how the information about packet availability is transmitted between nodes. From what I understand, they piggyback on normal packets inside the XOR header. If a node has no packets to send, it sends out this information in periodic updates. Packets are cached for about half a second before they disappear. In the case that no explicit information is available about whether or not a node has cached a particular packet, a sender may guess based on the link reliability. When transmitting, a sender requires that the overall probability that everyone has the desired packets must be at least some threshold (80% in this case).

No sender will ever encode two packets headed for the same next hop, so each sender keeps a set of virtual queues, one for each neighbor. However, XORing large packets with small packets is somewhat wasteful, so there are actually two virtual queues for each neighbor. Then, to figure out which packets to XOR together, the algorithm simply considers the packets at the head of each queue. The algorithm never delays packets, so if no XORing is possible, it sends just one packet.

They get great results out of this, not just because they can reduce the number of transmissions that need to be made, but also because this algorithm can increase fairness at various relays. If a relay is receiving traffic from two sources, and must then retransmit both packets, it can reduce the number of packets it needs to send from 2 to 1. This helps with fairness, since each of the three nodes is now sending one packet, instead of the relay trying to send at a 2:1 ratio.