Project

General

Profile

News

Open-Mesh: B.A.T.M.A.N. V status update

Added by Marek Lindner almost 14 years ago

In November 2009, when batman developers and wireless enthusiasts came together in Brussels (WBMv2) the first concepts ideas on how to improve the BATMAN IV routing algorithm emerged and after a couple of days of healthy discussion a first draft came to light. One year later, it is time to ask: What has been accomplished since then ? What is working right now ? Where are we going from here ?

This overview tries to present the state of development regarding the various B.A.T.M.A.N. V ideas/concepts. Some are already part of a release, others are in the design / implementation phase and a couple more are in the state of "vague idea". Feel free to join any topic and discuss with us to get your idea heard as well!

Mesh bonding mode

Status: implemented/stable

The bonding mode was one of the first B.A.T.M.A.N. V features to be implemented. It was tested during the WBMv3 in Italy and found its way into the 201010 release.

However, our tests have shown that bonding mode achieves maximum throughput over single hops only. For multi-hop paths interface alternating (see the next section) provides better performance results.

Incoming interface based routing / Interface alternating

Status: implemented/stable

Our original concept of how the incoming interface based routing (later called "interface alternating") should work turned out to be susceptible to routing loops, therefore the ideas had to be revised. While implementing the bonding mode it became apparent that these 2 features share the same base problem: Finding a neighbor which also has several interfaces that a node can communicate with simultaneously. As a result the same functionality was achieved by simply devising the interface alternating as a variation of bonding. Consequently, bonding mode and interface alternating were released together. Check our documentation section if you are interested to find out how to use these features and how they work internally.

Neighborhood Discovery Protocol

Status: implemented/experimental

B.A.T.M.A.N. IV uses a single message type (Originator Message - OGM) to solve two problems: Measuring the link quality to direct (single hop) neighbors and propagating the path qualities through the mesh. Albeit being simple, this approach leaves room for optimizations, especially in dense and/or mobile networks (see "overhead reduction" in the outlook). B.A.T.M.A.N. V introduces NDP, in addition to the OGMs. NDP takes care of the link quality measurements while OGMs take care of propagating the path qualities. This has the following advantages:
  • Modularization of the code
  • The delta changes between two OGMs can be increased with an NDP interval faster than the OGM interval, resulting in a higher influence of a single OGM.
  • Seperate optimization strategies can be used for NDP and OGMs individually then.
  • The more sparse the network is (number of single hop neighbors significantly smaller than the number of all nodes), the faster the NDP interval can be chosen relative to the OGM interval, resulting in major convergence speed improvements in sparse networks.
  • As NDP messages are never rebroadcasted it also helps to reduce the overhead in dense networks (many single hop neighbors).
  • (Mobile nodes can chose a faster OGM + NDP interval then. It directly improves their transmit path - which was not the case with the OGM LQ measurements due to the echo-quality dependency,
    and indirectly improves their receive path a little, due to the asymmetric penalty)

The first set of patches has been posted but the work is not complete yet. We hope to have it ready for the WBMv4.

Weighted LQ measurements

Status: design phase

Currently, B.A.T.M.A.N. IV is using a normal window for counting received packets and calculating the link quality from this information. However, these link quality measurements turned out to be the major convergence speed issue (with the default values, batman-adv needs 64 seconds to get from 0 to 100% link quality). The idea is, to give newer packets more importance in the counting and measuring process, either via a weighted window or an exponential weighted average.
  • Improves convergence speed due to more responsive link quality measurements in mobile scenarios.
  • NDP with faster intervals + weighted LQ measurements complement each other nicely for faster LQ measurements.

Dead node fast path switching/invalidating

Status: vague idea

When a node notices the breakdown of a neighbor (see routing scenarios to get an idea about the conditions), this node could send any data packet, which it would usually send over this neighbor to either its second best hop if available (which does not always have to be the case due to OGM forwarding policies). Or it could send the packet back to the next hop towards the source again. With the help of sequence numbers, any node on the 'backtracking' path (the backtracking path can be different from the usual path in case of asymmetric links) could notice that a path became invalid very quickly.
  • Quick response in case of node/link failures
  • Avoiding packet drops in case of rapid link failures

Host Network Announcements (HNA) and Roaming

