On optimal replication of data object at hierarchical and transparent Web proxies

This paper investigates the optimal replication of data objects at hierarchical and transparent Web proxies. By transparent, we mean the proxies are capable of intercepting users' requests and forwarding the requests to a higher level proxy if the requested data are not present in their local cache. Two cases of data replication at proxies are studied: 1) proxies having unlimited storage capacities and 2) proxies having limited storage capacities. For the former case, an efficient algorithm for computing the optimal result is proposed. For the latter case, we prove the problem is NP-hard, and propose two heuristic algorithms. Extensive simulations have been conducted and the simulation results have demonstrated significant performance gain by using the proposed data replication algorithms and also shown the proposed algorithms out-perform the standard Web caching algorithm (LRU threshold method).     

GEMA: An Object Replacement Algorithm for Cooperative Web Proxy Systems

In this paper, we design and analyze a web object replacement algorithm, referred to as gain-based exchange and migration algorithm (GEMA) suitable for a cooperative World Wide Web proxy caching environment. In a cooperative environment where more than one proxy exists, the replacement algorithms used for single system cache cannot not be directly put in use to achieve an acceptable performance. In this paper, we first present an analytical model, which quantifies the importance, referred to as object-caching gain, of an object at a cache. This gain is used in making replacement decisions and considers the benefit of caching at local as well as neighboring proxies. Our model efficiently exploits the advantages present in the existing the research contributions on designing replacement strategies for the single-cache environment. Further, with this model, we introduce two basic powerful primitive operations, namely the object exchange and object migration, to improve an overall performance. These two operations are carried out as an outcome of replacement decisions based on the comparison of gains among objects. Thus, the calculation of the gain and deciding on which of the operations to use constitute the main part of our algorithm GEMA. For quantifying the performance of GEMA, we carry out rigorous simulation experiments based on trace-driven and event-driven approaches. Using the event-driven simulation, we comprehensively testify the performance improvement of GEMA under a variety of performance measures such as, average access time of web objects, hit ratio, and byte hit ratio. We compare and analyze our strategies with some of the popular strategies found in the literature. We also highlight some possible extensions to the research contributions in this paper.     

A weighted segment-based caching algorithm for video streaming objects over heterogeneous networking environments

Traditional caching technology is not applicable to cache video streaming objects over heterogeneous networking environments. The popularity of mobile devices in the heterogeneous networking environments make the access of Internet content become a common phenomenon. To support different mobile devices in the heterogeneity networking environments, a transcoding proxy is used to transcode different versions of the streaming videos according to clients’ requests. In this paper, we propose a weighted caching replace strategy for video streaming objects over heterogeneous networking environments. A new caching algorithm with static weight transcoding graph and dynamic caching relation tree is introduced. The proposed algorithm is compared with LRU, LFU, CP and PF cache algorithms in three parts: hit ratio, byte hit ratio, and average transmission delay. Experimental results show that the proposed algorithm outperforms than traditional LRU, LFU, CP and PF cache algorithms.     

利用ZIPF定律建立有效的WEB对象缓存机制

通过对Web通信量的分析,人们发现用户对Web对象的访问模式服从Zipf定律或类Zipf定律。在Web缓存的设计中,为得到所期望的Web对象命中率的要求,设计人员可以根据Zipf定律近似计算出相应的缓存大小。因此,Zipf定律为Web缓存结构的设计提供了重要的依据。适当的缓存大小结合P-LFU替换策略可以得到很高的Web缓存命中率。     

COPACC: An Architecture of Cooperative Proxy-Client Caching System for On-Demand Media Streaming

Proxy caching is a key technique to reduce transmission cost for on-demand multimedia streaming. The effectiveness of current caching schemes, however, is limited by the insufficient storage space and weak cooperation among proxies and their clients, particularly considering the high bandwidth demands from media objects. In this paper, we propose COPACC, a cooperative proxy-and-client caching system that addresses the above deficiencies. This innovative approach combines the advantages of both proxy caching and peer-to-peer client communications. It leverages the client-side caching to amplify the aggregated cache space and rely on dedicated proxies to effectively coordinate the communications. We propose a comprehensive suite of distributed protocols to facilitate the interactions among different network entities in COPACC. It also realizes a smart and cost-effective cache indexing, searching, and verifying scheme. Furthermore, we develop an efficient cache allocation algorithm for distributing video segments among the proxies and clients. The algorithm not only minimizes the aggregated transmission cost of the whole system, but also accommodates heterogeneous computation and storage constraints of proxies and clients. We have extensively evaluated the performance of COPACC under various network and end-system configurations. The results demonstrate that it achieves remarkably lower transmission cost as compared to pure proxy-based caching with limited storage space. On the other hand, it is much more robust than a pure peer-to-peer communication system in the presence of node failures. Meanwhile, its computation and control overheads are both kept in low levels     

