Brown M.Topology management in rooftop wireless networks.2004

Figure 3.6: Example mesh network created by a neighbour selection algorithm

3.7Link Establishment

After the neighbour selection process has been completed the node must ensure that each of its interfaces is configured to participate in the appropriate links. A crucial step in configuring each interface is to ensure that the neighbouring mesh nodes that the link is to be established with have a synchronised view of the network. If nodes are not synchronised their neighbour selection algorithms will form different network topologies and the link may not be established.

3.7.1 Neighbour Synchronisation

Neighbour synchronisation is achieved through the use of hello packets as described in Section 3.3.1 and a simple handshaking procedure. Figure 3.7 shows the series of packets that are exchanged between Node A and

Node B as they establish a link. The top of the diagram shows each node at the completion of the neighbour selection algorithm but before a link is established. By the bottom of the diagram the nodes have established a link and are exchanging hello packets at regular intervals.

Node A initialises the link by sending a hello packet directly followed by an invite packet to Node B. The invite packet contains the the ESSID, 802.11 channel, 802.11 mode and IP network that Node A believes should be used for the proposed link. When Node B receives the hello and invite packets they are processed immediately. After checking the parameters contained in the invite packet match its configuration Node B sends an accept packet back to Node A and configures the interface with the parameters that were agreed upon. When Node A receives the accept packet it configures the interface with the agreed parameters. At this

24

Figure 3.7: Neighbour Synchronisation Procedure

point the link is established and both nodes commence the regular hello packet exchange.

If the link databases of Node A and Node B are not synchronised they will not agree on the parameters of the link (or even that the link should exist). In this scenario when Node B receives the invite packet it will send only a hello packet back to Node A without sending an accept packet. This hello packet combined with the hello packet that Node A sent to Node B before the initial invite packet serves to synchronise the link databases of the two nodes.

If Node A does not receive any response to its initial invite packet it will retransmit the invite every five seconds until it has been sent a total of five times. If a response still has not been received Node A assumes that the link is no longer possible and returns to neighbour discovery mode.

3.7.2 IP Addressing

IP addresses in the mesh network are always allocated to point to point links between two nodes. If an interface is part of a point to multi point link, or a multi point to multi point link where it has multiple neighbour nodes several IP networks are allocated and the interface ends up with several IP addresses.

The benefit of this scheme is that the logic for assigning and configuring IP addresses on an interface is the same, regardless of the type of link that the interface is participating in. One IP address is always added to the interface for each directly connected neighbour node. Additionally using only point to point IP networks solves a problem encountered in point to multi point and multi point to multi point links where the nodes are not connected in a full mesh. By configuring point to point links only between those nodes that can directly communicate (as established by the hello protocol) packets travelling between nodes that cannot directly communicate must be routed over the point to point links.

25

For this project each node in the mesh network has a pool of IP addresses that it ‘owns’ and may not be used by anyone else on the network. When a node generates an invite packet to send to a neighbour it allocates an unused network from within its pool to the link and includes the details in the invite packet. The node receiving the invite packet does not allocate any IP addresses from its pool as it uses the network specified in the invite packet.

Each link is allocated an IP network with a CIDR[39] prefix length of thirty bits. This leaves two bits of the IP address to identify hosts on the network, allowing four possible addresses, however the first and last address in each network are reserved for special purposes, leaving two IP addresses available to identify hosts. The node with the lowest node ID gets the lowest address. Each node is given a pool with a CIDR prefix length of twenty four bits, this pool contains sixty four networks with a prefix length of thirty bits which allows each interface on a node to participate in sixteen point to point links. Given the mesh protocols preference for point to point links it is hard to envisage this limit ever being reached on all interfaces of a node at one time. Currently the mesh protocol automatically allocates a pool of IP addresses to each node based on its node ID.

3.8Routing

