Mesh Network Details
Introduction
Details of the mesh networking provided by the XO-1 laptop and an early School server are provided here. The later XO-1.5, XO-1.75 and XO-4 laptops do not use the same protocol. See also a related Mesh Network FAQ.
Design goals
- 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. Currently (Oct, 2008) TGs is working on version 2.0 of the draft.
More information on the differences between OLPC-Mesh and the 802.11s mesh can be found here.
Backward 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.
A comprehensive discussion on the Path Selection Mechanism, is also available.
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.
Mesh Networking Security Implications
Mesh Point operation has some additional security implications compared to WiFi station or Ad-Hoc modes.
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 in the firmware will assign higher precedence to those MPPs that can be reached through lower cost routes.
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 composed 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
Usage
These are the steps to start the mesh manually.
1. Bring up a console (click Terminal on the Developer Console)
2. Type:
su - # enter root password if needed iwconfig msh0 mode ad-hoc channel <channel> essid <any name> ifconfig msh0 <IP address>
channel: Pick the same for all the nodes in the mesh. If in doubt, pick 6
IP address: Pick a unique IP address in the mesh. If in doubt, pick 10.X.Y.Z, and replace X.Y.Z with these 3 numbers
any name: Literally, any name will work. If in doubt, pick "olpc-mesh".
Soon turning on the mesh and IP address assignment will happen automatically. But these steps will allow you to start using the mesh as of build 368.
Disabling the mesh network
An XO-1 scans for nearby access points, and if a favourite is found it tries to connect to it. But if no favourite is found within ten seconds, it looks for a nearby mesh and connects to that, otherwise it starts a mesh.
A bug prevents this scan in large groups, see 12757 for the details. If the fix cannot be deployed, a workaround is to disable mesh networking on all XO-1 laptops in a school.
To disable mesh networking, in Terminal activity as root, enter the command
echo 0 > /sys/class/net/eth0/lbs_mesh
To disable permanently, add the command to a startup file,
echo "echo 0 > /sys/class/net/eth0/lbs_mesh" >> /etc/rc.d/rc.local
And in a post-resume script for powerd, as the Sugar Labs Dextrose distribution for XO's does (mailing list message).
Mesh in linear layout
http://video.google.com/videoplay?docid=-3339545498848597316
Mesh in separate groups
http://video.google.com/videoplay?docid=-5598928296852168708
Experimenting
Want to run a simple experiment to see the mesh in action? You will need 3 laptops, xoa, xob and xoc, with IP addresses IPa and IPc (xob does not need an IP for this experiment):
1. Bring all three xo's together.
xoa, xob, xoc ------------------------------------------------
2. At the terminal of laptop C type
ping IPa
3. Move xoc away from xoa and xob, until pings start failing. Mark that location (L1): that will indicate the direct range limit.
L1 xoa, xob -------------------------------- xoc ------------------------------------
4. Move xoc closer to xoa and xob. As soon as pings restart, mark that location (L2).
L2 L1 xoa, xob -------------------- xoc ----------------------------
5. Pick up xob and move it to L2.
L2 L1 xoa ------------------------- xob, xoc -----------------------
6. Move xoc to L1, you should now be able go substantially beyond L1 and successfully ping xoa.
L2 L1 xoa ------------------------- xob ------------------------ xoc
7. Move xob back to xoa, you should find that xoc will no longer be able to ping xoa.
L2 L1 xoa, xob ------------------------------------------------- xoc
That's the beauty of the mesh: you can extend the range just by inviting more people over to your party.
Interactions With Wireless Equipment
The mesh may be affected by legacy wireless equipment.
Footnotes
[1] Note that although the frame is discarded, it will still be acknowledged by the MAC layer.
See also
- Libertas - the Marvel 88w838X series of wireless chipsets