About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Sat, 02 Dec 2006

Multidimensional trie searching algorithm is completed.


I'm back to work on this problem and here are results.

Hardware.
Intel Core Duo 3.4 Ghz (each core runs with 3.7 Ghz) with 2Gb of RAM (userspace application is singlethreaded, so only one core is used).

Test description.
A number of 3-dimensional pseudo-random rules has been inserted/searched/inserted+searched.
More than 80% of rules contain pseudo-random wildcards (wildcard is formed with higher bits from 0 to 31 set without gaps). Each rule is a 32bit range, for example 192.168.0.0/255.255.255.0 produces such a range.
Searching is performed for the non-wildcard rule, i.e. rule with 0xffffffff mask.
Such setup is a powerfull IPv4 packet filter emulation.

Results.
Graph shows number of microseconds needed to insert (including time for memory allocation), search and sum one multidimensional rule depending on total number of rules.



This graph shows memory usage for trie implementation. Theoretical maximum limit is calculated by multiplying number of rules, number of directions, size of each rule object (in onde dimension), 32 (number of bits, i.e. number of rule objects to represent the rule) and 0.6 (20% is non-wildcard rules and 80% is wildcards with equal distribution of 1-31 bits, so 0.2 + 0.8*0.5). Each rule contains 28 bytes on x86 of auxiliary information, which is used to build the tree, it can be reduced though.



Test run for the case without wildcards shows increased memory usage (since with wildcard existing algorithm allocates nodes only for masked bits, i.e. the biger mask is (0xf0000000 is bigger mask than 0xffff0000 in above notation) the less memory it requires, thus insert time was increased, but still is constant value about 12 microseconds.
Search speed becomes constant and is about 1 microsecond.

I've started following test to run till Monday - system creates and inserts 500.000 rules with random data and prefixes, then 500.000 rules without wildcard, after each insertion it search for the rule, after one million rules has been isnerted, program starts from the beginning (by existing and restarting). I do not put rule deleting test, since there is no memory to hold all rules and all intervals used to create those rules (deleting was successfully tested on smaller amounts).

/devel/networking :: Link / Comments ()