Mesh Network Details
Introduction
Details of the mesh networking provided by the XO laptop and School server are provided here. See also a related Mesh Network FAQ.
Design goals
The design specifications for the wireless networking interface on the XO laptop include:
- Ability to act as a mesh point when laptop's main CPU is off. (Small enough to run autonomously on Marvell's 88W8388 802.11 wireless module)
- Minimize power consumption in autonomous mode.
- Support for asymmetric links/paths.
- Incremental releases -- mesh networking is needed immediately on XO. Upgrades will continue to improve functionality and adherence with standards.
- Simultaneously act as a Mesh Point as well as an infrastructure node.
- Follow 802.11s draft when possible.
Standards Compliance
The Mesh Routing Protocol used in the OLPC laptop (OLPC-Mesh) is based on the 802.11s standard being developed by the 802.11 Task Group S [1].
OLPC-Mesh was based on the first draft produced by TGs, version 0.1. At the time of this writing, TGs is working on version 1.0 of the draft.
As we are using hardware that was designed prior to the 802.11s draft, we cannot use the new mesh frame type, identified by type = 0x3 in the Frame Control field. Instead we are using WDS frames extended with mesh specific header fields.
Backwards Compatibility
In order to avoid forced obsolescence of XO laptops already deployed in a school, limited backwards compatibility should be an important feature of future firmware revisions. Laptops issued in previous years should mesh network peacefully with laptops issued to new classes. This compatibility may take a form similar to 802.11b/g operation --- if a single laptop requiring extended WDS frames is present on a mesh, all mesh points and portals should revert to extended WDS frames in order to support it and its brethren.
Mesh Points
In typical operation, the XO laptop is operating as a mesh point. It uses its WiFi interface to both access the network itself and to relay traffic from other mesh points. A mesh network requires a more dynamic path selection (routing) protocol than that utilized in wired networks. Even the decision of which wireless channel to use is more difficult in the mesh case.
Mesh Path Selection and Forwarding
The path selection mechanism is based on a simplified version of the Hybrid Wireless Mesh Protocol (HWMP) proposed in the 802.11s draft. HWMP combines on-demand route discovery with support for proactive routing.
Proactive routing requires the formation of a tree topology under a root node. OLPC-Mesh does not support proactive routing at this time.
On-demand path discovery is largely based on Ad-Hoc On-demand Distance Vector (AODV) routing.
Paths are built using a route request / route reply management frames. When a source node needs to transmit a frame to a destination for which no path exists, a broadcast route request (RREQ) is broadcast through the mesh. As these requests are propagated, nodes receiving them will create routes to the source node in their routing tables. These routes are termed reverse routes and are only used to forward mesh management frames. When a node receives a RREQ destined to itself, it will respond with a unicast route reply (RREP), which will be sent back to the source via reverse routes. The intermediate nodes that forward RREPs back to the source will create routes to the destination node. This routes are termed forward routes, and are the routes used to forward data frames.
Route Tear-down and Recovery
If a frame cannot be transmitted to the next hop (i.e. when the maximum number of retries is exceeded), the route that was used for the frame is marked as invalid. If the failed route has predecessors, route error (RERR) management frames are transmitted to the source of the route. This improves the route recovery time after a mesh node leaves the coverage area of a neighbor.
Limited Broadcast
The RREQ/RREP mechanism only works for unicast traffic. Broadcast traffic is propagated through the mesh through limited flooding. Each mesh data frame contains a unique end-to-end sequence number that is set at the source. Intermediate nodes maintain a list of recently broadcast frames indexed by this sequence number and the address of the source. This table ensures that broadcast frames are retransmitted only once.
Multicast
Multicast is supported in firmware versions 5.220.9.p9 and above.
OLPC-Mesh Association Algorithm
Under HWMP, a Mesh Point should use active or passive scanning to discover neighbors and establish peer links. OLPC-Mesh does not use this mechanism. Neighbors are discovered only via the RREQ/RREP cycle.
Upon power-up (resume as well?), an XO laptop will associate itself with a mesh network in the following manner:
- The laptop will issue a DHCP request, followed by a RREQ for a Mesh Portal anycast address and wait for RREP replies, on all three channels being proposed for OLPC meshes (1, 6, and 11) before making any decisions.
- If any channel provides a lower hop count to a Mesh Portal, it is selected unless its signal strength is significantly lower.
- If all channels provide the same hop count to a Mesh Portal, random selection is used.
As no authentication of neighboring mesh points is performed, the mesh is not protected against route disruption or node isolation attacks. It is unclear if such an authentication mechanism could be successfully implemented within the guidelines of OLPC.
Mesh Portals
Up to now we have described the operation of Mesh Points. Mesh Points that are connected to an external network, and that forward traffic in and out of the mesh are referred to as Mesh Portals (MPP).
Mesh Points must find paths to a Mesh Portal in order to access the Internet. When multiple Mesh Portals exist in the mesh, the Mesh Point must select one of them. The way the OLPC Mesh resolves this problem is by defining a layer 2 ANYCAST MAC address (0xC027C027C027) that will be claimed by all the MPPs in the mesh. When a Mesh Point needs to find an MPP, a RREQ is sent for that special ANYCAST address. Each Mesh Portal receiving the RREQ will generate a RREP. The path selection method will assign higher precedence to those MPPs that can be reached through lower cost routes. Is this done by the module firmware or the software running on the laptop ?
The Mesh Point then sends a UDP datagram to the selected mesh portal, which also replies with a datagram. In order to generate the ANYCAST message, a static binding is made in the Mesh Point ARP table between an arbitrary MPP IP address (172.31.255.254 is currently used) and the ANYCAST MAC address. Then a UDP message is composed to the MPP IP address and MPP service port (currently 16), containing the contents "MPPREQ".
Mesh Portals must bind the MPP IP address (172.31.255.254) to one of their network interfaces, and listen for configuration requests sent by Mesh Points to that address on the MPP service port (16). In reply to these requests, Mesh Portals will send to the Mesh Points all the information required to access outside the mesh network. At this time this configuration information is comprised of the IP address of the selected Mesh Portal and the addresses of DNS servers.
More information about this configuration daemon can be found:
Traffic forwarding in and out of the mesh is done at layer 3 via Network Address Translation (NAT) at the host. This gives the flexibility to use any other network connection to connect the mesh to the world (e.g. PPP, GPRS, etc.).
Driver Interface
The wireless driver creates a virtual network interface just for mesh traffic (msh0 on the laptop). The main interface (usually eth0 on the laptop) is used for infrastructure traffic when the laptop is associated to an AP. It is also used for some control operations that aren't currently supported by the mesh interface, such as assigning a MAC address.
Userspace Controls
There are several system calls available to examine and modify the behavior of the OLPC-Mesh. This calls are implemented as ioctls, and can be invoked via iwpriv commands.
The first of such tools are the iwpriv fwt_* family of commands. With these commands one can examine and modify the routing table. See the Wireless Driver README file in the libertas driver directory for details.
Another useful feature for debugging and testing is the blinding table. Incoming traffic from any address that exists in the blinding table will be silently discarded by the firmware. This is useful to test specific mesh topologies that would otherwise be hard to setup. The blinding table can be accessed using iwpriv bt_{add,del,reset,list}.
There is also one ioctl call that will change the maximum TTL of outgoing mesh traffic. The TTL determines the maximum number of hops that a frame will cross before being dropped. This is used to minimize the consequences of routing loops but it also limits the number of neighbors that can be reached in the mesh. The mesh TTL can be modified via iwpriv mesh_{get,set}_ttl.
Finally, there are mesh specific statistics available through ethtool -S
Currently the following counters are implemented:
drop_duplicate_bcast drop_ttl_zero drop_no_fwd_route drop_no_buffers fwded_unicast_cnt fwded_bcast_cnt drop_blind_table tx_failed_cnt
Footnotes
[1] Note that although the frame is discarded, it will still be acknowledged by the MAC layer.