At this point in the process a network such as the one shown in Figure 3.6 has been constructed. Each node in the network is able to communicate with its immediate neighbours, however it has no idea where to send packets for nodes that are not direct neighbours. Imagine that Node A in the figure has a packet that it wishes to send to Node G. Should the packet be sent to Node B, Node C, Node E or Node F? The job of the routing protocol is to discover all possible paths between any two nodes in the network, select the best performing path to use for delivering packets to their destination and ensure that the appropriate records are maintained on each node such that it can quickly determine which neighbour to send a packet to.

The mesh network constructed by this project consists of many wireless Ethernet links connected via a series of routers. A network of this type is not able to use the current implementations of specialised wireless routing protocols such as AODV, DSDV and DSR described in Section 2.4.3 as they operate on a single Ethernet link only. However the network is perfectly suited to use an IP layer routing protocol such as OSPF. This project uses the OSPF daemon from the Quagga routing suite. Currently the routing daemon is completely separate from the implementation of the mesh protocol and does not interact directly with it. The standard OSPF bandwidth based link metric is used which is not ideal given the shortest path problems identified in Section 2.4.1.

26

Chapter 4

Implementation Framework

The final phase of this project was to construct a framework that implements the protocol described in the previous section. The emphasis of this framework is on modularity such that elements of the mesh protocol can be easily replaced in the future as more sophisticated techniques are developed. This section describes the architecture of the framework and how it has been implemented.

4.1Implementation Environment

A typical environment that the mesh network framework must operate in is the CRCnet Biscuit PC Linux Distribution. This is a customised Linux distribution built as part of the CRCnet project that operates on small computers commonly called “Biscuit PCs”. These Biscuit PCs typically have a 486 processor with 64MB of RAM. There is no writable hard disk available, a single read only 64MB compact flash card is used to store the operating system and applications. Due to the limited amount of space many common features are not available.

The Biscuit PCs have two PCMCIA slots and a single miniPCI slot allowing up to three radio cards to be used at one time. Solutions are currently being investigated to allow the desired number of four radio cards to be operated at one time. For the purposes of this project all mesh nodes were configured with a maximum of three wireless interfaces.

4.2Implementation Language

One of the earliest decisions that had to be made regarding the implementation was the programming language to use. The choice of a low level language such as C would make the network and wireless configuration parts of the framework much easier, primarily due to the kernel and related tools also being written in C allowing a tight level of integration. On the other hand using a high level language such as Java or Python would allow

27

the more logic based parts of the framework to be written (and rewritten) quickly, where C would slow down development.

The emphasis of this project on creating a framework to enable further development of the mesh protocol in the future led to the decision that the rapid model of development offered by a high level programming language outweighed any benefits that a low level language would offer. The CRCnet Biscuit PC distribution did not contain any high level programming languages at the start of this project and one of the initial hurdles that was overcome was determining which language to use and installing it on the Biscuit PCs.

The Java Runtime Environment requires a minimum of 75MB of free disk space and recommends that you have 48MB of RAM available[13]. Neither of these requirements can be adequately met with the limited resources available on a Biscuit PC. Java is not open source, so the opportunity to recompile it leaving out unneeded features to save space is not possible. Python, as an open source application, is able to built from source and in this way a standard Python installation was able to be installed on a CRCnet Biscuit PC using less than 5MB of disk space.

Python has proved to be an excellent choice of language for the framework development. Had a low level language such as C been used for the mesh framework it is unlikely that this project would have progressed as far as it has towards creating the desired mesh network. One example of a benefit that Python has brought to the development process is its wide library of tools and functions. During preparation of the presentation for this project a need was identified to have real-time visualisations of the network topology. This presented the problem of how to get the data from each mesh node. Using one of Pythons built in modules a web server that returned a single page describing the state of the network was built in under thirty minutes. To implement a web server and integrate it with the existing code base would have taken at least a day in a lower level language such as C.

Despite the large number of modules that are present in the standard Python distribution there were some notable tasks a mesh node needs to perform that Python is not able to do. Fortunately Python has a very strong modular architecture allowing small snippets of C code to be easily inserting into the Python framework to extend its functionality. These user supplied modules can then be utilised in the same way as any built in Python module. Two such modules were written in the course of this project to provide functionality missing from Python that was required for the implementation of the mesh framework. Both of these modules will be released to the open source community in the near future.

