sfi

NDP

ENTERPRISE IRELAND

NCNRC

Communications Network Research Institute

Resource Aware Routing for Mesh Networks (RARE)

Karol Kowalik

The main technical objective of the project is to develop a resource-aware routing module for wireless mesh networks based upon Wi-Fi technology and which also will be compatible with the IEEE 802.11s ESS Mesh standard when it is approved. This module should enable stable and robust performance over a wide range of operating environments and be capable of supporting VoIP telephony calls with a quality of service that is acceptable to users.

Background

Wireless Mesh Networks (WMNs) are infrastructure-less communications networks that are formed solely by the clustering together of the constituent wireless nodes. The nodes can freely and dynamically self-organize into arbitrary and temporary ad hoc network topologies, allowing people and devices to seamlessly inter network in areas with no pre-existing communication infrastructure.

Data packets are routed through a mesh network as a series of multihop transmissions in a manner analogous to the operation of the Internet. Each wireless node in a mesh network in addition to acting as a termination point for data also acts a relay in providing an onward transmission facility to its neighboring nodes.

Routing protocols in mesh networks need to be aware of the radio environment. This is usually achieved by incorporating radio measurements taken on the medium into a link cost function. The link cost function can be constructed in many ways depending on the particular performance criteria required. For example, a link cost function may allow routing algorithms to compute minimum hop paths, maximum bandwidth paths, minimum loss paths, minimum delay paths, etc. Poorly selected paths may support only low data rates and consequently occupy the wireless medium for longer period of time than for high data rates links which in turn reduces the link capacity. Consequently the formulation of the link cost function is an important design issues for routing modules on mesh networks.

Project goal

The objective of the proposed project is to develop a routing module for mesh networks that is aware of the availability of resources (bandwidth), i.e. Resource Aware Routing for Mesh or RARE for short. The particularly innovative feature of the proposal is that it aims to passively (as opposed to intrusively) monitor the quality of the radio links. This function will be performed using the recently developed resource monitoring application. This radio link information is then required to be mapped into the link cost function. Moreover, the process of distributing control and management information also consumes bandwidth. Therefore, the routing protocols need to use an appropriate link cost function to maximize the throughput of the network and to also minimize the amount of state information exchanged. Thus the formulation of the link cost function is the key component of the proposed RARE module.

Radio link measurements

Mesh measurements can be used to support the routing protocol in the selection of stable and high throughput paths. Specifically, radio link measurements can be used to construct an appropriate link cost function which can accurately represent radio link characteristics thus making the routing protocol aware of the wireless medium. Such measurements can be obtained using active probing or passive scanning techniques.

Active Probing

When active probing is used, usually one node broadcasts packets while the other nodes monitor this transmission. The nodes may then check how many of the packets where successfully received (thus calculating the delivery ratio as used by De Couto et al. [1]), how it influences the current data transmissions (thus calculating the interference used by Padhye at al. [2]) or use it to estimate the bandwidth (as used by Keshav [3]). Many researchers use active probing because as they claim it provides accurate information about the radio link [1,4,5]. However, these active probing techniques generate more and more overhead when extended to provide additional measurements. Consequently, the overhead associated with active probing that can limit the capacity of the network under heavy load conditions.

Passive Monitoring

Passive monitoring allows a wireless node to intercept the transmission activities of other radios within its communication range. Here the wireless card is put into the RFMON (Radio Frequency Monitoring) mode, allowing the card to capture the data frames, as well as control and management frames. For example, by knowing how much time the medium is occupied with transmitting data, control, and management frames, it is possible to determine how much bandwidth is being consumed by these activities and thus is possible to infer how much free bandwidth is remaining. Moreover, such information can be used to detect when multiple nodes are contending for access and to ascertain the average level of contention for access to the medium.

One of the main advantages of passive monitoring is that it does not suffer from the overhead penalty associated with active probing and consequently does not impact on the capacity of the network (see Figure 3).

Overhead
Figure 3.

This passive monitoring and statistical analysis of available bandwidth, average contention (amongst other metrics) is performed by a unique WLAN resource monitor application that has been developed at the DIT CNRI laboratories developed by the DIT CNRI in a previous project.

RARE module

The RARE routing module being proposed in this project will make the routing protocol aware of the radio link resources. This will be achieved by providing the routing protocol with the link cost values which will quantify the usability of the link for the data transmission, assigning high cost for the links with limited resources and low cost for the high quality links. Thus the RARE routing module will perform the following functions:

The architecture of the proposed RARE module is presented in Figure 4.

Rare
Figure 4.

References

[1] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris, A High-Throughput Path Metric for Multi-Hop Wireless Routing, Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom 03), San Diego, California, September 2003.

[2] R. Draves, J. Padhye, and B. Zill. Routing in Multi-radio, Multi-hop Wireless Mesh Networks. ACM MobiCom, September 2004.

[3] S. Keshav. A Control-theoretic approach to flow control. In SIGCOMM, 1991.

[4] J. Padhye, S. Agarwal, V. N. Padmanabhan, L. Qiu, A. Rao, and B. Zill. Estimation of link-interference in static multi-hop wireless networks. In IMC, Oct. 2005.

[5] Gautam Kulkarni, Alok Nandan, Mario Gerla, and Mani Srivastava. A Radio Aware Routing protocol for Mesh Networks. Submitted to IEEE Globecom, 2005.

If you have any comments or suggestions please feel free to contact us at cnri@cnri.dit.ie


This project is being carried out under the financial support of Enterprise Ireland under the Commercialization Fund 2006.