Path Discovery Mechanism/Differences from 80211s

OLPC's XO was the first device to implement a mesh network based on the IEEE802.11s, but this implementation has its own particular characteristics and diverge, though not significantly, of the current status of the IEEE802.11s draft at some points. We may consider the XO's PDM a subset of IEEE802.11s (with minor adjustments).

Please note that OLPC (along with Nortel and other sponsors) support the open 802.11s project which will help spread the standard in Linux devices. It is OLPC's intention to adhere to the standard once it is published. And this page will be obsolete.

Main differences

In this section we point out two differences from the current status of the 802.11s draft.

Path asymmetry

In IEEE802.11s' HWMP a path between S and D is assumed to also be a good path between D and S.

Whenever S wants to find a path to D, it broadcasts a PREQs frame that will eventually be responded with PREPs. For the IEEE proposal the reverse path (learned by every intermediary node when it rebroadcasts a PREQ) and the forward path (learned by the intermediary nodes that forward the PREP back to the source) are the same. When D has frames to send back to S it will just use that reverse path without the need to start a new discovery cycle to S.

Differently from the IEEE proposal, in OLPC's implementation a new path discovery mechanism will be started to find a path between D and S. In one hand, radio links are known to be asymmetrical – the fact that a node A successfully decodes a frame from B, does not imply that the opposite is correct. We must recognize that A and B will suffer different interference and contention levels by the mere fact that they are in different positions – a phenomenon perfectly negligible in wired networks, but typical of a radio transmission.

On the other hand, though accounting for path asymmetry may result in more robust forwarding, it is also true that an additional path discovery cycle will increase route acquisition time. This approach may be considered advantageous if (1) path acquisition time is not critical or (2) most paths will be asymmetrical.

Metrics

The calculation of link cost is one item where the IEEE proposal and the OLPC implementation are very different. The first introduces an Airtime link metric that reflects the time necessary for the frame to be successfully transmitted and this time calculation takes the probability of error into account. For OLPC the cost for a given link will be solely derived from the data rate at each a PREQ was received. There is no account for the probability of error other than the successful reception of the PREQ frame at a given data rate.

Check the Metrics Page

Non implemented features

Some features described in the 802.11s draft are not implemented in OLPC’s mesh and this is mainly for two reasons. First, when the first prototypes of the XOs started being tested, the 802.11s draft was still in version 1.01 and many points of the proposal were still being discussed.

The second reason is simplicity. The XO is projected to consume low power – about 5% of what a regular laptop would do – and this led to the use of the Marvell 8388 SoC, primarily designed for cell phone use and thus limited in memory and processing power. For this reason every aspect of the draft that is not fundamental was not be implemented. A little gain in efficiency on the path discovery mechanism or in the mesh operation could mean a lot of extra complexity and computer power requirements and, in this case, the simpler approach was preferred.

Link establishment

For OLPC, there is no idea of a link as being established. There are no Open Peer Link, Confirm Peer Link or Close Peer Link elements and no periodic messages to keep or check if a link is still active (as the Hello messages in AODV). An active neighbor will be a one hop distant neighbor for which there is an active path in the forwarding table, and nothing else.

Security

Currently no security mechanism is implemented at the link layer. Security is left to be implemented at higher layers (examples: network IPsec, transport, application), though none of these mechanisms will prevent, for instance, authentication issues or spoofing.

Medium access protocol

An XO will content for the medium using the Distributed Coordination Function (DCF) as described in the 802.11 standard. The MDA proposed in IEE802.11s is not implemented. The only optimization in that concern was the introduction of a Dynamic Contention Window mechanism.

Congestion Control

There is no congestion control mechanism currently. Congestion detection is currently under discussion but only to support local decisions – as increasing the Contention Window, for instance.

Power Savings mode

Though OLPC is implementing an aggressive suspend and resume mechanism that will able to keep an XO running many hours, there is no mechanism in the mesh that will make a node buffer frames for other nodes in suspend mode.