Adaptive object cache pre-fetching scheme based on object flow

In this paper, we present a Web caching and pre-fetching scheme based on the concept of object flows. The scheme maintains a weighted directed flow graph whose vertices represent the objects accessed by the users and whose edges represent the reference flow relationships between these objects. Each directed edge in the graph is weighted in proportion to the frequency of occurrence of the reference sequence represented by that edge. Edge weights are adaptively changed to capture new access patterns and a controllable threshold parameter is used to prune out weak flow relationships. The decision for object pre-fetching or pre-eviction utilizes routines to compute objects that are strongly flow-related to the accessed/evicted object. The performance of the scheme was compared with LRU using an NS.2 simulation model. Our simulation used real life Internet traces from NANLR and UCB. An Oracle database was used to store/update the reference histories and was connected to the NS simulator using OCI (Oracle Call Interface). Extensive simulation tests were conducted to compare the performance of the two algorithms in terms of hit ratio and cost of pre-fetching. The tests covered a wide range of parameter values, e.g., cache size, the threshold for strong flow relationship, and the maximum number of objects that can be pre-fetched at a time. Our simulation experiments showed that the flow-based scheme is easy to implement and achieves significant improvement over LRU.