Re: Why are splay trees used in the preprocessors?

[Dragos Ruiu <dr () kyx net>]

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 () 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


-------------------------------------------------------
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 () 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