2008-10-07 Readings - Routing in Ad-hoc Networks

A HIGH THROUGHPUT PATH METRIC FOR MULTI-HOP WIRELESS ROUTING

Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris.

Summary:

Presents the ETX (Estimated transmission count) metric. Motivated by the fact that conventional DSDV hop-count metric is broken - picks long links with high error rates instead of short links with low error rates. Routing packets get through in DSDV but data packet does not. ETX calculated as 1/(df x dr) where df and dr are the forward and reverse delivery probabilities, and their product is the probability that a packet is transmitted successfully. df and dr found using dedicated link probe packets, sent according to some known size and average frequency. Can be implemented by modifying DSDV and DSR. Performance is best when the network has many loss links, or transmitters have low power. For a given network, performance improve is best for multi-hop links. Discrepancy between size of link probe packets and data packets can decrease performance.

Discussions & Criticisms:

Still don't somewhat skeptical about the multi-hop wireless network concept ... Where would such networks be needed, given that we have so much wired infrastructure in place, even in 3rd world countries? Seems only needed for sensor nets and other such niche applications.

As already mentioned in their own evaluation, any time you have a transmission count based thing you would likely have issues with packet size variations. Glad to see they modified the metric to ETT (Estimated transmission time) for Roofnet.

Also, the metric solves specifically the problem of conventional DSDV not finding routes with low loss rates. What about other metrics for evaluating a routing algorithm? Overhead (for both traffic and latency)? Stability? Speed of convergence? Topology changes (either nodes moving or link quality change)?

It wasn't immediately clear that with ETX replacing hop-count in DSDV, DSDV will preserve its loop-free property.

I think the whole wireless multi-hop routing thing has gone through the typical borrow-first refine-later process. That process is pretty evident in the paper.



A PERFORMANCE COMPARISON OF MULTI-HOP WIRELESS AD HOC NETWORK ROUTING PROTOCOLS

Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva.

Summary:

Compares the performance of DSDV, TORA, DSR, and AODV protocols. Emphasize the performance of protocols under various degrees of mobility. Done in ns2 with several modification to take care of wireless link details. Movement patterns with each node move to a random destination at a constant uniformly distributed speed, and then pause for a range of discrete pause times. Nodes send at constant bit rate, and various number of nodes send for various scenarios. Figure of merit include delivery ratio, and number of routing packets (overhead). Bottom line finding: AODV and DSR performs well, DSDV and TORA not so well.

Discussions & Criticisms:

Routing skepticism re multi-hop wireless networks.

The study emphasize mobility a lot. Good thing their results extend to pretty long pause times (900 seconds = 15 minutes), else we wouldn't know the protocol performance for stable topologies. I would argue they need even longer pause times. 30 sources and 15 minutes pause time = a topology change roughly every 30 seconds - still a very very non-stable network.

Also another interesting axis to plot might be the performance vs. the speed at which the nodes moved.

Maybe the Roofnet guys need to build a car-roof net and repeat this experiment for a "real" implementation comparison. Would be more convincing than ns2 stuff.