Limit Study Results

**Figure 3:** Fraction of requests that are serviced by the prefetch buffer (the first number specifies the lookahead, the second number specifies the prefetch buffer size).
$\begin{figure} \psfig {figure=graphs/limit_saves.eps,angle=270,height=3in}\end{figure}$

Figure 3 shows the fraction of requests that are serviced by the prefetch buffer for users connected to the proxy via 56Kbps modems, under different lookaheads (256, 8 or 4) and with different prefetch buffer sizes (16MB, 2MB or 256KB). Around 60% of user requests (that miss in the browser cache) are serviced by the prefetch buffer. In the case of the 256 look ahead and large buffer every document that is not seen for the first time is serviced by the prefetch buffer. Even with the minimal look ahead there is opportunity to prefetch nearly every request. The requests serviced by the prefetch buffer are broken into three categories. The first category is the cache affect. This is the case when a requests is for a document in the prefetch buffer that has already been used at least once since being brought into the buffer. This occurs in limited cases where the browser either doesn't have a cache, or the cache doesn't use the LRU replacement policy. The second category are requests that first use a document that has been brought into the buffer. This is the case of true prefetching. The third category is a special case of the second where the document the request is for is in the process of being brought into the buffer when the user requests it. In this last case the user sees a partial reduction in latency.

**Figure 4:** Request Savings, Latency Reduction and Extra Bandwidth.
$\begin{figure} \psfig {figure=graphs/limit_everything.eps,angle=270,height=3in}\end{figure}$

Figure 4 shows, for the same lookahead and buffer size combination, the fraction of requests serviced by the prefetch buffer, the average reduction in latency seen by the user and the extra bandwidth consumed by prefetching. The latency reduction is considerably smaller than the fraction of requests serviced by the prefetch buffer. The major reasons for this is that prefetching can only be used on requests that hit in the proxy cache, these requests on average have a smaller latency than requests that require accessing a server over the Internet. We also see that there is wasted bandwidth even with perfect prediction and in one case it is significant. This is an artifact of the prefetch buffer management where we may replace a document with one that has a lower prefetch probability (occurs later). This is discussed in Section 3.2. In the case of the 256 look ahead and the small buffer there is extreme pressure on the prefetch buffer and we see that this effect is significant, in the other cases the impact is minimal.

**Figure 5:** Breakdown of latency reduction.
$\begin{figure} \psfig {figure=graphs/limit_breakdown.eps,angle=270,height=3in}\end{figure}$

The latency reduction for the long look ahead is significantly larger than the reduction for more moderate look ahead even though the fraction of requests serviced by the prefetch buffer varies only slightly. The reason for this can be seen when we break the latency savings down to user latency hidden and contention avoidance, Figure 5. The user latency hidden is calculated by determining the amount of time the user would have waited for a document to be fetched if it had not been in the prefetch buffer. The contention avoidance is calculated by taking the total latency observed when there is no prefetching and comparing it to the total latency observed with prefetching plus the latency that was directly hidden by prefetching. We see that the long look ahead has significantly larger savings due to contention avoidance. This is logical because the ability to reduce contention is strongly dependent on how far you can move requests in order to capitalize on idle periods.

The latency directly hidden by prefetching is a direct result of prefetching. Some contention avoidance will occur from prefetching, but it is not clear that some, or even most, of the contention avoidance is an artifact of the trace driven nature of the simulation. Many requests are the direct result of a directive encoded into a preceding request. If the first request was serviced earlier the subsequent request would be issued earlier, but our simulations due not take this into account. In the case that there is a long chain of overlapping requests (each caused by the previous) our simulator may be able to move the first one earlier and it will observe that the requests now no longer overlap.

In the case of the moderate look ahead there is only minimal latency reduction due to contention avoidance and most of the user latency reduction is due to the direct hiding of latency due to prefetching. The next section will show that in for real predictors the contention avoidance is also a minimal impact.