[Snort-users] Why are splay trees used in the preprocessors?
dr at ...381...
Sun Nov 23 00:18:02 EST 2003
Splay trees are better than hashes in almost all applications.
Especially network traffic that is self similar.
On November 22, 2003 09:09 pm, Joe Smith wrote:
> I have been studying the Snort code (v2.0.2) for a few
> weeks with most of my focus on the stateful
> preprocessors (portscan, portscan2, frag2, stream4).
> I noticed that they all use splay trees to store
> information (such as Portscanner nodes, Target nodes,
> Conversation nodes, etc.). Obviously, speed is of
> utmost priority in packet processing code. My
> question is why is a splay tree the preferred data
> structure for this? Would a hash have worked better?
> I understand that a splay tree will arrange itself to
> have the most frequently accessed nodes near the top
> (root) and thus have a very low avg. search time.
> Also, it would be faster to examine every node in
> order (based on some comparison criteria) in a splay
> tree than in a hash because the hash would require a
> sorting of the keys for this purpose. Additionally,
> since the preprocessors prune their trees every time
> they recieve a packet, it seems the traversal becomes
> a critical feature of the chosen data structure.
> Anyway, this argument does not fully convince me that
> the splay tree is the fastest choice. What about the
> cost of inserting a node? Is it possible that the
> splay tree was chosen for reasons other than speed?
> Do you Yahoo!?
> Free Pop-Up Blocker - Get it now
> This SF.net email is sponsored by: SF.net Giveback Program.
> Does SourceForge.net help you be more productive? Does it
> help you create better code? SHARE THE LOVE, and help us help
> YOU! Click Here: http://sourceforge.net/donate/
> Snort-users mailing list
> Snort-users at lists.sourceforge.net
> Go to this URL to change user options or unsubscribe:
> Snort-users list archive:
Top security experts. Cutting edge tools, techniques and information.
Vancouver, Canada April 21-23 2004 http://cansecwest.com
pgpkey http://dragos.com/ kyxpgp
More information about the Snort-users