esta info le puede ser util especialmente a inalambricaDC ya que
andan buscando firmware, aca hay uno en pleno, esta siendo
desarrollado por la misma gente openwrt+freifunk asi que es
seguramente un buen camino a intentar:
------------------------------------------------------------------------
-
B.A.T.M.A.N-III 0.1-rc1 mesh routing daemon released
------------------------------------------------------------------------
-
During the Wireless Community Weekend 2006 people where experimenting
with
the first implementations of the B.A.T.M.A.N algorithm. Quite some
time has
passed since this event... Meanwhile we have improved the algorithm and
implemented the features that B.A.T.M.A.N needs to replace other routing
software in community mesh networks.
We are confident that the algorithm works better than other protocols
that we have seen so far, even in larger meshclouds. Until now we
have sucessfully
tested B.A.T.M.A.N in small mesh networks.
* B.A.T.M.A.N is building routes very fast compared to OLSRD and the
response to changes is quicker
- it doesn't calculate gigantic topology-graphs
- it doesn't need to synchronise topology information
- routing loops are theoretically impossible
- routing tables contain proactively all stations that are reachable
though, while reactive protocols don't
- a single, central server collects topology information from all
nodes for 2D or 3D topology visualisation software
* B.A.T.M.A.N doesn't populate routing tables with unreachable
stations
- routing tables are build organically i.e. routing entries are not
endlessly passed on. they appear only if they are available
* B.A.T.M.A.N connects to gateways via IP-tunnels
- gateway clients can select their gateway
- gateways are considered according to their speed and availability
- gateway clients can switch a gateway if it appears to be a
black whole
- no more gateway switching as long as the gateway is available,
i.e.
VOIP, SSH, Chat connections are stable
* B.A.T.M.A.N generates less protocol overhead
We hope that many people are going to test B.A.T.M.A.N extensively so
we can
sort out bugs. At the moment B.A.T.M.A.N-III 0.1-rc1 compiles for Linux.
Ports for Mac OS-X and Free-BSD are broken at the moment.
We are providing sources and pre-compiled binaries for ARM, MIPSEL and
i386 at:
http://snr.freifunk.net/svn/b.a.t.m.a.n
If you want to keep up with the development use subversion:
svn co http://snr.freifunk.net/svn/b.a.t.m.a.n
y esta es la descripcion tecnica.
B.A.T.M.A.N-III
BETTER APPROACH TO MOBILE AD-HOC NETWORKING
####################
# 1.) INTRODUCTION #
####################
B.A.T.M.A.N is a new approach to Ad-Hoc-Routing, unlike other
algorithms that we are aware of. Reactive MANET protocols search for
routes when a node initiates communication to a remote node. Proactive
protocols (link-state algorithms) calculate routes proactively from all
nodes to all nodes in the mesh-cloud, whether they are necessary or
not. B.A.T.M.A.N doesn't calculate routes - it continuously detects
the existence of routes by forwarding and receiving broadcast
packets. The algorithm does not try to find out which path packets
follow to a remote node. B.A.T.M.A.N merely checks which single hop
neighbor it has to send a package to in order to push it on the best
way to a node in the mesh. If you want to find out how B.A.T.M.A.N
routes to a certain node, perform a
ping -R <destination address>
Note that this command does not work with busy box (a multi-call binary,
the 'swiss knife' for embedded Linux systems, used for example in
OpenWRT and Freifunk firmware), since 'ping' doesn't have the -R
option in busybox. You can do
traceroute -n <destination address>
instead.
#################
# 2.) EVOLUTION #
#################
B.A.T.M.A.N-III is the third stage in the evolution of the
B.A.T.M.A.N. algorithm - hence the numbering scheme. B.A.T.M.A.N-I
didn't check for bidirectional link conditions when forwarding
packets. This was an obvious design flaw. We didn't bother to add
bidirectional link checks in the first experimental implementation
that was meant to merely test the algorithm. The results of
B.A.T.M.A.N-I were however promising, so B.A.T.M.A.N-II was
implemented introducing a simple mechanism to check for bidirectional
links to perform further tests in real-live scenarios.
B.A.T.M.A.N-II implemented the bare algorithm with bi-directional link
checks for meshnodes with one interface only and was tested in the
Freifunk meshclouds of Berlin and Weimar. Thank you very much, you are
really brave guys! It was working quite nice on PCs, but the quick and
dirty implementation was causing high CPU-Loads on embedded systems
and even broadcast packet storms!
We found out that the algorithm of B.A.T.M.A.N-II still had its
flaws. We identified conditions where B.A.T.M.A.N-II would choose
routes far from optimal and even could cause routing loops. Hence
B.A.T.M.A.N-III implements changes in the algorithm to cope with these
scenarios.
Some new features, namely Internet gateway detection and
auto-negotiation of IP-Tunnels, have been added. Support for multiple
interfaces per node has been implemented. And last but not least we
have a mechanism to collect link state information in a centralized
server so people can download data from this server to display those
fancy three-dimensional meshclouds with s3d or two-dimensional with
dot-draw.
Now B.A.T.M.A.N-III has - in theory - everything to replace other MANET
routing daemons. As this is a young and experimental development it
needs
further testing to improve maturity, of course.
We'll have a party at c-base in Berlin soon, to celebrate when this
milestone will finally be released as B.A.T.M.A.N-III-0.1!
B.A.T.M.A.N. will have a hard time to gain the same popularity like
olsrd
from olsr.org. OLSR is now the same for community mesh networks in
Europe
and elsewhere what 'Tempo' is for handkerchiefs in Germany. Tempo is a
German brand that produces handkerchiefs. Germans with a cold rather
ask for
a 'Tempo' than for a 'Taschentuch' (= handkerchief).
The formula:
OLSR = Community Mesh Network
is now established in the minds of community networkers today.
It is overwhelming to see what olsr.org has been growing into. Let's
wait and see
the way that B.A.T.M.A.N. goes :)
#####################################
# 3.) MANET THEORY AND B.A.T.M.A.N #
#####################################
A node in a B.A.T.M.A.N-MANET is only interested to learn about the
existence of all nodes that it can communicate with, either in single or
multi-hop range, and which single hop neighbor it has to choose as a
router
to a certain destination. To communicate with a node in multi-hop
range a
B.A.T.M.A.N node only needs to know which single hop neighbor is the
best
to send its packets to, so that the packets takes the best way to the
node
in the distance. To explain the advantage of this approach it may be
best to
compare it with other ideas about mesh routing - namely source
routing and
link state routing.
Reactive (Source Routing) Algorithms
Source routing means a node Y in the mesh 'thinks', that the best way to
send data to node D is a path where the packet travels from node Q to
node
S, from node S to node H, from H to W - and so on - until the data
terminates at the destination node. Y gives Q the directive to send
the data
to S. S receives the directive from Y to send the data to H - the whole
chain is planned by the originator of the traffic. So Y computes the
path to
D and tells intermediate nodes what to do.
One known design for MANET Routing is DSR - Dynamic Source Routing. DSR
contains an algorithm that aims to find source routes and to maintain
them,
in case they break down. The fly in the ointment is, that MANETs are
subject
to highly dynamic changes. A MANET does not only lose payload data, but
loses topology information also. If the originator is several hops
away from
the destination it is very likely that the information about the
topology on
the other end is very hazy, incomplete and outdated. The originator
is the
node most incompetent to decide the path of the data on the other end
of the
path. The chain could be already broken down before Y sends its first
packet. Y then receives a message that the destination host is
unreachable
and starts looking for a new path again.
Proactive (Link State Routing) Algorithms
In a mesh with proactive link state routing (LSR) every node tries to
calculate routes valid for the whole mesh from every single node to
every
other. Fortunately this does not mean source routing, because the
view about
the topology in the distance is hazy, too. In fact every node
maintains a
individual huge database and computes paths that packets should
follow and
hands payload packets confidingly to the next neighbor on the path
that it
has calculated. While one node may believe that it knows the path
that the
packages are actually going to travel, each node maintains its own
database
and calculates its own paths. So every node autonomously computes its
own
decisions when initiating or forwarding traffic.
There are two flies in the ointment that come with this approach. First
tradeoff is the calculation of huge databases, while all a node can
decide
is select the next single hop neighbor that it hands a packet to. Second
the databases in nodes in a mesh with a considerable number of nodes are
never really consistent - so routing loops can occur if the route
calculations of two nodes involved in forwarding traffic are not in
sync and
collide with each other. Link state routing therefore bears a lot of
overhead and problems. The advantage compared to source routing is
that a
node closer to the destination has better information about the
status of
the topology and can compute better decisions about the path.
If routing loops occur you get the message 'Time to live exceeded' when
performing a 'ping'.
The link state routing protocol (LSR) that is most popular today in
the open
source world is OLSR from olsr.org. OLSR with LinkQualityExtension and
Fisheye-Algorithm works quite well, apart from a few bugs and the
annoying
effect, that it too often switches between internet gateways which
causes
problems (connections break down, timeouts). OLSR lacks an IP-Tunnel-
Plugin
that would users allow to select their gateways.
In conclusion the algorithm of OLSR is too complicated for its own
good and
draws too much CPU-Power. So it is time for something more simple and
more
effective.
There is a well known quotation from Antoine Saint Exupery, Author of
the 'The
little prince':
All human doing goes the way from the primitive along the complicated
to the
simple.
B.A.T.M.A.N. could be a milestone in the development of a simple yet
well
performing routing algorithm for MANETs.
B.A.T.M.A.N. is a simple set of rules a node has to comply with.
##########################
# B.A.T.M.A.N. ALGORITHM #
##########################
NOTE:
A firewall must not block B.A.T.M.A.N traffic. B.A.T.M.A.N sends its
packets on Port 1966 UDP. This port must be open for incoming and
outgoing
UDP traffic.
B.A.T.M.A.N detects neighbors and distant nodes by transmitting,
receiving
and repeating broadcasts according to the rules of the B.A.T.M.A.N.
algorithm. These broadcasts travel through the mesh-cloud until they are
lost or nobody has to rebroadcast them any more. Once a node receives a
broadcast message initiated from a distant node it is aware of the
existence
of the node.
ORIGINATOR MESSAGES
A broadcast (we will call it originator message from now on) contains
at least the originator address, a sequence number and a TTL. TTL or
Time-To-Live is a counter that is decremented by 1 every time before
the packet is rebroadcasted. If the TTL value reaches 0 the packet is
dropped. The TTL is used in IP packets to avoid packets endlessly
travelling around. This is a common mechanism. If the initial
TTL-Value is known, the TTL does also tell the receiver how often a
originator
message has been rebroadcasted.
Particular important for B.A.T.M.A.N. is the sequence number.
Originators
number their broadcasts so other nodes can decide whether they receive a
originator message the first time or repeatedly.
Originator messages are initiated from every node at a given interval
and
forwarded by all other nodes according to the rules of the algorithm.
If a
broadcast gets lost it is not resend.
Imagine we have a chain of mesh nodes (A,B,C,D):
A <--> B <--> C <--> D
Imagine further that every node can only see its direct neighbors.
Now node A
broadcasts a originator-message. Node B receives the message and
rebroadcasts it.
Thereby node C receives the information: Message from node A,
forwarded from
node B, sequence number 0, TTL 49
Node C forwards the message again. Thus node D receives the information:
message from node A, forwarded by node C, sequence number 0, TTL 48
Now node D knows:
There is a node A that is three hops away. In order to communicate
with node
A I have to send packets to node C. Node D does not need to know more
than
that.
The first example was of course very simple. So what happens if the
network
looks like this:
*------- B --------- C ------*
| |
A --+-------------- D -----------+-- F
| |
*-------------- E -----------*
What does B.A.T.M.A.N do now?
Node A broadcasts an originator-message with sequence number 0. B, C,
D and E
all forward this message.
Node F receives the originator-message sequence number 0 from node A
forwarded by node D first and memorizes that it has seen A over D.
Node F
ignores the originator-message with sequence number 0 from A, that it
receives from node C because it receives the same message again. The
message
forwarded by node E may get lost or come too late to be the first, too.
Using the best path between node A and F the packets travel more
reliable and/or quicker. B.A.T.M.A.N. nodes consider the best path to
a destination only as far as to the best next hop (or neighbor)
towards the destination. The best next hop is simply identified by
gathering statistics about how often and via which neighbor a certain
originator and sequence number has been received first.
For the above given scenario, all node F has to do is memorize where it
gets most originator messages from. Speed is decisive, because node F
is only memorizing who is forwarding the packet first. If node F wants
to communicate with node A it simply sends its packets to the node
with the best statistic.
If the statistic is equal amongst two or more neighbors the biggest
TTL is decisive. If also the TTL is equal the last received originator
packet is decisive.
TABLES MAINTAINED BY B.A.T.M.A.N.
1.) Table of symmetric single hop neighbors
Each node maintains a list of direct neighbors that contains all
nodes that
it has a direct bidirectional (symmetric) communication link to.
Bidirectional links are detected when a originator receives its
self-initiated originator messages getting directly repeated by its
neighbors.
2.) Table of Originators and Ranking
This table contains all nodes that are detected by receiving their
originator messages and the number of originator-sequence-number
packets received first via the particular neighbor. The best neighbor
for each originator is added to the kernel routing table of the
underlying operating system as router to the originator.
Example: Ranking table in Node Q
List of Originator packets received from
Originators Neighbor A Neighbor B Neighbor C Neighbor D
A 12 9 7 3
B 3 7 17 4
C 0 3 27 1
D 0 2 17 8
X 3 3 9 4
Y 9 1 12 2
According to the ranking table Q would route payload traffic to:
A via A
B via C
C via C
D via C
X via C
Y via C
ORIGINATOR MESSAGE RANKING POLICY
If a originator message with a unknown sequence number is received
first via
a bidirectional neighbor the packet count is increased for this
neighbor.
ORIGINATOR MESSAGE FORWARDING POLICY
(Sorry if this sounds like program code :)
Only originator packets that are received via the best ranking
neighbor are rebroadcasted. This must also be
done if the originator-sequence-number tuple has already been seen via
another (non-best) neighbor as long as the TTL does not differ to the
last originator-sequence-number tuple that has been seen from the best
neighbor first.
BIDIRECTIONAL NEIGHBOR DETECTION AND UNIDIRECTIONAL FLAG
Originator messages initiated from single hop neighbors are always
re-broadcasted. If we don't receive our own self-initiated originator
messages getting rebroadcasted by a neighbor we add a unidirectional
flag before rebroadcasting the originator message of this neighbor.
There is one exception where the unidirectional flag is used in
response to originator packets from bidirectional single-hop
neighbors:
If a bidirectional neighbor is not the best ranking neighbor to itself
(ah, you're getting confused now, eh?!) we rebroadcast the originator
packet containing the unidirectional flag.
Originator messages with unidirectional flag that were not initiated
by us
are always ignored. If we see a neighbor directly repeat our self-
initiated
originator messages there is obviously a bidirectional link between
us.
_______________________________________________
Altred mailing list
[email protected]
http://altred.net/mailman/listinfo/altred_altred.net
