Wireless Mesh Networking

Introduction

A network is made up of nodes. The complextiy of mesh routing would make it very difficult, if not imnpossible to configure and manage large mesh networks. Therefore, intelligence has to be built into the nodes so that they can handle some of the configuration and management of the network. This becomes more important when the users/owners of the network aren't very computer literate. There are several aspects to this intelligence including the routing algorithms that tell the node how to route information to other nodes. These algorithms are implemented in Mesh routing protocols.

These nodes also need to be affordable, especially in the case of rural networks.

Mesh Routing Protocols

A large amount of research at Meraka CSIR will go into comparing the performance of various mesh routing protocols and understanding their suitability to different networking scenarios such as network size, latency and throughput requirements and the amount of mobility. Below is a list of mesh networking protocols that will be tested on our testbed networks.

OLSR

---

Optimized Link State Routing was developed by P. Jacquet at INRIA in france. This is a proactive protocol that addresses the issue of flooding the network with link state information across the network. OLSR reduced the overhead of by requiring fewer nodes to forward the link state information. This is done broadcasting a lnk state from node X through select multipoint relays.

Optimised Link State Routing

More info: OLSR

AODV

---

Ad-hoc On-Demand Distance Vector Routing was developed by C. Perkins while working at Sun Microsystems Laboratories. This is a reactive protocol that attempts to improve on DSR by maintaining routing tables with one entry per destination at the nodes. When a source node needs a route to a destination, it initiates a route discovery process to locate the destination node. The source node floods a query packet requesting a route to be set up to the destination. A reply is sent back directly to the source node either by the destination itself or any other intermediate node that has a current route to the destination. Since nodes reply to the first arriving route request, AODV favours the least congested route instead of the shortest route.

Ad-hoc On-Demand Distance Vector Routing

HSLS

---

Hazy Sighted Link State Routing was developed by BBN and implemented by cuwireless(See CuWIN Visit). In general a reactive protocol is local (only knows about its immediate neighbours) and a proactive protocol is global (stores routing information for entire network). HSLS is neither glocal nor local, each node has a different view of the network. The link -state approach that is followed is: send an update every ti seconds with a network scope of ri hops. The HSLS algorithm finds ti and ri so that the performance is optimized. HSLS is performance-driven, focusing on average system performance instead of focusing on handling exceptional rare cases whose impact on the overall system performance is not clear.

Hazy Sighted Link State Routing

ZRP

---

The Zone routing protocol was developed by Z.J. Haas (Associate professor, Cornell University), a lead researcher in the field of Ad Hoc networking. The ZRP is an example of a hybrid reactive/proactive routing protocol. On one hand, it limits the scope of the proactive procedure only to the node’s local neighbourhood, minimizing the waste associated with the purely proactive schemes. On the other hand, the search throughout the network, although it is global, is performed by efficiently querying selected nodes in the network, as opposed to querying all the network nodes. The protocol identifies multiple loop-free routes to the destination, increasing reliability and performance. Routing is flat rather than hierarchical, reducing organizational overhead, allowing optimal routes to be discovered, and reducing the threat of network congestion. Haas explains that the most appealing feature of the protocol is that its behaviour is adaptive, based on the current configuration of the network and the behaviour of the users.

Zone Routing Protocol

This protocol is very attractive for a city type network which will consist of both static wireless nodes installed on structures such as houses and moving nodes which could be people or cars. The local neighbourhood to the moving nodes can be proactive and react quickly whereas the static intrazone backbone will operate on a proactive scheme.

Other

---

Mobile Mesh One of the first mesh routing implementations that was looked at is, MobileMesh for Linux and the Windows equivalent IpMesh. The interest/activity around these seemed to be fading with the implmentation of more popular routing protocols like OLSR.

Standardisation

---

The IEEE and IETF are working on Mesh Standards.

IP Allocation

