by sunult.. » Tue, 28 Mar 2000 04:00:00
Is there literature any where that explains how a tcp connection
control block (tcb) is hash inserted? I am interested in:
1. Hashing data structure used. And what is the hash function?
2. How are collisions handled?
3. What is the worst case search time in case of collisions?
I did not find the answers to this anywhere. Any help would be highly
appreciated.
thanks
Sent via Deja.com http://www.deja.com/
Before you buy.
by Casper H.S. Dik - Network Security Engine » Tue, 28 Mar 2000 04:00:00
Standard implementation of linear search on hash collisions.Quote:>1. Hashing data structure used. And what is the hash function?
>2. How are collisions handled?
O(n) where N is the number of entries in a hash backet.Quote:>3. What is the worst case search time in case of collisions?
THe number of buckets is settable.
Check the pidentd sources for an implementation that searches
for TCP blocks in the kernel.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
I've got a program that is hashing the tcp source and destination
addresses on a packet to find the right hash bucket for the
tcp session it belongs to. The program is listening promiscuously to
potentially all the packets that it sees go by on a LAN.
Right now I'm doing something like XORing the source ip, source
port, destination ip, and destination port together and taking the
result modulo some prime. (I'm actually shifting one of the 16 bit
ports left 16 bits before XORing it in. )
Can anyone think of any reason what I'm doing is less than optimal from
a standpoint of getting even usage of the buckets? Any suggestions
on what you'd do instead? I realize the hash could be faster if I
were to use a power of 2 for the number of buckets instead of a
prime, but it's fast enough as is for my purposes and I'm more
concerned about worst-case usage of the buckets.
Empirically it seems to do ok. Just wondering if I am missing
anything obvious one could get combining a little number theory with
some assumptions about the distribution of addresses.
--
Craig Johnston "Windows 1984"
2. PPP Problem
3. KERN_INFO 2.4.19-pre2 IP/TCP hash table size printks
4. system admin @ intel in California
5. KERN_INFO: IPv4 IP/TCP hash table size printks
7. Fw: memory corruption in tcp bind hash buckets on SMP?
10. memory corruption in tcp bind hash buckets on SMP?
13. hash of hashes in C.. preferable with a lib