ExOR

This paper is a follow-on to roofnet and ETX. It describes ExOR, a broadcast-based routing algorithm. The basic idea is simple: You broadcast a packet. Those that hear it correctly decide amongst each other as to when they've received it. Then, the one closest to the destination does this again.

That's the story anyhow. The implementation is a mess, with "bundling" of packets required to mitigate the inevitable loss, and then traditional routing to deal with those lost packets. The latency losses for such a system are enormous, but that's not discussed at all by the authors. They simply emphasize throughput as some godly metric. There's no discussion of scalability either, as these gossip algorithms won't. This seems nearly wholly unusable.

That's not to say that there are not clever ideas here. It's clear that a great deal of data is wasted in a wifi network because of broadcast. Because only one router can talk at a time, we should gain some benefit by forcing the others to listen. The authors listed erasure coding in related work, but said that their system did not need to identify specific paths, or disjoint paths. That's true, but only in a superficial way. They do identify the optimal cost path, for instance.

I like the erasure coding mechanism more. I see that they are attempting to deal with the broadcast properties, but this is not correct. It seems to me that doing the following would be better:

S broadcasts.
All others hear it. You wait (random * error rate on the packet) to broadcast yourself. This means that those who got it better will broadcast first, getting the packet along. Also, the erasure coding will allow the first two or three packets to get to the end, and allow for reconstruction there.