A Multi-radio Wireless Mesh Network Architecture

Routers equipped with multiple 802.11 radios can alleviate capacity problems in wireless mesh networks. However, a practical, complete system architecture that can realize the benefits of multiple radios does not exist. The focus of our work is to offer such an architecture. Our architecture provides solutions to challenges in three key areas. The first is the construction of a Split Wireless Router that enables modular wireless mesh routers to be constructed from commodity hardware. A split wireless router alleviates the interference that can occur between commodity radios within a single piece of hardware. The second is the design of a channel assignment server responsible for collecting information about the mesh topology and the interference relationship between the mesh links, executing a channel selection algorithm that selects channels which result in high-throughput frequency-diversified routes, and disseminating channel assignments to mesh routers. Third is the design and implementation of several communication protocols, protocols that are necessary to make our architecture operational.

Our system is deployed, tested and evaluated on a 20-node multi-radio wireless testbed we constructed using the split-router architecture. Our evaluation focuses on multiple aspects of our architecture, including its performance in the presence of different traffic patterns, and the impact of short-term variations in link characteristics on system performance. Results demonstrate that our architecture makes feasible the deployment of multi-radio mesh networks built entirely with commodity hardware. An 802.11a dual-radio router in our deployment is able to forward aggregate TCP traffic over 15 Mbps while a traditional router construction is able to operate at only 2 Mbps. In addition, we show that our architecture offers TCP throughput improvement of 30-100% over two other channel assignment solutions.

Publication

Krishna Ramachandran, Irfan Sheriff, Elizabeth Belding, Kevin Almeroth, A Multi-radio Wireless Mesh Network Architecture, UCSB Technical Report, December 2006.

Architecture Overview

These slides contain an overview of the TIC architecture and also some results from our performance evaluation.

Software

All software provided below is released under the GPL license. Please feel free to inform me about bugs or possible improvements.

The documentation provided below is really only the bare minimum to get everything running. I will update this page regularly with more information.

Split Wireless Router

Our split router implementation is available here. More documentation to come soon.

Channel Selector

Our channel assignment algorithm is the Route and Interference-aware Channel Assignment algorithm (RICA). RICA uses the Dijkstra shortest path algorithm to find the best gateway to access point route. The best route is decided by RICA by factoring in the reliability of links, bandwidth attainable on links, and possible channel assignments of the various radios in the mesh network.

The RICA implementation is provided here. To compile, run the compile utility contained in the package.

Usage

Usage:
java com.tic.cas.rica -r relay_information -g gateway_info -n neighbor_table 
       -p ap-priority-list -c channel-rank-file

The relay_information file contains information about each node in the mesh network, such as its hostname, its radios, radio types (802.11a/b/g), and radio IP addresses. The gateway-info file contains the identity of the gateway in the network. In the example file provided in the config folder, the first name in the file is the gateway. All other hostnames are essentially routers that associate with this gateway. The neighbor_table file contains the latest topology information. RICA uses the latest topology information to decide which channels to uses for which radios. The paper indexed above describes how the topology information is gathered in the TIC architecture. The ap-priority-list contains a ranking of APs. RICA gives channel assignment priority to APs ranked higher. Ranking becomes important when not enough channels or radios are available because of which links in interfering range of each other can be assigned the same channel. Therefore ranking can influence inter-flow interference. The paper has more on this condition. Finally, channel-rank-file allows each radio to influence which channels are assignable to it. So for example, if there is a lot of external interference on channel 36 in the neighborhood of a router, that router can inform RICA of its disliking for channel 36 by placing it last on the ranking list.

Example use contained in source package:

java com.tic.cas.rica -r config/meshnet-dotab-hosts -g config/meshnet-gateways 
     -n neighbortable -p config/meshnet-ap-priority -c config/meshnet-channel-ranking

The above invocation generates an assignments file that contains the channel assignments for each IP address in the relay_information file. Any assignment equal to -1 means that RICA never assigned a channel to it. This typically happens because either the IP is not reachable or the router containing that radio is reachable through another of its own radio. RICA does not perform flow splitting. Therefore, the same "best" route is always used. The best route is the route that yields the lowest WCETT metric. WCETT is a multi-radio routing metric. This publication describes WCETT in detail. To understand how RICA uses WCETT, please refer our publication indexed above.




Contact: Krishna Ramachandran if you have any questions.
This work is currently supported in part by the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed in these materials are those of the author(s) and do not necessarily reflect the views of any of these organizations. We are very grateful to our sponsor - thank you!!!