[B.A.T.M.A.N.] batman-adv 0.2 released

[B.A.T.M.A.N.] batman-adv 0.2 released

[Marek Lindner]

The B.A.T.M.A.N. team is pleased to announce the availability of the second 
batman-adv release which brings major improvements, new features, changes
along the way and a series of bugfixes.
As the kernel module always depends on the kernel it was compiled against it 
does not make sense to provide binaries. However, you will find binaries for 
batctl at the usual location:
http://downloads.open-mesh.net/batman/stable/binaries/
as well as signed source tarballs for the module and batctl:
http://downloads.open-mesh.net/batman/stable/sources/


Important changes
-----------------

With this release we believe that the kernel module is fully capable to 
replace a routing daemon feature wise as well stability wise. Therefore the 
batman-adv user space daemon (which was marked deprecated since the last 
release) as well as the vis-adv daemon have been removed from our repositories 
as they are no longer supported. We urge all remaining users to consider a 
migration towards the the kernel module. 


Thanks
------

Special thanks go to:
* Sven Eckelmann who continuously provides us with patches and advice
   whenever problems show up
* Andrew Lunn & Yang Su for their analysis of the routing protocol which 
   helped us to identify temporary routing loops in the code
* Linus Luessing & Freifunk Luebeck for the rigorous testing & bug 
   reporting of all (im)possible race conditions they encountered
* Jacob Marble who tried to find a new home for our extravagant mailing list
   requirements and gave birth to the batctl idea

Thanks to all people sending in patches (in no particular order): 
 - Andrea Ghittino <a.mailevent@gmail.com>
 - Sven Eckelmann <sven.eckelmann@gmx.de>
 - Andrew Lunn <andrew.lunn@ascom.ch>
 - Yang Su <Yang.Su@ascom.ch>
 - Linus Luessing <linus.luessing@web.de>
 - Antoine van Gelder <antoine@7degrees.co.za> (JSON patch was ported)


batman-adv
----------

The module has undergone some major changes to better fit into the event based
nature of the kernel. We removed a number of timers (e.g the new interface 
detection) which also greatly reduces the risk of race conditions. Also new is 
the packet queue that allowed implementing the aggregation (already known from 
the user space implementation) as well as transmission retry (ARQ) for payload 
broadcasts because we noticed most broadcasts vanish in transit. This feature 
merits some extra attention as it is the first in which the routing module 
influences the payload traffic directly to enhance the mesh experience. 
We also spent quite some energy to fix bugs in the routing algorithm that 
triggered temporary routing loops, squashed a TTL code bug and removed the 
ghost entries from the originator table. The whole code received linux coding 
style adjustments, refactoring & cleanups. Furthermore all kernel version 
compatibility code has been unified in compat.h. The internal vis server 
received another output format (JSON) plus secondary interface export 
functionality in the dot draw format. Numerous small bugs were fixed such as 
using the random ethernet generator from the kernel for better randomness, 
exporting the version via /sys/module/batman_adv/version, fixing alignment 
issues, race conditions and deadlocks.


batctl
------

Although this is the first release of batctl it carries the same release 
version as the kernel module (for the sake of simplicity). It is based on the 
work of Andreas Langer who created the battools which were never officially 
released. Since then it has been extended to the point that it serves as 
configuration utility, monitoring and debugging application. It allows to 
modify the module parameters, reading the logfiles & tables, decapsulate 
embedded packets on the fly, traceroute to & ping mac addresses, generate 
sequence number graphs and more. Check the README to get an impression: 
http://www.open-mesh.net/browser/trunk/batctl/README?rev=1466


road ahead
----------

The batman-adv development lying ahead can be separated into 2 big chunks: The 
linux kernel integration already started and we began working on batman's move 
into the linux land (more information can be found on www.open-mesh.net) - 
expect follow up news in the coming weeks. In the meantime a large number of 
ideas are flying around how to further improve the B.A.T.M.A.N. algorithm to 
increase its convergence speed, reduce traffic overhead and much more. A first 
idea collection will be published soon.

Happy routing,
The B.A.T.M.A.N. team

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Donald Gordon]

