S. Biswas, R. Morris, “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” ACM SIGCOMM Conference, (August 2005). [PDF]

Summary

ExOR is an integrated routing and MAC technique that opportunistically exploits the broadcast characteristics of the wireless environment. Unlike the traditional routing protocols, where the best sequence of nodes from a source to a destination is decided before packets are routed along that path, ExOR defers the next hop decision until it knows all the nodes that received a packet and allows the closest node to the destination to be the next hop and retransmit that packet toward destination. As a result, ExOR can try multiple long but lossy links concurrently, resulting in high expected progress per transmission.

Packets are sent in batches. The source node includes in each packet a list of candidate forwarders prioritized by closeness to destination (ETX with only forward delivery probability is used in this paper) and a batch map that the sender’s best guess of the highest priority node to have received each packet. Receiving nodes buffer packets until the end of batch transmission. Then based on priority, each receiver broadcasts its received packets with updated batch maps. If a packet is somehow overheard by a node farther away than expected, it replaces the original guess with its own id as the highest priority receiver in the batch map. Essentially, each node end up with more or less the same batch map using this gossip-like protocol. Every forwarder transmits only those packets that are not ACKed by higher priority nodes. This cycle continues until 90% packets have reached the destination; the rest are transmitted using traditional routing protocol.

Evaluation of ExOR was performed on a 32 node testbed, and the authors claim that ExOR performed better than traditional routing for almost all node pairs with an average 2x end-to-end throughput gain. ExOR gain is more prominent in longer lower throughput routes (due to more probability of exploiting overhearing) than shorter higher throughput routes, but it manages to lead traditional routing throughout the spectrum. The authors believe that the best batch size is somewhere between 10 to 100 packets, but do not provide any specific value for magic formula.

Two of assumptions behind ExOR are that reception at different nodes is independent, and that there is a gradual falloff in delivery probability with distance. Through simulation, the authors show that with longer routes dependent loss more and more lags independent loss; however, maximum lag found in the simulation is 20%, which made the authors postulate that independent loss is not really a requirement but can be exploited if present.

Critique

The concept is simple and straightforward, but the paper somehow managed to make it more complex than it really is. Figure 6 as well as its description in Section 3.8 only confused everything more. And those massive plots with minute information only made things worse (LaTeX put them in an unordered fashion, which made reading the paper all the more annoying).The evaluation also did not reveal much except for showing that ExOR does increase throughput in their testbed. In addition, it also interacts badly with TCP and resorts to split connections breaking the end-to-end TCP semantics and possibly introducing overhead.