1 May
2017
1 May
'17
2:23 p.m.
You're absolutely right. I dropped some decimal
places. Thanks! However,
gateway addresses don't fit in a byte, they're stored in an unsigned long,
which is 4 bytes each. 4 * 16 million, right? And I think you need
counters and flags. So it's an array of structs of some modest size each.
My estimate of 128MB was based on having 4 bytes per entry and 2 tables for
convenient updating (update one table then toggle a single indicator or pointer
to make the updated table active).
Of course when you require more bytes per entry the table will expand, but
8-16 bytes per entry should still fit comfortably in a modern machine.
But I see a complication: You will have to have n
entries per route,
which will make loading the table a little less straightforward.
Well, searching a datastructure for the correct route isn't straightforward
either... remember when there is a tunnel to e.g. 44.137.0.0/16 and another
one to 44.137.1.80/28 (an example from the current table) then any traffic to
44.137.1.81 should go to the tunnel for 44.137.1.80/28, not something that
you can easily do with a binary search. However, a lookup in the table
populated with entries for 44.137.0.0/16 and then overwritten with entries
for 44.137.1.80/28 is easy. It will find the correct gateway with a single
array index operation. So you only need to build the table starting
from the subnets sorted by number of subnet bits to get it right.
Indeed it is best to make the program multithreaded, or you could put the
lookup table in shared memory and have a process doing the routing and another
process doing the updating. I would still opt for having a "current" and
a "next" table where the routing code always has a working table and the
switch to the next version is instaneous.
Of course you can also do a quick check before starting the laborious update
process, to see if the new encap table is different from the previous one.
Rob
1 May
1 May
2:26 p.m.
New subject: amprgw routing
As I said, we already do that.
- Brian
On Mon, May 01, 2017 at 08:23:09PM +0200, Rob Janssen wrote:
Of course you can also do a quick check before
starting the laborious update
process, to see if the new encap table is different from the previous one.
2:46 p.m.
New subject: amprgw routing
I think the most efficient technique is to make the per-address lookup
table an mmap'd array of pointers to entries in the existing route table.
The existing routing table lookup returns a pointer to an entry
in the routing table or NULL, so none of the program logic needs
major change except the process of loading the routing table itself
would need to update the per-address lookup table too.
And your idea of toggling between two tables is good too, as it
saves all the locking logic. You just update the one that's not
in use, then flip.
That makes it effectively addrtable[2][2**24], right?
That way we can make the per-address lookup VERY fast, and offload
all the table updating to a separate thread. It also allows quick
access to the routes table entry on successful lookups to update its
statistics counters and retrieve its gateway address. One extra
step of indirection is cheap. And I don't have to change much
code (just two major subroutines), which is always a good thing.
I'm going to have to look into this. Thanks for the ideas!
- Brian
On Mon, May 01, 2017 at 08:23:09PM +0200, Rob Janssen wrote:
My estimate of 128MB was based on having 4 bytes per
entry and 2 tables for
convenient updating (update one table then toggle a single indicator or pointer
to make the updated table active).
Of course when you require more bytes per entry the table will expand, but
8-16 bytes per entry should still fit comfortably in a modern machine.
2761
days inactive
2761
days old
2 comments
2 participants
participants (2)
-
Brian Kantor -
Rob Janssen