Subject: subscribe
From: [email-masked] (Gary Friedman)
To: [email-masked]
Date: Tue, 29 Sep 92 15:29:50 PDT

Subscribe

To: [email-masked]
Reply-To: [email-masked] (Thomas Skibo)
From: [email-masked] (Thomas Skibo)
Subject: Re:  Source Code
Date: Tue, 29 Sep 1992 21:37:44 GMT

My Net-2 release BSD patch should still be available from uxc.cso.uiuc.edu.

The file you want is "pub/tcplw.shar.Z".  

The patched TCP has been running quite stable on a uVAX at U. of
I. for at least 5 months.  There is a minor bug (described in the README)
which I've been reluctant to fix because I don't want to redo all
the testing that I went through.  It's a one line change.  Also, the
PCB's are stored in cluster mbufs which is REALLY wasteful.  You might
want to change that.

-skibo

---
Thomas Skibo
[email-masked]

Date: Tue, 29 Sep 92 14:21:58 -0700
From: [email-masked] (Thomas Skibo)
To: "Sean O'Malley" <[email-masked]>
Subject: Re:  Source Code
Cc: [email-masked]

My Net-2 release BSD patch should still be available from uxc.cso.uiuc.edu.

The file you want is "pub/tcplw.shar.Z".  

The patched TCP has been running quite stable on a uVAX at U. of
I. for at least 5 months.  There is a minor bug (described in the README)
which I've been reluctant to fix because I don't want to redo all
the testing that I went through.  It's a one line change.  Also, the
PCB's are stored in cluster mbufs which is REALLY wasteful.  You might
want to change that.

-skibo

---
Thomas Skibo
[email-masked]

Date: Tue, 29 Sep 1992 13:29:47 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: Source Code

Is there a version of the extended TCP available by ftp?

(Preferablty a BSD version)

Sean O'Malley

Date: Tue, 15 Sep 92 13:01:08 PDT
From: [email-masked] (Wayne Hathaway)
To: [email-masked]
Subject: Re: eliminate TCP input demuxing

Christian Huitema <[email-masked]> comments:

> You mention the your-ref/my-ref exchange of TP4 as an optimization.
> It certainly can be used to facilitate demuxing and quickly locating
> your context in a PCB list, modulo a couple of caveats -- one needs
> to check the consistency of "your-ref" with the source address if
> one is serious about security, so the instruction count is not so
> small as it appears.

True, but a consistency check is just a compare, which can be done a
*LOT* faster than searching a hash chain or something.  It could even
be done relatively easily by the hardware in parallel with "other
stuff," although that probably isn't worth it.

> But this exchange has one big cost: it prevents "direct transmission",
> and inserts a delay during which a complete transaction could probably
> have taken place on a high speed network. It can only be factored
> out for long connections, not for RPC type transactions.

Remember that this discussion was in the context of TCP, which of
course suffers the same COTS drawback.  The point was that a
connection identifier in TCP is a 12-byte quantity, which takes time
to process, while a connection identifier in TP4 is a 16-bit quantity
that can be used as a direct index.  All of which has nothing at all
to do with CLTS!

    Wayne Hathaway               domain: [email-masked]
    Ultra Network Technologies     uucp: ...!ames!ultra!wayne
    101 Daggett Drive             phone: 408-922-0100 x132
    San Jose, CA 95134              FAX: 408-433-9287

PS: You mention an "exchange" as if it were something extra beyond the
normal connection-establishment handshake.  It is not, of course, so
using a reference *IS* "free" once you bite the connection-oriented
bullet.

Date: Tue, 15 Sep 92 12:57:44 PDT
From: [email-masked] (Wayne Hathaway)
To: [email-masked]
Subject: Re: eliminate TCP input demuxing

Me:

> Since the term "Ultra-net" (actually UltraNet :-) was used in this
> discussion in the sense of a "protocol" like XTP I feel justified in
> jumping in ...
> 
> UltraNet actually runs fairly vanilla ISO TP4 internally (as well as
> TCP),...

Vernon Schryver:

> Does it still move the checksum to the end of the packet, after the
> data? 

