[B.A.T.M.A.N.] Route selection over VPN links

[B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!

As we are nearing to our transition to Batman, we are playing some
scenarios with it and our current setups and layouts. Currently we
have many nodes connected to more and more VPN servers we have. And we
would like to use Batman on top of that. What happens is that we would
like to use the Batman also for routing over those VPN links. So that
we can connect our nodes to all VPN servers at the same time and
Batman then chooses over which tunnel the data should be routed. And
of course this is a bit different situation then wireless routing. For
example, different VPN servers might have different free capacities at
the moment available, or at least different overall capacity provided
(somebody can donate 100 Mbit/s on the server, somebody else 50
Mbit/s), and then there are also different latencies. Is there some
way for Batman to prefer routes based on this information? So latency
over one link and capacity? I know that capacity is problematic to
measure for wireless links, but here we could configure them manually.
Latency could be measured. And maybe it would even be enough to
measure latency, assuming that congested link would have higher
latency. So the logic could be:
 * if packet loss is different, choose the one with lower packet loss
 * if packet loss is the same, choose the one with lower latency

Such logic could probably be even user also on wireless links, no?

Anyway, is this doable? If I understand correctly, Batman does not
support some plugin system where we could inject this in? Would be
this some addition which could go into the core implementation?

I think I asked a bit of this questions before, but now we have a bit
more concrete picture what would be nice to have for our setup to play
really nicely.


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Marek Lindner]

Hi,

> As we are nearing to our transition to Batman, we are playing some
> scenarios with it and our current setups and layouts. Currently we
> have many nodes connected to more and more VPN servers we have. And we
> would like to use Batman on top of that. What happens is that we would
> like to use the Batman also for routing over those VPN links. So that
> we can connect our nodes to all VPN servers at the same time and
> Batman then chooses over which tunnel the data should be routed. And
> of course this is a bit different situation then wireless routing. For
> example, different VPN servers might have different free capacities at
> the moment available, or at least different overall capacity provided
> (somebody can donate 100 Mbit/s on the server, somebody else 50
> Mbit/s), and then there are also different latencies. Is there some
> way for Batman to prefer routes based on this information? So latency
> over one link and capacity? I know that capacity is problematic to
> measure for wireless links, but here we could configure them manually.
> Latency could be measured. And maybe it would even be enough to
> measure latency, assuming that congested link would have higher
> latency. So the logic could be:
>  * if packet loss is different, choose the one with lower packet loss
>  * if packet loss is the same, choose the one with lower latency
> 
> Such logic could probably be even user also on wireless links, no?
> 
> Anyway, is this doable? If I understand correctly, Batman does not
> support some plugin system where we could inject this in? Would be
> this some addition which could go into the core implementation?
> 
> I think I asked a bit of this questions before, but now we have a bit
> more concrete picture what would be nice to have for our setup to play
> really nicely.

the later versions of batman support a routing protocol plugin structure 
(check bat_iv_ogm.c to get an idea). Using bandwidth information for the 
routing decision is a nice idea but how does your concept look like ? How 
should the routing logic look like ?

Cheers,
Marek

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!



On Mon, Jul 16, 2012 at 3:02 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
>
> Hi,
>
>> As we are nearing to our transition to Batman, we are playing some
>> scenarios with it and our current setups and layouts. Currently we
>> have many nodes connected to more and more VPN servers we have. And we
>> would like to use Batman on top of that. What happens is that we would
>> like to use the Batman also for routing over those VPN links. So that
>> we can connect our nodes to all VPN servers at the same time and
>> Batman then chooses over which tunnel the data should be routed. And
>> of course this is a bit different situation then wireless routing. For
>> example, different VPN servers might have different free capacities at
>> the moment available, or at least different overall capacity provided
>> (somebody can donate 100 Mbit/s on the server, somebody else 50
>> Mbit/s), and then there are also different latencies. Is there some
>> way for Batman to prefer routes based on this information? So latency
>> over one link and capacity? I know that capacity is problematic to
>> measure for wireless links, but here we could configure them manually.
>> Latency could be measured. And maybe it would even be enough to
>> measure latency, assuming that congested link would have higher
>> latency. So the logic could be:
>>  * if packet loss is different, choose the one with lower packet loss
>>  * if packet loss is the same, choose the one with lower latency
>>
>> Such logic could probably be even user also on wireless links, no?
>>
>> Anyway, is this doable? If I understand correctly, Batman does not
>> support some plugin system where we could inject this in? Would be
>> this some addition which could go into the core implementation?
>>
>> I think I asked a bit of this questions before, but now we have a bit
>> more concrete picture what would be nice to have for our setup to play
>> really nicely.
>
> the later versions of batman support a routing protocol plugin structure
> (check bat_iv_ogm.c to get an idea). Using bandwidth information for the
> routing decision is a nice idea but how does your concept look like ? How
> should the routing logic look like ?

