> There are actually
> several instances where there is an encap route for a /16 and
> then there are some /28s or /29s nested inside it.
> BGP-only subnets aren't in the encap file.
Our BGP-routed /16 is in the encap file as well, for compatibility with
gateway stations that cannot send their net-44 traffic over internet due
to source address filtering, or that are otherwise configured in such a way that
net-44 traffic is never sent to internet directly.
So we are one of those /16 networks with several small networks and single
addresses inside it routed to different gateways. I don't know if the other
instances are a result of the same setup.
Good to hear that those are properly handled.
Rob
> 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.)
Well this is where you could gain some time using the mmap, depending on various
factors. When you do a fresh mmap of /dev/zero (or ANON) every time you need a
new clear array, that will execute much quicker than clearing all that space,
because in fact it is only setting up some page table entries that all point to
the same already zeroed memory block.
Then, when you start populating it of course you lose some of that advantage as
each write into a page causes a page fault and a new memory block being allocated
and zeroed and inserted into the page table.
Only experimentation can show what the total time of the mmap + page COW operations
is when compared to the bzero. It will depend on the density of the routed AMPRnet
space.
So, you would change the array[2][2**24] into a *array[2] (2 pointers to 16M entries)
and mmap/munmap them every time you need them cleared.
Rob
> Deletions zero the corresponding entries in the addrs table, so if the
> deletion count was non-zero, then when you're through deleting all the
> expired entries, you run through the subnets table and load the remaining
> routes into the addr table.
Ok that sounds good, it should save a lot of time because most of the table
is zero and never touched. I presume you do the reloading in order of
decreasing subnet size so "nested" subnets are properly handled.
(of course nested subnets primarily occur in the case of BGP routed networks
and in that case it does not matter too much because the traffic is not
supposed to go via amprgw anyway)
Rob
> Replacing the earlier sequential search through the routing
> table with a binary search has significantly sped up lookups,
> which can happen up to twice per packet forwarded (once for
> source address, once for destination address).
With "only" 16 million addresses in AMPRnet, why don't you use a 16-million entry array
holding the next hop for each IP in 44.x.x.x or zero for those addresses that have no tunnel?
Then you only need a single index operation to get the next hop for a packet.
That requires 64MB of memory to store, hardly a significant amount today.
And it can double-up as the filter to forward traffic only to/from registered addresses.
Of course the update operation becomes more expensive, but it could probably be done in-place
without disrupting packet forwarding. Or you could build a second table and then switch
to it after the build is complete (requiring 128MB).
Rob
> 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
Hello all, and thank you for your assistance. I have 44.10.10.0/24
allocated and announced via BGP. The subnet terminates to an Ubuntu
server in a data center. I want to allocate addresses from this subnet
via tunnels to other locations. For example, I would like to assign an
address or a block of addresses to my home location (Cisco 1900 router)
from this subnet. Is this possible, or do I need to look at a different
option? Thank you!
--
73 de Phil Pacier, AD6NH
APRS Tier2 Network Coordinator
http://www.aprs2.net
I've made some changes to the amprgw routing mechanism.
Replacing the earlier sequential search through the routing
table with a binary search has significantly sped up lookups,
which can happen up to twice per packet forwarded (once for
source address, once for destination address).
Three times an hour, a background process fetches the encap
routing table from the portal, and if it has changed, signals
the router process to update its routing table. The routing
table update seems to take about 3 msec during which packets
can't be looked up and so are not forwarded.
This fetch also updates the data source for the rip sender,
so you'll receive updates more quickly now.
- Brian
> 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.
> That makes it effectively addrtable[2][2**24], right?
Yes. Of course a single pointer would be 8 bytes when it is compiled for 64 bits,
but it would not need to be. When your existing route table is an array
rather than a collection of malloc'ed objects linked by pointers, the "pointer"
from the address lookup table into the route table could be the smaller index
into the route table (that would easily fit in an unsigned short integer, allowing
for 65535 gateways).
Or, in 32 bit mode a simple pointer can be used (4 bytes per entry).
Rob
> 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
> 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.
Another possibility would be to have a 16-million entry array of short integers
holding a "gateway number" (starting at 1) for each IP address, and a separate
table of gateways holding all the other info you want to keep per gateway.
(e.g. counters)
Then the processing of a packet would first index the destination IP in the
first array, retrieving the gateway number (0 means drop the packet), then
use that number as an index in the gateway table to access the per-gateway
data including the endpoint address and the counters. This would require only
slightly more than 32MB of memory for the tables, which should be no problem without
any tricks.
Rob
