ExOR: Opportunistic Multi-Hop Routing for Wirless Networks; Biswas & Morris

ExOR is a routing technique that broadcasts batches of packets to some set of nodes, out of which the "best" receiver proceeds to send the packets it received, with other receivers taking turns to fill in the packets the "best" one left out. In this way, ExOR can send packets with a smaller number of retransmissions than via traditional routing. Since a packet is forwarded by a single node, ExOR works with existing radio hardware, unlike many cooperative diversity schemes, which is why I assume the paper didn't attempt to compare any cooperative diversity techniques to ExOR.

ExOR uses a forwarder list that contains an ordering of when receivers should send their packets. Receivers "closer" to the destination send their packets sooner than those farther away, and nodes further down in the forwarder list decide when to transmit as-of-yet-unsent packets based on a predicted time of how long it takes higher priority nodes to send. Nodes pass around a batch map with each packet that contains information about which packets have been transmitted by which nodes, so packets won't be retransmitted unnecessarily. This method adds a bit of overhead since it's a map of all packets in a batch, sent in every packet, but this overhead doesn't seem to be all that detrimental to throughput based on an experiment that varied batch size.

ExOR only guarantees 90% packet arrival and cannot be paired with reliable transport such as TCP because its batching scheme might not work with TCP's chosen window size. After 90% of packets have reached the destination, ExOR finishes the batch using traditional routing.

The authors compare ExOR to traditional source routing using the ETX metric in Roofnet. They enforce the "store and forward" model at the level of entire files to prevent multiple nodes from sending at a time. A strength ExOR has over ETX-based source routing is that ExOR can make use of asymmetric links because the batch map doesn't have to flow back over the same path the packets used, though how the path is chosen in that case the authors don't say. ExOR has over 2x the throughput with mostly fewer packet transmissions; its hops can travel longer distances, hence bypassing some intermediate transmissions.

One complaint I have about the paper is an aesthetic one: the figures were laid out out-of-order, which made it difficult to quickly find the figure the text was describing.