Path Discovery Mechanism/Metrics
This page is dedicated to the Metrics implemented in XO's PDM. Before we discuss the details of this implementation we briefly introduce some popular metrics used in multihop wireless networks, including the Airtime Link Metrics, proposed in IEEE802.11s. Those familiar with the topic might want to skip to the XO's metric section.
Brief introduction to Metrics
An important characteristic in which routing protocols can be classified is the metrics used in support of a routing decision. A metric is a numeric indication of the cost of a path (generally the lowest the better) that will grasp how desirable (or undesirable) a given path is.
The most intuitive of the metrics is probably the path length. In this case, the metric will try to determine the shortest path between any two points of a network. In computer networks it is common to try to minimize the number of hops a datagram will to go through. This is called a hop-count metrics. It is not difficult to see that minimizing the hop counts are not always the best decision. Anyone used to the traffic on large cities will agree that the shortest path is not always the fastest.
Multihop wireless networks
In a network in which nodes move quickly, the links will break and form continuously and the routing protocol must be able to converge to the new topology in a short interval. In such an environment, hop count seems to be a natural choice, particularly if we assume that traffic seems to flow to and from gateways connecting the mesh network to the wired Internet. But it is important to observe that 802.11 networks are multirate networks. It is common for a node to support more than ten codification rates and higher rates mean shorter ranges. For this reason, hop count might not always be the best option. In today’s multihop wireless networks, the medium is the scarcest resource and it makes sense to privilege the higher rates, for they consume less airtime, even if this will result in longer paths.
ETX and ETT
One of the earliest proposed metrics – the Expected Transmission Count (ETX) – computes the expected number of times a packet would have to be transmitted to successfully reach a neighbor. An evolution to ETX is the ETT metric, where the number of tries is replaced by the expected time a node would need to successfully forward a frame. This way, the metric would account for the different rates at which nodes can transmit in a wireless network.
Beyond ETX and ETT
Recent WMNs implementations may take advantage of some more advanced techniques as the simultaneous use of orthogonal radio channels. This brings new demands in terms of metrics – they will have to account for intra-flow interference (when two nodes transmitting packets from the same flow interfere with each other) and inter-flow interference (when it happens among concurrent flows). A protocol which deals with inter-flow interference is Weighted Cumulative ETT (WCETT), while the Metric of Interference and Channel-switching (MIC) and iAWARE are designed to deal with both inter and intra flow interferences.
The quick and unpredictable variation of the link quality is another phenomenon to take into consideration when determining an effective metric for wireless networks. Some metrics take the standard deviation in addition to link quality average values. Examples of instability-aware metrics are the modified ETX (mETX) and Effective Number of Transmissions (ENT).
Another increasingly popular approach is the use of power-aware metrics, which accounts for the battery power available for a given node in a mesh. Power aware metrics are more keen to MANETs where the routing nodes are mobile (and thus battery powered) than to WMNs, where routing nodes may in general be AC powered.
IEEE802.11s: Airtime Link Metric
The IEEE 802.11 Task Group “s” is standardizing the Airtime Link Metric, which tries to minimize medium usage by taking into account not only the datarates that a given link can support, but also the probability of success on the transmission of frames.
The Airtime Link Metric formula:
COST = [O + (Bt/R)] / [1 - Ef]
where O is a constant overhead latency that varies according to the PHY layer implementation, Bt is the test frame size (1024 bytes), R is the data rate in Mb/s at which the MP would transmit a test frame and Ef is the measured test frame error rate
XO's metrics
For the XO's PDM the cost of a path will be the sum of the costs of best PREQs forwarded (and successfully decoded) by the nodes that form the path during the path discovery process. With best PREQs we mean those transmitted at the highest data rates.
In a path formed by four nodes (A -> B -> C -> D) each of the participants have broadcast four PREQs with the costs and data rates listed in Table 1. If all nodes successfully receive the 54Mbps PREQ from its predessesor in the path, the cost of the path will be 39 (13 x 3). But it may be the case that some of the PREQs are lost, due to poor link quality or collision. Say, that C could not decode the 54 and the 36Mbps PREQs. In this case, the cost of the path will be 72 (13 + 46 + 13).
| datarate (Mbps) | link cost |
|---|---|
| 54 | 13 |
| 36 | 28 |
| 11 | 46 |
| 1 | 64 |
Airtime versus Path Length
Given the costs in Table 1, it is easy to see that the second less expensive path is a two hops path formed by two 54Mpbs links (i.e. links that were able to transfer the 54Mbps PREQ). Even a four hops path will be preferred over a single hop path if the former consists of three good links whereas the latter is a marginal link that cannot work at rates superior to 1Mbps.
It makes sense to choose many fast links instead of a slow one. A 1,500 bytes frame will take 12.2ms to be transmitted over a 1Mbps link, this is as long as 49 times the time needed to transfer the same frame over a good link (one that supports 54Mbps).
For one side we may consider that deciding the quality of a link over the reception of a single frame may not be a very precise mechanism - a 54Mbps PREQ frame may not be received just because of a transient spectrum condition or even due to a congested medium. On the other hand, we have to consider that (a) the routes will expire after some seconds (current default is 10 seconds) and (b) sending more control traffic in order to make better inferences cost airtime.
Table 2 displays all the possible combinations of links and associated costs for a mesh not bigger than 5 hops.
| total cost | datarates for each link |
|---|---|
| 13 | 54 |
| 26 | 54,54 |
| 28 | 36 |
| 39 | 54,54,54 |
| 41 | 54,36 |
| 46 | 11 |
| 52 | 54,54,54,54 |
| 54 | 54,54,36 |
| 56 | 36,36 |
| 59 | 54,11 |
| 64 | 1 |
| 65 | 54,54,54,54,54 |
| 67 | 54,54,54,36 |
| 69 | 54,36,36 |
| 72 | 54,54,11 |
| 74 | 36,11 |
| 77 | 54,1 |
| 80 | 54,54,54,54,36 |
| 82 | 54,54,36,36 |
| 84 | 36,36,36 |
| 85 | 54,54,54,11 |
| 87 | 54,36,11 |
| 90 | 54,54,1 |
| 92 | 11,11 |
| 92 | 36,1 |
| 95 | 54,54,54,36,36 |
| 97 | 54,36,36,36 |
| 98 | 54,54,54,54,11 |
| 100 | 54,54,36,11 |
| 102 | 36,36,11 |
| 103 | 54,54,54,1 |
| 105 | 54,11,11 |
| 105 | 54,36,1 |
| 110 | 11,1 |
| 110 | 54,54,36,36,36 |
| 112 | 36,36,36,36 |
| 113 | 54,54,54,36,11 |
| 115 | 54,36,36,11 |
| 116 | 54,54,54,54,1 |
| 118 | 54,54,11,11 |
| 118 | 54,54,36,1 |
| 120 | 36,11,11 |
| 120 | 36,36,1 |
| 123 | 54,11,1 |
| 125 | 54,36,36,36,36 |
| 128 | 1,1 |
| 128 | 54,54,36,36,11 |
| 130 | 36,36,36,11 |
| 131 | 54,54,54,11,11 |
| 131 | 54,54,54,36,1 |
| 133 | 54,36,11,11 |
| 133 | 54,36,36,1 |
| 136 | 54,54,11,1 |
| 138 | 11,11,11 |
| 138 | 36,11,1 |
| 140 | 36,36,36,36,36 |
| 141 | 54,1,1 |
| 143 | 54,36,36,36,11 |
| 146 | 54,54,36,11,11 |
| 146 | 54,54,36,36,1 |
| 148 | 36,36,11,11 |
| 148 | 36,36,36,1 |
| 149 | 54,54,54,11,1 |
| 151 | 54,11,11,11 |
| 151 | 54,36,11,1 |
| 154 | 54,54,1,1 |
| 156 | 11,11,1 |
| 156 | 36,1,1 |
| 158 | 36,36,36,36,11 |
| 161 | 54,36,36,11,11 |
| 161 | 54,36,36,36,1 |
| 164 | 54,54,11,11,11 |
| 164 | 54,54,36,11,1 |
| 166 | 36,11,11,11 |
| 166 | 36,36,11,1 |
| 167 | 54,54,54,1,1 |
| 169 | 54,11,11,1 |
| 169 | 54,36,1,1 |
| 174 | 11,1,1 |
| 176 | 36,36,36,11,11 |
| 176 | 36,36,36,36,1 |
| 179 | 54,36,11,11,11 |
| 179 | 54,36,36,11,1 |
| 182 | 54,54,11,11,1 |
| 182 | 54,54,36,1,1 |
| 184 | 11,11,11,11 |
| 184 | 36,11,11,1 |
| 184 | 36,36,1,1 |
| 187 | 54,11,1,1 |
| 192 | 1,1,1 |
| 194 | 36,36,11,11,11 |
| 194 | 36,36,36,11,1 |
| 197 | 54,11,11,11,11 |
| 197 | 54,36,11,11,1 |
| 197 | 54,36,36,1,1 |
| 200 | 54,54,11,1,1 |
| 202 | 11,11,11,1 |
| 202 | 36,11,1,1 |
| 205 | 54,1,1,1 |
| 212 | 36,11,11,11,11 |
| 212 | 36,36,11,11,1 |
| 212 | 36,36,36,1,1 |
| 215 | 54,11,11,11,1 |
| 215 | 54,36,11,1,1 |
| 218 | 54,54,1,1,1 |
| 220 | 11,11,1,1 |
| 220 | 36,1,1,1 |
| 230 | 11,11,11,11,11 |
| 230 | 36,11,11,11,1 |
| 230 | 36,36,11,1,1 |
| 233 | 54,11,11,1,1 |
| 233 | 54,36,1,1,1 |
| 238 | 11,1,1,1 |
| 248 | 11,11,11,11,1 |
| 248 | 36,11,11,1,1 |
| 248 | 36,36,1,1,1 |
| 251 | 54,11,1,1,1 |
| 256 | 1,1,1,1 |
| 266 | 11,11,11,1,1 |
| 266 | 36,11,1,1,1 |
| 269 | 54,1,1,1,1 |
| 284 | 11,11,1,1,1 |
| 284 | 36,1,1,1,1 |
| 302 | 11,1,1,1,1 |
| 320 | 1,1,1,1,1 |