A neural network proxy cache replacement strategy and its implementation in the Squid proxy server

As the Internet has become a more central aspect for information technology, so have concerns with supplying enough bandwidth and serving web requests to end users in an appropriate time frame. Web caching was introduced in the 1990s to help decrease network traffic, lessen user perceived lag, and reduce loads on origin servers by storing copies of web objects on servers closer to end users as opposed to forwarding all requests to the origin servers. Since web caches have limited space, web caches must effectively decide which objects are worth caching or replacing for other objects. This problem is known as cache replacement. We used neural networks to solve this problem and proposed the Neural Network Proxy Cache Replacement (NNPCR) method. The goal of this research is to implement NNPCR in a real environment like Squid proxy server. In order to do so, we propose an improved strategy of NNPCR referred to as NNPCR-2. We show how the improved model can be trained with up to twelve times more data and gain a 5–10% increase in Correct Classification Ratio (CCR) than NNPCR. We implemented NNPCR-2 in Squid proxy server and compared it with four other cache replacement strategies. In this paper, we use 84 times more data than NNPCR was tested against and present exhaustive test results for NNPCR-2 with different trace files and neural network structures. Our results demonstrate that NNPCR-2 made important, balanced decisions in relation to the hit rate and byte hit rate; the two performance metrics most commonly used to measure the performance of web proxy caches.     

A dynamic caching algorithm based on internal popularity distribution of streaming media

Most proxy caches for streaming videos do not cache the entire video but only a portion of it. This is partly due to the large size of video objects. Another reason is that the popularity of different parts of a video can be different, e.g., the prefix is generally more popular. Therefore, the development of efficient cache mechanisms requires an understanding of the internal popularity characteristics of streaming videos. This paper has two major contributions. Firstly, we analyze two 6-month long traces of RTSP video requests recorded at different streaming video servers of an entertainment video-on-demand provider, and show that the traces provide evidence that the internal popularity of the majority of the most popular videos obeys a k-transformed Zipf-like distribution. Secondly, we propose a caching algorithm which exploits this empirical internal popularity distribution. We find that this algorithm has similar performance compared with fine-grained caching but requires significantly less state information.     

User-assisted in-network caching in information-centric networking

In information-centric networking, in-network caching has the potential to improve network efficiency and content distribution performance by satisfying user requests with cached content rather than downloading the requested content from remote sources. In this respect, users who request, download, and keep the content may be able to contribute to in-network caching by sharing their downloaded content with other users in the same network domain (i.e., user-assisted in-network caching). In this paper, we examine various aspects of user-assisted in-network caching in the hopes of efficiently utilizing user resources to achieve in-network caching. Through simulations, we first show that user-assisted in-network caching has attractive features, such as self-scalable caching, a near-optimal cache hit ratio (that can be achieved when the content is fully cached by the in-network caching) based on stable caching, and performance improvements over in-network caching. We then examine the caching strategy of user-assisted in-network caching. We examine three caching strategies based on a centralized server that maintains all content availability information and informs each user of what to cache. We also examine three caching strategies based on each user’s content availability information. We first show that the caching strategy affects the distribution of upload overhead across users and the number of cache hits in each segment. One interesting observation is that, even with a small storage space (i.e., 0.1% of the content size per user), the centralized and distributed approaches improve the cache hit ratio by 50% and 45%, respectively. With an overall view of caching information, the centralized approach can achieve a higher cache hit ratio than the distributed approach. Based on this observation, we discuss a distributed approach with a larger view of caching information than the distributed approach and, through simulations, confirm that a larger view leads to a higher cache hit ratio. Another interesting observation is that the random distributed strategy yields comparable performance to more complex strategies.     

Web-log mining for predictive Web caching

Caching is a well-known strategy for improving the performance of Web-based systems. The heart of a caching system is its page replacement policy, which selects the pages to be replaced in a cache when a request arrives. In this paper, we present a Web-log mining method for caching Web objects and use this algorithm to enhance the performance of Web caching systems. In our approach, we develop an n-gram-based prediction algorithm that can predict future Web requests. The prediction model is then used to extend the well-known GDSF caching policy. We empirically show that the system performance is improved using the predictive-caching approach.     

Proxy Cache Replacement Algorithms: A History-Based Approach

Accesing and circulation of Web objects has been facilitated by the design and implementation of effective caching schemes. Web caching has been integrated in prototype and commercial Web-based information systems in order to reduce the overall bandwidth and increase system's fault tolerance. This paper presents an overview of a series of Web cache replacement algorithms based on the idea of preserving a history record for cached Web objects. The number of references to Web objects over a certain time period is a critical parameter for the cache content replacement. The proposed algorithms are simulated and experimented under a real workload of Web cache traces provided by a major (Squid) proxy cache server installation. Cache and bytes hit rates are given with respect to different cache sizes and a varying number of request workload sets and it is shown that the proposed cache replacement algorithms improve both cache and byte hit rates.     