4.2.1 Python Netlink Module

The standard Python distribution does not provide any way for a Python program to manipulate the network interfaces of the computer it is running on. A mesh node needs to be able to bring interfaces up and down at various times of its operation as well as being able to add and remove IP addresses from interfaces. To solve

28

this problem a python module was written in C to provide additional functionality to the mesh framework. The interface exposed to python scripts by the netlink module is documented in Appendix A.

4.2.2 Python Wireless Tools Module

The Linux kernel includes a driver abstraction layer to allow standardised configuration of a range of different wireless hardware. This abstraction layer is called the Linux wireless extensions and is used in conjunction with a set of userspace tools[42]. Python does not provide a standard module to interface with the Linux wireless extensions.

The module that was written in the course of this project provides a generic interface to the Linux wireless extensions by reusing parts of the Linux wireless tools source code in a Python C module. The module allows Python programs to configure the important parameters for a wireless interface such as the ESSID, channel and mode. Additionally the module provides access to the scanning functionality of the radio card which is crucial to the success of the neighbour discovery procedure described in Section 3.5. Development of this module encountered several problems with data structures inside the wireless extensions being changed during the course of the project. This usually resulted in strange bugs such as the network name missing the first two characters. Careful effort needs to be put into monitoring the version of the wireless extensions that are being used as they have very a loose versioning scheme.

The use of the Linux wireless extensions layer to provide access to the underlying hardware is desirable as it accomplishes most of the work that is needed for a seamless transition between 802.11b wireless cards and 802.11g wireless cards.

The interface exposed to python scripts by the wireless tools module is documented in Appendix B.

4.3Mesh Framework Architecture

The mesh framework that has been implemented by this project draws components from several different places. The key component of the framework is the mesh daemon which implements most of the protocol logic. This daemon interacts with the Linux kernel via several python modules including the two written by this project that were described in the previous section. Figure 4.1 shows how the various components of the framework fit together. Components with a dashed border are existing projects that were not written by this project.

4.3.1 Mesh Network Daemon

The key component of the mesh framework is the mesh daemon (shown in the top left hand corner of Figure 4.1). Within the mesh daemon are two main code units. These are implemented as separate threads and are

29

Figure 4.1: Mesh framework architecture

unshaded in the diagram. The first unit is the node control thread which controls the operation of the entire mesh daemon and ties the other units together. Only one node control thread exists in each instance of the mesh daemon. The second unit is a per interface thread created by the interface management class in the node control thread as part of the node initialisation.

The interface threads communicate with each other and the rest of the mesh daemon through the interface management class. The interface management class continually polls each interface thread to retrieve updated information on the directly connected neighbours which can be used to update the link database. Every five seconds the node control thread executes the neighbour selection algorithm. If this process changes the configuration for an interface, the interface management class is responsible for informing the appropriate interface thread of its new configuration. The structure of each interface thread and the tasks it performs is described further in Section 4.4.

The node control thread also contains the link database and neighbour selection algorithm. These components have been implemented as separate classes to allow for new implementations to be easily inserted in the future.

4.3.2 Routing Protocol

This project utilises the Quagga routing suite introduced in Section 2.4.3 to perform routing on the network using the OSPF routing protocol. The Quagga suite is run entirely independently of the mesh daemon on each Biscuit PC and has a configuration that enables it to detect and utilise links as they are established and removed by the mesh daemon. There is no direct communication between the mesh daemon and Quagga as Quagga is able to receive messages from the Linux kernel to automatically notify it when an interface on the

30

node is modified. An example Quagga configuration is provided in Appendix C.