I thought I explained it enough. So for now, I would just go with only
measuring latency (I don't know what would be the best way to measure
this, though). If I have the latency (and this could be only one hop),
I would do:

* if packet loss is different, choose the one with lower packet loss
* if packet loss is the same, choose the one with lower latency in the next hop

What do you think?


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Marek Lindner]

On Tuesday, July 17, 2012 08:36:30 Mitar wrote:
> > the later versions of batman support a routing protocol plugin structure
> > (check bat_iv_ogm.c to get an idea). Using bandwidth information for the
> > routing decision is a nice idea but how does your concept look like ? How
> > should the routing logic look like ?
> 
> I thought I explained it enough. So for now, I would just go with only
> measuring latency (I don't know what would be the best way to measure
> this, though). If I have the latency (and this could be only one hop),
> I would do:
> 
> * if packet loss is different, choose the one with lower packet loss
> * if packet loss is the same, choose the one with lower latency in the next
> hop

I was more curious about the bandwidth routing than the latency stuff. The 
current routing algorithm already takes latency into account. An alternate 
path always need to be better than the current path. If both paths are equal 
the faster packets win the race.

Regards,
Marek

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!

On Tue, Jul 17, 2012 at 3:57 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> I was more curious about the bandwidth routing than the latency stuff. The
> current routing algorithm already takes latency into account. An alternate
> path always need to be better than the current path. If both paths are equal
> the faster packets win the race.

Hm. This happens only first time, it does not really change the route
latter on, if chosen path latency increases and becomes worse than the
second path, but packet loss stays the same (zero). Or it does?

For bandwidth, I would say that we first need multipath routing. And
then route on all possible paths some percentage of packets, based on
given capacity ratio. So if you have three paths A, B, and C with same
packet loss and capacity Ca, Cb, and Cc, you route over A with Ca/(Ca
+ Cb + Cc) ratio.

The other way would be to route based on free capacity, but this means
you would also have to know how much capacity is already taken for the
given path. This is probably hard. But for given interface maybe not
so much.

So for wall links we probably cannot know capacity. (This is
especially true for WiFi.) But for some links we can know (VPN links,
especially where people can set caplimit how much of their link they
want to donate to the network). So probably this information (link cap
and free capability) should be transmitted to all neighbors. And for
those links where you have this additional information, I would route
like:

- if packet loss on a path is different for some epsilon, route based on that
- if latency on a path is different for some epsilon, route based on that
- otherwise route based on the largest free capacity for some epsilon
available for the next hop (or preferably even path)

This would do correct thing for the case of VPN links, where most of
links will have almost zero packet loss, latency will be or small (for
local VPN servers) or big (for foreign VPN servers), and then based on
free capacity we would route on that.

So there should be some hysteresis and some "epsilon equality" so that
we do not flap the links all the time.

One more thing, we have currently one gateway server and multiple VPN
servers connecting to it. So most of the time traffic flows from or to
this gateway server from VPN servers. So if we transmit around
information about capacity on links, this would be a case where nodes
connected to multiple VPN servers could decide not just on next hop
capacity link, but also on the link to gateway. And so not just
congest the VPN server, because the link to it is free, but that also
link from it to gateway server should be free.

The above logic tells me, that routing plugins could be stacked. So
that you could have a stack of routing decisions where each of plugins
in the stack, in order, over which paths the packet should be routed.
It simply returns a list of those with some ratio/vote on each path.
Or simply remove some out of the list if it determines it is really
bad. For example, for above logic, for paths A, B and C:

- packet loss would return [A:0.33, B:0.33, C:0.33] because there is
no significant packet loss
- latency would return the same
- free capacity would return [A:(Ca/(Ca + Cb + Cc)), ...]

And at the end, for now, Batman could choose the best one route. Later
on with multipath routing, it could use this information to choose for
example n best.

Just some ideas ...


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Andrew Lunn]

On Tue, Jul 17, 2012 at 11:06:27AM -0700, Mitar wrote:
> Hi!
> 
> On Tue, Jul 17, 2012 at 3:57 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> > I was more curious about the bandwidth routing than the latency stuff. The
> > current routing algorithm already takes latency into account. An alternate
> > path always need to be better than the current path. If both paths are equal
> > the faster packets win the race.
> 
> Hm. This happens only first time, it does not really change the route
> latter on, if chosen path latency increases and becomes worse than the
> second path, but packet loss stays the same (zero). Or it does?
> 
> For bandwidth, I would say that we first need multipath routing. And
> then route on all possible paths some percentage of packets, based on
> given capacity ratio. So if you have three paths A, B, and C with same
> packet loss and capacity Ca, Cb, and Cc, you route over A with Ca/(Ca
> + Cb + Cc) ratio.

You have to be careful with packet reordering. If i remember
correctly, Linus did some measurements when link bonding was
introduced in BATMAN. TCP can cope with packet reordering, but it has
negative effects on goodput.

...