Yes, internally to an UltraNet we still put the checksum in a trailer,
computed by special hardware as the packet is flowing through.  (We do
this with TCP as well.)  This gives us a significant performance gain,
and is why I said "fairly vanilla TP4."  However, whenever a packet
*LEAVES* an UltraNet (e.g., being routed onto Ethernet or FDDI) then
we do stop the packet long enough to move the checksum up front where
the rest of the world expects to find it.

    Wayne Hathaway               domain: [email-masked]
    Ultra Network Technologies     uucp: ...!ames!ultra!wayne
    101 Daggett Drive             phone: 408-922-0100 x132
    San Jose, CA 95134              FAX: 408-433-9287

To: [email-masked] (Wayne Hathaway)
Cc: [email-masked]
Subject: Re: eliminate TCP input demuxing 
Date: Mon, 14 Sep 92 14:37:46 -0400
From: Christian Huitema <[email-masked]>

You mention the your-ref/my-ref exchange of TP4 as an optimization.
It certainly can be used to facilitate demuxing and quickly locating
your context in a PCB list, modulo a couple of caveats -- one needs
to check the consistency of "your-ref" with the source address if
one is serious about security, so the instruction count is not so
small as it appears.

But this exchange has one big cost: it prevents "direct transmission",
and insert a delay during which a complete transaction could probably
have taken place on a high speed network. It can only be factored
out for long connection, not for RPC type transactions.

Christian Huitema

To: [email-masked]
Reply-To: [email-masked] (Vernon Schryver)
From: [email-masked] (Vernon Schryver)
Subject: Re: eliminate TCP input demuxing
Date: Sun, 13 Sep 1992 05:09:31 GMT

[email-masked] (Wayne Hathaway) writes:
> Since the term "Ultra-net" (actually UltraNet :-) was used in this
> discussion in the sense of a "protocol" like XTP I feel justified in
> jumping in ...
> 
> UltraNet actually runs fairly vanilla ISO TP4 internally (as well as
> TCP),...

Does it still move the checksum to the end of the packet, after the data?

Vernon Schryver,  [email-masked]

Date: Sat, 12 Sep 92 10:44:05 PDT
From: [email-masked] (Wayne Hathaway)
To: [email-masked]
Subject: Re: eliminate TCP input demuxing

Since the term "Ultra-net" (actually UltraNet :-) was used in this
discussion in the sense of a "protocol" like XTP I feel justified in
jumping in ...

UltraNet actually runs fairly vanilla ISO TP4 internally (as well as
TCP), and one of the reasons for choosing TP4 for a high speed net is
exactly the topic being discussed: the TP4 "reference" field.  This is
a fixed-location 16-bit VC identifier that can be *VERY* quickly
translated into a PCB pointer.  Our custom hardware actually uses it
directly as a "subscript" into a PCB array, so we have no hashing, no
caching, no nuttin': just stuff it into a register and the hardware
does the rest.

And frankly it surprises me to see this idea being "reinvented" in
this group.  ISO TP4 sure ain't God's gift to protocols, but it did do
a *FEW* things right that even almighty TCP can learn from! :-)

    Wayne Hathaway               domain: [email-masked]
    Ultra Network Technologies     uucp: ...!ames!ultra!wayne
    101 Daggett Drive             phone: 408-922-0100 x132
    San Jose, CA 95134              FAX: 408-433-9287

Date: Fri, 4 Sep 92 11:59:33 -0700
From: [email-masked] (Rob Warnock)
To: [email-masked]
Subject: Re: TCP demultiplexing

[email-masked] writes:
+---------------
| We use this method on one of our proprietary protocols. It works very well.
| I have wished for it with TCP for awhile now. My problem is that even with a
| hash table with 511 slots in it I have to search approximately 50 tables on
| average if there are 50,000 connections.
+---------------

So use a bigger hash table! If you have 50,000 connections (PCBs) you surely
can afford the memory space for an average of one more pointer per connection,
so build a hash table with 50,000 entries in it. Hashing only works really
well if the *average* number of probes per lookup is ~1.

But you should also note that if you have 50,000 connections, you might as
well use a direct index on a 16-bit port number as the "hash". There are two
common methods:

1. XOR the local and remote port numbers. (Simple enough.)

2. If the local port number is above the "reserved" range, use it by itself
   as the "hash", else use the remote port number by itself. That is:

	hash = (lport > IPPORT_RESERVED) ? lport : rport;

   For most TCP connections, this means that the hash will be a "randomly"-
   assigned port number.

-Rob

-----
Rob Warnock, MS-9U/510          [email-masked]
Silicon Graphics, Inc.          (415)390-1673
2011 N. Shoreline Blvd.
Mountain View, CA  94043

