OLPC - Mesh Network details

Laptop design evolution

As first conceived, the XO laptop display used LCOS (liquid crystal on silicon) in the form of a projector. Nicholas Negroponte demonstrated the concept in early 2005, using a set of black sticks sliding across a frame to convey some sense of how the folding optics would work.

The laptop began to evolve in June of that year, when Mary Lou Jepsen, newly named as acting CTO, began considering a dual-mode display: one a conventional color LED laptop screen, the other a sunlight-readable, black-and-white e-book. The concept made abundant sense for the developing world, where outdoor classes are common and the cost of shipping textbooks is a major expense.

At a July board meeting, Design Continuum presented an array of innovative prototype designs that would lead, by November 2005, to the famous “green machine”, with its distinctive pencil-yellow crank, which was unveiled to the world by UN Secretary General Kofi Annan at the World Summit on the Information Society at Tunis.

The yellow crank, while cute, in the end proved impractical; it migrated to the AC adapter as it also morphed into one or more other types of human-power devices. Its status as an icon for OLPC would be supplanted by the mesh-network antennas, or “ears.” At the same time, Quanta Computer, our ODM, made a strong case for fitting the laptop with a so-called transformer hinge to simplify the machine's transformations from classic laptop, to game device, to e-book reader. In the spring of 2006, Yves Behar, the noted San Francisco industrial designer, came aboard to complete the final design of the Generation-One XO.

In November of 2006, the first XO test machines, the B1 (Beta1), rolled off the Quanta assembly line in Shanghai.

In early 2007, the B2 iteration of XO, stronger, sturdier, with a slight increase in tilt, was ready for its debut. B3 followed in May 2007, and pallets of B4 machines arrived in OLPC offices on July 6, 2007.

Mesh Network Details

From OLPCWiki

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.

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.

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:

1. 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.
2. If any channel provides a lower hop count to a Mesh Portal, it is selected unless its signal strength is significantly lower.
3. 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 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:

• Establishing a Mesh Portal
• Trial1 School Server Software
• Cozybit's MPP Utils

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  essid 
ifconfig msh0 

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.

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.