home  wiki

MWRPAdhocFrottleDev

 This page describes what's going on in our quest to create a version of Frottle for Adhoc Networks.

The Problem


Transmission distances


Radio transmissions can cause interference at a greater distance than which they can be clearly received.

Node RF Zones
A simplified view of the distances at which a node can communicate and cause interference.

Node A has a theoretical reception zone. Other nodes inside this zone are able to clearly communicate with Node A.

The size and shape of the reception zone depends on factors such as

Outside the reception zone is the interference zone. Node A cannot clearly receive the transmissions from other nodes in this zone, but their transmissions still cause interference.

Below is a link to an excellent paper that describes the problems of using RTS/CTS with the 802.11 MAC in an Adhoc netowork:
External linkOn the Impact of Noise Sensitivity on Performance in 802.11 Based Ad Hoc Networks

Hidden Node


Even without obstacles in the way, nodes spread across distances using omnidirectional antennas can be hidden from each other
The Hidden Node Effect in an Adhoc network

In the above diagram:

External linkFrottle designed to coordinate traffic on Infrastructure-style networks - that is, networks that make use of Access Points. Frottle currently uses a Master/Client approach whereby the Master coordinates the traffic and the clients only transmit when the Master tells them to. In an infrastructure-style network there is obvious place to put the Master - at the Access Point. An Adhoc network is by it's nature non-heirarchical. There is no obvious place to put a Frottle Master to coordinate transmissions. Some nodes may not be in range of a fixed Master node and therefore would be unable to be directly coordinated by the Master. Direct coordination via a single hop link is required by Frottle - relaying control packets from the Master via one Frottle Client to another does not work very well because the relaying node must wait for it's own poll to to transmit.

But the requirement still exists that only one node should ever be transmitting at any one time. Rather than relying on a Master to coordinate traffic, nodes must be able to coordiante each other. Therefore, nodes must be able to act as Frottle Clients and Frottle Masters at different times.

The Solution


Token Passing


Token Ring networks are not a new concept. The definitive External linkToken Ring protocol was written by IBM in the 1970's for wired networks.

Token Ring in a wired network
Token Ring in a wired network. Image from webopedia.com

Nodes have the right to transmit when they receive a token from another node. The transmitting of a token from one node to another is referred to as External linktoken passing. The token may give the node the right to transmit all data waiting in it's queue, or the node may only be allowed to transmit for a set time period - this is it's Transmit Window.

When the node has finished transmitting, it transmits it's token - which is addressed to the next node in turn. This continues on until all the nodes in the ring have had their turn. A network of computers circulating tokens amongst thesmelves are a token ring. One complete circuit of the token around all the nodes in the network is referred to as a round.

Using a token-passing protocol in a wireless mesh network isn't an obvious choice. After all, nodes arranged in a mesh topology usually look nothing like a circular ring. How does the token find it's way around all the nodes and then end up at the beginning? Adhoc networks are in constant flux - nodes enter, move around and exit the mesh at will. Writing a protocol that can deal with this is the real challenge. This wiki page aims to bring together the current ideas on the subject and to propose algorithms that can be written into an Adhoc version of Frottle.

The idea of using token-passing to coordinate transmissions on a wireless network is not new. Over the years mountains of academic papers have been published.
Here are a few of them:
External linkWireless token ring protocol-performance comparison with IEEE 802.11
An idea for a Wireless Token Ring Protocol. Describes well the method for nodes to join and exit a ring, and suggests that a network be made of a number of small rings. It suggests that different rings be on different channels, but does not explain how different nodes on different channels can communicate with each other.
External linkDistributed Token Circulation in Mobile Adhoc Networks
An excellent review of the different methods of circulating tokens in wireless mesh networks. It suggests that the most effecient method for mobile networks not the same as for static networks.

Steps involved in token transmission

When a node first initialises itself it waits a set time and listens for nearby traffic. If no traffic is received it waits a random period of time and then transmits a hello packet asking nodes within link-range to announce themselves. The nodes that receive the hello wait a random period of time then transmit acknowledgements to the hello.

