ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

S. Biswas, R. Morris, "ExOR: Opportunistic Multi-Hop Routing for Wireless Networks," ACM SIGCOMM Conference, (August 2005).

One line summary: This paper describes a wireless routing protocol called ExOR that is inspired by cooperative diversity schemes and that achieves significant improvement in throughput over traditional routing protocols.

Summary

This paper describes a wireless routing and MAC protocol called ExOR. In contrast to traditional routing protocols that choose a sequence of nodes along a path to route through and then forward packets through each node on that path in order, ExOR is inspired by cooperative diversity routing schemes, and broadcasts each packet to a list of candidate forwarders from which the best node to receive the packets forwards them in turn. The authors demonstrate that ExOR substantial increase in throughput over traditional routing protocols. One reason for this is that each transmission in ExOR may have a more chances of being received and forwarded. Another reason is that it takes advantage of transmissions that go unexpectedly far or that fall short. Four key design challenges for ExOR were (1) nodes must agree on which subset of them received each packet, (2) the closest node to the destination to receive a packet should be the one to forward it, (3) there is a penalty to using too many nodes as forwarders since the cost of agreement go up, and (4) simultaneous transmissions must be avoided to prevent collisions.

Briefly, the way ExOR works is as follows. The source batches packets destined to the same host and broadcasts the batch. Each packet contains a batch map that indicates the highest priority node to have received a packet. Each packet also contains a forwarder list of nodes that is in order of increasing cost of delivering a packet from that node to the destination. The cost metric used is similar to ETX. A node that receives a packet checks the forwarder list for itself. It checks the batch map in the packet and uses it to replace its local batch map if it indicates a higher priority node has received it. Nodes forward all remaining packets that have not been yet received by the destination and the nodes do this in the order in which they appear in the forwarder list. Nodes estimate the time they need to wait before sending or use a default value if they have no basis for guessing. Once the last node in the forwarder list has transmitted, the source starts the process again by broadcasting all packets not yet received by any node. The destination sends copies of its batch map to propagate information back to the sender about which packets were received. Nodes only continue transmitting until they receive indication that 90% of the batch has been received; the rest is then forwarded using traditional routing.

ExOR was evaluated on Roofnet. The authors measure the throughput obtained when transmitting 1MB using traditional routing and ExOR between each of 65 pairs of nodes. They compare the 25 highest and 25 lowest throughput pairs (with respect to traditional routing). ExOR outperforms traditional routing even over just one hop. They also show that ExOR had to retransmit packets on average half as many times as the traditional routing protocol did. They examine the performance of ExOR using various batch sizes and conclude the optimal size is likely between 10 and 100 packets. They use a simulator to study the effects of shared interference on the performance of ExOR and conclude that it only slightly hurts ExOR’s performance. Lastly they show that the throughput of ExOR exhibits less variance than that of traditional routing.

Critique

I liked the ExOR protocol because I thought it was unusual and clever and it did get much better throughput than traditional routing. I thought it was especially interesting that it got better throughput even over one hop. I also liked how in the evaluation section, the authors broke their results down to the 25 highest and lowest throughput pairs because it was informative and a nice way to think about the results.

All that said, here are some things I didn’t like about this paper. The authors assume that the reception at different nodes is independent and that there is a gradual falloff in delivery probability with distance, and the performance of ExOR in part depends upon these assumptions, but it seems these could be looked at more closely. I thought their simulation might have been too oversimplified to the extent that I’m not convinced it really gave much useful information. Another thing is that it seems like the nodes have to maintain a lot of state (delivery probability for all pairs, unless I’m misunderstanding something). Also, again as in some other papers from these authors, they ran their evaluations while other traffic was running over their Roofnet testbed. This just seems bad to me because I thought scientists were supposed to control as many variables as possible so that their experiments are repeatable. Another thing regarding their evaluations is that they had the traditional routing protocol send the entire file to the next hop before the next node starts sending. They claim this is more fair, and that may indeed be the case, but since I don’t think this is what traditional routing normally does it seems like they probably should have tried it both ways to verify that the modified approach indeed does give traditional routing better performance.

