2 May
2017
2 May
'17
3:16 a.m.
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
2 May
2 May
5:50 a.m.
New subject: amprgw routing
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
8:14 a.m.
New subject: amprgw routing
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(a)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(a)hamradio.ucsd.edu
http://hamradio.ucsd.edu/mailman/listinfo/44net
9:59 a.m.
New subject: amprgw routing
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
10:25 a.m.
New subject: amprgw routing
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.
2760
days inactive
2760
days old
4 comments
3 participants
participants (3)
-
Brian Kantor -
Dan Cross -
Rob Janssen