Tuesday, October 7, 2008

A High Throughput Path Metric for Multi-Hop Wireless Networking

Minimum hop-count is the metric widely used for route selections. This is sort of a natural extension from the wired world where a link is treated as up/down. The wireless world requires a more nuanced dealing and this paper starts off with experimental results showing why hop-count often doesn’t pick the route with the best throughput. Links have varying losses and asymmetry. Picking a route based on hop-count is clearly meaningless especially under churn.

ETX to the rescue! Expected Transmission Count (ETX) tries to estimate the number of link-layer retransmissions. Dedicated link probe packets are sent to calculate the delivery ratio of the link. Each node broadcasts probes periodically, and nodes calculate the ratio of the number of packets received to the number of packets that would have been transmitted, in a window. Inverse of the products of the delivery ratios in both directions is the ETX of the link. ETX of a route is the sum of the link metrics. The authors show the elegance of their metric by easily retro-fitting their metric into existing routing protocols.

I had a few questions on the paper:

1. How does the metric function when different node pairs have links with different bit-rates? I guess we could incorporate this information into ETX and calculate the end-to-end throughput for route selection.

2. While the authors have been clear that load balancing is not what they are targeting, I wonder how different ETX would behave when the network is loaded.

3. While on load, a sensitivity analysis on the significance of w, the window used for calculating the ETX of the link would be interesting. Like most systems this is a parameter to be “tuned” – high values would make it less susceptible to transient changes while low values would make it agile.

4. I wasn’t clear on how “interference between successive hops in a multi-hop path” is captured by ETX.

5. ETX seems to give equal weightage to delivery ratios in both directions – can we optimize this? I am not sure how link layer acknowledgements work, but is every packet acknowledged? If not, shouldn’t I assign more weight to the forward delivery ratio?

Overall, I vote to keep this paper in the reading list. It presents a landmark shift and also encourages discussion with a bunch of related/unanswered questions.

1 comment:

cs268ozan said...

I like the idea of weighting the forward link reliability more than the backward reliability. Even if not every packet is acked, the acks are still much smaller than data packets, and are therefore less likely to collide with other packets.