Nalanda

Citation: S. Biswas and R. Morris, “ExOR: opportunistic multi-hop routing for wireless networks,” in SIGCOMM ‘05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, vol. 35, no. 4. New York, NY, USA: ACM Press, October 2005, pp. 133-144. Available: http://dx.doi.org/10.1145/1080091.1080108

Biswas and Morris present draw from cooperative diversity schemes to present an alternative to traditional routing mechanisms. Rather than route a packet along a single best possible route, ExOR relays packets along multiple routes. This allows ExOR to take advantage of longer lossy links: even though the probability of packet delivery may be lower on such a link, even the few packets that manage to get through on many of these links can add significantly to overall throughput. Additionally, ExOR sends packets in batches, rather than one at a time, which can improve throughput even on short low loss links. Since probabilistic forwarding may not account for all packets in a batch, ExOR is used until the destination has at least 90% of the packets, and then the remaining are sent using conventional routing.

The sender chooses a subset of forwarders from all nodes in the network (to allow scaling up to larger network sizes) using a metric such as ETX. The forwarders coordinate amongst themselves to ensure that their transmissions do not interfere by setting timers which anticipate when other forwarders, ordered by priority, would probably have completed transmission. For their tests, the authors used a centralized server to maintain and distribute the routing metric. It is not clear from the paper how decentralized relay of the metric might affect ExOR performance. The requirement for ordering of transmissions amongst all forwarders surprised me; if only one node transmits at a time, this would seem to imply an overall loss of network capacity. While the results of the authors’ tests for single large files are compelling, I think it would have been very useful to get some sense of how ExOR would function with multiple sources.

The problem of coordination amongst forwarders aside, the authors also suggest that 802.11 fairness mechanisms would take care of coordination with competing transmissions. It would be useful to have some discussion in class of 802.11 fairness, and how ExOR might work with this.

The principal contribution of the paper, for me, is the way in which a property of the wireless medium which makes it problematic for traditional routing protocols - every terminal can hear every other terminal - is effectively leveraged to make routing more efficient. This is a compelling idea. However, I would really have liked to see some of the details of the protocol worked out a bit more.