Jason Thorpe <thorpej@nas.nasa.gov> writes:

> 
> Another way to improve the performance of the address list is to use
> the notion of temporal locality to dynamically re-sort the list.  It
> was observed by a co-worker here at the NAS facility (while he was
> busy working on a tcp connection tracing and modeling tool) that
> if you recieve a packet associated with a given connection, chances
> are that you are very likely to see another packet associated with
> that connection within a short period of time.

That observation is not true for servers that have many clients, like
high-volume WWW servers (which is the case at hand).  It is often true
for end-user workstations, but they're not likely to have many IP
addresses, and there are already mechanisms for dealing with the
searching the connection list.

Implementing some sort of fast lookup would also speed up
SIOC[ADSG]IF{ADDR,BRDADDR,DSTADDR,NETMASK}, although in several of
these cases using if_addrlist to find the first address might work
just as well.  Preferrably, the implementation would be
protocol-independent.

> In his tool, he was able to _dramatically_ increase the performace
> of tracing all connections occuring on a well-used network here simply
> by placing the "packet list" at the beginning of the "all connections"
> list whenever he encountered a packet for that connection.

Indeed; the same assumption is the origin of the single-entry PCB
cache implemented in 4.3BSD for both TCP and UDP.  Again, for servers
with many clients, this is not useful.  In fact, searching the TCP
connection list is one of the things that was hosing pain some time
ago, which caused me to implement a connection hash table.