[Snort-users] Why are splay trees used in the preprocessors?

Dragos Ruiu 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.

--dr

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?
>
>
> Thanks,
> Peter
>
> __________________________________
> Do you Yahoo!?
> Free Pop-Up Blocker - Get it now
> http://companion.yahoo.com/
>
>
> -------------------------------------------------------
> 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:
> https://lists.sourceforge.net/lists/listinfo/snort-users
> Snort-users list archive:
> http://www.geocrawler.com/redir-sf.php3?list=snort-users

-- 
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 mailing list