ExOR

If this paper tells us what ExOR stands for, I couldn't find it. In any case, ExOR is a routing algorithm that takes advantage of variations in signal quality and the broadcast nature of wireless networks. The main idea behind ExOR is that the source broadcasts every packet (where packets are grouped into batches). Then, every receiver re-broadcasts packets in order of priority, where the priority is determined by the sender and sent with the ExOR header. The retransmitters do this by determining their place on the list, and then waiting for everybody above them on the priority list to transmit. Retransmitters only retransmit packets that have not been transmitted by higher priority nodes.

How do sources determine priority? From what I could tell in the paper, periodic pairwise tests are conducted, and then the information is transmitted throughout the network. Each node therefore ends up with a full map of the network and therefore knows the preferred intermediate nodes for any destination.

The claim is that this algorithm is great for bulk data transfer, because it can take advantage of 1) packets that travel farther than expected and 2) packets that don't travel as far as expected. Packets that travel farther than expected are simply that much closer to the destination, which is good. Packets that don't travel as far as expected would normally be retransmitted by traditional routing algorithms, whereas they at least make some progress with ExOR.

I have a few complaints about ExOR. First of all, it is useful only for bulk transfers. It is very good at improving throughput, but the latency cost is (I imagine) rather high (this is not mentioned in the paper). The paper gets around this by saying that it uses split TCP connections, and that ExOR should only be used for bulk file transfer. This naturally violates the E2E principle, not only because the TCP connection is being split, but also because there must be some decision maker at the wireless-wired interconnect that decides whether or not to use ExOR. This decision maker probably has to inspect packets (to see if they are file transfers of some sort - such as FTP or torrents), and guess on this issue. This is less than ideal.

ADDENDUM (8:56 PM): I forgot to mention that this is unlikely to work for incredibly dynamic networks, and is much better in static networks, where the broadcast-your-neighbors mechanism works much better (as we saw in the previous paper comparing DSDV and DSR).