Date: Fri, 4 Sep 92 11:50:34 -0700
From: [email-masked] (Rob Warnock)
To: [email-masked]
Subject: Re: eliminate TCP input demuxing

[email-masked] (Vernon Schryver) writes:
+---------------
| [email-masked] (Steve Wise) writes:
| > 	hash algorithm REDUCES the need for connection ID passing that
| > 	is used in other protocols (TP4, X.25, and XTP are cited). 
| > 
| > 	I'm wondering what the gain (if any) would be going from the
| > 	hash table lookup described by the folks at Sequent to actually
| > 	passing some sort of connection ID's...
| 
| I know some XTP silicon designers who seemed to me to find the XTP
| connection ID equivalent to the TCP/IP 96-bit connection ID of
| ((host,port)(host,port)).  I think both get hashed to find the "context."
+---------------

The problem with the XTP "connection" ID is that its number space is local
to a "route" ID, and route IDs are local to the "source MAC" addresses, so
what you end up looking up is {connection, route, src_MAC}. Hmmm... 96 bits,
just like TCP's {src_host, src_port, dst_host, dst_port}. So, yes, we [SGI/PEI
joint-development] built some generic conditional extracting/hashing hardware
into the PEI chipset's data pipeline, and we hashed {protocol, protocol-
dependent-96-bits}, in hardware.

I did a bunch of simulations on hashing functions for the hardware, to see
what kind of hash distributions we got with actual traces from the traffic
from a few internal LANs (no attempt at a really broad sampling), and found
that:

1. Division by just about any primitive polynomial (think "prime", if you like)
   is a decent hash.

2. You really want about as many buckets as the average number of open
   connections, to avoid too many collisions and too-long chains.

3. If you including the cost of moving the most recent match to the head
   of its hash chain, the average cost of a lookup was (slightly) more
   expensive than *not* promoting the most recent match, for the traces
   I was working with with (a few million packets).

This latter was a surprising result to me, until I realized that (a) the
cost in memory/CPU cycles to promote a non-first entry in a chain to the
first entry is more than the cost of sequentially searching a two-entry
chain, and (b) most of the chains were short -- even *without* promoting
recent matches, the average number of chain entries searched per lookup
was ~1.1.

-Rob

-----
Rob Warnock, MS-9U/510		[email-masked]
Silicon Graphics, Inc.		(415)390-1673
2011 N. Shoreline Blvd.
Mountain View, CA  94043

Subject: Re: eliminate TCP input demuxing
To: [email-masked]
Date: Fri, 4 Sep 92 8:48:45 CDT
From: [email-masked]

> 
> In article <[email-masked]>, [email-masked] (Steve Wise) writes:
> > ....
> > 	I've read this paper.  They note at the end that their proposed
> > 	hash algorithm REDUCES the need for connection ID passing that
> > 	is used in other protocols (TP4, X.25, and XTP are cited). 
> > 
> > 	I'm wondering what the gain (if any) would be going from the
> > 	hash table lookup described by the folks at Sequent to actually
> > 	passing some sort of connection ID's...
> 
I think the point here was that the hashing reduced the search time enough so
that there was less incentive to go to connection id passing. Connection id
passing will be more efficient since there is no search at all.

Kurt Matthys

Date: Thu, 3 Sep 1992 11:49:04 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: PCB's and Timestamps
Cc: [email-masked]

I was incorrect in my last message:

> The problem with all of this is that we don't really have a hell
> of a lot of room in the TCP option field if the SACK option is
> ever standardized.

It is highly unlikely that one would want to run 
50,000 tcp connections at gigabit speeds (you would need a 
lot of buffer space). Thus the problems would appear to 
be orthogonal. 

Given this you could in fact simply overload the timestamp 
option to contain a PCB index. Simply open a connection requesting 
the timestamp option and a zero window scaling factor and use 
the timestamp field to store a PCB index (or poniter if you 
are brave). As define the recievier must treat the timestamp 
as a magic cookie and return it. (It will waste some time 
agonizing about which timestamp to return which in this 
case is irrelevent.) The other side of the connection could 
be using the timestamp for an actual timestamp or could also 
be using it for a PCB pointer. It would not affect the outcome 
in either case. Note that this could add signficant processing 
overhead to very low bandwidth connections.

Sean W. O'Malley 