One of the ourstganding issues amongst the mesh gurus is the issue of IP allocation. The general approach is to assign each person in the mesh a staic Ip in the 10.x.x.x or 192.168.x.x range. The ideal is to give everyone a generic box - they install it, turn it on, and it automatically gets assigned an IP, updates it's routing table based on the mesh routing algorithm being used, gets a gateway and a dns (basically like DHCP)

More: IP Allocation

Mesh Partitioning problem due to BSSID issue

One of the frustrating problems in 802.11 ad hoc networks is the issue of mesh partitioning due to the method 802.11 uses to form an ad-hoc network using the BSSID.

When 802.11 interfaces are put into Ad Hoc mode, they go through a somewhat complicated procedure to join what is known as a Basic Service Set, or BSS. A BSS is a kind of virtual network; even if two different nodes are operating on the same channel, they will not “see” each other’s packets unless they are in the same BSS. Basic Service Sets are identified by a 6-byte number known as the Basic Service Set ID, or BSSID, which is transmitted in the header of every 802.11 frame. When an 802.11b adapter enters Ad Hoc mode, it is configured with a Service Set ID (SSID), which is a string that is intended to identify the network it wishes to join. The adapter then scans through all of the 802.11b channels, listening for beacons sent by other nodes. Beacons contain, among other things, the SSID and BSSID being used by the sending node. If the adapter hears a beacon containing the SSID that matches its own, then it joins this existing Basic Service Set by setting its own BSSID to the one received in the beacon.

If the adapter does not receive any beacons with a matching SSID within a certain period of time, it decides that no Basic Service Set currently exists with its SSID. In this case, it sets up itself as a new Basic Service Set by selecting a random BSSID and using that for all of its traffic. Any other nodes using the same SSID which start up in range of this node will hear its beacons and configure themselves to use its BSSID. This creates a serious problem for an Ad Hoc network. Namely, if two nodes start up at different times and are not within radio range of each other, they will start with different BSSIDs and be on different logical networks, despite both having the same SSID. Because 802.11 adapters ignore all frames whose BSSID does not match their own, this creates a partition in the network and prevents all of the nodes from being able to communicate prop erly.

To solve this problem many new 802.11 devices allow you to manually set the BSSID to a specific 6 byte number of your chosing. If you set all the nodes in the mesh to this same BSSID you will avoid this problem.

Network Simulation

Why? to simulate mesh networks, VOIP, etc, to determine placement of Internet access gateways, suitability for rural community access given terrain features, distance between participants and the like.

Requirements: We need to choose a simulator that is customisable, well-known so that we can export or share models, easy to use, inexpensive, has a predeveloped library of protocols, propagation characteristics, etc, that could be tweaked for our requirements. Should be able to incorporate terrain models (I think)

Someone should investigate the following options and provide comment here...

Proprietary candidates: - Opnet - Comnet III

Open Source candidates: - NS-2 - Ptolemy (Java based) - OMNet++ - CSim++ - SimJava - JavaSim. There is some confusion of packages here as Lund Institute of Technology (Sweden), Ohio State and University of Newcastle have all created something called JavaSim. Ohio State seem to have the most advanced package which they have since renamed to J-Sim.

There is a good listing of simulation languages, IDEs and simulators here

There is also a general purpose simulation language in Python called SimPy which appears to be rather interesting but without a lot of add-ons at this stage.

At this stage, Opnet, Ptolemy, SimJava and OMNet++ appear to be most interesting...

During 2006 it was decided to focus on the open source simulators, Omnet++ and NS-2

Omnet++

Download from omnetpp comunity site After untarring the file make sure you put the following in your .bash_profile file

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:"/home/djohnson/simulators/omnetpp-3.1/lib"
export PATH=$PATH:/home/djohnson/simulators/omnetpp/bin:/home/djohnson/simulators/omnetpp-3.1/bin"

NS-2

