Mesh - Revision history

Pavlo at 14:32, 2 June 2009

2009-06-02T14:32:42Z

← Older revision		Revision as of 14:32, 2 June 2009
Line 178:		Line 178:

	Two mesh protocols of 802.11s draft: Peer Management Protocol and Hybrid Wireless Mesh [Routing] Protocol (HWMP) are implemented using the framework described above in the devices/mesh/dot11s module.		Two mesh protocols of 802.11s draft: Peer Management Protocol and Hybrid Wireless Mesh [Routing] Protocol (HWMP) are implemented using the framework described above in the devices/mesh/dot11s module.

			=== Wireshark dissector ===

			Patch to [http://www.wireshark.org/ Wireshark 1.0.7], allowing nice 802.11s management frames and headers representation is included -- [[Media:Wireshark-1.0.7-dot11s.patch]].

Pavlo: /* IEEE 802.11s Protocols */

2009-04-13T05:26:20Z

IEEE 802.11s Protocols

← Older revision		Revision as of 05:26, 13 April 2009
Line 177:		Line 177:
	== IEEE 802.11s Protocols ==		== 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.		Two mesh protocols of 802.11s draft: Peer Management Protocol and Hybrid Wireless Mesh [Routing] Protocol (HWMP) are implemented using the framework described above in the devices/mesh/dot11s module.

	~~This work is scheduled to finish at April 7 2009~~.

Pavlo at 16:06, 25 March 2009

2009-03-25T16:06:53Z

← Older revision		Revision as of 16:06, 25 March 2009
Line 11:		Line 11:

	Nodes of the mesh network are ''mesh points''. Each mesh point has several dedicated wireless interfaces, working together to		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''.		stay connected with its neighbors. 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.		This protocols are supposed to implement unicast and multicast routing, neighbor (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 [http://en.wikipedia.org/wiki/Ad_hoc_routing_protocol_list 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.		Note that there are many possible ways to solve each of this tasks, see e.g. this overwhelming [http://en.wikipedia.org/wiki/Ad_hoc_routing_protocol_list 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 and so on.

	So, the mesh model architecture must support		So, the mesh model architecture must support
Line 25:		Line 25:
	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 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).		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 implemenets only basic functions: ad-hoc WiFi MAC + beacon generation and runtime extensions mechanism -- ''plugins'' (class MeshWifiInterfaceMacPlugin).

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

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

	MeshWifiInterfaceMac is a modification of ''high'' level of WiFi MAC implementing basic functions inherited from WifiMac, beaconing and plugins.		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.		Beacons are periodically sent, beacon send time can be adjusted to avoid beacon collisions.

	Each MAC plugin must define three pure virtual methods inherited from MeshInterfaceMacPlugin:		Each MAC plugin must define three pure virtual methods inherited from MeshInterfaceMacPlugin:
Line 106:		Line 106:
	==== Receive ====		==== Receive ====

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

	<pre>		<pre>
Line 151:		Line 151:
	==== UpdateBeacon ====		==== UpdateBeacon ====

	Beacons are supposed to be collectively used by distinct (~~m.b.~~ all) protocols. All plugins are invited to add information elements to beacon:		Beacons are supposed to be collectively used by distinct (may be all) protocols. All plugins are invited to add information elements to beacon:
	<pre>		<pre>
	void		void
Line 173:		Line 173:
	</pre>		</pre>

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

	== IEEE 802.11s Protocols ==		== IEEE 802.11s Protocols ==

Pavlo at 13:28, 23 March 2009

2009-03-23T13:28:14Z

← Older revision		Revision as of 13:28, 23 March 2009
Line 120:		Line 120:
	// Forward data up		// Forward data up
	if (header->IsData())		if (header->IsData())
	ForwardUp(packet, header->GetAddr4(), ~~hdr~~->GetAddr3());		ForwardUp(packet, header->GetAddr4(), header->GetAddr3());
	}		}
	</pre>		</pre>

Pavlo at 13:27, 23 March 2009

2009-03-23T13:27:21Z

← Older revision		Revision as of 13:27, 23 March 2009
Line 4:		Line 4:

	== Goals ==		== Goals ==
	The ultimate goal is to create a playground for ~~level 2~~ mesh networking protocols simulation and evaluation.		The ultimate goal is to create a playground for MAC-layer mesh networking protocols simulation and evaluation.

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

Pavlo at 13:22, 23 March 2009

2009-03-23T13:22:17Z

← Older revision		Revision as of 13:22, 23 March 2009
Line 96:		Line 96:
	</pre>		</pre>

	Then plugin is installed to the `MeshWifiInterfaceMac`:		Then plugin is installed to the MeshWifiInterfaceMac:
	<pre>		<pre>
	/// Install plugin. TODO return unique ID to allow unregister plugins.		/// Install plugin. TODO return unique ID to allow unregister plugins.

Pavlo at 13:20, 23 March 2009

2009-03-23T13:20:46Z

← Older revision		Revision as of 13:20, 23 March 2009
Line 21:		Line 21:
	The toplevel view of proposed architecture is shown on the figure below:		The toplevel view of proposed architecture is shown on the figure below:

	[[Image~~(ArchitectureDocument~~:ns3_mesh_toplevel.png)]]		[[Image:ns3_mesh_toplevel.png]]

	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 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.

Pavlo: Mesh arch ported to nsnam wiki for review

2009-03-23T13:12:49Z

Mesh arch ported to nsnam wiki for review

New page

{{TOC}}

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 [http://en.wikipedia.org/wiki/Ad_hoc_routing_protocol_list 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
# arbitrary number of interfaces and protocols installed on single mesh point and
# relatively simple addition/removal of mesh L2 protocols.

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

[[Image(ArchitectureDocument:ns3_mesh_toplevel.png)]]

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:
# class FooMeshL2Protocol is tied to MeshPointDevice and implements station-level protocol logic.
# 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:
<pre>
// 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)
</pre>

=== 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:

<pre>
/// 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;
</pre>

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:
<pre>
/// 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;
</pre>

Then plugin is installed to the `MeshWifiInterfaceMac`:
<pre>
/// Install plugin. TODO return unique ID to allow unregister plugins.
void InstallPlugin (Ptr< MeshWifiInterfaceMacPlugin > plugin);
</pre>

and its methods are used in the following way:

==== Receive ====

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

<pre>
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());
}
</pre>

==== UpdateOutcomingFrame ====

Before forwarding frame down, MeshWifiInterfaceMac asks all registered plugins to update it, in pseudocode:
<pre>
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);
}
</pre>

==== UpdateBeacon ====

Beacons are supposed to be collectively used by distinct (m.b. all) protocols. All plugins are invited to add information elements to beacon:
<pre>
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 ();
}
</pre>

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.