To: [email-masked]
Reply-To: [email-masked] (Vernon Schryver)
Control: cancel <[email-masked]>
From: [email-masked] (Vernon Schryver)
Subject: cmsg cancel <[email-masked]>
Date: Thu, 3 Sep 1992 17:13:03 GMT
Approved: [email-masked]

cancel <[email-masked]>

To: [email-masked]
Reply-To: [email-masked] (Vernon Schryver)
From: [email-masked] (Vernon Schryver)
Subject: Re: eliminate TCP input demuxing
Date: Thu, 3 Sep 1992 17:12:54 GMT

In article <[email-masked]>, [email-masked] (Steve Wise) writes:
> ....
> 	I've read this paper.  They note at the end that their proposed
> 	hash algorithm REDUCES the need for connection ID passing that
> 	is used in other protocols (TP4, X.25, and XTP are cited). 
> 
> 	I'm wondering what the gain (if any) would be going from the
> 	hash table lookup described by the folks at Sequent to actually
> 	passing some sort of connection ID's...

I know some XTP silicon designers who seemed to me to find the XTP
connection ID equivalent to the TCP/IP 96-bit connection ID of
((host,port)(host,port)).  I think both get hashed to find the
"context."

Vernon Schryver,   [email-masked]					(retrans #3)

To: [email-masked]
Reply-To: [email-masked] (Vernon Schryver)
Control: cancel <[email-masked]>
From: [email-masked] (Vernon Schryver)
Subject: cmsg cancel <[email-masked]>
Date: Thu, 3 Sep 1992 17:11:24 GMT
Approved: [email-masked]

cancel <[email-masked]>

Date: Thu, 3 Sep 1992 09:51:10 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked], [email-masked]
Subject: Re:  TCP demultiplexing

>Granted, PCB pointers is implementation specific, but the idea could be
>generalized...

I think that a better way to think about the problem is to use 
additional information in the TCP header to increase the cache 
size. Suppose we define a TCP option which contains two 16 bit 
values. Each end of the connection assigns a value to each connection
and the other end simply reflects that value. (much in the way 
the timestamps are defined) This value is an index into a very 
large cache of PCB's (up to 64k). When a message arives the value 
in the option is used to look up a TCB. The same steps used to 
check the current single value cache are required. 
	1. check to see if anything is cached in that slot
	2. check to see if the PCB is the right one.

This approach would eliminated security and bad pointer problems 
and allow one to cache the 64k most used connections. 

The problem with all of this is that we don't really have a hell 
of a lot of room in the TCP option field if the SACK option is 
ever standardized. 

Sean O'Malley

ps. I may implement this in our x-kernel TCP (which uses a hash 
table anyway). Anyone have any good test cases?

Subject: TCP demultiplexing
To: [email-masked]
Date: Thu, 3 Sep 92 9:53:00 CDT
From: [email-masked]

>Has there been any discussion about modifying (via RFC + negotiated TCP
>option) TCP to allow the sending of PCB pointers in each TCP packet?
>It seems to me that if at connect time, the TCPs send pass their
>respective PCB pointers, and the pair of pointers are sent in all
>traffic on this particular TCP connection, then on receive, tcp_input()
>would not have to demux at all...
>
>Granted, PCB pointers is implementation specific, but the idea could be
>generalized...

>This could potentially greatly improve TPC/A type performance (mucho 
>connections, small packets, few packet trains)...

We use this method on one of our proprietary protocols. It works very well.
I have wished for it with TCP for awhile now. My problem is that even with a
hash table with 511 slots in it I have to search approximately 50 tables on
average if there are 50,000 connections. I would be interested in any info
on good hashing functions for the socket information since that is all that
you have to hash with. If there are any papers available that discuss this
I would appreciate it someone would let me know.

On the original question, you don't need to pass both pointers with every
message: only the pointer of the destination of the message. Also, the option
would not have to be a pointer per se, but could just be an identifier. The
option could contain the length of the identifier which would allow different
implementations to have different lengths and formats for the identifier. It
is certainly reasonable to put some other information in the identifier other
than the pointer to the connection table. A limit on the identifier length 
would probably be necessary though to limit how much space a receiver would
have to allocate to store the peer's identifier.

Kurt Matthys