The node that transmitted the hello elects itself the token Originator and chooses a successor.

Step 1

 Node A has the token and transmits the data in it's queue. Node B can receive data addressed to it.

Node A then transmits a solicit successor packet to give any nearby nodes a chance to join the ring

If no other nodes answer Node A, Node A transmits the token. Node A addresses the token to it's previously established successor - Node B.

Node A can also transmit link-state information. In this case Node A broadcasts that Node B is still it's only link partner. Node B records this information.

Step 2

 Node B has the token and transmits the data in it's queue.

Node A can see that Node B is transmitting and infers that the token was successfully passed. Explicit acknowledgement of token-passing is not always required. If the node that just passed it's token sees the next node transmit it can assume that the token was successfully received.

If Node A for some reason does not see Node B transmit, it should then ask for explicit acknowledgement of the token pass. If no acknowledgement is received from Node B, Node A can assume that Node B is no longer it's neighbour.

Node A and Node C can receive the data that Node B is transmitting.

Node B transmits the solicit successor packet if Node C was not previously established as B's successor it will wait a random period then transmit it's willingness to be Node B's Successor.

Node B chooses Node C as it's Successor

Node B also makes a note of any other nodes that responded to the solicit successor packet and notes that they are also one-hop neighbours.

Node B broadcasts link-state information stating that Node A and Node C are are it's neighbours. Node B then transmits it's token which is addressed to Node C.

Node A receives Node B's token transmission and knows that Node C now has the token.

Step 3


Rinse and repeat until all nodes in the mesh have received the token at least once.

A full circulation of the token to every node in the mesh is known as a round.

Information carried in the Token

 Tokens should contain the following information

Originator Address (CA)

 The MAC address of the node that created the token

Predecessor Address (PA)

 The MAC address of node last visited by the token - not necessarily the address of the node that last transmitted the token

Successor Address (SA)

 The MAC address of the node the token is visiting next - not necessarily the address of the node to next receive the token

Sequence Number (SN)

 Every time a node creates a new token, it increments it's sequence number.

Nodes that receive a token with the same SN (from the same originator) more than once will know that it has not completed a full circuit of the ring and can address it to a different successor.

The first time node receives a token it should transmit the data in it's queue. The token is said to have visited this node. If it receives the same token again it should address it to a successor that has't received the token. Having already visited this node the token is now said to have on-passed this node. If the node has sent the token to all the neighbours that it knows about, or if the node receives a token addressed to an unknown node, it should send the token back to it's first Predecessor

If a node receives a token not addressed to it, it should simply on-pass the token without transmitting the data in it's own queue. This is so that no node gets an unfair slice of air-time. By default, each node should transmit once and only once per round.

Visit Count (VC)

 The number number of times the token has visited a node since it's generation

Hop Count (HC)

 The total number of nodes the current token has traversed (visiting or just passing) since generation

This is a measure of how efficiently the token is being passed - the number of times a token is on-passed should be kept to an absolute minimum - the Hop Count should be as close to the Visit Count as possible.

The Hop Count can also be used to test if a token has been duplicated. If a node receives a token with the same Sequence Number as one received previously, but with an equal or lower hop count (or even equal +1), the only assumption to make is that the token was somehow duplicated and it should be immediately retired.

Ring Size (RS)

 A count of the total number of nodes in the ring. Each time a node adds a new successor to the ring it increments the Ring Size counter. Each time a node receives no acknowledgement from it's successor when the token is passed, the Ring Size is decremented.

If a node receives a token (visit or on-pass) in which it's visit count equals or is greater than it's ring size, and if the node has no other successors to pass the token to, it should address the token to the originator node.

When the originator node receives a token that has a Visit Count that is equal to or greater than the Ring Size, it will retire the token and issue a new token with a new Sequence Number. The Ring Size of the new token will be equal to the Visit Count of the previous token.

Notes


If nodes simply broadcast their one-hop neighbours before passing the token, neighbouring nodes can learn about their 2-hop neighbourhood without extra topographical information being included in the control packets.