Design and analysis of a variable bit rate caching algorithm for continuous media data

In this paper, the problem of caching continuous media data in a (main) memory and disk caching system is addressed. Caching schemes can significantly reduce the load on the network as well as on the servers, also the retrieval of documents from the cache requires short response time. In interval-level caching algorithms, an interval of data between two adjacent streams is the basic caching entity. In this paper, we design a novel algorithm, referred to as variable bit rate caching (VBRC) algorithm, which belongs to the interval-level caching algorithms. The proposed VBRC algorithm can be used in the system for memory caching or disk caching. VBRC can handle variable retrieval bandwidth as well as constant retrieval bandwidth . In designing the VBRC algorithm, we propose the strategies of reducing the number of switching operation, which will probably cause discontinuity of retrieving data. Also, we propose a just-in-time scheme for resource allocation in our VBRC algorithm and show that the caching performance in comparison with the reservation scheme adopted in the resource-based caching (RBC) algorithm is significantly improved. Our simulation study compares the recent and most popular generalized interval caching, RBC, and VBRC, on several influencing factors such as cache space size, cache I/O bandwidth, request arrival rate, and percentage of requests for large documents, with respect to the byte hit ratio and the number of switching operations. The simulation result confirms our analysis.

Neuro-fuzzy system in partitioned client-side Web cache

This paper proposes a novel contribution in Web caching area, especially in Web cache replacement, so-called intelligent client-side Web caching scheme (ICWCS). This approach is developed by splitting the client-side cache into two caches: short-term cache that receives the Web objects from the Internet directly, and long-term cache that receives the Web objects from the short-term cache. The objects in short-term cache are removed by least recently used (LRU) algorithm as short-term cache is full. More significantly, when the long-term cache saturates, the neuro-fuzzy system is employed efficiently in managing contents of the long-term cache. The proposed solution is validated by implementing trace-driven simulation and the results are compared with least recently used (LRU) and least frequently used (LFU) algorithms; the most common policies of evaluating Web caching performance. The simulation results have revealed that the proposed approach improves the performance of Web caching in terms of hit ratio (HR), up to 14.8% and 17.9% over LRU and LFU. In terms of byte hit ratio (BHR), the Web caching performance is improved up to 2.57% and 26.25%, and for latency saving ratio (LSR), the performance is better with 8.3% and 18.9% over LRU and LFU, respectively.     

Evolutionary Techniques for Web Caching

Web caching has been proposed as an effective solution to the problems of network traffic and congestion, Web objects access and Web load balancing. This paper presents a model for optimizing Web cache content by applying either a genetic algorithm or an evolutionary programming scheme for Web cache content replacement. Three policies are proposed for each of the genetic algorithm and the evolutionary programming techniques, in relation to objects staleness factors and retrieval rates. A simulation model is developed and long term trace-driven simulation is used to experiment on the proposed techniques. The results indicate that all evolutionary techniques are beneficial to the cache replacement, compared to the conventional replacement applied in most Web cache server. Under an appropriate objective function the genetic algorithm has been proven to be the best of all approaches with respect to cache hit and byte hit ratios.     

基于网络性能的智能Web加速技术——缓存与预取

Web业务在网络业务中占有很大比重,在无法扩大网络带宽时,需要采取一定技术合理利用带宽,改善网络性能。研究了基于RTT（round trip time)等网络性能指标的Web智能加速技术,在对Web代理服务器上的业务进行分析和对网络RTT进行测量分析的基础上,提出了智能预取控制技术及新的缓存（cache）替换方法。对新算法的仿真研究表明,该方法提高了缓存的命中率。研究表明预取技术在不明显增加网络负荷的前提下,提高了业务的响应速度,有效地改进了Web访问性能。     

On exploring aggregate effect for efficient cache replacement in transcoding proxies

Recent technology advances in mobile networking have ushered in a new era of personal communication. Users can ubiquitously access the Internet via many emerging mobile appliances, such as portable notebooks, personal digital assistants (PDAs), and WAP-enabled cellular phones. While the transcoding proxy is attracting an increasing amount of attention in this environment, it is noted that new caching strategies are required for these transcoding proxies. We propose an efficient cache replacement algorithm for transcoding proxies. Specifically, we formulate a generalized profit function to evaluate the profit from caching each version of an object. This generalized profit function explicitly considers several new emerging factors in the transcoding proxy and the aggregate effect of caching multiple versions of the same object. It is noted that the aggregate effect is not simply the sum of the costs of caching individual versions of an object, but rather, depends on the transcoding relationship among these versions. The notion of a weighted transcoding graph is devised to evaluate the corresponding aggregate effect efficiently. Utilizing the generalized profit function and the weighted transcoding graph, we propose, in this paper, an innovative cache replacement algorithm for transcoding proxies. In addition, an effective data structure is designed to facilitate the management of the multiple versions of different objects cached in the transcoding proxy. Using an event-driven simulation, it is shown that the algorithm proposed consistently outperforms companion schemes in terms of the delay saving ratios and cache hit ratios.     

