Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!hc!pprg.unm.edu!unmvax!tut.cis.ohio-state.edu!rutgers!bellcore!ka9q.bellcore.com!karn
From: karn@ka9q.bellcore.com (Phil Karn)
Newsgroups: comp.protocols.tcp-ip
Subject: Re: routing hash table sizes on 4.3bsd
Message-ID: <13268@bellcore.bellcore.com>
Date: 6 Jan 89 20:12:56 GMT
References: <11066@ulysses.homer.nj.att.com>
Sender: news@bellcore.bellcore.com
Reply-To: karn@ka9q.bellcore.com (Phil Karn)
Organization: Secular Humanists for No-Code
Lines: 15


Another thing I'd suggest to anyone thinking of redoing the routing lookup
routines is something I've put in my own code that seems to work pretty well.

Each time you find the entry you're looking for in a hash chain, move that
entry to the top of the list.  When a router sees a given address it is very
likely to see that same address again fairly soon, so this constitutes a
cheap form of caching that should reduce the average search length.

Depending on how expensive the hash function is, it might also be worthwhile
to put a very small direct-mapped cache on top of the whole lookup function.
This would help greatly when handling rapid bursts of data between the same
two points.

Phil