From: Manikantan Ramadas (mramadas@masaka.cs.ohiou.edu)
Date: 11/03/04
Date: Wed, 3 Nov 2004 18:11:39 -0500 From: Manikantan Ramadas <mramadas@masaka.cs.ohiou.edu> Subject: Re: tcptrace taking a very very long time Message-ID: <20041103231139.GB7126@masaka.cs.ohiou.edu>
Hey Russ,
We have been having a strong look at our AVL implementation in
tcptrace for the past two days. We *do* have a hash table still. AVL
tree is designed to hold only the hash-bucket for every hash-table
entry. AVL trees replaced the linked-list hash-bucket to improve average case
performance under heavy hash-collisions.
We uncovered a bug in the AVL function and have fixed it now.
That may/may not be the cause for the performance hit that you have
reported, however. But we have some synthetic dumpfiles having
quite a lot of hash-collisions on which the AVL implementation
actually does 4 times better than a simple linked-list hash-bucket.
In any case, we should have a bug-fix release of tcptrace by
tomorrow. If you guys get the chance to have it crunch over your huge
dumpfiles and lemme know if tcptrace does better now, that would be nice.
Thanks!
Mani.
On Mon, Nov 01, 2004 at 09:04:39AM -0500, Russ Fink wrote:
> Sad to say (and I'm sure I will get flames), tcptrace is broken in this
> regard. It does not work for very large cap files.
>
> What you are experiencing is an endless loop in the AVL tree data structure
> with regard to the rotates. I have experienced this same problem a couple
> months back (whatever the current version was) and manually rolled out the
> AVL tree and reverted to the hash table. [I don't currently use tcptrace
> because I needed additional features and switched to an internal tool.]
>
> To the community, hash tables are the most efficient way to manage
> connections in any kind of TCP system. Any kind of tree structure or
> queue, which tries to do constant optimization of its internal structure,
> is doing way more work than necessary. Look at libnids
> (libnids.sourceforge.net) and see how that is implemented using hashes.
>
> Russ
>
>
> ----------------------------------------------------------------------------
> To unsubscribe, send a message with body containing "unsubscribe tcptrace"
> to
> majordomo@tcptrace.org.
-- "'Beauty is truth, truth beauty,'--that is all Ye know on earth, and all ye need to know." - John Keats ____________________________________________________________________ * Manikantan Ramadas * IRG, OU * http://irg.cs.ohiou.edu/~mramadas * ____________________________________________________________________
----------------------------------------------------------------------------
To unsubscribe, send a message with body containing "unsubscribe tcptrace" to
majordomo@tcptrace.org.
This archive was generated by hypermail 2.1.7 : 11/04/04 EST