Listen Print Discuss

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:

  • Price: 802.11 radios have become quite cheap, but the radios are often still among the most expensive elements of such a network. The fact that each mesh node runs both as a client and as a repeater potentially means saving on the number of radios needed and thus the total budget.

  • Ease and simplicity: If you have a box that is pre-installed with wireless mesh software and uses standard wireless protocols such as 802.11b/g, the setup is extremely simple. Since routes are configured dynamically, it is often enough to simply drop the box into the network, and attach whatever antennas are required for it to reach one or more existing neighboring nodes (assuming that we can solve the issue of IP address allocation).

  • Organization and business models: The decentralized nature of mesh networks lends itself well to a decentralized ownership model wherein each participant in the network owns and maintains their own hardware, which can greatly simplify the financial and community aspects of the system.

  • Network robustness: The character of mesh topology and ad-hoc routing promises greater stability in the face of changing conditions or failure at single nodes, which will quite likely be under rough and experimental conditions.

  • Power: The substrate nodes of a mesh network -- possibly excepting those nodes that maintain an up-link to the Internet -- can be built with extremely low power requirements, meaning that they can be deployed as completely autonomous units with solar, wind, or hydro power. (A side comment: Piggybacking mesh networks on projects that primarily aim at energy production might be a very feasible strategy -- with every panel or windmill, a node. Power generating units are typically connected to points of infrastructure and human presence. This makes them valid locations for network nodes. As a secondary benefit, the presence of integrated network nodes within power networks may allow for better monitoring and management.)

  • Integration: Mesh hardware is typically small, noiseless, and easily encapsulated in weatherproof boxes. This means it also integrates nicely outdoors as well as in human housing.

  • Reality fit: Reality rarely comes as a star, ring, or a straight line. In difficult terrain -- be that urban or remote -- where not every user can see one or few central points, chances are she can see one or more neighboring users.

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:

  • AODV is a routing protocol for ad-hoc networks designed with mobile wireless devices in mind. It is not subject to copyright protection and is in the public domain.

  • Mobile Mesh protocol contains three separate protocols, each addressing a specific function:

    1. Link Discovery
    2. Routing
    3. Border Discovery

    The Mobile Mesh software is covered by the GNU General Public License (Version 2).

  • TBRPF, or Topology Broadcast based on Reverse-Path Forwarding, is a proactive, link-state routing protocol designed for mobile ad-hoc networks, which provides hop-by-hop routing along minimum hop paths to each destination. It seems it is patent-protected unless it becomes a IETF standard.

  • OSPF is a link-state routing protocol. It is designed to be run internal to a single Autonomous System. Each OSPF router maintains an identical database describing the Autonomous System's topology. From this database, a routing table is calculated by constructing a shortest-path tree.

  • GNU Zebra is free software that manages TCP/IP-based routing protocols. It is released as part of the GNU Project, and is distributed under the GNU General Public License. It supports BGP-4 protocol as described in RFC1771 (A Border Gateway Protocol 4) as well as RIPv1, RIPv2, and OSPFv2.

  • LocustWorld develops a free bootable CD solution based on the AODV protocol, and also develops and sells a complete ready-to-deploy MeshBox running its software, most (but not all) of which is available under the GPL. The MeshBox and mesh software have been used in a number of community networks in the UK.

  • 4g MeshCube. The German company 4G Mobile Systems has developed a tiny MeshCube running Debian Linux on a MIPS processor, using MITRE Mobile Mesh routing software. This is a ready-to-deploy gateway with both a wireless and a wired interface. With a power consumption of 4W (and potentially lower), it is ideal for deployment with an autonomous sustainable power source.

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:

  • Make sure no zeroconf stuff is running on your box -- check for zcip and tmdns! They will mess up your Mobile Mesh. This seems to be a problem at least on newer versions of Mandrake (> 9.0).
  • Compiling the dynamic source might give problems with gcc, newer than gcc 2.95.
  • Some combinations of wireless cards and drivers behave strangely – for example, we have seen cards we could not get to work in ad hoc mode, but only in "infrastructure" mode.

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.