| |||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
2nd USENIX Symposium on Internet Technologies & Systems, 1999
[Technical Program]
Hyokyung Bahn*, Sam H. Noh**,
Sang Lyul Min***, Kern Koh* * Department of Computer Science, Seoul National University, Seoul
151-742, Korea.
http://oslab.snu.ac.kr **
Department of Computer Engineering, Hong-Ik University, Seoul
121-791, Korea.
http://www.cs.hongik.ac.kr/~noh ***
Department of Computer Engineering, Seoul National University, Seoul
151-742, Korea. http://archi.snu.ac.kr Abstract With the increase in popularity
of the World Wide Web, the research community has recently seen a proliferation
of Web caching algorithms. This paper presents a new such algorithm, that is
efficient and robust, called Least Unified-Value (LUV). LUV evaluates a Web document
based on its cost normalized by the likelihood of it being re-referenced. This
results in a normalized assessment of the contribution to the value of a
document, leading to a fair replacement policy. LUV can conform to arbitrary
cost functions of Web documents, so it can optimize any particular performance
measure of interest, such as the hit rate, the byte hit rate, or the
delay-savings ratio. Unlike most existing algorithms, LUV exploits complete
reference history of documents, in terms of reference frequency and recency, to
estimate the likelihood of being re-referenced. Nevertheless, LUV allows for an
efficient implementation in both space and time complexities. The space needed to
maintain the reference history of a document is only a few bytes and furthermore,
the time complexity of the algorithm is O(log2n), where n is the
number of documents in the cache. Trace-driven simulations show that the LUV
algorithm outperforms existing algorithms for various performance measures for
a wide range of cache configurations. 1.
Introduction In an
effort to relieve the problem of network congestion and latency on the World
Wide Web (WWW), the research community has recently seen a proliferation of Web
cache replacement algorithms [1, 2, 3, 5, 6, 8, 9, 10, 14]. This paper presents
yet another such algorithm. However, the algorithm that we propose has the
following salient features: ·
First, it shows the best performance for a wide range of cache configurations
in terms of popular performance measures used in evaluating Web caching
algorithm, namely, the hit rate, the byte hit rate, and the delay-savings ratio.
·
Second, the proposed algorithm makes full use of all of the past activities, in
terms of reference frequency and recency, made upon the Web cache in deciding
which document to evict. By so doing, it not only accurately distinguishes actively
referenced documents and those that are not so, i.e. hot and cold documents,
but it also distinguishes those documents that are hot but are getting colder,
and those that are cold but are getting hotter. This is the main reason behind
the superior performance. ·
Third, the implementation of the replacement algorithm is efficient in both
space and time complexities. The space needed to maintain the reference history
of a document is only a few bytes per document and furthermore, the time
complexity of the algorithm is O(log2 n), where n is the number of
documents in the cache. This is a feature that is not easy to satisfy when the
size of the document and cost of fetching documents from remote sites have to
be incorporated into the algorithm, as it is in Web caching [5,6,8]. ·
Fourth, the replacement algorithm retains the above features irrespective of
what the performance measure of interest is. As mentioned above, in Web caching
environments, the typical performance measures of interest are the hit rate,
the byte hit rate, and the delay-savings ratio. The proposed algorithm can
easily be conformed to execute based on a particular performance measure. This
is unlike many previous algorithms that tightly couple the optimization of a
particular performance measure into the algorithm itself. Before
describing the algorithm, we describe, in the next section, the measures that
have been the focus of interest and optimization in the Web caching realm. We
also briefly make comparisons of previously presented algorithms. We focus on
the differences and main features of the algorithms rather than describing them
individually in detail. In Sections 3 and 4, we describe the proposed
algorithm, namely, the Least Unified-Value (LUV) algorithm and its
implementation. In Section 5, we describe the results of the simulation
experiments, and compare LUV’s performance with previously proposed algorithms.
Finally, we conclude in Section 6. 2.
Performance Measures and Related Works Performance
measures of interest in the Web caching realm can be defined according to the
goal of caching. The three popular performance measures used in Web caching,
that is, the hit rate, the byte hit rate, and the delay-savings ratio, denoted
as HR, BHR, and DSR, respectively, can be described as follows: HR
= ∑hi / ∑ri BHR
= ∑(si * hi ) / ∑(si
* ri ) DSR
= ∑(di * hi ) / ∑(di
* ri )
where hi : number of hit references to document
i, ri : total number of references to document
i (number of hits + number of misses), si : size of document i, di : delay time to fetch document i
from the original server to the cache. HR is the measure
used in traditional caching systems such as file caching and database buffer
management, and represents the number of hit references over the total number
of references. BHR represents the number of bytes saved from retransmission by using
the cache over the total amount of bytes referenced. BHR considers the size of the
Web document, but does not consider the difference in retrieval costs. Among
documents that are of the same size, those that incur higher cost in retrieving
the document should be retained in the cache longer than those that incur lower
cost. DSR, which considers this matter in terms of retrieval latency,
represents the reduced latency by virtue of a cache hit over the total latency incurred
when assuming caches are not used [8]. One may also define other new
performance measures that reflect the focus of interest one wants to measure.
For example, Kelley et al. define VHR (value hit rate) which represents a
normalized measure of social welfare [14]. In this case, performance is measured
by simply replacing the delay time (di ) in DSR by value in VHR. Many of
the previous algorithms proposed for Web caching have attempted to optimize
performance for one particular measure. The LRU, LFU, SIZE [9], HYBRID [10],
and LNC-R-W3 [8] are such algorithms (Note the Performance Measure column of
Table 1). These algorithms have a weakness that as the performance measure of
interest changes due to circumstantial changes, they have difficulty in
adjusting to these changes. The GD-SIZE [2], LRV [5], sw-LFU [14], and LUV
algorithms, on the other hand, are robust to changes in the performance measure
of interest. However, for the LRV algorithm, the time complexity varies
according to the performance measures. While the algorithm is efficient for the
byte hit rate measure, for other measures the complexity of the algorithm is
O(n), which makes it impractical as an on-line algorithm. For this reason, a recent version of LRV restricts their optimization
of the algorithm to only the byte hit rate measure [15]. Another weakness of
the LRV is that its replacement decision is based on extensive empirical
analysis of trace data. Finally, the
MIX algorithm tries to optimize the combination of the three measures, i.e.,
HR, BHR, and DSR [6]. For
caching algorithms to be practical, it is important that the time complexity of
the algorithm not be excessive, preferably not higher than O(log2 n)
where n is the number of documents in the cache [2,4]. Algorithms that do not
meet this criterion are the LNC-R-W3 and MIX algorithms (Note the Complexity
column of Table 1). In terms
of maintaining previous reference history, most of the algorithms maintain and
use the recency of the last reference to the document, with the exception of
the LNC-R-W3 algorithm that uses the k-th reference (Note the Maintaining
Reference History column of Table 1). The LNC-R-W3 algorithm uses a strategy
similar to the LRU-k algorithm that was proposed for buffer caching [7]. In
contrast, the LUV algorithm, as we will show later, uses the reference recency
history of all past references. As for the
reference frequency history, some algorithms simply use the frequency count,
while others combine this information with the recency history that is
maintained. The GD-SIZE algorithm,
however, does not consider any frequency information. Again, note that the LUV
algorithm uses the frequency count as well as the recency history of all prior
references to a document. Another
aspect that may be considered in classifying replacement algorithms is the way
in which reference history is maintained. Basically, there are two ways to
maintain the reference history of documents. One is in-cache-history and the
other is perfect-history. The in-cache-history method retains the reference
history of only those objects that are in the cache. Hence, reference
information is lost once the object is evicted. On the other hand, the perfect-history
method retains the reference history of an object even after its eviction,
allowing this information to be used when it returns to the cache. This method
may offer considerable information about the reference behaviors, resulting in
better prediction of future references than the in-cache-history method.
However, it incurs more space and time overhead for maintaining the information
of the evicted objects. To resolve this problem, perfect-history algorithms may
choose to retain approximations of the reference history. Breslau et
al. show that perfect-history LFU outperforms in-cache-history LFU in terms of
HR and BHR [13]. Recency history, i.e. reference time information, can also be
maintained as either in-cache-history or perfect-history. In fact, most caching
algorithms may be implemented using both in-cache-history and perfect-history
methods. However, this paper basically deals with in-cache-history algorithms
with the exception of some
algorithms that inherently use perfect-history such as the LNC-R-W3 and LRV
algorithms. Other algorithms shown in Table 1 are in-cache-history algorithms
unless explicitly stated. Other features of various Web caching algorithms,
including advantages and weaknesses, are summarized in Table 1.
3. The LUV (Least Unified-Value) Algorithm In this
section, we describe the Least Unified-Value (LUV) replacement algorithm. LUV
evaluates a Web document based on its retrieval cost normalized by the
likelihood of it being re-referenced. This results in a normalized assessment
of the contribution to the value of a document, leading to a fair replacement
policy. Like most existing algorithms, LUV associates a value Value(i) to each
document i in the cache and, when needed, replaces the document that has the
smallest Value. Value(i) in LUV is defined as
Value(i) = Weight(i) *H(i). Weight(i) denotes the retrieval cost of a document per unit
size and is defined as
Weight(i) = ci / si where ci
and si denotes the cost and the size of document i, respectively. ci
can be defined differently according to the performance measure of interest,
and for the HR, BHR, and DSR measures, the ci value used would
normally be 1, the document size, and the download latency, respectively. For
other measures such as social welfare as referred to by Kelly et al. [14], one
can define ci appropriately for the performance measure of interest.
H(i) represents
the likelihood of re-reference, that is, the worth of the document based on
observations of past behavior. For the LUV algorithm, this is based on the
recency and frequency history of all of the past references on document i. This
notion is taken directly from the LRFU replacement policy [4]. Each reference
to a document i in the past contributes to H(i) and a reference’s contribution
is determined by a weighing function F(x) where x is the time span from the
reference in the past to the current time. For example, assume that document i
was referenced at t1, t2, and t3. Then, H(i)
at current time, tc, is computed by H(i) = F(d 1 ) + F(d 2 ) + F(d 3 ) where d 1= tc – t1,
d 2= tc – t2,
and d
3= tc –
t3. A formal
definition of H(i) is, then, given as
H(i) = ∑k=1,2,…,n F(tc – tk ) where tc
is the current time, n is the number of references made to document i since it
has been brought into the cache, and tk is the time of the k-th reference. F(x) would
generally be a decreasing function as more weight should be given to more
recent references. In this paper, we use the function that was chosen in the
original LRFU presentation [4], that is, F(x)=(1/2)lx | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
