ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

Summary
The ExOR paper is an approach to leverage the broadcast nature of wireless radios to achieve better performance. For each hop nodes compute what other nodes they think should forward this packet in a priority order. The priority is based on a similar metric to ETX, that is, the number of transmissions from that node to the receiver, including retransmissions. When nodes receive a packet, they look at the list of nodes that are supposed to be the next transmitter of the packet. If they are in the list they schedule it for transmission. Each node waits the amount of time it expects higher priority nodes to take to transmit their packets (packets are batched for better performance), and then, if it hasn't heard the packet(s) already transmitted, sends its batch. The intuition here is that, all nodes in the forwarder list should be 'closer' to the destination, so they should all be able to overhear each other if they heard the previous hop.

A map of successfully transmitted packets is kept at each node which is updates in response to overhearing other neighbors and in receiving maps from neighbors. This acts as a gossip mechanism and keeps maps fairly synchronized between nodes and also can prevent unnecessary retransmissions when the standard MAC ACKs aren't received. When the sender discovers that 90% or more of its packets have been transmitted to the destination it sends the last bit using traditional routing. This is because sending those few packets would require running a whole batch, which is expensive for so few packets.

This method allows ExOR to take advantage of transmissions that go unexpectedly far and/or that fall unexpectedly short. A sender might compute that a distant node close to the receiver is a great hop, but packets might not always make it that far. The sender puts that node at the top of the priority list, so if packets do make it that far they will be quickly send on to the destination, but if they don't, nodes closer to the sender will transmit the packets too. Likewise, if a packet doesn't make it as far as expected, closer nodes (to the sender) will send the packets after a short delay waiting for the expected nodes to transmit.

By running experiments on Rootnet the authors show that ExOR provides an increase in throughput for most node pairs. For short hop pairs ExOR's map acknowledgement prevents retransmission and boosts throughput by almost 35%. For more distant pairs the improvement is more like a factor of 2 to four due to the many path options in ExOR.

Comments
I liked the idea in this paper. Taking advantage of the inherent broadcast nature of wireless is a great way to improve performance. The priority lists are a nice way to deal with having to have a low overhead in reaching consensus on what packets have been received where.

A few thoughts:

• Given that an ETX metric is used to rank nodes in the priority list, and that ETX is based on probabilities, usually the highest priority node will receive the packet. This is not going to be the closest node to the target often (since that node will have a low ETX rating as it will have a high # of expected re-transmissions). Thus ExOR seems it will often simply route as ETX, with added delays for the batching. It would be interesting to see if simply using min hop-count as a metric would actually perform better here since the fall-back to lower priority nodes would naturally handle the major issue with using min hop-count metrics.

• ExORs poor interaction with TCP is unfortunate as it prevents it from being plugged in seamlessly. The reduction in variance in transmit times due to ExOR seems like it would boost TCP performance (lower RTOs) if the window size problem could be handled.

I enjoyed this paper and would keep it on the reading list.