2 May
2017
2 May
'17
9:25 a.m.
And I thank you for the pointer. Had I not already coded the existing
subnet routing, I probably would have tried it, but as it is, I was
looking for the simplest add-on that I could come up with.
Rob's huge array idea only works because we have a /8 and thus only 16
million addresses to deal with; it's not practical for a routing structure
that has to deal with the entire 32-bit IPv4 Internet address space, where
your radix tree would shine. (In fact, the BSD kernel uses compressed
radix trees for its ipfw firewall and for routing, and it's very fast.)
With the huge array, the lookup code consists pretty much solely of this:
lookup(addr) {
addr &= 0x00ffffff;
ptr = hugearray[addr];
if (ptr == 0) return 0;
return(&rttable[ptr-1]);
}
Which is pretty time efficient! In practice, it seems to be well
sub-microsecond per call.
I use mainly static memory structures in the router to avoid the
overhead and bother of dynamic memory structures. There's currently
room for 2048 subnets (we have only 600 currently), and that number
is easily bumped should we ever approach that limit.
- Brian
On Tue, May 02, 2017 at 08:14:56AM -0400, Dan Cross wrote:
(Please trim inclusions from previous messages)
_______________________________________________
I had mentioned to Brian possibly using the compressed radix tree structure
I implemented in 44ripd; that is a both space- and time- efficient
structure for maintaining exactly this sort of data; since keys are 32-bit
integers but with a fixed prefix, operations (including additions, updates
and removals) are always strictly less than O(32) and may be thought of as
O(1) in the asymptote. I haven't benchmarked it and suspect the
coefficients would dominate over an array, but one could imagine an
"in-place" update process where one iterates over the input data, updates
the tree by either adding entries or updating a timestamp, then walks the
tree looking for old entries and making a note. These could then be removed
after the fact. Indeed, that's basically what 44ripd does, and while it is
currently single-threaded, one could extract the data structure and wrap it
in a read/write lock and then use the same method but process only each
individual removal operation while holding the write lock. There would be
no need to zero anything on an add or delete.
https://github.com/dancrossnyc/44ripd
Specifically look for the "IPMap" code:
https://github.com/dancrossnyc/44ripd/blob/master/dat.h (data structure
definitions)
https://github.com/dancrossnyc/44ripd/blob/master/fns.h (function
prototypes)
https://github.com/dancrossnyc/44ripd/blob/master/lib.c (function
implementations)
- Dan C.