home 
wiki
wiki
Spelling: 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.
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
* Radio transmit power
* Radio receive sensitivity
* Antenna gain
* Antenna pick-up pattern
* Obstacles such as trees and buildings
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:
On the Impact of Noise Sensitivity on Performance in 802.11 Based Ad
Hoc Networks [1]
HIDDEN NODE
Even without obstacles in the way, nodes spread across distances
using omnidirectional antennas can be hidden from each other
In the above diagram:
* Node B can see both Node A and Node C
* Nodes A and C are hidden from each other
* Being unaware of each other, both Node A and Node C will often
attempt to transmit at the same time
* Node B, being in range of both A and C, will suffer from
interference when A and C transmit simultaneously
* RTS/CTS do not always work. RTS packets transmitted by Node A will
interfere with data being sent from C to B. Furthermore, if Node C is
transmitting for any reason, Node B cannot send CTS packets back to A
Frottle [2] 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 Token Ring
[3] protocol was written by IBM in the 1970's for wired networks.
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 token passing [4]. 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:
Wireless token ring protocol-performance comparison with IEEE 802.11
[5]
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.
Distributed Token Circulation in Mobile Adhoc Networks [6]
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.
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 [7] 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 [8]
and ScatterNets [9] are formed and destroyed.
ISSUES
* Can cope with lost "token" but need to add duplicate token
quenching.
* Staticly configuring relationships sucks but makes for a nice
controlled environment to get it working
* Need to make it smarter so we can partition and have multiple
rings in operation at once based on LOS and interference information.
-------------------------
Back to MelbWirelessRouterProject [10]
Links:
------
[1] http://www.cs.utsa.edu/faculty/boppana/papers/Icc04.pdf
[2] http://frottle.sourceforge.net/
[3]
http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/tokenrng.htm
[4] http://www.webopedia.com/TERM/t/token_passing.html
[5] http://www.eecs.berkeley.edu/~ergen/docs/wtrpiscc.pdf
[6] http://faculty.cs.tamu.edu/welch/papers/icnp01.pdf
[7] http://melbournewireless.org.au/?FirstD
[8] http://melbournewireless.org.au/?PicoNets
[9] http://melbournewireless.org.au/?ScatterNets
[10] http://melbournewireless.org.au/?MelbWirelessRouterProject
[EditText] [Spelling] [Current] [Raw] [Code] [Diff] [Subscribe] [VersionHistory] [Revert] [Delete] [RecentChanges]