Status: "(partly) implemented/experimental"

So far, every host's mac address in the mesh network (either of bridged-in hosts or the batman-adv node itself on bat0) are being announced proactively, periodically: Those mac addresses are just
attached to every OGM. A (semi-)reactive approach shall be introduced, as the HNA information usually do not change that frequently. It further has the following advantages:
  • Minimizing size of OGMs, reducing overhead
    -> Reduces overhead a lot in case of whole wired networks being bridged into the mesh network
  • Allowing many, many, many more hosts being bridged into the network without affecting the routing protocols performance in a negative way.
  • Fast HNA handover: Instead of having to wait for a new OGM and its HNA entries to notice the roaming of a host, a reactive technique shall minimize this time frame needed for the roaming.
  • Any layer 2 implementation (such as batman-adv) would be able to use this new mechanism to reduce the hand-over time to nearly zero as packets can be safely redirected from the old node in charge of the host to the new one (usually the new node in charge will notice the roaming earlier than the sender of data, as the new node is usually physically closer to the old node) until the mesh is in sync again.

This task is work-in-progress - a first draft describing full mechanism has been posted.
-A second draft describing full mechanism has been posted

Multicast optimizations

Status: implemented/experimental

B.A.T.M.A.N. IV has no explicit multicast support, therefore batman-adv does not treat multicast packets any different than broadcast packets: They just get flooded through the mesh. To make services like audio/video transfer feasible, the retransmissions should be reduced. 2 different approaches have been proposed around the same time:
  • The first scheme offers the possibility to 'flood' multicast packets on the according unicast paths only for nodes which are both sender and receiver of the same group.
  • The second multicast optimization approach is non-group-specific and works for both multicast and broadcast packets.

Both approaches share similar concepts but are not identical. These two groups exchanged many ideas and probably merge the best of both approaches in the weeks to come.

Thanks again for the tremendous input and sharing of experiences, ideas and code! Seeing all these ideas coming together is what makes this project worthwhile!

Happy routing,

The B.A.T.M.A.N. team

Open-Mesh: Batman-adv 2010.2.0 released

Added by Marek Lindner about 14 years ago

The B.A.T.M.A.N. team proudly presents the last batman-adv release in the year 2010, carrying the version number 2010.2.0. This release contains a mix of new features, Linux kernel compliance and bug fixes. As the kernel module always depends on the Linux kernel it was compiled against, it does not make sense to provide binaries on our website. As usual, you will find the signed tarballs in our download section:

https://downloads.open-mesh.org/batman/releases/batman-adv-2010.2.0/

as well as prepackaged binaries in your distribution.

Important changes

The batman-adv module now supports multiple mesh clouds simultaneously which made changes to the 'bat0' interface behavior necessary: Mesh interfaces (such as bat0) are created only after 'real' interfaces (e.g. wlan0) have been assigned. Mesh interfaces that have no real interfaces assigned are removed from the system. Furthermore the mesh interface can be freely named such as bat5, mesh0, etc, therefore batman-adv might be active even though bat0 does not exist. More details can be found below as well as in our documentation.

Thanks

Thanks to all people sending in patches:

and to all those that supported us with good advice or rigorous testing:

batman-adv

The work that nearly a year ago began has finally come to an end: Multiple mesh cloud support has been completed. This allows one host to participate in multiple meshes at the same time via different interfaces. This often requested feature is particularly useful to segment large batman-adv installations, thereby reducing overhead. Each mesh cloud can be individually configured, deals with its traffic flow independently and possesses its own batX interface. Also added was a layer 2 fragmentation for unicast data flowing through the mesh which will allow to run batman-adv over interfaces / connections that don't allow to increase the MTU beyond the standard Ethernet packet size of 1500 bytes. This initial fragmentation only supports splitting the large packets at "the beginning of mesh" whereas an extension which allows fragmenting "on the fly" anywhere in the mesh network will be included in the following release.

As usual, many improvements happened under the hood: The module uses the kernel supplied functions for network buffer manipulations instead of re-implementing them and takes advantage of the optimized kernel functionality for OGM counting. The RCU protected lists have been revamped and enhanced with referenced based counting which squashes quite some race conditions. The HNA handling needed some fixes too when it was stress tested with a very large local network. Many minor bugs such as false warnings, reduced memory usage and coding style issues were addressed.