Frottle could theoretically receive information from the Routing Protocol in use on the mesh and learn about the entire topography of the mesh. Each node running Frottle could execute a search algorithm and determine most efficient node path and address the token to the most suitable successor accordingly.

Frottle by itself must be able to function with a basic rule-set without any need to be "plugged in" to a routing protocol. The task of Frottle is only to ensure that all nodes receive a fair share of airtime. Frottle should not take on the task of a discovering the entire topography of the network - that's the job of the routing protocol. Without full topographical information the token circulation path may not be optimal, but must be able to visit all nodes eventually. Optimisation of the circulation path can occur when Frottle receives additional topographical information from the routing protocol (such as OLSR). Frottle's packet structure and search algorithms should take into account that in some cases nodes will be aware of the entire network topography and sometimes will only be aware of their one-hop neighbours. In the case where the full topography is not known, a token that reaches a dead-end in the network should back-track until a node with a neighbour that hasn't received the token is found.

If a node receives a token which is to be on-passed and the location of Successor isn't known, what does the node do?
1. broadcast token blindly to see if any other node does know where the Successor is.
2. If no acknowledgement then assume Successor has left the ring
3. Retire the token and elect self as new Originator

Just Idea's on mapping layer 1 zones.


this would probably work for better for dense mesh network.

How do you calculate if you have a hidden node when using omni's in the first place? this could be done with forcing different 802.11 rates, for instance a packet transmitted at 54meg via ofdm, will have a smaller coverage than a packet transmitted at 1meg via CCK. using this method , frottle can also learn the concept of interference zones. You will know that (unless you override) that layer 2 broadcast's and multicast packets and 802.11 control frames (rts/cts) are sent at the lowest data rates avaible for maxium coverage and reliablity, so that all stations can hear the 'broadcast'. these broadcasts/mutlicasts are not ack knowleged by the network (this would mean on a network of 10 nodes, all in range, that 9 ack's would need to be generated!...doh!).

if all nodes agree (to be negotiated via a protocol) to communicate at a higher fixed rate (this requires a stable radio enviroment), then multiple token's can be allocated into distinct wireless zones. A groups of nodes can communicate in different zones without fear of causing a collision or interference with the other zone.

What I've read in my microwave radio engineers handbook, that ofdm uses a higher datarate, so it spreads more data into the same amount of 20mhz spectrum, thus reducing the over all signal strength over distance, this I'm hoping translates into a much smaller interference 'bubble'. ofdm said to deal with interference much better than cck or the other 'spreading' methods, so it may be the fact the the interfence zone is much less of a problem when using ofdm encoding methods (which occur at the higher datarates)... still I've got to prove all of this, It maybe the fact the ofdm signal makes same channel cross cell noise worse than with other layer 1 encoding systems (cck) without test equipment I can't really tell at this stage. somebody put me out of my misery ;).

http://www.airespace.com/technology/technote_using_picocells.php

this has an explanation of it, seem the each packet transmitted starts with a low datarate header (for 802.11b backward compatiblity) and then high data rate 'data section' so it seems that this method will not work. unless the unit's receive sensitivty can be altered :-(

an example.

all nodes are on the same radio channel

so A---B-----C-------D-------------E--------F 
  |---token Zone 1--|--token Zone 2--------|


if A is transmitting at a datarate of 1meg CCK, it can communicate with B, C, and interfere with D. E and F cannot hear A at all. A transmitting at a data rate of 54meg ofdm, A can communicate well with B, interfere with C , D and E,F cannot hear A at all. if B is transmitting at 54meg ofdm, it can see both A and C, and in this example. D and E, F cannot hear it.

thus we have two zones, which could support independent token. When D transmits, it will need to hold token's from both zones to do so.

so what so different about this solution, mainly we are using 802.11 data rates to build a physical wireless map of where nodes are in relation to other nodes. the same could be done with tx strength, but I beleive ofdm is much more resistant to cross node interference than slower 802.11 encoding methods. (I may be wrong on this, if I am this idea needs to be deleted)

