[Babel-users] hashing lookups in general in babel

[Dave Taht]

On Thu, Nov 29, 2018 at 8:37 AM Christof Schulze
<christof.schulze at gmx.net> wrote:
>
> On Wed, Nov 28, 2018 at 10:28:50PM -0800, Dave Taht wrote:
> >Dave Taht <dave at taht.net> writes:
> >
> >> Juliusz Chroboczek <jch at irif.fr> writes:
>
> >>>> Why not? If it's not MTI you risk the case where you get to pick between
> >>>> "good performance on weak devices" and "interoperability with RFC-only
> >>>> implementations".
>
> >>> Is there any evidence that there are devices that can reasonably run Babel
> >>> and that are too weak to use SHA256 for protecting control traffic?
>
> >>> I don't have an ARM device handy right now, but a 450MHz MIPS 24Kc is able
> >>> to SHA256 on the order of 16MB/s.  That's 10000 full-size frames per second,
> >>> or on the order of 600000 Babel updates per second.
> >
> >I've been meaning to poke into this a while:
> >
> >https://code.fb.com/connectivity/open-r-open-routing-for-modern-networks/
> >
> >But I do take your point. It would be good to know that on a given
> >10,000 route 200 router babel network that hashing overhead accounted
> >for .0X% of the 100% of cpu in use.
> As it is we are having trouble to achieve that figure even without
> hashing. Doesn't this mean this should be priority?

Heh. You spotted the cynicism. :)

The two goals are kind of congruent in the long term. Picking a good,
fast hash function for auth, and then possibly re-using the heck out
of it elsewhere in babel's hash tables if it's fast enough. [1] If it
lives in icache/dcache, it stays fast. [2]

Recently I stumbled across this paper:

https://arxiv.org/pdf/0903.0391.pdf

Skip all the math and go to fig 5. the world is full of algorithms
that have great averages but really pathological behavior on the
outliers - including most hash table designs I've seen. This one,
doesn't. (or at least, claims to) Constant worst case times are
something that fill me with joy, I'm perpetually worrying about my
"go" driven steering wheel controller going into garbage collection at
precisely the wrong time.

He goes into more detail in his thesis:

https://sites.google.com/site/yuriyarbitman/Home/de-amortizedcuckoohashing

as for - as best as I can tell - nobody's yet looked at the typical
distribution of source specific ipv6 addresses. Ipv6 is weird, lots of
0 bits..

https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

And for all I know I'm overthinking it... (but I like pretty pictures
like the above, and really want to dump the BGP route table into
it)... as a constant reminder to myself to stop doing assembly
language optimizations, I got myself the following poster for
christmas:

http://bigocheatsheet.com/

Anyway, attached is a *broken*, 2AM, 40 minutes attempt at tossing
blake into the hmac-challenge branch. To use, apply the patch, and do
a

git submodule add https://github.com/BLAKE2/BLAKE2.git

then a make, then add

key id key1 type blake2s value deadbeefdeadbeefdeadbeefdeadbeefdeadbeef
default enable-timestamps true unicast true hmac key1 # unicast false hmac key1

It briefly will swap routes, and then crash. I didn't quite "get" how
to specify key length right or digest size, my principal purpose was
to find something small (it is) and cross compilable (it does).  Or
for all I know I have another bug elsewhere.  I don't have time to get
back to it this week.

it adds a mere 4k to the binary.



[1] things like spookyhash seem faster but perhaps not good enough for
that cuckoo hash method
[2] this is one of lua's performance secrets

>
> viele Grüße
>
> Christof
>
> >
> >You are reasonable to assume that sha256 would be low overhead relative
> >to other factors, I think. Still, would like to go measure.
> >
> >Aside: Where does the 300ms figure for re-attempting a challenge and
> >response come from?
> >
> >
> >_______________________________________________
> >Babel-users mailing list
> >Babel-users at alioth-lists.debian.net
> >https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users
>
> --
> ()  ascii ribbon campaign - against html e-mail
> /\  against proprietary attachments
>
> _______________________________________________
> Babel-users mailing list
> Babel-users at alioth-lists.debian.net
> https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users--

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740
-------------- next part --------------
A non-text attachment was scrubbed...
Name: broken_blake_for_babel.patch
Type: text/x-patch
Size: 8564 bytes
Desc: not available
URL: <http://alioth-lists.debian.net/pipermail/babel-users/attachments/20181129/d36d2642/attachment-0001.bin>