[Babel-users] Route-dete :wq

Thu Mar 8 18:58:19 UTC 2018

On Wed, Mar 7, 2018 at 2:41 PM, Juliusz Chroboczek <jch at irif.fr> wrote:
> Christof, I'm very much interested in your experiments, which are likely
> to improve the quality of the Babel implementations.
>
>> We have update-interval set to 5 minutes to reduce the load on the network
>> because we are hoping to run this topology on 500+ APs with 1000+ Clients.

I wrote the rtod tool to experiment with creating large topologies.
I've not got around
to publishing the veth topos, but the tool is here:
https://github.com/dtaht/rtod

One thing that fell out of that was mainline babeld had a very
suboptimal routine
for merging routes (also it's use of memcmp was inefficient) - and
juliusz put out a call for a qsorted implementation a while back.

Elsewhere in babeld, atomic updates remain elusive. I made a bit of
progress on that
last year (unreachable routes have to keep the same metric to be an
atomic change) but got beat by another bug
that juliusz/martin(?) fixed later.

These are both problems that I've long meant to get to, but the
prospect of redeploying
with the pending unicast feature and source specific routing, as well
as reflashing a
few dozen devices in treetops with modern code, has thus far stopped
me. I kind of hope
to use bird on a goodly portion of the next deployment, and hopefully
this summer
I can find someone that likes climbing trees in california more than I do.

I have high hopes for the unicast stuff to lighten the routing load by
potentially orders of magnitude.

Somewhere in there (after breaking every routing daemon and protocol
in multiple ways with rtod,
and making several improvements to "rabeld", and scheming to replace
all! all of it, with my own
massively sorted, threaded, NEON coprocessor using version of
everything rewritten from scratch and running out of time long before
it reached plausible promise)...

I read "No Free Lunch Theorems for Search", and despaired. Every
daemon and protocol will break on some number of routes. Period.

See:

https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization

Short of a revolution in graph theory I see no way to get anywhere on
that, and yet tend to think
dynamically making the update interval larger to account for various
bounds (cpu,bandwidth) is part of a way out,
along with having a harder r/t scheduler for the bellman-ford calc
(needn't be threaded) would help to make sure it fits within bounds,
repeating important packets more often, etc.

(please note that most of what I'm saying as per NFL, etc is common to
all routing protocols and daemons)

> The protocol is very flexible, but the reference implementation is not
> designed to work with such large update intervals.  The amount of data in
> an update is pretty small, so I would recommend reducing the update
> interval -- it should be fine with thousands of routes in your network.

Try to remember that other traffic eats capacity, and even in a
fq_codel'd environment you only can get a percentage of bandwidth
(with low delays). I've seen devices with essentially infinite  queues
for mcast, also - over 16 seconds long!

I start running into trouble with 1000+ routes using 1Mbit mcast.
Sooner if I seriously
slam the network with flent or something else that abuses mcast like mdns. YMMV.

> The right way to reduce the amount of routing traffic in Babel is not to
> increase the update interval (which can at best yield a linear reduction),
> but to use aggregation and filtering (which can yield an exponential
> decrease in a well designed network).  Dave Taht has been successful with
> this approach, perhaps he'll want to chime in.

I've also experimented with dynamically changing the broadcast update
interval, as long term stable routes are, well, long term stable. Even
a linear reduction seemed worthwhile at the time I was fiddling with
this. Another way to preserve some percentage of sanity would be to
always update default routes often but with a long declared broadcast
interval and less used routes on a longer one.

As for aggregation and filtering: Most of my APs have at minimum,
ethernet, and two channels - usually four, including the meshy links.
The meshy links are ptp, so I've generally "wasted" an entire /22 ipv4
network to talk to the APs. ipv6 /62s.

The lab component of my network, for example, has two main links to
the production net, and the gateways only announce the
subnet it is on (172.22.0.0/16). This cuts the churn seen outside the
network when I do crazy things like reboot the whole thing.

The biggest problem I've run into, is that meshy links, are, meshy -
and I've lost track of the number of times where
I had a well defined /16 network in the lab suddenly leak all the
meshy /32 bits over the worst possible link - because I plugged
something in that was adhoc (and poorly) connected to the outside
network that I shouldn't have.

Lede creates one /48 ULA by default per AP, and then more /60s. I've
had a tendency to try to share one /48, but more recently I was trying
to go native ipv6 and disabled the ULA generation entirely.

I don't bridge anything except sometimes on the last APs on a link
(which don't announce babel on that bridge). Bridging can do weird
things to daemons that want also to be measuring the individual links.

So in your network design I'd try to identify your backbone links and
try upfront to rationally partition the network numbering scheme,
and still, periodically try to optimize it. It makes no sense to
export all the churn the last hop of a meshy, yet leaf network can
have to the whole network. I'd simulate what you plan, and then slam
it with traffic from every point with a tool like flent, and deploy
cake or htb+fq_codel on the ISP up/downlinks.

I'm working these days, on making netem better emulate wifi's
behaviors. I'm not satisified with it yet.

>
> Note that babeld currently sends updates as a single burst when the upate
> interval expires (the same is true of Toke's implementation of Babel, as
> far as I'm aware).  For very large networks, it would be good to split
> updates into one-packet pieces that are sent throughout the update
> interval.  I'd be glad to accept a patch that does that.
>
>> * making babel trigger updates on newly appeared routes
>
> I've gone through different approaches for scheduling updtes, and the
> current master is more aggressive with scheduling updates.  I'd need to
> check to make sure, but I believe it already does what you suggest.  If
> you have time, could you please check if current master improves things;
> if it doesn't, we need to work together to improve the implementation (no
> protocol changes will be needed).
>
> You could also try Toke's implementation, which is very well written.
>
>> * communicating the appearance of a route across the network outside
>> babel and inserting that at the gateway
>
> I'm not sure what you mean.
>
>> What do you think about those approaches?
>
> Please try current master.  If not, we'll need to think together about
> redesigning our approach to sending triggered updates.
>
> -- Juliusz
>
> _______________________________________________
> Babel-users mailing list
> Babel-users at lists.alioth.debian.org
> http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users

-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619