Wireless DevCenter    
 Published on Wireless DevCenter (http://www.oreillynet.com/wireless/)
 See this if you're having trouble printing code examples


Wireless Mesh Networking

by Tomas Krag and Sebastian Büettrich
01/22/2004

Editor's note: Tomas Krag and Sebastian Büettrich are wireless consultants working primarily on ways to promote the use of wireless technologies in developing countries. At next month's Emerging Technology Conference, Tomas will discuss how wireless technologies can bring Internet and Intranet connectivity to those parts of the world not included in the plans of the commercial telecommunications companies.

Our current project, the Wireless Roadshow, deals with enabling local communities and non-profits in the developing world to plan, deploy, and maintain local, sustainable network infrastructure to enable voice and data communications, both locally and on the Internet.

Some of the key requirements for these networks include that the network infrastructure be decentralized, to avoid a central point of failure and control, and that the technology used be both cheap enough and simple enough that it can be maintained and expanded by locals with limited technology experience. This sometimes means using off-the-shelf hardware combined with cheap, homebrew antennas, as well as looking hard at some technologies that are gradually becoming mainstream enough to be easily deployable. These technologies include VoIP and so-called Mesh networks. The argument for VoIP is obvious, especially given the power of voice communications in areas where literacy cannot be taken for granted.

The subject of this article is mesh networks, another technology that is gradually maturing to a point where it cannot be ignored when considering various wireless networking technologies for deployment. While the first large-scale community mesh deployments are yet to be seen, existing lab-level implementations and feasibility tests have demonstrated enough advantages to motivate further experimenting. Let's run down some of the reasons why mesh networks should get a second look:

In the rest of this article we'll take a closer look at some of the principles of wireless mesh networking, as well as looking at a simple test scenario for running a mesh routing protocol on a Linux-based computer.

Definition

ETech 2004 Conference

Session by Tomas Krag
Wireless Networks as a Low-Cost, Decentralized Alternative for the Developing World

Billions of people in the world have never been online. The Internet as a technology is a elitist tool, reserved for the few and unreachable by the many. This is a problem not likely to be solved by the commercial interests of existing telecommunications companies and existing ideas about expensive, centralized infrastructure.

O'Reilly Emerging Technology Conference
February 9-12, 2004
San Diego, CA


Roughly following TechTarget and Telecom Glossary 2K definitions, we define a mesh network as follows:

"A mesh network is a network that employs one of two connection arrangements, full mesh topology or partial mesh topology. In the full mesh topology, each node is connected directly to each of the others. In the partial mesh topology, nodes are connected to only some, not all, of the other nodes."

Note that these definitions mention no dependency on any time parameter -- nothing is necessarily dynamic in a mesh. However, in recent years, and in connection with wireless networks, the term "mesh" is often used as a synonym for "ad hoc" or "mobile" network. Obviously, combining the two characteristics of a mesh topology and ad hoc capabilities is a very attractive proposition.

So, when we speak of a wireless mesh network, we assume a network that handles many-to-many connections and is capable of dynamically updating and optimizing these connections. This may be (but does not have to be) a "mobile network" in which it is assumed that each (or at least some) of the nodes of the network are mobile units that change position over time. The dynamic management of complex routing information, very likely to include information about external networks (e.g. the whole wide Internet and the gateways to it), is arguably the biggest challenge for (dynamic) mesh protocols.

The "mobility" scenario in which each client unit is a PDA, mobile phone, or other mobile unit is an appealing scenario for airport lounges, shopping malls, offices, and parties. While this vision might be valid, it may still be some years before we see a successful implementation of this idea, especially given the current constraints in battery and processing power of typical mobile units. However, utilizing other strengths of mesh networks, we can come up with relevant real-world scenarios where hybrids between "static" and "ad-hoc" networks offer some clear advantages -- networks where a number of static nodes form the matrix (the substrate) in which other nodes appear, roam, and disappear. In a similar way, hybrids between mesh topologies and other topologies (star, ring, etc.) are likely to be optimal solutions in real-world environments.

Often, drawing a simple map of potential nodes and the link blocks (mountains, trees, buildings, clouds, human beings, etc.) in between them will suggest the appropriate mix ratio and the network pattern to deploy.

Protocols and Implementations

There are a large number of protocols and implementations in the field of mesh and ad-hoc networking, each with differing goals and design criteria, and more are being developed as we write this. It is beyond the scope of this article to give a comprehensive list of available protocols and systems, but the authors maintain a Wiki-page with a list of links and further reading on the subject.

In the following we will briefly introduce a couple of the most commonly seen protocols, standards, systems, and products in the world of wireless mesh.

Seen from an implementers' angle, it is important to note that some implementations are built for dedicated computers (the box will do nothing but mesh) while others seem to assume a user (desktop, laptop) machine that becomes a mesh node more or less invisibly in the background.

While this is not a true characteristic of the different approaches -- it is cosmetics more than core -- it is a very relevant aspect for practical deployments, even more so when budget and machinery are limited. Let's review the different approaches:

Building a Mesh Network: How to Get Started with Mobile Mesh

The following is a basic guideline for getting Mobile Mesh up and running on a GNU/Linux box with a wireless network card already configured. Mobile Mesh is a good starting point for mesh experiments since it can be run entirely in user space, and in our tests has worked for just about any Linux box we've tried it on. It also proved stable and performed OK as we dragged a mesh network out into the streets of Berlin at last autumn's Freifunk Summer Convention -- one laptop per street corner.

We will assume that you have a working GNU/Linux box of some kind with at least a 2.2.x kernel. We have successfully tested Mobile Mesh on 2.2 and 2.4 kernels, but not yet on the new 2.6 (we've also tested successfully on a variety of distributions including Debian, Mandrake, RedHat, Suse, and even Knoppix for those that do not have a permanent Linux installation on their laptops.)

We also assume that you have a 802.11 wireless client (PCMCIA card, USB adapter, PCI card) working that will run in ad hoc mode. Note: It is entirely feasible to run Mobile Mesh on a cabled Ethernet interface, but it does take some of the fun out of "mobile."

First set your SSID to be mobilemesh and your card to work in ad hoc mode.

Here are the steps that typically make a node out of your box; details and mileage may vary:

Download a Mobile Mesh tarball from mitre.org.

In the download directory, as root:


 tar -xvf <your_downloaded_mobilemesh>
 cd <your_mobilemesh_directory>

Read and follow ./INSTALL.

Once installed, you need to configure mmrp.

Edit the file /etc/mobilemesh/mmrp.conf. Most importantly, check the interface name. For example, typically wlan0 (used hereafter), eth0, eth1, or whatever your wireless card is...

Then:


 ifconfig wlan0 10.XXX.XXX.XXX netmask 255.255.255.255 
 broadcast 10.255.255.255

with the Xs as your choice, but agreed on with your neighbors ... duplicate IP addresses are a no-no.


 mmdiscover -i eth1 -z &
 mmrp \x{2013}z &

That should do it, but before we really take the system for a spin, remove the existing default route to the network for your wireless interface. This makes sure that Mobile Mesh is in full control of the routing table.


 route del -net w.x.y.z netmask 255......0

Now repeat this process on all the laptops in your office (since being alone in a mesh is about as interesting as being connected to it through a cable).

That's it, you have a mesh.

At this point, consider getting a group together, each grabbing a laptop, and heading for the park, while you try and keep the pings going between the laptops, and/or see the routing table dynamically update itself by running:


 netstat -nr

It may also be worth checking out the mmrpviz package that comes with the Mobile Mesh tarball. It shows a graphical view of the current Mobile Mesh network topology.

Note: It seems that mmrpviz is dependent on an outdated version of the graphviz package, which means that you will probably need to download and compile a version from the archives rather than use whatever package is provided by your distribution. We've successfully used Graphviz 1.6, but have failed with both 1.8 and 1.9.

Here's a list of some of the issues we've seen so far:

Setting Up a Gateway to External Networks

Now that you have successfully set up a couple of mesh nodes it's time to get one of them to run as a gateway to the Internet, so that every node on the network can get online. Assuming one of your boxes has a second interface (wired or wireless) with a connection to the Internet that you would like to share with other mesh users: In /etc/mobilemesh/mmrp.conf, define networks external to the mesh by,


  external <ip address> <netmask> <metric>

where <ip address> and <netmask> specify a range of addresses that this node can reach, which are external to the Mobile Mesh cloud.

<metric> is the associated cost to reach these addresses from this node. For example,

  external 0.0.0.0 255.255.255.0 7

Note: You advertise a network (0.0.0.0) here, not a gateway!

Don't forget to restart mmrp to make the changes happen.

Again, it's as simple as that. Enjoy the mesh...

Tomas Krag is a partner at consulting firm wire.less.dk and a team member at the nonprofit organization Informal. He is a specialist on low-cost, decentralized Internet infrastructure for the developing world, as well as an open source, Open Tech evangelist.

Sebastian Büettrich is a partner at the consulting firm wire.less.dk and a team member at the nonprofit organization Informal.


Return to the Wireless DevCenter.

Copyright © 2009 O'Reilly Media, Inc.