Overall though I liked this paper and I think it should stay in the syllabus.

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

J. Broch, D. Maltz, D. Johnson, Y-C Hu, J. Jetcheva, "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols," ACM Mobicom Conference, (October 1998).

One line summary: This paper uses a network simulator that the authors improved by adding relatively realistic physical and spatial models to compare four wireless ad hoc network protocols: DSDV, TORA, DSR, and AODV, that cover a wide range of different design choices.

Summary

This paper compares four wireless ad hoc network routing protocols using detailed simulations. The four protocols compared were (1) Destination-Sequenced Distance Vector using sequence number triggered updates (DSDV-SQ), (2) Temporally Ordered Routing Algorithm (TORA), (3) Dynamic Source Routing (DSR), and (4) Ad Hoc On-Demand Distance Vector using link layer feedback to detect link breakage (AODV-LL). DSDV-SQ is a hop-by-hop distance vector routing protocol that uses periodic broadcast updates and guarantees loop freedom. TORA is a distributed routing protocol that uses a link-reversal algorithm to provide on demand route discovery and runs on top of IMEP. DSR uses on-demand source routing and consists of Route Discovery and Route Maintenance phases. Lastly, AODV-LL is like a combination of DSR and DSDV because it has on-demand Route Discovery and Route Maintenance along with hop-by-hop routing and sequence numbers. These protocols were simulated using ns-2 at varying levels of node mobility and number of senders. The simulator was enhanced to allow for realistic physical layer and propagation modeling as well as node mobility. It used a random waypoint model to simulate mobility and constant bit rate (CBR) sources. The metrics by which the protocols were judged were (1) packet delivery ratio, (2) routing overhead, and (3) path optimality.

The results are presented for each metric. These results are for hosts that move at a speed of 20 m/s when not paused. In terms of the percentage of packets delivered, DSR and AODV-LL deliver between 95% and 100% of packets regardless of offered load and node mobility. DSDV-SQ drops to 70% packet delivery with constant node mobility, which the authors attribute to packets dropped on account of a stale routing table entry. TORA does well until the number of sources sending packets reaches 30 then experiences congestive collapse due to a positive feedback loop. In terms of routing overhead, DSR and AODV-LL have similar curves although AODV-LL has higher overhead when node mobility is near constant. The authors later note that if measured in bytes instead of packets, the overhead of DSR becomes much greater than AODV-LL. The overhead of TORA depends in part on node mobility and is much higher than any of the other protocols. DSDV-SQ has nearly constant overhead independent of node mobility or offered load. In terms of path optimality, both DSDV-SQ and DSR use near optimal routes regardless of node mobility, whereas TORA and AODV-LL use less optimal routes when node mobility is high. Other interesting observations the authors make are that the percentage of packets successfully delivered for broadcast packets is lower than for unicast packets. They also note that early in their experiments they found a serious integration problem with ARP; they found a workaround but note that this problem would have to be addressed in any real implementation running on top of ARP. The authors don’t really conclusively rank the protocols in the end but it is clear from the experiments that DSR is probably the best protocol, followed by AODV-LL and DSDV, with the relative ranking of these two being less clear due to tradeoffs. TORA is obviously the worst protocol in almost every respect.

Critique

Although I tend to think that real-world experiments are always preferable to simulations, I like that the authors improved the network simulator to include a spatial model to simulate host mobility and a relatively realistic physical layer and radio network interface model. I also appreciated the thoroughness of their simulations with respect to their clearly stated metrics. Their section describing their experimental results was considerably easier to follow than most papers and the way they laid out their graphs made it pretty easy to compare the results from the different protocols. I also like that they provided additional, more in-depth explanations for certain observations where they were warranted, for example, their explanation of the congestive collapse of TORA. Their section containing additional observations was nice too. For some reason I am having trouble questioning their assumptions and making criticisms of this paper (nothing immediately jumps out at me), but because they used a simulator and also implemented all the protocols themselves there are clearly going to be a lot of assumptions that underlie their results. I thought they did a pretty good job of clearly stating what all these assumptions were though, so at least they are there for readers to take into account. I liked this paper and I think it’s probably good to keep it in the syllabus.