From: Christopher Maeda <[email-masked]>
Date: Thu, 3 Sep 92 09:36:52 EDT
To: [email-masked]
Cc: [email-masked]
Subject: eliminate TCP input demuxing 
Reply-To: [email-masked]

   From: [email-masked] (Steve Wise)
   Date: Thu, 03 Sep 92 08:14:31 -0600

	   True.  I guess PCB pointers was a bad choice...maybe connection
	   ID's that are ONLY used by the host sending them.  So, their
	   semantics don't need to be standardized or defined...

Hmm.  I sub-optimally posted my message *before* carefully reading the
McKenney paper (I have the version in Computing Systems).  PCB
pointers are perfectly reasonable when you think about them as
connection ids.

So if you ship around a connection id, I'm assuming you'll stick it in
the tcp options.  (This means you still have to ship around the ip
addresses and tcp port numbers.  Yuck.)  Still, it would be
interesting to implement it and see what kind of savings you get for
various workloads.

The algorithms people have looked at this (the in_pcblookup) problem.
Search for papers on self-adjusting datastructures by {Tarjan,
Sleator}.  There was actually one result that showed the move to front
heuristic was within a constant factor of optimal for certain
distributions of requests.

Chris

From: [email-masked] (Steve Wise)
To: [email-masked]
Cc: [email-masked]
Subject: Re: eliminate TCP input demuxing 
Date: Thu, 03 Sep 92 08:14:31 -0600

| A number of problems with this approach:
| 
| (1) Your tcp might be implemented in a language with garbage collected
| storage.  The pcb may get moved around during a gc.

	True.  I guess PCB pointers was a bad choice...maybe connection
	ID's that are ONLY used by the host sending them.  So, their
	semantics don't need to be standardized or defined...

	The remote TCP simply echos the ID you sent at connection time
	in every packet destined for this connection.  Since the remote
	TCP does not use the ID,semantics do not have to be agreed upon
	between both TCPs.  One side could use it's ID as a pointer to
	a PCB, while the other side uses it's ID as an index into an
	array...  
| (2) How big is a pointer?  
|     16bits?  18bits? 32bits?  64bits?  What byte order?

	Right.  Pointer is a bad choice...I would choose 32 bits :-)
| 
| (3) If you don't very carefully check to see that the pointer points
| to a real piece of memory that is in fact a pcb, you could crash your
| machine or even create a potential security hole.

	Yep.  There would be overhead in verifying this.  Assuming the
	remote TCP is compliant to the proposed RFC would not be wise
	especially if you're passing memory pointers around...

Stevo.	

From: [email-masked] (Steve Wise)
To: [email-masked] (William E. Fisher)
Cc: [email-masked], [email-masked]
Subject: Re: eliminate TCP input demuxing 
Date: Thu, 03 Sep 92 08:08:39 -0600

| One paper that was recnetly published in measuring the PCB lookup overhead was:
| 
| 1992 ACM SIGCOMM Conference Proceedings
| August 17-20, 1992, Baltimore, Maryland
| 
| Efficient Demultiplexing of Incoming TCP Packets
| Paul McKenney and Ken Dove
| Sequent Computer Systems
| 
| The paper covers a number of different algorithms and presents some analytical
| approximations to describe the behavior of various TCP demultiplexing algorithms
| when presented with packet traffic resulting from running the TPC/A benchmarks.

	I've read this paper.  They note at the end that their proposed
	hash algorithm REDUCES the need for connection ID passing that
	is used in other protocols (TP4, X.25, and XTP are cited). 

	I'm wondering what the gain (if any) would be going from the
	hash table lookup described by the folks at Sequent to actually
	passing some sort of connection ID's...

From: [email-masked] (William E. Fisher)
Subject: Re: eliminate TCP input demuxing
To: [email-masked] (Steve Wise)
Date: Wed, 2 Sep 92 18:41:29 PDT
Cc: [email-masked], [email-masked], [email-masked]

