Prefetch Buffer

  The prefetch buffer is implemented as a cache. We model various size prefetch buffers from 256 Kilobytes to 16 Megabytes. The replacement policy of the user's prefetch buffer is a combinations of two different policies. First, the buffer implements a LRU policy for the pages in the buffer. During the prefetching sequences the buffer management is slightly modified. The first document of a prefetch sequence is ordered as the most recently used (highest priority), the second document is ordered as the second most recently used and so on. This ordering is implemented because documents are sent in the order of decreasing probability.

A prefetched document should not replace a higher probability document of the same prefetch sequence. The proxy attempts to detect this case and stop pre-pushing when it occurs, but it uses a simple mechanism that can not detect all cases. When the prefetch buffer is full and there are more pages to prepush the least-recently used (lowest priority) document in the buffer is checked to see if it is a higher probability document of the same prefetch sequence. If the new document is larger than the lowest priority document it may force multiple documents out of the buffer, some of these additional documents may be of a higher probability than the new document.