this would not work in a mobile enviroment as each node needs to work out where it's sit in the 'real world' radio enviroment before it's start chatting.

using a layer 3 routing protocol is not going to be able to identify wireless coverage zones at layer 1, most routing protocol use broadcast's (1/2 meg cck encoding). I did see a paper on using varible transmit power to reduce interference in mesh networks. However I'be need seen a method like this one. ofdm might be able to save us from mesh interference hell. :-) comments please.
Laters, Tox

Multiple Tokens


If the mesh gets very large some nodes may be waiting a long time for a visit from the token. Since there will need to be a timeout mechanism to ensure a resumption of traffic if the token is lost, the same timeout mechanism will result in multiple tokens in a large mesh. This is not necessarily a problem. If two tokens enter the same area, one of them should be retired immediately to prevent transmission collisions.

But multiple tokens following the same rules may be able to circulate in a mesh for a long time without ever meeting each other. In a static mesh, tweaking the timeouts and search algorithm variables can make it more likely that multiple tokens do not meet. The protocol itself may be able to specify a method for tokens to automatically tweak their own parameters and pass tweak suggestions to other nodes to maximise the number of simultaneous tokens circulating, and minimise the number of token collisions.

Current implementation

 The current implementation of frottle for mesh retains the concept of a master polling known clients. What is diferent to the BSS version is that a Node that is a client of one domain can be a master of another. When that Node registers with the first domain it declares itself as a master. The Master of the first domain now knows it has become a co-master and has to pass control to the second Master when it concludes a poll.

An example probably makes this clearer:

Scenario 1


Domain First D
Node A, Master First D
Node B, Client First D
Node C, Client First D

Nodes start in random order, there is no control until Node A is up, then It receoves broadcast register packets from Node B and Node C. Node A starts to regulate transmissions of all nodes according to the RF Rate of the link and the defined parameters.

There is another node Node D that is in range of Node A. Node D is a Master of another "cluster" of Nodes

Domain Second D
Node D, Master Second D, Client First D
Node E, Client Second D
Node F, Client Second D

When Node D starts it will accept registration for Node E and Node F. Because it is also a Client for doamain FirstD it registers as a Client in that domain with Node A. In the registration packet it identifies itself as a Master of Domain Second D.

Node A will poll Node B, Node C and Node D. When it reaches Node D it passes conrol in the poll. Node D will transmitt any traffic it has and then do it's poll of Node E, Node F. At this stage Having no Clients registered that are masters it will pass control back to Node A. 

  Node B )------( Node A )------( Node C     Domain First D
                    V
                    |
                    |
                    A
  Node E )------( Node D )------( Node F     Domain Second D


Scenario 2


Same as above but Node A is also a Client of Second D.

In this case Node D registers as a client with Node A and Node A registers as a client with Node D.
Node A polls its clients then passes control to Node D. Node D polls its clients then passes control to Node A - we have a ring rather than a out and back.

General case

 This can continue indefinitely with any Master passiing control to a leaf Master (where it comes back after the leaf Master is done) or a ring Master (where control moves forward all the time). Note, you can configure a very sub-optimal arrangement as it stands, you really need to think about what nodes are Masters and where control passes next.

This requires prior identification of the Nodes that will be masters and definition of the domains. Future implementations may be able to derive this information from the routing tables and nodes could dynamicly become Masters if needed. I'm thinking along the lines of what happens in the MAC layer of dot11.15 here, the way PicoNets and ScatterNets are formed and destroyed.

Issues

Back to MelbWirelessRouterProject

Version 6 (current) modified Mon, 26 Jul 2021 12:49:29 +0000
[EditText] [Spelling] [Current] [Raw] [Code] [Diff] [Subscribe] [VersionHistory] [Revert] [Delete] [RecentChanges]
© Melbourne Wireless Inc. 2012
> home> about> events> files> members> maps> wiki board   > home   > categories   > search   > changes   > formatting   > extras> site map

Username
Password

 Remember me.
>

> forgotten password?
> register?
currently 0 users online
Node Statistics
building132
gathering193
interested515
operational233
testing214