We consider five aspects of web caching benefits: hit ratio, byte hit ratio, latency reduction, hop reduction, and weighted-hop reduction. By hit ratio, we mean the number of requests that hit in the proxy cache as a percentage of total requests. By byte hit ratio, we mean the number of bytes that hit in the proxy cache as the percentage of the total number of bytes requested. By latency reduction, we mean the percentage of the sum of downloading latency for the pages that hit in cache over the sum of all downloading latencies. Hop reduction and weighted-hop reduction are used to measure the effectiveness of the algorithm at reducing network costs, as explained below.
To investigate the regulatory role that can be played by proxy caches, we model the network cost associated with each document as ``hops''. The ``hops'' value can be the number of network hops travelled by a document, to model the case when the proxy tries to reduce the overall load on Internet routers, or it can be the monetary cost associated with fetching the document, to model the case when the proxy has to pay for documents travelling through different network carriers.
We evaluate the algorithms in a situation where there is a skew in
the distribution of ``hops'' values among the documents.
The skewed distribution models the case when a particular part of the network
is congested, or the proxy has to pay
a different amount of money for documents travelling through different networks
(for example, if the proxy is at an Internet Service Provider).
In our particular simulation, we assign each Web
server a hop value equal to 1 or 32 
, so that
1/8 of the servers have hop value 32 and 7/8 of the servers have hop
value 1.
This simulates the scenario, for example, that
1/8 of the web servers contacted are located in Asia, or can only
be reached through an expensive or congested link.
Associated with the ``hop'' value are two metrics: hop reduction and weighted-hop reduction. Hop reduction is the ratio between the total number of the hops of cache hits and the total number of the hops of all accesses; weighted-hop reduction is the corresponding ratio for the total number of hops times ``packet savings'' on cache hits. A cache hit's packet saving is 2 + file_size/536 , as an estimate of the actual number of network packets required if the request is a cache miss (1 packet for the request, 1 packet for the reply, and size/536 for extra data packets, assuming a 536-byte TCP segment size).
For each trace, we first calculate the benefit obtained if the cache size is infinite. The values for all traces are shown in Table 1. In the table, BU-272 and BU-B19 are two sets of traces from Boston University [CBC95], VT-BL, VT-C, VT-G, VT-U are four sets of traces from Virginia Tech [WASAF96], DEC-U1:8/29-9/4 through DEC-U1:9/19-9/22 are the requests made by users 0-512 (user group 1) for each week in the three and half week period, and DEC-U2:8/29-9/4 through DEC-U2:9/19-9/22 are the traces for users 1024-2048 (user group 2). We experimented with other subsets of DEC traces and the results are quite similar to those obtained from these subsets.
Table 1: Benefits under a cache of infinite size for each trace, measured
as hit ratio, byte hit ratio, latency reduction, hop reduction, and weighted-hop reduction.
Below, we divide our results into three subsections. In Section 5.2, we measure the hit rate and byte hit rate of different algorithms. In Section 5.3 we compare the latency reduction. In Section 5.4 we compare the hop reduction and weighted hop reduction. The corresponding value under the infinite cache are listed in Table 1. Since these simulations assume limited cache storage, their ratios cannot be higher than the infinite cache ratios.
The cache sizes investigated in the simulation were chosen by taking a fixed
percentage of the total sizes of all distinct documents requested in the
sequence. The percentages are 0.05%, 0.5%, 5%, 10% and 20%.
For example, for trace DEC-U1:8/29-9/4, which includes the requests made by users
0-512 for the week of 8/29 to 9/4 and has a total data set size of 9.21GB,
the cache sizes experimented are 4.6MB, 46.1MB,
461MB, 921MB
and 1.84GB.
Due to space limitation, we organize the traces into four groups: Boston University traces, Virginia Tech traces, DEC-U1 traces, and DEC-U2 traces, and present the averaged results per trace group. The results for individual traces are similar.
