Thursday, October 9, 2008

A High-Throughput Path Metric for Multi-Hop Wireless Routing (MIT '03)

Minimum hop count is not a good metric to choose a route. First, one high-loss link along a route would create major delay and congestion. This causes retransmission and timeout which leads to decrease in overall network throughput. However, these links may be suitable for sending routing packets instead of data packets. Min hopcount is also bad when it chooses arbitrarily among multiple "equivelant" routes. It mostly likely pick a suboptimal one. Having a metric that is more refined than hop count helps to increase throughput.

ETX is one metric specification. It predicts for each link the expected transmission count per packet. Then it picks the route that has the least combined ETX count. It approximates the ETX by sending a periodic probe (every 1 sec). By dividing the actual received probes by the number sent, you get the delivery ratio. The inverse of it is ETX. It's very simple to understand and easy to implement. It adds very little to the routing states.

ETX has its own limitations. It only interacts and reacts to mobility as good as it updates the routing states, which is delayed by WST (weighed settling time). The main essense of using transmission count is a step further than hop count; however, it doesn't go into the size of packets. It would more ideal to have something like ETX/bit.

The paper presents a simple understandable routing algorithm and implementation. It makes a argument and brings attention to the problem of min hop count. Although it would be nice to see a more comprehensive paper on routing metrics, this paper is a pretty good introduction.

No comments: