Using a simple global array to be the list of addresses and pointers, full load time went from about 3ms to 15ms. But it works just fine and the lookups are so fast the microsecond timer registers zero.
Great! I would think that the gain in efficiency of the routing more than offsets the extra processing for setup. You could consider making it multithreaded but I don't think anyone would notice an occasional 15ms delay and/or some drops. On our radio network such behaviour is quite normal.
Another possibility would be to first scan for the "common case" of all subnets and gateways remaining the same but only the endpoint address of one or two gateways changing, and in that case omit the entire table setup and only patch the nexthop addresses of those gateways.
Rob
That is exactly what I'm doing. It is necessary to clear and reload the global array if a subnet is added or deleted, but not when it is aged (as part of the route expiry system) or the gateway next-hop address is changed.
The delay is entirely caused by clearing the array. I'm using 'bzero()' to do that, as that's the fastest way I know of to zero an existing array, but it still takes 25ms to zero a vector of 16 million shorts. (Stepping through it with a for loop takes roughly 5 times as long.)
Luckily most changes in the encap routing table are indeed just revisions to the gateway next-hop address caused by gateways with dynamic addresses that change. That only takes less than 3ms to do all 600+ subnets. - Brian
On Tue, May 02, 2017 at 09:16:23AM +0200, Rob Janssen wrote:
Another possibility would be to first scan for the "common case" of all subnets and gateways remaining the same but only the endpoint address of one or two gateways changing, and in that case omit the entire table setup and only patch the nexthop addresses of those gateways.
Rob
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.
On Tue, May 2, 2017 at 5:50 AM, Brian Kantor Brian@ucsd.edu wrote:
(Please trim inclusions from previous messages) _______________________________________________ That is exactly what I'm doing. It is necessary to clear and reload the global array if a subnet is added or deleted, but not when it is aged (as part of the route expiry system) or the gateway next-hop address is changed.
The delay is entirely caused by clearing the array. I'm using 'bzero()' to do that, as that's the fastest way I know of to zero an existing array, but it still takes 25ms to zero a vector of 16 million shorts. (Stepping through it with a for loop takes roughly 5 times as long.)
Luckily most changes in the encap routing table are indeed just revisions to the gateway next-hop address caused by gateways with dynamic addresses that change. That only takes less than 3ms to do all 600+ subnets. - Brian
On Tue, May 02, 2017 at 09:16:23AM +0200, Rob Janssen wrote:
Another possibility would be to first scan for the "common case" of all
subnets
and gateways remaining the same but only the endpoint address of one or
two
gateways changing, and in that case omit the entire table setup and only
patch the
nexthop addresses of those gateways.
Rob
44Net mailing list 44Net@hamradio.ucsd.edu http://hamradio.ucsd.edu/mailman/listinfo/44net
That is exactly what I'm doing. It is necessary to clear and reload the global array if a subnet is added or deleted, but not when it is aged (as part of the route expiry system) or the gateway next-hop address is changed.
After sleeping on it (and discussing it with my cat), I've come to the conclusion that after deleting an old entry from the subnets routing table, it is only necessary to make a second pass down the entire subnets structure to clean up the resulting loose ends. That would add another 3ms to the load processes, but completely negate the need to zero the whole addrs map array, thus saving 25ms. I'll look into giving this a try.
The stats page now displays route table load and lookup times. - Brian
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.
-
Brian Kantor -
Dan Cross -
Rob Janssen