[B.A.T.M.A.N.] Small feature request

[B.A.T.M.A.N.] Small feature request

[poelzi]

Hi,

I got a interessting paper forwarded which discussed routing in tcp on
ad-hoc networks (especially tcp vegas). The idea was like that:
If the routing protocol notices the tcp stack that the route has
changed, it can recalculate some of its parameters (here the BaseRTT
value) to optimize speed.

Implementing meshferry, a tcp over udp proxy to surround most of tcp
problems, I can see a lot of usage for this. Because batman doesn't know
the topology itself, i thought about a mechanism to detect route changes
without knowing topology itself.

All batman originator packets would become an additional flag, lets say
uint32. When batman starts, it generates a random uint32 for its
complete runtime.
On a new broadcast message, it sets this new flag to his own random
value. If it rebroadcasts a message, it used the original value XOR its
own. This mechanism detects route changes very likely and even batman
restarts.

If the this new flag changes, the route somewhere in the network has
changed, it can't say where, but it doesn't have to.

The operations are cheap, the overhead is small. And allows analysis if
routes are more static or switching (would be interessting to see).

Long term I was thinking about a socket interface between routing daemon
and transport daemon. For the case of switching routes, batman would
then notify the route to host x has changed somehow, so he can optimize
his parameters.

kindly regards
 daniel

Re: [B.A.T.M.A.N.] Small feature request

[Marek Lindner]

Hi,


> I got a interessting paper forwarded which discussed routing in tcp on
> ad-hoc networks (especially tcp vegas). The idea was like that:
> If the routing protocol notices the tcp stack that the route has
> changed, it can recalculate some of its parameters (here the BaseRTT
> value) to optimize speed.
>
> Implementing meshferry, a tcp over udp proxy to surround most of tcp
> problems, I can see a lot of usage for this. Because batman doesn't know
> the topology itself, i thought about a mechanism to detect route changes
> without knowing topology itself.

interesting idea but I don't get your big picture. Could you further explain 
what you have in mind while considering the following:

Even with your algorithm, detecting route changes is quite difficult for 
batman, simply because batman does not know the concept of routes through the 
network. Batman just counts packets which arrived via one or the other 
neighbor and does not care about how the packets arrived at its neighbors. 
Which "route change" should be considered ? A route change after one / two / 
three / ... hops ? A one hop routing change could be detected without your 
algorithm. That is why I think you want to detect more.
If we make a 2 hop example: We have a batman running and (for the sake of 
simplicity) one neighbor A. This neighbor has 3 neighbors of its own which 
equally supply originator packets of our target, lets say 3 and we receive 9 
packets via our neighbor A. What is our new route ?
On the other hand we begin to leave the new approach of a one hop horizon 
towards OLSR based routing which makes routing assumptions based on outdated 
data.

TCP Vegas is an algorithm in which the sending side increases and decreases 
its window size. If you upload something it is your very host or in case of a 
download it is the server. Apart from the fact that you would need an altered 
TCP stack, batman has no big chance in helping out because its most 
widespread use is to build the "backbone infrastructure". Batman hosts 
seldomly act as client or server.

TCP Vegas algorithm to detect congestion is based on the round trip times of 
the packets. It simply observes if the RTTs get bigger or smaller and derives 
its window size from it. No information about a routing change is needed.

If you really plan to deploy TCP Vegas in your network you should make sure 
that *all* your clients do the same. Otherwise the users of TCP Vegas will 
experience a massive throughput loss because the commonly used TCP stack is 
much less fair. More information on that matter can be found here: 
http://www.isoc.org/inet2000/cdproceedings/2d/2d_2.htm


Regards,
Marek

Re: [B.A.T.M.A.N.] Small feature request

[Daniel Poelzleithner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Marek Lindner wrote:

> interesting idea but I don't get your big picture. Could you further explain 
> what you have in mind while considering the following:
> 
> Even with your algorithm, detecting route changes is quite difficult for 
> batman, simply because batman does not know the concept of routes through the 
> network. Batman just counts packets which arrived via one or the other 
> neighbor and does not care about how the packets arrived at its neighbors. 
> Which "route change" should be considered ? A route change after one / two / 
> three / ... hops ? A one hop routing change could be detected without your 
> algorithm. That is why I think you want to detect more.

every node xors the detect stamp before relaying. this way, if the route
is the same, the stamp is the same all the time. if anywhere on the
route, you can't detect where, changes, the stamp also changes. maybe
there will be routes that change very often, so batman will get a
constant flipping stamp. i don't want to change batman to know the
topology of the network, i love this simple yet genius approach much
better, because this is what network actually is, talking to your direct
neighbors :)
for the case of vegas tuning, this is another story, see below...

