Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> This paper introduces a new approach to database disk buffering, called the LRU-K method. The basic idea of LRU-K is to keep track of the times of the last K references to popular database pages, using this information to statistically estimate the interarrival times of references on a page by page basis. Although the LRU-K approach performs optimal statistical inference under relatively standard assumptions, it is fairly simple and incurs little bookkeeping overhead. As we demonstrate with simulation experiments, the LRU-K algorithm surpasses conventional buffering algorithms in discriminating between frequently and infrequently referenced pages. In fact, LRU-K can approach the behavior of buffering algorithms in which page sets with known access frequencies are manually assigned to different buffer pools of specifically tuned sizes. Unlike such customized buffering algorithms however, the LRU-K method is self-tuning, and does not rely on external hints about workload characteristics. Furthermore, the LRU-K algorithm adapts in real time to changing patterns of access. <s> BIB001 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> The problem of document replacement in Web caches has received much attention in the literature research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in Web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizeable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M<N least useful documents are retained for the succeeding iteration. When the next replacement is to be performed, the algorithm obtains N-M new samples from the cache, and replaces the least useful document from the N-M new samples and the M previously retained. Using theory and simulations, we analyze the algorithm and find that it matches the performance of existing document replacement schemes for values of N and M as low as 8 and 2 respectively. Rather surprisingly, we find that retaining a small number of samples from one iteration to the next leads to an exponential improvement in performance as compared to retaining no samples at all. <s> BIB002 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and {\rm O}(\log_2 n) (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered. <s> BIB003 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> The self-tuning, low-overhead, scan-resistant adaptive replacement cache algorithm outperforms the least-recently-used algorithm by dynamically responding to changing access patterns and continually balancing between workload recency and frequency features. Caching, a fundamental metaphor in modern computing, finds wide application in storage systems, databases, Web servers, middleware, processors, file systems, disk drives, redundant array of independent disks controllers, operating systems, and other applications such as data compression and list updating. In a two-level memory hierarchy, a cache performs faster than auxiliary storage, but it is more expensive. Cost concerns thus usually limit cache size to a fraction of the auxiliary memory's size. <s> BIB004 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> This paper introduces a novel analytical model for estimating the cache hit ratio as a function of time. The cache may not reach the steady-state hit ratio when the number of Web objects, object popularity, and/or caching resources themselves are subject to change. Hence, the only way to quantify the hit ratio experienced by Web users is to calculate the instantaneous hit ratio. The proposed analysis considers a single Web cache with infinite or finite capacity. For a cache with finite capacity, two replacement policies are considered: Least Recently Used (LRU) and First-In-First-Out (FIFO). Based on the insights from the proposed analytical model, we propose a new replacement policy, called Frequency-Based-FIFO (FB-FIFO). The results show that FB-FIFO outperforms both LRU and FIFO, assuming that the number of Web objects is fixed. Assuming that new popular objects are generated periodically, the results show that FB-FIFO adapts faster than LRU and FIFO to the changes in the popularity of the cached objects when the cache capacity is large relative to the number of newly generated objects. <s> BIB005 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> This work studies on the issue of energy efficient caching for Content-centric Networking (CCN) architecture. We first build the energy consumption model for content distribution in an Internet Service Provider (ISP) and find that the objective of energy optimization can translate into that of minimizing average response hops. We then develop an aging popularity-based in-network caching scheme (APC), where each router implements caching policy using its local information but relying little on coordination. Simulation results show that APC has significant advantage over the widely used Leaving Copies Everywhere (LCE) in terms of the saved energy consumption, cache hit rate and the average number of response hops, so it helps improve user access experience and reduce network traffic other than the energy optimization. Encouragingly, APC can save up to 70% energy. <s> BIB006 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> To reduce network redundancy, in-network caching is considered in many future Internet architectures, such as Information Centric Networking. In in-network caching system, the item sojourn time of LRU (Least Recently Used) replacement policy is an important issue for two reasons: firstly, LRU is one of the most common used cache policy; secondly, item sojourn time is positively correlated to the hit probability, so this metric parameter could be useful to design the caching system. However, to the best of our knowledge, the sojourn time hasn't been studied theoretically so far. In this paper, we first model the LRU cache policy by Markov chain. Then an approximate closed-form expression of the item expectation sojourn time is provided through the theory of stochastic service system, which is a function of the item request rates and cache size. Finally, extensive simulation results are illustrated to show that the expression is a good approximation of the item sojourn time. <s> BIB007 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> Information-Centric Networking (ICN) has a great potential to better support the content distribution over the future Internet. Meanwhile, users with mobile devices will also access ICN, introducing a new challenge to ICN providers to handle such mobile content requests. In this paper, a mobility and popularity-based caching strategy is proposed to increase the cache hit rate through WiFi while people are moving from one WiFi hotspot to another. It thus lowers the network traffic from the local ICN to the outside Internet. Specifically, a precise derivation on the content request rate is provided based on the content popularity and user mobility. A novel caching strategy is further developed based on this derivation for both the mobility-oblivious and mobility-aware scenarios. We evaluate different caching strategies with a trace-driven simulation and our new approach can achieve a 33.84% reduction on the network traffic when compared with the caching strategies only considering the content popularity. <s> BIB008 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> Wireless ad hoc networks (WAHNs) consist of autonomous nodes cooperating with each other to transmit/receive data over multiple-hops in the network. Caching is a useful mechanism to leverage this cooperation. Nodes with cached content can satisfy requests from other nodes, thus helping reduce network traffic and energy consumption, and improve latency. With the proliferation of wireless devices on the Internet and the proposal of a future Internet with emphasis on in-network caching, improvements in caching can significantly improve network response while reducing network load. In this paper, we present a holistic caching framework, Split-Cache, which enables a network node to account for the frequency of requests of data items and their presence in the network, and to leverage a split-cache (one part caches popular items and the other caches less popular items) to make caching and cache-eviction decisions. We performed exhaustive simulations to compare Split-Cache with the state-of-the-art: Split-Cache improved the cache request resolution time on an average by 30% (and as high as 72%), and required 15% less average traffic for resolving requests-large savings when considering large number of requests. <s> BIB009 </s> Information-centric mobile caching network frameworks and caching optimization: a survey <s> Cache eviction policies <s> The information centric networks (ICN) can be viewed as a network of caches. Conversely, ICN type of cache networks has distinctive features e.g, contents popularity, usability time of content and other factors inflicts some diverse requirements for cache eviction policies. In this paper we defined four important characteristics of a suitable eviction policy for ICN. We analysed well known eviction policies in view of defined characteristics. Based upon analysis we propose a new eviction scheme which is well suitable for ICN type of cache networks. <s> BIB010
The cache eviction policy refers to the policy to remove contents from cache due to caching space limitation. The state-of-the-art cache eviction policies mainly include FIFO  , simple Random Replacement (RR) BIB002 , LRU BIB007 , LFU  , Least Recently/Frequently Used (LFRU) BIB003 , LRU-k BIB001 , Time Aware Least Recent Used (TLRU) BIB010 , Frequency-Based-FIFO(FB-FIFO) BIB005 , Aging popularity-based caching scheme (APC) BIB006 and Adaptive Replacement Cache(ARC) BIB004 ,etc. The processes of the cache eviction policies are analyzed as following. FIFO: FIFO is the simplest policy for content eviction. The content item which has been in the BIB008 cache for longest time is evicted to make room for a new content item. The popularity of contents and expiration time of content availability are not considered. RR: It is designed to evict a content item randomly in the cache to make room for a new content. In RR, N contents already in the cache are sampled and from the samples the content with least usefulness content is replaced which is mainly determined according to its recentness, frequency of use and size. The next M < N samples are retained for the succeeding iteration. When the next new content arrives, N-M new contents in the cache are sampled, and the least useful content from the N -M new samples and the M old samples are replaced. LRU: It is a typical cache eviction policy often used in caching system. Upon arrival of a request, if the requested content k is not the one already in the cache(namely, a new content), the least recently used content(the bottom content) in the cache is evicted to make room for the new content item. If the requested content k is already in the cache, then it is brought to the first position and contents previously cached above the content k are moved one position down. LFU: Assuming the content popularity is known a-priori, LFU statically stores the C most popular contents in the cache. When the cached content is requested, the counter value is added by one; when a content item is needed to be evicted, the content with the minimum counter value is selected. LFRU: the LFRU policy is proposed by associating a value with each lock in the buffer, which is called the Combined Recency and Frequency value and quantifies the likelihood that the block will be referenced in the near future. Each reference to a block in the past contributes to this value 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. There exists a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O(log 2 n) (the time complexity of LFU), where n is the number of blocks in the buffer. LRU-K: LRU-K algorithm keeps track of the times of the last K references to popular database pages, and uses this information to statistically estimate the interarrival times of references on a page by page basis. The LRU-1 (classical LRU) algorithm can be thought of as taking such a statistical approach by keeping in memory only those pages that seem to have the shortest interarrival time. TLRU: TLRU is an extension of simple LRU. In TLRU, TTU is defined as a time stamp of a content which stipulate the usability time for content based upon the locality of content and content publisher announcement. TTU i j is calculated for arriving content based on composite function, and if the average request time t ij is smaller than TTU i j , then save the arriving content in cache; otherwise, apply LRU on a content set which the less popular contents are contracted. FB-FIFO: In FB-FIFO, a variable-size protected segment S p is created in the cache for content items which are requested more than once within a short time span, and the remaining cache is considered as an unprotected segment S U . Assuming that both cache segments are managed separately with the FIFO algorithm, when a new content item is requested, the item is moved to S U as the newest content item. If S U is full, the content item that was brought into earliest will be evicted from the cache; If an item in S U experiences a cache hit, the item is moved to S p as the newest item; If S p is full, the item that was brought into earliest will be moved back to S U as the newest item. APC: It is an online caching eviction policy. In APC, each node maintains a table of interested content objects, where each content object is attached by an aging key which is used to indicate the popularity of the object. The value of the key is updated periodically in order to track the change of content popularity effectively. When all the cache space of the CR has been occupied, the tagged object with the least value of aging key in the cache will be evicted. ARC: ARC is presented as a self-tuning, low-overhead algorithm that responds to online changing access patterns. ARC maintains two LRU page lists: L1 and L2. L1 maintains pages that have been seen only once recently, while L2 maintains pages that have been seen at least twice recently. The algorithm actually caches only a fraction of the pages on these lists. The pages that have been seen twice within a short time may be thought of as having high frequency or as having longer term reuse potential. Hence, L1 captures recency, while L2 captures frequency. If the cache can hold c pages, and these two lists are kept to roughly the same size c, together, the two lists comprise a cache directory that holds at most 2c pages. ARC caches a variable number of most recent pages from both L1 and L2 such that the total number of cached pages is c. ARC outperforms the LRU algorithm by dynamically responding to changing access patterns and continually balancing between workload recency and frequency features. Some cache management schemes include content insertion and eviction, such as q-LRU, k-LRU, k-Random  and Split-Cache BIB009 . Both q-LRU and k-LRU differ from LRU for the insertion policy, but are identical to LRU for eviction policy. In q-LRU, upon arrival of a request, a new content item is inserted into the cache with probability q. In k-LRU, the cache is managed by a virtual cache. The requests have to traverse a chain of k − 1 virtual caches, which store only content item hashes and perform meta-cache operations before the content item is stored in the physical cache indexed by k. When a cache request arrives, the request enters cache i if its hash is already stored in cache i-1 (or if i = 1). k-Random works like k-LRU, the only difference is that the eviction policy of each cache is random. In Split-Cache scheme, the cache C is splitted into two parts C1 and C2 for popular and less popular items respectively. Some percent of the most frequently requested items are cached in C1, and the rest are cached in C2. Every node u keeps track of the number of unique requests for a data item i (request frequency). Information of the presence of item i in its neighborhood is also kept, and a presence index for each data item is computed. Merit Function is formulated by using estimated cumulative presence index and request frequency counter. If a new data item n comes to node u and the cache is full, then u first uses the request frequency of n to identify which cache (C1 or C2) item n should be put in. Then u performs the eviction procedure using the Merit function value and the corresponding merit values of the other items in the cache, and removes the item with the highest merit value in the process. From the procedures of cache eviction policies, it is necessary to categorize the policies according to content granularity, content popularity, mobility support and complexity. Table 3 gives the comparison of the cache eviction policies described aforesaid.