Tuesday, October 7, 2008

Summary: ETX

I found the discussion here a bit repetitive but the overall contribution compelling.  Although wireless networks have an especially high penalty per hop (a node cannot simultaneously send and receive, so pipelining is impossible and adding a hop to a route effectively halves the throughput), metrics based solely on hop count are unlikely to choose the best routes, in general because they will make an arbitrary choice among several routes with the same hop count.  A better metric is an estimated transmission count, that takes into account asymmetry and counts retransmissions due to loss into the total.  ETX calculates a probability of delivery based on the receipt of regularly spaced probe packets: the probability of receiving a packet from a neighbor is the ratio of received to expected probes in a given time window.  To accommodate asymmetry, each node must also forward its own results (according to the above calculation) to its neighbors.  Only in this way can a given node have both a sense of receipt probability over a given link (determined by expected vs. received probes along that link) and send probability (determined by the receipt probability forwarded from the other side).  The ETX is then 1/sendP*recvP -- a perfect link will have probabilities of 1 in the denominator and estimate a single transmission.  

It was considerably less painful to write this than it was to read the paper.

2 comments:

Andy Konwinski said...

"and adding a hop to a route effectively halves the throughput"

if I have a 5 hop route currently, and I add a 6th hop, you are claiming that my throughput is effectively cut in half? I don't follow. Why is this?

Peter Alvaro said...

sorry, no, I didn't say that right.

turning a 1-hop route to a 2-hop route halves the throughput. adding a 6th hop to a 5-hop route will, I believe, half the throughput of the last (5th node). overall, the best throughput for a 6-hop route will be min(nodeThroughput)/6 -- which is certainly worse that min(nodeThroughput)/5. at least, that's my interpretation.