While integrating Quagga into the mesh framework a bug was observed that prevented Quagga from detecting changes to an interface if they occurred after Quagga had started running. This was a serious problem as it meant that every time the mesh framework reconfigured an interface on a node there was the possibility that Quagga would fail to detect the change and routing on that interface would be disabled. This in turn could lead to a node being unable to fully participate in the network as each interface loses its routing over time. In conjunction with the Quagga maintainers the bug was diagnosed and a patch to Quagga was written and tested in the mesh framework. This patch has been submitted to the Quagga maintainers for integration into a future release of Quagga[31]. Further details on the diagnosis and fixing of the bug can be found in the Quagga mailing list archives[29].

4.4Interface Threads

The interface thread is a critical part of the mesh daemon described in Section 4.3.1 as it is responsible for all packet transmission and processing tasks as well as ensuring that the physical interface on the node has been given the correct configuration. To implement the mesh protocol designed by this project each interface transmits and receives mesh protocol packets at the Ethernet level as opposed to the IP level. This approach is taken as it allows nodes to communicate as soon as the 802.11 parameters for the network have been configured without having to configure IP addresses. Transmitting and receiving packets at the Ethernet layer raises several problems as the standard Python libraries only support sending and receiving packets through the standard Linux IP stack.

Two existing Python modules were able to be used to solve this problem. The first module, named Pcapy[7] provides an interface to the Linux PCAP[37] library which provides functions to capture all packets received at the Ethernet layer of an interface and forward them to a userspace application (such as the mesh daemon) for processing. The second module, Pylibnet is a Python wrapper for the well known libnet library[38] and allows Python programs to generate arbitrary Ethernet frames to be transmitted by the interface. Together these modules allow each interface thread on a node to transmit and receive the mesh protocol packets.

Every mesh protocol packet sent from an interface has the header shown in figure 4.2 prepended to it to allow mesh protocol packets to be distinguished from standard data packets on the wireless link. The header also contains a simple checksum over the packet to ensure that the information received by the remote node is the same as what was originally sent. Each field in the packet is described below.

Version (1 byte) – The mesh protocol version that the format of this packet adheres to. If the version is greater than the version the receiving node implements the packet must be discarded.

31

	0		1	2	3
	0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+	---------------	+	---------------+---------------	+	---------------	+
|	Version	|	Length (Bytes)	|	Type	|
+	---------------	+---------------	+---------------	+---------------		+
|			Checksum (CRC32)			|
+	---------------	+---------------	+---------------	+---------------		+
.						.
.			Optional Packet Data			.
.						.
.						.
+	---------------	+---------------	+---------------	+---------------		+

Figure 4.2: Mesh Framework Packet Header

Length (2 bytes) – The length in bytes of this packet, including the header.

Type (1 byte) – The type of mesh protocol packet. Valid values are:

0(Probe) – Probe packets used for neighbour discovery.

1(Hello) – Hello packets as described in Section 3.3.1.

2(Invite) – Invite packets used for neighbour synchronisation as described in Section 3.7.1.

3(Accept) – Accept packets used for neighbour synchronisation as described in Section 3.7.1.

Checksum (4 bytes) – A CRC32 checksum of the entire packet (including header). For the purposes of calculating the checksum the checksum field is set to all zeros.

Each interface thread contains a lock which is set whenever a portion of code is modifying the interfaces internal data structures. This lock is provided by the Python thread class and prevents the interface thread data structures from being corrupted as concurrent modifications are blocked by the lock.

32

Chapter 5

Results

The mesh framework created by this project was evaluated on two test bed networks. The primary characteristic that was evaluated in each case was the ability of the framework to establish wireless links through the network and setup routing. Performance measurements of the resulting networks have not been performed at this time, however as the networks that are created by this framework simply consist of a series of ad-hoc point to point links as used by CRCnet there is no reason to believe that the performance of the mesh network will be significantly different to that of CRCnet. Both test-beds were built using Soekris Biscuit PCs running the CRCnet Biscuit PC distribution and the mesh framework.

5.1Indoor Mesh Test Bed

The first of the test bed networks was built inside the WAND Lab in G1.02 and consisted of three mesh nodes arranged in a triangular topology as shown in figure 5.1.

Figure 5.1: Topology and possible links in the G1.02 test bed network

33