ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

ExOR is a routing protocol that attempts to exploit ‘lucky’ delivery of packets along multiple lossy (hopefully in an uncorrelated way) hops from each router on the path. Each sent batch of packets is broadcast with an ordered list of next-hops. When a router receives a packet, it waits an amount of time according to where it is in the priority list and the sending rate in its environment and forwards packets it did not overhear from nodes higher in the priority list. The nodes on the ordered list are sorted by each nodes ETX to the destination and pruned based on which nodes which are used well enough in a simulation of ExOR. ExOR only attempts to transmit 90% of the packets in a batch, on the assumption that the last packets in a batch will be more expensive to send due to a higher liklihood of collisions (due to insufficient information to schedule packet sending well). The remaining packets are expected to be transmitted through traditional hop-by-hop metrics (though the authors did not appear to do this in their evaluation).

The authors evaluated ExOR on RoofNet comparing its efficiency to the RoofNet's routing with the ETX metric. The authors measured throughput compared to traditional routing (presumably with the ETX metric). They sent 10% more traffic when testing ExOR to compensate for the reduced delivery rate. Even accounting for this extra traffic, the authors found substantially better throughput than the ‘traditional’ routing for multi-hop paths and especially for the poorest routes under traditional routing.

Based on the evaluation, it appears that this protocol targets bulk transfers. The authors did not evaluate latency, and appear to expect users to run a transport protocol unlike TCP, since this technique will certainly introduce jitter and/or out-of-order delivery and/or losses. The authors implemented a web proxy, only using ExOR for 100KB or larger transfers, but unfortunately the paper does not evaluate that proxy's actual overhead.