Download from [http://sourceforge.net/projects/nsnam ns2 sourceforge site> After untarring the file the following bug needs to be fixed

If you find this error in your installation of the new version ns-allinone 2.29 2 :

"checking system version (for dynamic loading)... ./configure: line 7624: syntax error near unexpected token ')'
./configure: line 7624: ' OSF*)' tcl8.3.2 configuration failed! Exiting ...
Tcl is not part of the ns project. Please see www.Scriptics.com to see if they have a fix for your problem."

the problem is due to these files :

1. tcl: file tcl8.x.x/unix/tcl.m4.
2. tk: file tk8.x.x/unix/tcl.m4.
3. otcl: file otcl-1.x/configure.in.

The line generating the problem is :

system=MP-RAS-`awk ' { print $3 } '/etc/.relid'`

The problem lies in how bash 3.1.x and 4.x.x parse the configure file. This will simply pass through bash 3.0.x and lower versions. So in order to make things work changed the above line to:

system=MP-RAS-`awk ' { print $3 } '/etc/.relid`

You will have to take following steps in order to bring the changes into effect: Remove the second last character ( ' ) from the line and do this for all the three files above. Now after changing the configuration files you will have to delete older configure file and any cache if it exists in the respective folders. After that do not forget to run autoconf from command line in the respective folders to generate a fresh configure file.

And finally re-install it by the following command :

./install

Now fix your path environment by putting the following in .bash_profile

export PATH=$PATH:home/djohnson/ns-allinone-2.29/bin:/home/djohnson/ns-allinone-2.29/tcl8.4.11/unix:/home/djohnson/ns-allinone-2.29/tk8.4.11/unix
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/djohnson/ns-allinone-2.29/otcl-1.11:/home/djohnson/ns-allinone-2.29/lib
export TCL_LIBRARY=$TCL_LIBRARY:/home/djohnson/ns-allinone-2.29/tcl8.4.11/library

Test the ns2 suite by running ./validate from the ns2 directory

Voice over Mesh

The aim of this topic of research will be to conduct a Protocol QoS Shoot-out in order to determine the optimum protocols and configuration required to provide the QoS needed for voice communiction (VOIP) over a mesh network. The experiments will be conducted on the 49-node Indoor Mesh, Pretoria Mesh and possibly the Mpumulanga Mesh.

MAC Layer

This is a great article that discusses the whole issue of loss of performance in a single radio mesh network with many hops. Modifying the MAC layer on our 50 Altheros cards we are getting for the massive mesh could prove a very novel way of dealing with the inherent problems in the WiFi spec when trying to build large mesh networks.

Network Visualisation

In order to get a better idea of what is going on within the inner workings of network routings, it is particularly useful to have a graphical representation thereof. Several options are being looked at into providing such a representation, including a plugin feature of the OLSR.org implementation of the OLSR protocol, called the OLSR Dot Draw plugin.

OLSR Dot Draw shows some of the work done in implementing a "first-cut" visualisation.

Outdoor mesh networks require planning and co-ordination and a visualisation tool combined with location information would be a valuable tool. Freifunk have implemented such a tool, which we may try on the Pretoria Mesh.

Test Networks

49-node Indoor Mesh

Pretoria Mesh

Mpumulanga Mesh

Other Network Services

The success of mesh networks ultimately depend on the type and quality of services that can be implemented. The primary services or Killer Applications still remain VOIP (Voice over IP),especially for underserviced areas, and Internet Access. However, other services will also need to be looked at in the South African context such as:

Security Surveilance

Local Content provision

Education

Network Security

VPN(Virtual Private Networking) can be implemented on a mesh network to provide secure virutal networks within the bigger network. The HowTos page describes how to set one up.

Low-cost devices

Cost is a critical factor, since the mesh networks are to be installed in rural areas. Part of the research done is to try and reduce the cost of components as much as possible.

Node

Several options are being looked at to try and bring this major cost component down, including Wireless Routers, SBC(Single Board Computers) and Open Hardware

Antennae

Home-Brew Antennae

User Terminals

Mobile Devices

See Links for other Mesh Network initiatives

Network performance tools

Summary of all network performance tools here

Iperf

• main page
• How to
• FAQ