  The size of computer networks, along with their bandwidths, is growing
exponentially. To support these large, high-speed networks, it is neccessary to
be able to forward packets in a few microseconds. One part of the forwarding
operation consists of searching through a large address databse. This problem
is encountered in the design of bridges, routers, gateways and name servers.
  Caching can reduce the lookup time if there is a locality in the address
reference pattern. Using a destination reference trace measured on an extended
local are a network, we attempt to see if the destination refernces do have a
significant locality.
  We compared the performance of MIN, LRU, FIFO, and random cache replacement
algorithms. We found that the interactive (terminal) traffic in our sample had
quite different locality behavior than that of the noninteractive traffic. The
interactive traffic did not follow the LRU stack model while the
noninteractivetraffic did. Examples are shown of the environments in which
caching can help as well as those in which caching can hurt, unless the cache
size is large.
