Implementation Concerns

The above ``champion'' algorithms vary in time and space complexity. In the cases when there are a large number of documents in the cache, this can have a dramatic effect on the time required to determine which document to evict.

• LRU can be implement easily with O(1) overhead per cached file and O(1) time per access;
• Size can be implemented by maintaining a priority queue on the documents in memory based on their size. Since the size of a document does not change, handling a hit requires O(1) time and handling an eviction requires time, where k is the number of cached documents.
• Hybrid is also implemented using a priority queue, thus requiring time to find a replacement. Furthermore, it requires an array keeping track of the average latency and bandwidth for every Web server. It is used in estimating the downloading latency of a web page. This requires extra storage. In addition, since the estimate is updated every time a connection to the server is made, a faithful implementation requires updating many pages' latency estimation. We found this prohibitively time-consuming, and we omit the step in the implementation. We find that omitting the step does not affect our results significantly.
• LRV requires O(1) storage per cached file plus some bookkeeping information. If the Cost in LRV is proportional to Size, the authors of the algorithm suggests an efficient method that can find the replacement in O(1) time, though the constants can be large. If Cost is arbitrary, then O(k) time is needed to find a replacement. We also found that the cost of calculating D(t) are very high, since it uses log and exp.

Another concern about both Hybrid and LRV is that they employ constants which might have to be tuned to the patterns in the request stream. For Hybrid, we use the values which were used in  [WA97] in our simulations. We did not experiment with tuning those constants to improve the performance of Hybrid.

Though LRV can incorporate arbitrary network costs associated with documents, the O(k) computational complexity of finding a replacement can be prohibitively expensive. The problem is that D(t) has to be recalculated for every document every time some document has to be replaced. The overhead makes LRV impractical for proxy caches that wish to take network costs into consideration.