The average wireless network depends on the presence of an access point device, which serves as a connection point for wireless clients and links the WLAN to the Internet. This technology is so widespread in urban areas that a wireless user is never far from a point of connection – in airports, coffee houses, offices, and even millions of homes.

In spite of its omnipresence, the access point is, in fact, not really an essential element of the wireless network. An access point--style network is said to be operating in infrastructure mode. An alternative approach, known as ad hoc mode, lets computers establish direct connections with each other. Ad hoc mode is sometimes used for one-to-one connections between (say) a laptop and a desktop system when no access point is available. Computers that connect through ad hoc mode do not have the benefit of DHCP and other services that typically run on the access point, so they must negotiate any network settings.

In remote areas, and in developing countries without a pervasive networking infrastructure, decentralized alternatives such as ad hoc mode become increasingly attractive. However, users who attempt to operate in a conventional ad hoc setting run into restrictions fairly quickly. Although you can communicate with immediate neighbors, conventional ad hoc networking does not let you use neighbors as intermediaries to access other systems, so the range of the network is limited to the range of a single wireless device. Some operating systems, in fact, don't even support more than two peers in an ad hoc network.

A further extension of the ad hoc concept is the mesh network, which is embodied in the IEEE 802.11s draft standard. Mesh networking expands the size and range of the ad hoc network by letting network peers forward messages and transmit network information to other peers. The peers can thus build a collective picture of the network topology, and a message can pass through a chain of peers to a node beyond the immediate signal range.

IEEE 802.11s received renewed attention through the work of the One Laptop Per Child (OLPC) project, which was formed with the goal of providing network-enabled laptop computers for millions of school children in developing countries. The OLPC developers needed a way to interconnect these little laptops in a setting in which a whole village might have only a single access point or Internet gateway. Mesh networking provides the solution [1]; even if a device can only find one peer, it can still access other devices (and, ideally, an Internet access point) by transmitting through a chain of connections across the mesh. Mesh networking also has uses in the developed world, although it is unlikely to ever replace the convenience and simplicity of access point networks. In rural areas, or in situations in which a network must assemble and self-configure temporarily, mesh networking might someday play an important role.

IEEE 802.11s is still a draft [2], and it is unlikely to be officially approved before 2010.

In August 2008, the Linux kernel added a patch for meshing support in the ath5k module, with native support available for the b43, libertas_tf, and zd1211rw wireless drivers. In Linux kernel version 2.6.26, zd1211rw already has rudimentary IEEE 802.11s support based on the mac80211 subsystem [3]. The code in kernel 2.6.26 does not let users set up genuine mesh networks, but the current developer version of the wireless-testing.git repository adds additional mesh networking support [4].

Unless you happen to own an OLPC laptop or some equivalently pre-configured device, the game of mesh networking in Linux is not exactly for beginners, but if you feel like experimenting with your own mesh network, the necessary tools are certainly available – but make sure your wireless hardware supports IEEE 802.11s.

How It Works

In an IEEE 802.11s network, each node is in contact with its direct neighbors. The nodes can be computers, laptops, or devices such as IP-capable smartphones. The mesh protocol tries to auto-discover the best possible route for a packet. (See the "OLSR and Batman" box for more abou routing on mesh networks.)

No fixed connections exist between individual nodes. A node transmits packets to a specific target node that it considers most suitable for taking the packets closer to their final destination. The next hop uses the same approach until the package reaches its target.

In meshing, data is synchronized as often as possible – typically every few seconds. This approach keeps the network dynamic and allows it to react to changing conditions caused by moving nodes, obstacles, or direct connections. The mesh evaluates each active link path on the basis of specific criteria and chooses the best path. Thus, routing is one of the most critical, and the most expensive, tasks in meshing.

Mesh Networking Up Close

Mesh networks with Internet access typically have a main node that provides broadband Internet access via DSL or UMTS. This main node often offers other network services, such as DHCP. The network admin sets up gateway functionality on this node only by, say, running the echo 1 > /proc/sys/net/ipv4/ip_forward command and possibly adding NAT rules for masquerading.

The individual mesh nodes should have at least two WLAN modules. Three modules will improve availability and increase the maximum number of possible clients. Typically, one module will run in access point mode to give other clients access, or the other modules will use ad hoc mode for meshing. In a perfect world, all of these modules have omnidirectional antennas that cover a large reception area (see Figure 1).

As you might guess, the effectiveness of mesh networks is largely dependent on the range at which the nodes can receive the signal. For systems that are built specifically for mesh networking, the antenna configuration receives significant attention. (Notice the two external antennas in the OLPC XO laptop shown in Figure 2.) A network with multiple modules per node can use a more flexible antenna configuration; for example, one module can use a sector antenna to reach peers within a wide range, and another can work for nodes in close proximity. The following sections describe how to set up mesh networking in Linux.

Setting Up the Mesh

The wireless-testing.git repository now has an updated, mesh-ready version of the kernel with matching drivers. The command

git clone git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-testing.git

downloads the current version.