Thursday, October 9, 2008

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

This paper uses the inherent broadcast mechanism in wireless networks to increase throughput of multi-hop wireless networks. I think the idea of late-binding in routing decisions is very smart. Traditional routing protocols choose the best route beforehand. ExOR broadcasts every packet with a “forwarder list”. The list contains the set of packets that are likely to be closest to the destination. But since other packets hear it too, we inherently end up with redundancy in routes.

ExOR operates on batch of packets. The source node includes a list of candidate forwarders for each packet, essentially an ordered list of nodes prioritized by their distance to the destination. All nodes that receive the packets wait till the end of the batch. Using a timer for synchronization, nodes transmit the packets they have received in order of priority. This keeps moving forward till the packet reaches the destination. The forwarding list is estimated by the source by having a “link-state” of the entire network. The metric used is ETX. ETX ensures that this seemingly crazy method of broadcasting at every step is making forward progress towards the destination. After 90% of the transfer is complete, ExOR falls back on traditional routing mechanisms. Overall, I think this is a very smart idea and the fact that they got it to work on real networks is impressive.

By design, this mechanism increases latency. Hence it is not suited for streaming, web etc. Given that the only practical example of a multi-hop network that I know of is RoofNet (or networks that increase the coverage of a wireless network), and Internet access typically consists of web accesses, I wonder how useful ExOR is in practice.

All this variable latency per packet might leave TCP totally confused! If TCP isn’t happy with ExOR, this makes its case even weaker. What are the other scenarios? Maybe applications that work over intermittent networks…

Also, this idea seems unsuited to scenarios that concentrate on power optimization. If nodes mostly sleep and wake up only periodically as in sensor nodes or PSM in Wi-Fi (does it make sense in ad hoc Wi-Fi?), ExOR is not too useful.

If you buy into the idea of multi-hop wireless networks, I think ExOR is a good paper to keep. I vote for it.

Btw can somebody tell me what has ExOR got to do with the XOR operator? J

1 comment:

Ashima Atul said...

I liked your point about ExOR not well suited for sensor nodes or PSM in Wi-Fi. ExOR may not be useful for networks that change too often.