Another major concern for proxies is to reduce the latency of HTTP requests through caching, as numerous studies have shown that the waiting time has become the primary concern of Web users. One study [WA97] introduced a proxy replacement algorithm called Hybrid, which takes into account the different latencies incurred to load different web pages, and attempts to minimize the average latency. The study [WA97] further showed that in general the algorithm has a lower average latency than LRU, LFU and SIZE.
We also designed two versions of GreedyDual-Size that take latency
into account. One, called
GD-Size(latency), sets the cost of
a document to the latency that was required to download the document.
The other, called GD-Size(avg_latency), sets the cost to
the estimated download latency of a document, using the same
method of estimating latency as in Hybrid [WA97].
Figure 7: Latency, hops, and weighted hops reductions under various
algorithms.
Figure 7(a) shows the latency reductions for LRU, Hybrid,
GD-Size(1), GD-Size(latency) and
GD-Size(avg_latency).
The graphs, from left to right, show the results for Boston University
traces, DEC-U1 traces and DEC-U2 traces.
The figure unfortunately does not include results for Virginia Tech traces
because they do not have latency information for each HTTP request.
Clearly, GD-Size(1) performs the best, yielding
the highest latency reduction.
GD-Size(latency) and GD-Size(packets) finish the second, with
LRU following close behind. GD-Size(avg_latency) performs badly for
small cache sizes, but performs very well for relatively large cache
sizes. Finally, Hybrid performs the worst.
Examination of the results shows that the reason for Hybrid's poor performance is its low hit ratio. In the Boston University traces, Hybrid's hit ratio is much lower than LRU's for cache sizes <= 5% of the total data set sizes, and only slightly higher for larger cache sizes. For all DEC traces, Hybrid's hit ratio is much lower than LRU's, under all cache sizes. Hybrid has a low hit ratio because it does not consider how recently a document has been accessed during replacement.
Since [WA97] reports that Hybrid performs well, our results here seem to suggest that Hybrid's performance is perhaps trace-dependent. In our simulation of Hybrid we used the same constants in [WA97], without tuning them to our traces. Unfortunately we were not able to obtain the traces used in [WA97].
It is a surprise to us that GD-Size(1), which does not take latency into account, performs better than GD-Size(latency) and GD-Size(avg_latency). Detailed examination of the traces shows that the latency of loading the same document varies significantly. In fact, for each of the DEC traces, variance among latencies of the same document ranges from 5% to over 500%, with an average around 71%. Thus, a document that was considered cheap (taking less time to download) may turn out expensive at the next miss, while a document that was considered expensive may actually take less time to download. The best bet for the replacement algorithm, it seems, is to maximize hit ratio.
In summary, GD-Size(1) is the best algorithm to reduce average latency. The high variance among loading latencies for the same document reduces the effectiveness of latency-conscious algorithms.