[-- Attachment #1: Type: text/plain, Size: 872 bytes --]

That's really exciting.

I have a feature request -- has there been any consideration to getting
batman-adv to fragment ethernet frames, so as to get a 1500 byte MTU
batman-adv network running on top of a 1500 byte MTU ethernet network?  This
would be a useful feature for people trying to reuse whatever random
ethernet networks happen to be nearby to extend their mesh, while not
requiring the mesh users to all configure a lower MTU.  And the support
you've announced for combining small ethernet frames into larger batman-adv
frames means that the overhead might not be too bad.

donald

On Mon, Nov 9, 2009 at 2:44 AM, Marek Lindner <lindner_marek@yahoo.de>wrote:

>
> The B.A.T.M.A.N. team is pleased to announce the availability of the second
> batman-adv release which brings major improvements, new features, changes
> along the way and a series of bugfixes.
>
>

[-- Attachment #2: Type: text/html, Size: 1170 bytes --]

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Marek Lindner]

On Monday 09 November 2009 16:43:33 Donald Gordon wrote:
> I have a feature request -- has there been any consideration to getting
> batman-adv to fragment ethernet frames, so as to get a 1500 byte MTU
> batman-adv network running on top of a 1500 byte MTU ethernet network? 
>  This would be a useful feature for people trying to reuse whatever random
>  ethernet networks happen to be nearby to extend their mesh, while not
>  requiring the mesh users to all configure a lower MTU.  And the support
>  you've announced for combining small ethernet frames into larger
>  batman-adv frames means that the overhead might not be too bad.

You will need quite some code to implement a good fragmentation but even if 
you find the time to do so it comes with a severe performance penalty. 
Imagine a payload packet comes in (1500 bytes), batman-adv adds its stuff (24 
bytes) and then we make 2 packets out of it: one 1500 Bytes and one 24 Bytes 
(probably a bit more for fragmentation handling). Now you have 2 packets 
instead of one! Wired networks tend to avoid it (which is why applications 
tried to determine the PMTU) - wireless networks should avoid it even more 
because if you loose one of the packets both need to be retransmitted. 

You can handle this issue elegantly by increasing the MTU of the mesh 
interfaces. Most wifi cards / drivers already accept MTUs greater than 1500 
bytes and most ethernet cards do as well.

Nevertheless, it might be neat to have fragmentation as a fallback mechanism. 
Be sure we review and submit your code as soon as it is available.  :)

Regards,
Marek

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 1214 bytes --]

Donald Gordon wrote:
> That's really exciting.
> 
> I have a feature request -- has there been any consideration to getting
> batman-adv to fragment ethernet frames, so as to get a 1500 byte MTU
> batman-adv network running on top of a 1500 byte MTU ethernet network? 
This would mean that we have to add extra information to find which parts 
belong together. It is also needed that we buffer everything and put it 
together if needed - so out of order receiving of ethernet frame must be 
possible. I am not sure if we real want that as other protocols running on top 
of it should do that work.

>  This would be a useful feature for people trying to reuse whatever random
>  ethernet networks happen to be nearby to extend their mesh, while not
>  requiring the mesh users to all configure a lower MTU.
Most modern switches and routers should support 800.3as which makes it 
possible to use a larger MTU on ethernet to connect two meshes. And if a 
router receives a to large IP packet is should send an ICMP "fragmentation 
needed and DF set" when it cannot be fragmented by the router.

Is there any tunneling protocol which support ethernet frame fragmentation?

Best regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Marek Lindner]

On Monday 09 November 2009 23:08:27 Sven Eckelmann wrote: 
> And if a router receives a to large IP packet is should send an ICMP
> "fragmentation needed and DF set" when it cannot be fragmented by the
> router.

The problem is we keep the payload on layer 2, so that it never will bubble up 
to layer 3, hence never emit fragmentation needed (we even might not have an 
IP address). All you see is a hanging connection.


> Is there any tunneling protocol which support ethernet frame fragmentation?

Good question.

Regards,
Marek

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Sven Eckelmann]

[-- Attachment #1: Type: Text/Plain, Size: 862 bytes --]

Marek Lindner wrote:
> On Monday 09 November 2009 23:08:27 Sven Eckelmann wrote:
> > And if a router receives a to large IP packet is should send an ICMP
> > "fragmentation needed and DF set" when it cannot be fragmented by the
> > router.
> 
> The problem is we keep the payload on layer 2, so that it never will bubble
>  up to layer 3, hence never emit fragmentation needed (we even might not
>  have an IP address). All you see is a hanging connection.
Ah, I think I misunderstood him. My idea was that he has meshA and a meshB and 
between them is a normal router which connects both. In this case it would 
work - but yes, he probably meant one mesh and only one connection is ethernet 
cable (or many of them) instead of a wireless link. In this case there is 
nothing like a router which looks at the layer 3 stuff.

Best regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Donald Gordon]

