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

Jim Cervantes jcervant at ...9478...
Sun Nov 23 13:06:06 EST 2003


Can you explain why you regard splay trees as better than hashes in almost
all applications?

Further, when you refer to network traffic, what do you mean?

Thanks,

Jim

-----Original Message-----
From: snort-users-admin at lists.sourceforge.net
[mailto:snort-users-admin at lists.sourceforge.net]On Behalf Of Dragos Ruiu
Sent: Sunday, November 23, 2003 3:15 AM
To: Joe Smith; snort-users at lists.sourceforge.net
Subject: Re: [Snort-users] Why are splay trees used in the
preprocessors?


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


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





More information about the Snort-users mailing list