ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

[paper]

"Traditional" routing protocols choose a single path for a packet before sending the packet. In contrast, "cooperative diversity schemes" simultaneously transmit information through multiple paths and the route may dynamically change. ExOR is a cooperative diversity scheme geared towards highly lossy wireless connections.

At each hop, ExOR broadcasts each packet and then chooses the next hop in the path based on who actually received the packet. The benefit of broadcasting is to increase the chance that at least one node successfully receives the packet. Unlike standard cooperative diversity schemes, only one node is chosen to forward the packet (chosen by all the recipient nodes agreeing on who the chosen sender is). ExOR batches packets together, and each packet has a list of preferred next hops. If not all the batch makes it to one node, then other nodes that have the remaining packets will forward those packets separately. Once 90% of the packets have reached the end, traditional routing is used to send the last 10%. The forward priority list is made based on ETX with only forward delivery probability.

Their evaluation was conducted on Roofnet. They measure throughput between 65 random node pairs. First to kickstart ETX they broadcast 1500-byte packets every 10 seconds for 10 minutes and distributed the delivery probabilities. Then each selected pair transferred a 1MB file using traditional routing and then 1.1MB using ExOR. They used the different sizes because in actual ExOR the last 10% is transferred using traditional routing; they chose to omit that part and only transfer the first 90% of the 1.1MB. This is kind of weird because .9*1.1=.99, not quite 1MB. This is also weird because their actual protocol isn't pure ExOR, it's a 90/10 mix of ExOR and traditional routing; you'd think they would want to measure the actual end-to-end performance of their system.

I couldn't figure out what the heck Figure 6 is showing. Why did they only show part of the second batch? Why does it look like 2 packets left N5 and 3 ended up at N24? Shouldn't N24 have only received one copy of each packet? In general though their other results show that ExOR improves throughput, with more improvement for longer traditional routes. The main benefit seems to come from ExOR's ability to use long-distance, lossy, and asymmetric links that otherwise wouldn't have been chosen by a traditional routing protocol. I wonder though whether that would be true if the traditional routing protocol used something other than ETX?

When I first read the design of ExOR, I had a question: At what point is a longer successful path (including the cost of an agreement protocol) faster than the cost of retransmission? This seems like it would be a function of how long the path is and how likely it is for the retransmission to also fail. However looking at their evaluation I get the sense that their routes must not be much longer than the traditional routes.

Also -- I am wondering about doing traditional routing but with retransmission for each hop (meaning each interior node checks to see if the next hop received it or not and it retransmits in case of failure; but only one copy is sent out). How would that compare with ExOR?

----------------------

Class notes:
-- trying to exploit luckiness - maybe a packet will make it extra far! also unluckiness - maybe it didn't make it as far as you'd expect, but still made it a bit closer to destination.

0. determine batch size / forwarding group
1. forwarding order. topo order based on ETX to DST
2. schedule transmission of local cached packets
3. approx shared view of which node has which packets

Problems with TCP:
- batching requires more packets than typical TCP window
- changes RTT estimates a lot; will make TCP retransmission timer confused
- lots of packet reordering probably