> If we make a 2 hop example: We have a batman running and (for the sake of 
> simplicity) one neighbor A. This neighbor has 3 neighbors of its own which 
> equally supply originator packets of our target, lets say 3 and we receive 9 
> packets via our neighbor A. What is our new route ?

i don't understand.
lets assume a topology like that:

   [A]
  /   \
[B]  [C]
   \ /
   [D]
    |
   [E]

lets say all links a equally good (very unlikly but anyway), so D is
receiving originator packets from A through B and C, but always relaying
only the first received. yes, this could break my idea. does batman
switch the route every time it receives a packet or only when it detects
that B sends less then C ?
to fix this problem, we could:
 - save the stamp received from the last originator packet from the
neighbor which is the neighbor we actually choose to route through.
 - every packet received from a different neighbor then the one we
actually use to route to, will get the stamp we saved XOR the own stamp

this would make the stamp not switch when the route is not switching, as
soon as batman decides to switch the route, the stamp will change on all
nodes behind D.

> On the other hand we begin to leave the new approach of a one hop horizon 
> towards OLSR based routing which makes routing assumptions based on outdated 
> data.

to make it clear, this stamp is not for routing decisions, it only
detects if a route has changed, nothing more, it won't change how batman
routes, it is just used to notify transport of changes.

> TCP Vegas algorithm to detect congestion is based on the round trip times of 
> the packets. It simply observes if the RTTs get bigger or smaller and derives 
> its window size from it. No information about a routing change is needed.

thats not right. it uses the so called BaseRTT as one parameter, which
is the smallest RTT received ever. The problem ist, that if the route
changes, the BaseRTT is most likly not valid anymore because the route
changed and the new one might have a higher or lower BaseRTT which
decreases performance.

i don't think vegas will perform very good in meshes, because we have
jitter like hell, and i think thats the reason tcp performes very bad in
generall, because all tcp implementations hate large jitter and a lot of
packet reordering.

> If you really plan to deploy TCP Vegas in your network you should make sure 
> that *all* your clients do the same. Otherwise the users of TCP Vegas will 
> experience a massive throughput loss because the commonly used TCP stack is 
> much less fair. More information on that matter can be found here: 
> http://www.isoc.org/inet2000/cdproceedings/2d/2d_2.htm

no, i don't plan to, because tcp is always senderside. the only thing
there could be done is installing proxys on the edges, but thats not
very good either. I'm currently trying another, very experimental
approach by writing a TCP-proxy (meshferry [1]). Currently it listens on
a tcp port to which you can connect, opens a UDP connection to another
proxy and this one translates this mesh optimized udp stream back to
TCP. If i can optimize the UDP protocol to perform better then TCP, the
next step would be to implement this as a tap device, so this could be
done totally transparent on the border of the mesh.

I'm thinking about something like that:

b.a.t.m.a.n notifies meshferry one specific events:
(b is batman, m is meshferry)
b- new host detected
 m- tests if the new host is speaking meshferry protocol
 m- if yes, notifies batman to route though the tap device
b- route has changed
 m- can optimize parameters again
m- detects to less memory for new connections, meshferry on the
otherside died,...
 b- notifies batman to not use tap device
 b- or sets firewall that new connections should be routed directly

...
this however would be long term and should be thought through very
carefully.

Because i think that detecting that a route has changed could help a lot
making long living or even short living connections to perform better. I
also think that BaseRTT is a useful parameter in general, just that it
shouldn't relay on it to much.



[1] https://dev.leipzig.freifunk.net/svn/meshferry/trunk

its currently broken due massive rewrite from the original source its
based on.


kindly regards
 daniel
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: GnuPT 2.7.2
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGdUFUy/mkIQp7AD0RAhdfAJ9iPbDX3pBvHVgycCrHr96Lufuf1QCdEyln
OEIzc2mMDfc7BipG2KllNeo=
=9i6L
-----END PGP SIGNATURE-----