[Babel-users] Ability to work with massive number of routes? (global full-table)

[Dave Taht]

On Tue, Sep 25, 2018 at 6:48 AM Toke Høiland-Jørgensen <toke at toke.dk> wrote:
>
> Dave Taht <dave.taht at gmail.com> writes:
>
> > And - setting a goal for 64k routes - I thought that switching to a
> > normalized table structure internally would be useful. Instead of
> > storing the nexthop as a full address store an 16 bit index pointing
> > to an array of those nexthops. And so on.
>
> Incidentally, it looks like the Linux kernel will start doing this as
> well:
>
> https://marc.info/?l=linux-netdev&m=153576423232067&w=2

Well the aim for me was more "try to scale higher than 802.11s" but
still fit into the memory of small routers.

The biggest meshy network I was aware of at the time was guifi, at
17,000? wlan-slovinia was over 1000 routes and flaky as heck. I'd
really hoped they'd redeploy with the 17.01 release but they didn't.
My
network peaked at, oh, 600 routes before I went nuts with covering
routes, stopped using ipv6, and split core router to static. There's
not a lot of redundancy left in that network. When it goes down
someone complains immediately instead of it taking weeks for someone
to notice.

I figured, then, that by setting a default goal of 64k routes and
optimizing some codebase for that goal exclusively would meet the
meshy market need.

So in this hypothetical city-scale babeld - that meant 16 bit indexes
into the ipv4 'tables', 16 bit indexes for source, dest, and nexthop
(all into the same ipv6 table probly), in general, a 16 bit index into
the routerid, things like "zeros" and "ones" would live in that table,
etc.
equality is index equality. Still would need some hashes or btrees for
lookups. Could try to make it possible to use 32 bit indexes, as
"4 billion routes ought to be enough for everyone", but default to 16
to start with.

I haven't thought about this in a long time, but I seem to recall it
seemed feasible (tricky) to also have shared metrics which would
vastly
reduce the time it took to recalc bellman-ford.

I cut a wide swath through the code and my problems then, it was just
hacking, I should have written up the good results and the bad
at the time, 'cause at least 98% of my other ideas were terrible. I
seem to recall rebuilding the compiler ABI in order to get more
static neon registers and trying to get rid of errno in the musl C
library as two of the crazier ones, while regularly encountering
hardware bugs in the parallella version....

I'm trying to pull together the "good bits" from the debris as I
write, now that I have a couple years perspective.

> -Toke



-- 

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