一个基于集中管理的协作式Web缓存系统

共享不同代理的缓存Web文档是减少通信量和减轻网络瓶颈的重要方法。在分析原有Web缓存通信协议（ICP）的基础上,提出了一种新的协作Web缓存系统（CMCS）并作了分析比较。通过将HTTP请求均匀分散到系统各个代理,消除了代理之间庞大的通信开销以及由此带来的处理负担。在动态变化的网络环境下,有效地将各个代理组织起来,处理来自服务器的文档。另外也克服了以往每个代理里有大量冗余内容,造成各个代理内容趋向的情形。     

An expiration age-based document placement scheme for cooperative Web caching

The sharing of caches among proxies is an important technique to reduce Web traffic, alleviate network bottlenecks, and improve response time of document requests. Most existing work on cooperative caching has been focused on serving misses collaboratively. Very few have studied the effect of cooperation on document placement schemes and its potential enhancements on cache hit ratio and latency reduction. We propose a new document placement scheme which takes into account the contentions at individual caches in order to limit the replication of documents within a cache group and increase document hit ratio. The main idea of this new scheme is to view the aggregate disk space of the cache group as a global resource of the group and uses the concept of cache expiration age to measure the contention of individual caches. The decision of whether to cache a document at a proxy is made collectively among the caches that already have a copy of this document. We refer to this new document placement scheme as the Expiration Age-based scheme (EA scheme). The EA scheme effectively reduces the replication of documents across the cache group, while ensuring that a copy of the document always resides in a cache where it is likely to stay for the longest time. We report our study on the potentials and limits of the EA scheme using both analytic modeling and trace-based simulation. The analytical model compares and contrasts the existing (ad hoc) placement scheme of cooperative proxy caches with our new EA scheme and indicates that the EA scheme improves the effectiveness of aggregate disk usage, thereby increasing the average time duration for which documents stay in the cache. The trace-based simulations show that the EA scheme yields higher hit rates and better response times compared to the existing document placement schemes used in most of the caching proxies.     

Web cache management based on the expected cost of web objects

With the recent explosion in usage of the World Wide Web, Web caching has become increasingly important. However, due to the non-uniform cost/size property of data objects in this environment, design of an efficient caching algorithm becomes an even more difficult problem compared to the traditional caching problems. In this paper, we propose the Least Expected Cost (LEC) replacement algorithm for Web caches that provides a simple and robust framework for the estimation of reference probability and fair evaluation of non-uniform Web objects. LEC evaluates a Web object based on its cost per unit size multiplied by the estimated reference probability of the object. This results in a normalized assessment of the contribution to the cost-savings ratio, leading to a fair replacement algorithm. We show that this normalization method finds optimal solution under some assumptions. Trace-driven simulations with actual Web cache logs show that LEC offers the performance of caches more than twice its size compared with other algorithms we considered. Nevertheless, it is simple, having no parameters to tune. We also show how the algorithm can be effectively implemented as a Web cache replacement module.     

Distributed caching in unstructured peer-to-peer file sharing networks

Nowadays, the peer-to-peer (P2P) system is one of the largest Internet bandwidth consumers. To relieve the burden on Internet backbone and improve the query and retrieve performance of P2P file sharing networks, efficient P2P caching algorithms are of great importance. In this paper, we propose a distributed topology-aware unstructured P2P file caching infrastructure and design novel placement and replacement algorithms to achieve optimal performance. In our system, for each file, an adequate number of copies are generated and disseminated at topologically distant locations. Unlike general believes, our caching decisions are in favor of less popular files. Combined with the underlying topology-aware infrastructure, our strategy retains excellent performance for popular objects while greatly improves the caching performance for less popular files. Overall, our solution can reduce P2P traffic on Internet backbone, and relieve the over-caching problem that has not been properly addressed in unstructured P2P networks. We carry out simulation experiments to compare our approaches with several traditional caching strategies. The results show that our algorithms can achieve better query hit rates, smaller query delay, higher cache hit rates, and lower communication overhead.     

Web对象可缓存性研究及加速方案

讨论了Web缓存的一般工作原理,描述了Web对象可缓存性的判断方法.为减少不可缓存对象对系统效率的影响,提出了Web缓存技术的加速方案.对于不可缓存的Web对象的请求,直接发给相应的Web服务器,而不通过代理服务器转发,系统的效率可以得到一定程度的提高.