Mesh

Main Page - Roadmap - Summer Projects - Project Ideas - Developer FAQ - Tools - Related Projects

HOWTOs - Installation - Troubleshooting - User FAQ - Samples - Models - Education - Contributed Code - Papers

This page describes NS-3 effort aimed for wireless mobile ad hoc (aka mesh) networks simulation.

Goals

The ultimate goal is to create a playground for level 2 mesh networking protocols simulation and evaluation.

IEEE 802.11s draft protocols will be implemented as a short term goal.

Model & Architecture

Nodes of the mesh network are mesh points. Each mesh point has several dedicated wireless interfaces, working together to stay connected with its neighbours. Operation of the entire mesh network is provided by coordinated work of several layer 2 mesh protocols. This protocols are supposed to implement unicast and multicast routing, neighbour (aka peer) discovery and management, spectrum management, etc. Note that there are many possibile ways to solve each of this tasks, see e.g. this overwhelming list of ad-hoc routing protocols. Distinct protocols are supposed to outperform the others in distinct mobility and traffic conditions, network densities and sizes, QoS requirements ans so on.

So, the mesh model architecture must support

1. arbitrary number of interfaces and protocols installed on single mesh point and
2. relatively simple addition/removal of mesh L2 protocols.

The toplevel view of proposed architecture is shown on the figure below:

From the layer 3 point of view, mesh point (class MeshPointDevice) looks like usual network device. Note, that any other devices can be installed on the same node, e.g. Wifi access point seems to be useful.

From the layer 2 point of view, MeshPointDevice is a multiplexer of several wireless devices (class WifiNetDevice). Each interface has its own "high" MAC (class MeshWifiInterfaceMac) and channel. Instead of implementing all known L2 mesh protocols, MeshWifiInterfaceMac implmenets only basic functions: ad-hoc WiFi MAC + beacon generation and runtime extentions mechanism -- plugins (class MeshWifiInterfaceMacPlugin).

Every mesh L2 protocol (let it be Foo protocol) is implemented by two classes:

1. class FooMeshL2Protocol is tied to MeshPointDevice and implements station-level protocol logic.
2. class FooMeshInterfaceMacPlugin is tied to each MeshWifiInterfaceMac and extends its functions to support corresponding protocol.

The interface between FooMeshL2Protocol and FooMeshInterfaceMacPlugin is not restricted here, but it is recommended for MAC-level plugin to parse/make specific management frames and run interface specific state machine, while station level protocol doesn't known frame details but implements protocol logic, global state and MLME.

Next section describes current implementation of this architecture in more details.

Implementation

Class MeshPointDevice

Mesh point device is the coordinator of all its interfaces and the fixing point for all mesh L2 protocols. All mesh protocols are supposed to be tied with mesh point. MeshPointDevice implements NetDevice interface for layer 3 protocols interaction.

Single routing protocol (subclass of MeshL2RoutingProtocol, see below) must be selected to allow route discovery. All frames will first pass through the routing protocol to resolve route information before forwarding down to interface(s).

Apart of NetDevice interface, MeshPointDevice public interface looks like:

// Interfaces: 

/// Attach new interface to the station. Interface must support 48-bit MAC address and SendFrom method.
void AddInterface (Ptr< NetDevice > iface)
/// Number of interfaces
uint32_t GetNInterfaces () const
/// Interface access
Ptr< NetDevice > GetInterface (uint32_t id) const

// Protocols:

/// Register routing protocol to be used. Protocol must be alredy installed on this mesh point. 
void SetRoutingProtocol (Ptr< MeshL2RoutingProtocol > protocol)	

Class MeshL2RoutingProtocol

This is an abstract interface for all unicast mesh routing protocols. The async. route request interface is copied from IP routing, MeshL2RoutingProtocol public interface is:

/// Route reply callback. Last uint32_t is interface number to forward packet, or ALL interfaces.
typedef Callback< void, bool, Ptr< Packet >, Mac48Address, Mac48Address, uint16_t, uint32_t > RouteReplyCallback;
/// Request a route
virtual bool RequestRoute (uint32_t sourceIface, 
                           Mac48Address source, Mac48Address destination, 
                           Ptr< Packet > packet, 
                           uint16_t protocolType, 
                           RouteReplyCallback routeReply) = 0;

RequestRoute is supposed to annotate route information as some protocol-specific tag(s) on the packet to send. Then, corresponding MAC plugin (see below) is responsible to read this tag(s) and correctly update frame header.

Classes MeshWifiInterfaceMac and MeshInterfaceMacPlugin

MeshWifiInterfaceMac is a modification of high level of WiFi MAC implementing basic functions inherited from WifiMac, beaconing and plugins. Beacons are periodically sent, beacon sent time can be adjucted to avoid beacon collisions.

Each MAC plugin must define three pure virtual methods inherited from MeshInterfaceMacPlugin:

/// Process received frame. \return false if frame should be dropped.
virtual bool Receive (Ptr< Packet > packet, const WifiMacHeader &header) = 0;

/// Update frame before forwarding it down. \return false if frame should be dropped.
virtual bool UpdateOutcomingFrame (Ptr< Packet > packet, WifiMacHeader &header, Mac48Address from, Mac48Address to) const = 0 ;

/// Update beacon before it will be formed and sent.
virtual void UpdateBeacon (MeshWifiBeacon &beacon) const = 0;

Then plugin is installed to the `MeshWifiInterfaceMac`:

/// Install plugin. TODO return unique ID to allow unregister plugins. 
void InstallPlugin (Ptr< MeshWifiInterfaceMacPlugin > plugin);

and its methods are used in the following way:

Receive

When MeshWifiInterfaceMac receives frame it asks all registered plugins to process it, in pseudocode:

void
MeshWifiInterfaceMac::Receive (Ptr<Packet> packet, WifiMacHeader const *header)
{
  for all plugins 
    {
      bool drop = ! plugin->Receive(packet, header);   
      if (drop) return;
    }

  // Forward data up
  if (header->IsData())
    ForwardUp(packet, header->GetAddr4(), hdr->GetAddr3());
}

UpdateOutcomingFrame

Before forwarding frame down, MeshWifiInterfaceMac asks all registered plugins to update it, in pseudocode:

void
MeshWifiInterfaceMac::ForwardDown (Ptr<Packet> packet, Mac48Address from, Mac48Address to)
{
  // 1. Create wifi header. Address 1 is unknwon here. Routing plugin is responsible to correctly set it.
  WifiMacHeader header = CreateHeader(from, to);
  
  // 2. Filter packet through all installed plugins
  for all plugins {
    {
      bool drop = ! plugin->UpdateOutcomingFrame(packet, header, from, to);
      if (drop) return;  // plugin drops frame
    }
  
  // 3. Assert that address1 is set. Assert will fail e.g. if there is no installed routing plugin.
  CheckHeader(header);
  
  // 4. Queue frame
  Queue(packet, header);
}

UpdateBeacon

Beacons are supposed to be collectively used by distinct (m.b. all) protocols. All plugins are invited to add information elements to beacon:

void
MeshWifiInterfaceMac::SendBeacon ()
{
  // 1. Create beacon header
  MeshWifiBeacon beacon (GetSsid (), GetSupportedRates (), m_beaconInterval.GetMicroSeconds ());
  
  // 2. Ask all plugins to add their specific information elements to beacon
  for all plugins
    {
      plugin->UpdateBeacon (beacon);
    }
  
  // 3. Queue beacon frame
  Queue (beacon.CreatePacket(), beacon.CreateHeader(GetAddress()));
  
  // 4. Schedule next beacon
  ScheduleNextBeacon ();
}

Here MeshWifiBeacon is a container of infomation elements, see IEEE 802.11-2007.

IEEE 802.11s Protocols

Two mesh protocols of 802.11s draft: Peer Management Protocol and Hybrid Wireless Mesh [Routing] Protocol (HWMP) will be implemented using the framework described above.

This work is scheduled to finish at April 7 2009.