Subject: linear search of TCP control blocks on demultiplexing of an incom ing IP datagram

From: "Vishnepolsky, Oleg" <[email-masked]>
Date: Wed, 17 Apr 2002 14:06:10 -0400

Which TCP implementations do a hash lookup ? I know that most BSD
derivatives do a linear search, except for the freebsd stack which does a
hash. What about MS stacks ? My stacks (OS/2, FlexOS) being BSD derivatives
used linear search except I used a one control block cache lookup since most
of the TCP packets come in "trains". I had a 70% hit ration in my
experiments.
Is there a study/comparison of various TCP stacks re this and many other
characteristics ? I am aware of external TCP fingerprinting  but that does
not reveal the internals that much. Any help will be appreciated.
Oleg Vishnepolsky

---

From: Rick Jones <[email-masked]>
Date: Wed, 17 Apr 2002 11:18:16 -0700

I thought that the rise in the web pretty much obsoleted any stack that
still used a linear search.

rick jones
-- 
Wisdom Teeth are impacted, people are affected by the effects of events.
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to raj in cup.hp.com  but NOT BOTH...

---

From: Luigi Rizzo <[email-masked]>
Date: Wed, 17 Apr 2002 11:29:24 -0700

On Wed, Apr 17, 2002 at 02:06:10PM -0400, Vishnepolsky, Oleg wrote:
...
> of the TCP packets come in "trains".

well, this seems to be more a feature of your test environment than
a general property. It may be true on a workstation-type of system,
where there are only very few active connections at once (but then
the PCB lookup load is probably negligible compared to the cycles
spent doing DCT and XML parsing and bytecode interpretation), but
certainly not in a server-type of system with hundreds of active
sessions.

	cheers
	luigi
-----------------------------------+-------------------------------------
  Luigi RIZZO, [email-masked]  . Dip. di Ing. dell'Informazione
  http://www.iet.unipi.it/~luigi/  . Universita` di Pisa
  TEL/FAX: +39-050-568.533/522     . via Diotisalvi 2, 56126 PISA (Italy)
  Mobile   +39-347-0373137
-----------------------------------+-------------------------------------

---

From: Murali Bashyam <[email-masked]>
Date: Wed, 17 Apr 2002 11:40:07 -0700

> of the TCP packets come in "trains". I had a 70% hit ration in my

Actually the NetBSD implementation another BSD derivative also hashes the five
tuple, i'm sure
even the Linux implementation does.

Murali

---

From: Alan Cox <[email-masked]>
Date: Wed, 17 Apr 2002 21:18:33 +0100 (BST)

> even the Linux implementation does.

Linux has had hashed lookups since before 1.0. I don't believe it ever
had straight lists in any incarnation. The size and sophistication of the
hash has increased massively over time, as things like big porn sites
pretty much demand nowdays.

Alan