batctl

To support the "multiple mesh clouds" feature batctl received a new (optional) parameter '-m' to specify the mesh cloud interface in order to query the mesh cloud of interest. If '-m' is not specified batctl will assume 'bat0' as mesh cloud interface which maintains backward compatibility and suits most users. The newly added fragmentation on/off switch also was added as well as batctl tcpdump support for fragmented packets. In addition, the batctl tcpdump can deal with multiple header encapsulation (e.g. HTTP in VLAN in BAT UNICAST in VLAN) and the batctl ping utilities' '-i' option is not silently ignored any longer. Various cleanups took place and a crash fixed if the HOME environment variable is not set.

Happy routing,

The B.A.T.M.A.N. team

Open-Mesh: Batman-adv 2010.1.0 released

Added by Marek Lindner about 14 years ago

New versions of the batman-adv kernel module and batctl are released today with the version number 2010.1.0. The B.A.T.M.A.N. team's main focus was on new features, Linux kernel compliance and a bunch of bug fixes. As the kernel module always depends on the Linux kernel it was compiled against, it does not make sense to provide binaries on our website. As usual, you will find the signed tarballs in our download section:

https://downloads.open-mesh.org/batman/releases/batman-adv-2010.1.0/

as well as prepackaged binaries in your distribution.

Important changes

As part of the ongoing kernel interface restructuring all remaining tables and debug output was migrated from the proc filesystem to the debug filesystem. Also, some tables which went into sysfs followed this example as well as the layer 2 icmp socket which resided in /dev. All programs / scripts accessing these files directly need to be adjusted. Scripts using batctl are not affected by this transition as the batctl command line parameters are unchanged. More details can be found below as well as in our documentation.

Thanks

Thanks to all people sending in patches:

and to all those that supported us with good advice or rigorous testing:

batman-adv

The first B.A.T.M.A.N. V features left the experimental stage and went into this release: interface alternating (formerly known as incoming interface based routing) & bonding mode. These are optimizations for scenarios in which mesh nodes possess several WiFi cards to run the mesh on. In alternating mode batman-adv will switch the WiFi interface to forward the traffic with each hop, thereby avoiding store & forward (which would half the bandwidth with each forwarding node). Bonding mode will use all available interfaces at the same time to forward the traffic. Both modes do not require the whole network to have the same hardware configuration - the available interfaces are automatically detected and used if possible. Per default batman-adv operates in the alternating mode, bonding mode can be activated.

To achieve Linux kernel compliance all tables and debug information have been concentrated in the debug filesystem (all configuration options remain in sysfs). Make sure your kernel has the debug filesystem compiled in if you want to access those information. The user space API is now considered clean and won't require significant changes in the future. The originator table outputs the "last seen" field to allow observing originator outages in real time. The batman-adv debug log returned with the debugfs changes, after it had been removed in previous releases. The batman icmp socket left the /dev directory to join the other debug facilities in debugfs (before it was not possible to create a socket for each configured mesh). This release also contains numerous bug fixes regarding stability, broadcast flood protection through 32Bit sequence numbers, supporting newer kernel versions, multiple interface bugs, rounding issues and more.

batctl

Batctl has been adapted to retrieve the tables and other information from the debug filesystem. To provide a smooth user experience batctl automatically mounts the debug filesystem whenever necessary. As the debug log output moved from the standard kernel logging to the batman-adv log file, batctl re-introduces the convenience features to retrieve the logs and replace mac addresses with names. Batctl also followed the icmp socket move and is prepared for the multiple mesh support. The ping utility received the "record route" ability which allows to monitor route changes. The originator table viewer gained some additional options to filter for "fresh" entries (using the "last seen" field) and allows to specify a refresh interval to continuously print the table.

Happy routing,

The B.A.T.M.A.N. team

Open-Mesh: Batman-adv 2010.0.0 released

Added by Marek Lindner over 14 years ago

The B.A.T.M.A.N. team today announces the release of the latest batman-adv milestone which brings API changes, new features as well as bugfixes and linux coding style compliance.
As the kernel module always depends on the Linux kernel it was compiled against, it does not make sense to provide binaries on our website. As
usual, you will find the signed tarballs in our download section:

https://downloads.open-mesh.org/batman/releases/batman-adv-2010.0.0/

as well as prepackaged binaries in your distribution.

Important changes

The batman-adv version numbering has been adapted to better reflect our release / feature cycle (the detailed explanation can be found here: https://lists.open-mesh.org/mailman3/hyperkitty/list/b.a.t.m.a.n@lists.open-mesh.org/message/Y3RU5ZGTMOUYPMVDN7IIS4GHYA5T7HXO/). The first part of the number represents the year of the release, the second part is the release number per year and the last digit is the bugfix release counter. Because this release is the first of its kind in 2010 we chose "2010.0.0" as its name.

Furthermore, all batman-adv options residing in the proc filesystem have been migrated to the sys filesystem, therefore all scripts accessing these options directly need to be adjusted. Scripts using batctl are (almost) not affected by this transition as the batctl commandline parameters are unchanged. More details can be found below as well as in our documentation.

Thanks

Thanks to all people sending in patches:

and to all those that supported us with good advice or rigorous testing:

batman-adv

This release contains a complete rework of the configuration interface, formerly to be found in the proc filesystem. The options have been split into the mesh wide settings and per interface settings. It is now possible to activate/deactivate individual interfaces via their respective folder within sysfs which fullfills an often wanted feature request. In addition, the kernel module will automatically detect & avoid non-compatible interfaces such as non-ethernet or mesh interfaces. During this transition many smaller & bigger annoyances have been cleaned up and prepared the way for features yet to come. Details regarding the new settings interface can be found in our documentation.

Explicit netfilter support has been added that allows to filter batman's layer2 traffic and protocol messages with e.g. ebtables, the broadcast traffic code has been restructered to deal with broadcast storms and the internal sequence number handling has been revamped fixing several bugs. Linux coding style compliance was a big topic too in order to ensure the code is "checkpatch clean".

batctl

Most of the work went into the sysfs changes to make sure the new API is properly handled. When using batctl you won't notice the difference except for the interface handling. Since you can activate and deactivate interfaces one by one, the parameter list had to be adjusted. Also, batctl parses your input before configuring the kernel module and warns if the input is not correct which saves you from having to consult the kernel logs. Some bugfixes in ping and traceroute complete this release.

Happy routing,

The B.A.T.M.A.N. team

Open-Mesh: WirelessBattleMesh in Bracciano

Added by Marek Lindner over 14 years ago

After the 2 successful WirelessBattleMesh gatherings in 2009, the interest in CommunityWireless events with focus on meshing and idea exchange was growing and resulted in the 3rd WirelessBattleMesh. Due to lack of time and space to deploy a decent test network during previous events, we decided to get together at the camping site in Bracciano / Italy. The owner was a big fan of the FOSS movement that allowed us to deploy the nodes wherever we wanted and helped us in many occasions. The persons from Ninux made sure we had all the things we needed (for example a broadband symmetric wireless internet uplink across the lake) and managed to make this event a great success. Thank you!

We managed to flash, configure and deploy roughly 40 nodes (in a rather random manner) across the camping site. All nodes ran 5! routing protocols simultaneously, thus creating quite a "wifi warzone". The good news is: All protocols ran without major problems - we had no crashes, memory problems, etc. Some people were measuring protocol traffic, cpu overhead and so on which were published towards the end of the event. This is a major step forward, since the previous events never managed to get a big test bed running to perform these kind of tests. Unfortunately, this test bed was rather chaotic and delivered unreproducible test results. If the same test was performed twice with a 5 minute pause in between the results were totally different. We hope that future events will focus on a more predictable environment.

Map of the camping site with node positions (photo by hispanic)

For us batman developers it definitely was a worthwhile event. Apart from meeting a lot of interesting people from other projects we also met some of the Italians who wrote papers about the B.A.T.M.A.N. protocol. As we noticed recently our protocol became quite popular in Italy (go to google scholar and see for yourself), so we used the chance to see some of the faces and chat about future improvements & collaboration. Some cool things might show up over the next couple of months. Furthermore, we had the time to discuss our release cycle. The result of this discussion can be read here.

Next to the "regular" testing we organized some specialized batman tests on our multi-radio wifi hardware. Since a while a new feature called "alternating/bonding" is in preparation which needed some more testing before it could be finalized. The idea of this feature sounds simple: Using multiple (wifi) interfaces to avoid the bandwidth killing store & forward mechanism which one usually encounters when forwarding traffic over multiple hops on the same channel. First, batman would have to detect that the other end has several interfaces connected to the mesh. Then this could be used to send data to one interface and forward it via another one (which we call alternating) or use both interfaces to send & forward at the same time (which we call bonding). If you are interested how the protocol detects it, please see this document.

This graph shows a 3 node setup each with 2 802.11abg wifi interfaces connected to the mesh network (1x 2.4GHz and 1x 5.8GHz). As you can see the alternating mode is able to maintain the performance. The old default behavior sometimes manages to maintain a similar level of performance but is rather unstable.

As the alternating mode proved to be so effective, it will be activated by default (if multiple wifi interfaces are available). This feature will be part of the September release but if you want to test it now, check out the trunk and let us know about your results!

We are looking forward to the Wireless Battle Mesh v4,

the B.A.T.M.A.N. team

Open-Mesh: Scheduled server downtime

Added by Marek Lindner over 14 years ago

Our service provider (Hetzner) will move this server to a new location. It will be necessary to shutdown all offered services for a couple of hours until the server hardware has moved to its new home. Since the entire server infrastructure is going to move no URLs / DNS records / etc will need to change. The downtime is scheduled for:

May 11th 10.30pm till May 12th 7.30am (CET)

We hope this will be a smooth ride but as you know, things might get delayed because of unforeseen events. Don't grow impatient if it takes a couple of hours longer. Keep in mind that this will affect the repos (svn & git), the mailing lists (batman & batman-commit) and its archives, the wiki as well as downloads. Please, make all necessary preparations to get over this period without hassle.

There will be another reminder on the batman mailing list once the event comes closer. If you have questions or concerns feel free to contact us.

[Update: 12/05/2010]
Our server successfully came up after being moved to the new location and all services came back online.
[/Update]

The B.A.T.M.A.N. team

Open-Mesh: Batman-adv 0.2.1 released

Added by Marek Lindner over 14 years ago

The B.A.T.M.A.N. team hereby announces the release of the first bugfix milestone for the batman-adv 0.2 branch which focuses on stability but also brings improvements and small changes.
As the kernel module always depends on the Linux kernel it was compiled against, it does not make sense to provide binaries on our website. As usual, you will find the signed tarballs in our download section:

https://downloads.open-mesh.org/batman/releases/batman-adv-0.2.1/

as well as prepackaged binaries in your distribution.

Important changes

The batman-adv logging facilities underwent structural changes to fully integrate into the standard Linux logging mechanisms. Please study the README to get further details on how to access the debug logs. In addition, the "vis" /proc file has been split up into two files: vis_server and vis_data. The vis_server controls the vis server status whereas the vis_data file exports the visualization "raw"
data which can be easily parsed by user space tools. Again, details can be found in our documentation.

Thanks

Special thanks go to:

  • Andrew Lunn for going through the entire code base to refactor the code and adjust the coding style to match standard Linux coding style guidelines
  • Linus Luessing for his restless testing in so many scenarios and sending a lot of patches and suggestions.
Thanks to all people sending in patches:

and to all those that supported us with good advice or rigorous testing:

batman-adv

Albeit being a bugfix release we dared to include some bigger changes because we felt their gain outweighs the risk. For instance, we replaced the packet handling thread which was responsible for routing the payload data through the mesh by an advanced skbuff handling technique. Now, packets are received directly by registering the Ethernet type and handling skbs instead of
self-allocated buffers which boosts the performance considerably and reduces latency.

On the other hand batman-adv is moving towards full Linux kernel integration which requires some significant changes under the hood as well as on the surface. Batman's own logging facility has been removed (the standard Linux logging is used instead). The vis output comes now in a neutral format, easily parsable by user space applications. Since the module entered the official Linux realm several
people threw static code analyzers (e.g. Coccinelle, sparse) onto the code to find bugs. Some (possible) memory leaks, optimizations and a false alarms have been found and dealt with. Many more bugs, race conditions and crashes have been fixed. Now, it also is possible to change the MAC address on bat0.

batctl

Since the vis output format has changed, batctl received a parser for the neutral format to convert the output into either dot draw or JSON. If you wish to write your own parser, please see our documentation and/or the batctl code as an example. The batman-adv debug log will show up in the standard kernel logs of your system, hence to access the logs "batctl log" is not needed any longer. Please use the tools provided by your distribution (dmesg/logread/syslog/etc). However, "batctl log" remains available and can be used to filter existing logfiles for batman-adv output
and to replace the mac addresses by bat-host names.

Happy routing,

The B.A.T.M.A.N. team

Open-Mesh: B.A.T.M.A.N. at the WirelessBattleMeshv3

Added by Marek Lindner almost 15 years ago

It has just been made official - we will have a WirelessBattleMeshv3 in Italy (mainly organized by the persons from Ninux/Italy). After participating in the first WirelessBattleMesh in Paris as well as the second WBM in Brussels we definitely won't miss the next one. Due to the success of the past events, Wireless Communities across Europe have shown interest in a larger gathering in Italy (50-100 people are expected). To coordinate the various efforts an official "Wireless Battle of the Mesh" website has been created: http://battlemesh.org/

Most of the B.A.T.M.A.N. developers already confirmed that they are going to be there. Despite what the title might imply it is a very peaceful event which has a lot of room for talks & discussions, coding & debugging or just having fun. So, if you want to meet / chat / hack the code with us - come to Italy! Details about the event's registration / locations / costs can be found in the announcement text below.

Announcing the Wireless Battle of the Mesh v3

(02-06 June 2010, Bracciano, Italy)

The next 'Wireless Battle of the Mesh' will take place from Wed 2nd till Sun 6th of June in Bracciano (near Rome), Italy. The event aims to bring together people from across Europe to test the performance of different routing protocols for ad-hoc networks, like Babel, B.A.T.M.A.N., and OLSR. This third WBM will be improving the testbed conditions for mesh protocols with standardized testing procedures that will be reported after the event for the wireless communities.

On the development side, a flashing tool will be presented to simplify the deployment of such wireless networks based on OpenWrt stable release and packages for each protocol.

If you are a mesh networking enthusiast, community networking activist, or have an interest in mesh networks you have to check this out!

Informations about the event are gathered at: http://battlemesh.org/

Location

The event will take place in the camping Porticciolo in Bracciano, Italy. along the border of the lake of Bracciano, just North-West of Rome.

Registration

Registrations will be available at different hackerspaces (Fusolab, HSBXL, /tmp/lab, metalab, CCC, ...) and on the official website for the event at http://battlemesh.org

Fees

Every participant needs to donate 50 EUR (this should cover the costs for the camping, and the infrastructure). To finance this event, we ask you to pay when subscribing (paypal, bank transfer or cash).

Contact

Web: http://battlemesh.org/BattleMeshV3

Email:

IRC: irc.freenode.net #battlemesh

Open-Mesh: Retrospect - B.A.T.M.A.N. in 2009

Added by Marek Lindner almost 15 years ago

Now that the end of the year is close, it is time to lean back for a moment and review the events & achievements happening throughout the past year.

We published 2 bugfix releases of our batmand [layer 3] branch (batmand 0.3.1 and "batmand 0.3.2::/news/5) as well as a major milestone of our batman-adv [layer 2] kernel module (batman-adv 0.2). Deprecated branches (batman-advanced userland version and vis-advanced) were removed from the repository because their functionality was replaced by the kernel module. The newly created tool 'batctl' (former battools) matured enough to be added to the standard release.

The trac based webinterface celebrated its first birthday a few days ago. Especially in the first months of 2009 we spent quite some time to ease the transition and improve the setup to serve better the growing needs of the project. During the late summer git.open-mesh.org was born which plays a crucial role in our efforts to merge the batman-adv kernel code into the linux kernel. The git repository got up to speed in autumn and the first set of patches was accepted during the 2.6.33 merge window.

In April we took part in the Paris WirelessBattleMesh meeting with French hackers and other routing protocol developers to swap ideas and to get up to date with each others' latest improvements The follow-up meeting in Brussels was a very good occasion to prepend a BATMAN developer meeting in which we squashed bugs discussed the current development strategy upcoming releases and BATMAN V. At the 26C3 we are going to come together again - drop us a mail if you want to meet us there.

In 2010 B.A.T.M.A.N. will continue to evolve. Expect more linux kernel integration, another batman-adv major release as well as B.A.T.M.A.N. V.

We wish you all a successful 2010,

the B.A.T.M.A.N. team

Open-Mesh: B.A.T.M.A.N. V outlook

Added by Marek Lindner almost 15 years ago

Now that B.A.T.M.A.N. IV is out there and works quite well, it is time to merge our gained experience and work towards B.A.T.M.A.N. V. This page contains the first collection of ideas of what the improvements could look like. To keep the list size in a digestable format we had to draw a line somewhere. Therefore it only contains items which come with a plausible concept or (even better) a proof-of-concept patch. Nevertheless, it is not final yet. Over time some ideas might proove to not work or new ideas might arise. Feel free to contact us] if you want to [[Contribute.

Convergence speed:

In order to increase the convegence speed B.A.T.M.A.N. IV forwards all valid OGMs coming by and thus increasing the probability of more packets coming through. To avoid routing problems it fixes the TQ and TLL values of packets not coming from the best neighbor. It turned out this behaviour of forward and replace may cause transient routing loops under certain conditions and the convergence speed leaves room for improvements.
B.A.T.M.A.N. V will forward packets from the best neighbor only without replacing any values. Furthermore, in case of packet loss it will detect when an OGM packet from its best neighbor did not arrive and will then broadcast the missing packet by itself (using the last known sequence number & TQ value). That way, B.A.T.M.A.N. increases the probability of transmitting OGMs over a longer chain of nodes. B.A.T.M.A.N. V could send the originator interval along with the OGM to let other nodes determine whether an OGM was missed or not.

Overhead reduction:

The traffic B.A.T.M.A.N. IV generates to discover the best path through the network is quite low compared to other protocols, but especially when B.A.T.M.A.N. has many single hop neighbors which rebroadcast each others OGMs we see room for improvements. B.A.T.M.A.N. V will split the well-known originator message into two different message types. The OGM will remain but only be used to flood the TQ throughout the network. The new message type (a name needs to be found) will contain the link qualities of the single hop neighbors only. This message won't be rebroadcasted and just reaches the local neighborhood. These local message can be sent much more often than the global TQ messages and thus reduce the traffic [nearly just create a linear growth of traffic with more nodes in the local neighborhood instead of a squared amount].

Starving mode:

Fast moving nodes always have the problem of adjusting their routing information in time. They can choose to send more routing information, so that their environment can adjust to them but stationary nodes won't do the same and increase the mobile node's adaption time greatly. However, when a B.A.T.M.A.N. V node detects that his local environment changed quickly he will enter the starvation mode. In this mode the node will actively try to confirm a working route as fast as possible by sending a "batman ping" to its new neighbors. Each B.A.T.M.A.N. neighbor will try to forward the message to its destination, once arrived there it will travel back. If the mobile node receives the reply it can change its route towards the new neighbor without waiting for OGMs as the route has been verified.

Mesh bonding mode:

In certain setups it might be desirable to use 2 or more dedicated wifi links (towards your direct neighbor) at the same time to increase the bandwidth. B.A.T.M.A.N. V will provide the mechanisms to automatically detect neighbors it could bond with and establishes the bonded connection.

Incoming interface based routing:

B.A.T.M.A.N. IV will find the best route through the network which does not fully utilize the capabilities of "multi-link nodes". If a single node is able to maintain several connections via its various interfaces to its neighbors the protocol should consider switching the interfaces in order to reduce latency and increase bandwidth. To achieve this B.A.T.M.A.N. V will create a routing table on a per interface basis. Whenever a payload packet arrives at the node it will lookup the path using the routing table for that interface. Imagine a network full of nodes having 2 wifi interfaces - B.A.T.M.A.N. V would try to make use of all existing interfaces to avoid interference and maximize throughput.

There are numerous other ideas such as faster HNA handover, optimized multicast support, etc which need to mature before they can be added to the list.

(101-110/118)

Also available in: Atom