>  
> | Since you asked...
> | 
> | You are right that in the case of packet trains (this packet is the
> | same as the last) there is no performance difference because a simple
> | check to see that this packet is the same as the previous one will
> | allow you to have the PCB pointer already validated without processing
> | any option fields.
> | 
> | Tell me, how much faster is validating this option verses finding the
> | PCB from scratch?
> | 
> | If the packet is not part of a train, the you must at least validate
> | that the PCB is still valid and indeed for this connection.
> | 
> | Has the search been optimized?
> | 
> | If the search is log n, [n connections open], then the average search
> | cost is 1/2 log n.
> | 
> | With significantly large hash tables then the overhead would be (on
> | the average) a simple hash, single look up, and a simple verification.
> | 
> | If you use the PCB option, what is the validation cost? What is the
> | cost of pulling the PCB "cookie" out of the options?
> | 
> | Have you MEASURED that IP lookup is indeed a high overhead point in
> | your implementation? I have measured several TCP implementations and
> | in the ones I have measures (not IBM) the total elimination IP lookup
> | would not make a significant difference. Thread signalling, thread
> 
> 	Are you measuring thousands of connections, each sending small
> 	packets intermittently?  
> 
> | dispatches, data copies, Mbuf allocation, timer maintance, page fixing
> | and or flushing are all areas to significantly improve the protocol
> 
> 	Yes, these are all areas which need to be dealt with.  Assuming,
> 	however, that you can do input path with one data copy, then
> 	maybe the demux time becomes important for reducing CPU usage
> 	in DB & OLTP environments...
> 
> | implementation without resorting [even gracefully] changing the
> | protocol.
> 
> 	I agree.  Again, just wondering if folks have considered
> 	the approach I mentioned.  I believe this type of demuxing
> 	is done by other networks/protocols?  Like Ultra-net?  XTP?
> 
> 
> 	Currently in AIX 3.2, we're using a linear search (ala RENO)
> 	to find the PCB.  If it was the last one accessed, we don't
> 	have to search.  I am aware of the hash table algorithms and
> 	realize that this will help.  
> 
One paper that was recnetly published in measuring the PCB lookup overhead was:

	1992 ACM SIGCOMM Conference Proceedings
	August 17-20, 1992, Baltimore, Maryland

	Efficient Demultiplexing of Incoming TCP Packets
	Paul McKenney and Ken Dove
	Sequent Computer Systems

The paper covers a number of different algorithms and presents some analytical
approximations to describe the behavior of various TCP demultiplexing algorithms
when presented with packet traffic resulting from running the TPC/A benchmarks.

The McKenney and Dove paper also references some of the original e-mail
postings on this subject posted to the tcp-ip mailing list.

1) Jon Crowcroft. Re: Inefficient dfemultiplexing by 4.3 TCP/IP
   Message-ID [email-masked], to the tcp-ip mailing list, December 1991

2) Lance Visser. Re: Inefficient dfemultiplexing by 4.3 TCP/IP
   Message-ID [email-masked] to the tcp-ip mailing list,
   December 1991

On other paper which might be of interest is:

	Multiplexing Issues in Communciation System Design
	David Fieldmeier
	1990 ACM SIGCOMM Conference Proceedings, Pages 209-219
	September 1990, Philadelphia, PA

-- Bill

From: Christopher Maeda <[email-masked]>
Date: Wed, 2 Sep 92 21:09:11 EDT
To: [email-masked]
Cc: [email-masked]
Subject: eliminate TCP input demuxing
Reply-To: [email-masked]

   From: [email-masked] (Steve Wise)
   Date: Wed, 02 Sep 92 16:41:15 -0600

   Has there been any discussion about modifying (via RFC + negotiated TCP
   option) TCP to allow the sending of PCB pointers in each TCP packet?
   It seems to me that if at connect time, the TCPs send pass their
   respective PCB pointers, and the pair of pointers are sent in all
   traffic on this particular TCP connection, then on receive, tcp_input()
   would not have to demux at all...

A number of problems with this approach:

(1) Your tcp might be implemented in a language with garbage collected
storage.  The pcb may get moved around during a gc.

(2) How big is a pointer?  16bits?  18bits?  32bits?  64bits?  What byte order?

(3) If you don't very carefully check to see that the pointer points
to a real piece of memory that is in fact a pcb, you could crash your
machine or even create a potential security hole.

Chris

From: [email-masked] (Steve Wise)
To: [email-masked] (Jim Hughes)
Cc: [email-masked]
Subject: Re: eliminate TCP input demuxing 
Date: Wed, 02 Sep 92 19:24:29 -0600