> This would do correct thing for the case of VPN links, where most of
> links will have almost zero packet loss, latency will be or small (for
> local VPN servers) or big (for foreign VPN servers), and then based on
> free capacity we would route on that.

Are these assumptions really true? In my home setup, my ADSL modem is
where my telephone socket is. My VPN server is somewhere else and
there is a wifi and a powerline link in between. If my neighbors swamp
the wifi channel with their torrent download, my VPN will
suffer. (Well not really, i known this wifi stuff better than my
neighbors)

   Andrew

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!

On Tue, Jul 17, 2012 at 11:22 AM, Andrew Lunn <andrew@lunn.ch> wrote:
> You have to be careful with packet reordering.

Hm. True. Yes, maybe multipath routing is just in theory a good idea.
;-) I also don't really believe in it. Or even believe it is
necessary. But some balancing could be useful to have. For example,
based on origin. So all packets from same origin goes on the same
link, and the other on the other. Is this possible to achieve?

> Are these assumptions really true? In my home setup, my ADSL modem is
> where my telephone socket is. My VPN server is somewhere else and
> there is a wifi and a powerline link in between. If my neighbors swamp
> the wifi channel with their torrent download, my VPN will
> suffer. (Well not really, i known this wifi stuff better than my
> neighbors)

I think we talk about different topologies here. We have a gateway
server on collocation, with VPN servers spread around the country. We
connect all nodes to those VPN servers, and VPN servers to gateway
server. We do not use ADSL uplinks for anything else than just to
connect to those VPN servers.

I am not talking about user's VPN servers, but network's. The ones
which allow nodes to be in the same network even if there is no (yet)
existing WiFi link between them.


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Christian Huldt]

2012-07-17 kl. 21:29 skrev Mitar:

> Hi!
> 
> On Tue, Jul 17, 2012 at 11:22 AM, Andrew Lunn <andrew@lunn.ch> wrote:
>> You have to be careful with packet reordering.
> 
> Hm. True. Yes, maybe multipath routing is just in theory a good idea.
> ;-) I also don't really believe in it. Or even believe it is
> necessary. But some balancing could be useful to have. For example,
> based on origin. So all packets from same origin goes on the same
> link, and the other on the other. Is this possible to achieve?
> 

the multipath tcp folks might be able to shed some light on multipath: https://scm.info.ucl.ac.be/trac/mptcp/

>> Are these assumptions really true? In my home setup, my ADSL modem is
>> where my telephone socket is. My VPN server is somewhere else and
>> there is a wifi and a powerline link in between. If my neighbors swamp
>> the wifi channel with their torrent download, my VPN will
>> suffer. (Well not really, i known this wifi stuff better than my
>> neighbors)
> 
> I think we talk about different topologies here. We have a gateway
> server on collocation, with VPN servers spread around the country. We
> connect all nodes to those VPN servers, and VPN servers to gateway
> server. We do not use ADSL uplinks for anything else than just to
> connect to those VPN servers.
> 
> I am not talking about user's VPN servers, but network's. The ones
> which allow nodes to be in the same network even if there is no (yet)
> existing WiFi link between them.

So you might be able to build virtual a community network on top of the internet?

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!

On Tue, Jul 17, 2012 at 11:43 PM, Christian Huldt <christian@solvare.se> wrote:
> So you might be able to build virtual a community network on top of the internet?

Not might, but we are already doing that. :-)

The only problem is that current wireless routing protocols are not
really behaving best with good fiber VPN links in between. :-)

The other problem, lack of good VPN solution, we just solved by
implementing our own L2TP broker daemon.


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Marek Lindner]

On Tuesday, July 17, 2012 20:06:27 Mitar wrote:
> > I was more curious about the bandwidth routing than the latency stuff.
> > The current routing algorithm already takes latency into account. An
> > alternate path always need to be better than the current path. If both
> > paths are equal the faster packets win the race.
> 
> Hm. This happens only first time, it does not really change the route
> latter on, if chosen path latency increases and becomes worse than the
> second path, but packet loss stays the same (zero). Or it does?

No, it always works. The slower route needs to be better than the faster 
route. If there is a new "faster" route the same applies. Just give it a try 
and see for yourself.


Cheers,
Marek

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Mitar]

Hi!

On Wed, Jul 18, 2012 at 1:06 PM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> No, it always works. The slower route needs to be better than the faster
> route. If there is a new "faster" route the same applies. Just give it a try
> and see for yourself.

But is there any hysteresis? Or route just flap?


Mitar

Re: [B.A.T.M.A.N.] Route selection over VPN links

[Marek Lindner]

On Friday, July 20, 2012 23:14:30 Mitar wrote:
> > No, it always works. The slower route needs to be better than the faster
> > route. If there is a new "faster" route the same applies. Just give it a
> > try and see for yourself.
> 
> But is there any hysteresis? Or route just flap?

Obviously, the switch is not instant. You need to be faster for a number of 
packets. Let me suggest again that you give it a try.

Regards,
Marek