A High-Throughput Path Metric for Multi-Hop Wireless Routing

De Couto, Aguayo, Bicket, Morris; Mobicom 2003

networking routing ad-hoc metrics roofnet etx

@inproceedings{decouto:mobicom03,
  title = {A High-Throughput Path Metric for Multi-Hop Wireless Routing},
  author = {Douglas S. J. {De Couto} and Daniel Aguayo
            and John Bicket and Robert Morris},
  booktitle = {9th {ACM} International Conference on Mobile
               Computing and Networking ({MobiCom} '03)},
  year = {2003},
  month = {September},
  address = {San Diego, California},
}

Minimizing hop count is not the best routing metric for all cases

• On wired networks, where loss is relatively low and differences between most links negligible, it makes more sense
• On wireless networks where links vary greatly with physical distance, terrain, and other factors and where losses may be high, it's not as suitable
  • Minimizing hop count equates to minimizing geographic distance, thereby preferring links with lower signal strength, more loss, etc
  • Hop count also doesn't provide enough information to differentiate between paths of same length, a common case in dense networks
    • Interesting note: Low-quality links may not be useful for data, but may be fine for low-bandwidth messages, e.g. routing control updates

This paper introduces expected transmission count metric (ETX)

• "Minimizes expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination."
• ETX goals: Find high throughput paths while accounting for loss rates, asymmetry, and interference, but ignoring network load (congestion)
• ETX of a link = 1 / (d_f * d_r), where:
  • Value d_f is the delivery ratio in the forward direction (data)
  • Value d_r is the delivery ratio in the revers direction (ack)
  • Both are measured using dedicated link probe packets
    • Broadcast packet of fixed size at known average period (jittered by 10%), say 1 second
    • Nodes track probes received recently, say 10 seconds
    • Delivery ratio from a sender is then the number of probes received recently over the number of probes that should have been received
    • Probes contain the number of probes received by sender from each of its neighbors, needed to calculate the reverse directon for ETX at recipient
• ETX of a path is sum of ETX along links

Alternatives:

• Hop count with a maximum loss threshold may cause some destinations to be unreachable
• Product of per-link delivery ratios fails to account for interference
  • E.g., a two hop path with perfect links is not a better choice than a one hop path with 10% loss, because of the self-interference present at the middle node (it can't Tx to the 3rd node while receiving from the 1st node)
  • Note though, that this doesn't extend in the same fashion beyond three hops, as other segments may then be able to transmit
• By the same token, can't minimize highest loss ratio along a path

Points from paper:

• For many platforms, notably including WiFi, both delivery and acknowledgement (forward and back directions) must work well for transfer to be reasonable
  • ETX only makes sense under that assumption
• Heavy congestion may block probes from being sent, unduly causing link ETX to go to zero