| Since you asked...
| 
| You are right that in the case of packet trains (this packet is the
| same as the last) there is no performance difference because a simple
| check to see that this packet is the same as the previous one will
| allow you to have the PCB pointer already validated without processing
| any option fields.
| 
| Tell me, how much faster is validating this option verses finding the
| PCB from scratch?
| 
| If the packet is not part of a train, the you must at least validate
| that the PCB is still valid and indeed for this connection.
| 
| Has the search been optimized?
| 
| If the search is log n, [n connections open], then the average search
| cost is 1/2 log n.
| 
| With significantly large hash tables then the overhead would be (on
| the average) a simple hash, single look up, and a simple verification.
| 
| If you use the PCB option, what is the validation cost? What is the
| cost of pulling the PCB "cookie" out of the options?
| 
| Have you MEASURED that IP lookup is indeed a high overhead point in
| your implementation? I have measured several TCP implementations and
| in the ones I have measures (not IBM) the total elimination IP lookup
| would not make a significant difference. Thread signalling, thread

	Are you measuring thousands of connections, each sending small
	packets intermittently?  

| dispatches, data copies, Mbuf allocation, timer maintance, page fixing
| and or flushing are all areas to significantly improve the protocol

	Yes, these are all areas which need to be dealt with.  Assuming,
	however, that you can do input path with one data copy, then
	maybe the demux time becomes important for reducing CPU usage
	in DB & OLTP environments...

| implementation without resorting [even gracefully] changing the
| protocol.

	I agree.  Again, just wondering if folks have considered
	the approach I mentioned.  I believe this type of demuxing
	is done by other networks/protocols?  Like Ultra-net?  XTP?

	Currently in AIX 3.2, we're using a linear search (ala RENO)
	to find the PCB.  If it was the last one accessed, we don't
	have to search.  I am aware of the hash table algorithms and
	realize that this will help.  

STevo.

From: [email-masked] (Jim Hughes)
Subject: Re: eliminate TCP input demuxing
To: [email-masked] (Steve Wise)
Date: Wed, 2 Sep 92 19:16:57 EDT
Cc: [email-masked]

> 
> 
> Hi!
> 
> Has there been any discussion about modifying (via RFC + negotiated TCP
> option) TCP to allow the sending of PCB pointers in each TCP packet?
> It seems to me that if at connect time, the TCPs send pass their
> respective PCB pointers, and the pair of pointers are sent in all
> traffic on this particular TCP connection, then on receive, tcp_input()
> would not have to demux at all...
> 
> Granted, PCB pointers is implementation specific, but the idea could be
> generalized...
> 
> This could potentially greatly improve TPC/A type performance (mucho 
> connections, small packets, few packet trains)...
> 
> Any thoughts?

Since you asked... 

You are right that in the case of packet trains (this packet is the
same as the last) there is no performance difference because a simple
check to see that this packet is the same as the previous one will
allow you to have the PCB pointer already validated without processing
any option fields.

Tell me, how much faster is validating this option verses finding the
PCB from scratch?

If the packet is not part of a train, the you must at least validate
that the PCB is still valid and indeed for this connection. 

Has the search been optimized?

If the search is log n, [n connections open], then the average search
cost is 1/2 log n. 

With significantly large hash tables then the overhead would be (on
the average) a simple hash, single look up, and a simple verification.

If you use the PCB option, what is the validation cost? What is the
cost of pulling the PCB "cookie" out of the options?

Have you MEASURED that IP lookup is indeed a high overhead point in
your implementation? I have measured several TCP implementations and
in the ones I have measures (not IBM) the total elimination IP lookup
would not make a significant difference. Thread signalling, thread
dispatches, data copies, Mbuf allocation, timer maintance, page fixing
and or flushing are all areas to significantly improve the protocol
implementation without resorting [even gracefully] changing the
protocol.

> Steve Wise	IBM AWD - Austin, TX.

But I am open to other thoughts.

jim

From: [email-masked] (Steve Wise)
To: [email-masked]
Subject: eliminate TCP input demuxing
Date: Wed, 02 Sep 92 16:41:15 -0600

Hi!

Has there been any discussion about modifying (via RFC + negotiated TCP
option) TCP to allow the sending of PCB pointers in each TCP packet?
It seems to me that if at connect time, the TCPs send pass their
respective PCB pointers, and the pair of pointers are sent in all
traffic on this particular TCP connection, then on receive, tcp_input()
would not have to demux at all...

Granted, PCB pointers is implementation specific, but the idea could be
generalized...

This could potentially greatly improve TPC/A type performance (mucho 
connections, small packets, few packet trains)...

Any thoughts?

********
Steve Wise	IBM AWD - Austin, TX.
Internal: 	[email-masked]
VNET:		AUSVMQ(SWISE)
Internet:	[email-masked]