[-- Attachment #1: Type: text/plain, Size: 1479 bytes --]

One implementation possibility I was thinking of was adding yet another
ethernet device that sat like a proxy in front of bat0.  It would fragment
transmitted frames larger than the bat0 MTU (changing the ethernet frame
type), and reassemble recieved frames.  This would push the load of frame
fragmentation to the edge of the network, and shouldn't add too much
overhead.  Does that sound like a reasonable way forward?  And if so, does
anyone have any pointers on how to develop fake ethernet drivers?

With the frame-combining that batman-adv now does, those extra frame
fragments would be good candidates for combining to cut down on wifi
overhead.

With resepect to the motivation for allowing 1500 MTU frames over a 1500 MTU
intermediate network, I guess my grand vision is to borrow bits of network
that are already there to get the mesh extended further.  Hopping through a
citywide hotspot network (conveniently all bridged together), borrowing
existing ethernet segments in buildings, that sort of thing.  Which means
I'm also keen on some sort of integrated way to tunnel batman packets over
IP without the overhead of passing them to userspace through a tun/tap but I
guess that'll have to wait :-)

donald

On Tue, Nov 10, 2009 at 3:39 AM, Marek Lindner <lindner_marek@yahoo.de>wrote:

> Nevertheless, it might be neat to have fragmentation as a fallback
> mechanism.
> Be sure we review and submit your code as soon as it is available.  :)
>
> Regards,
> Marek
>
>

[-- Attachment #2: Type: text/html, Size: 1837 bytes --]

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Andrew Lunn]

Thinking a little out of the box here...

So far, everybody has talked about fragmenting so that you can
transfer 1500byte frames over interfaces with an MTU of 1476.

24 bytes are the problem. We could try to compress the packet as a
first stage to solving the problem. If we cannot sufficiently compress
it, then segment it.

There are a few well know compression schemes that could be used, some
generic, so more tailored to network traffic.

V. Jacobson TCP/IP header compression, often used on PPP links:
http://tools.ietf.org/html/rfc1144

There is already a kernel implementation of this which might be
reusable. It may also be possible to extend the scheme to compress
part of the original ethernet header.

There is a more generic header compression scheme:
http://tools.ietf.org/html/rfc3095

The advantage of this is that it can compress more than just TCP/IP
and is decoupled from PPP.

Then there is the more traditional compression schemes, eg LZO etc.
There are a few academic papers available looking at this subject.
The disadvantage of trying to compress the packet data is often it is
already compressed, eg images. Or it is https traffic which makes it
harder to compress.

I would tend more towards header compression. It requires a lot less
CPU usage then data compression and should provide the 24 bytes of
compression we need most of the time. However, as i said at the
beginning, we need to be able to fall back to segmentation when it
does not work, or has to send full header information in order to
establish the compression tables.

	  Andrew

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Marek Lindner]

On Wednesday 11 November 2009 11:17:22 Donald Gordon wrote:
> One implementation possibility I was thinking of was adding yet another
> ethernet device that sat like a proxy in front of bat0.  It would fragment
> transmitted frames larger than the bat0 MTU (changing the ethernet frame
> type), and reassemble recieved frames.  This would push the load of frame
> fragmentation to the edge of the network, and shouldn't add too much
> overhead.  Does that sound like a reasonable way forward?  And if so, does
> anyone have any pointers on how to develop fake ethernet drivers?

If you look for simple interfaces then just dive into the bat0 code - it is 
exactly that. But at that point I doubt you would need yet another interface 
to achieve your goal. If you wanted your fragmentation happening at each 
beginning and ending of the mesh you easily could do that inside of the 
batman-adv code. The data will go in and out via bat0 ...

Besides, I'm not sure your approach will make everyone happy as you might have 
different MTUs throughout the network (e.g. see you batman over IP suggestion). 
The endpoints might have a higher MTU than a segment inbetween. In that case 
the fragmentation could not help.


>  Which means I'm also keen on some sort of integrated way to tunnel batman
>  packets over IP without the overhead of passing them to userspace through
>  a tun/tap but I guess that'll have to wait :-)

Well, if static tunneling solves the problem you easily could use GRE or 
similar techniques.

Regards,
Marek

Re: [B.A.T.M.A.N.] batman-adv 0.2 released

[Juliusz Chroboczek]

>> I have a feature request -- has there been any consideration to getting
>> batman-adv to fragment ethernet frames, so as to get a 1500 byte MTU
>> batman-adv network running on top of a 1500 byte MTU ethernet network? 

> it comes with a severe performance penalty.

Fragmentation over multiple hops is harmful, as explained in detail in

   Kent and Mogul, Fragmentation Considered Harmful, 1995.

On the other hand, in the presence of hop-to-hop ARQ, hop-to-hop
fragmentation/reassembly is a good thing, especially in wireless
networks.  The difference with the above is that when doing hop-to-hop
fragmentation and ARQ, you only need to resend the lost fragments, not
the whole packet.  And since loss probability is proportional to the
fragment size, this is a net gain.

Of course, this has to be balanced with the overhead of sending multiple
frames, which can be pretty high if you contend for the link at every frame.

In short, there's good reason why 802.11 includes link-layer fragmentation.

> Imagine a payload packet comes in (1500 bytes), batman-adv adds its stuff (24 
> bytes) and then we make 2 packets out of it: one 1500 Bytes and one 24 Bytes

Obviously, it's better to send two 750-byte packets.

                                        Juliusz