Hierarchical Web caching systems: modeling, design and experimental results

This paper aims at finding fundamental design principles for hierarchical Web caching. An analytical modeling technique is developed to characterize an uncooperative two-level hierarchical caching system where the least recently used (LRU) algorithm is locally run at each cache. With this modeling technique, we are able to identify a characteristic time for each cache, which plays a fundamental role in understanding the caching processes. In particular, a cache can be viewed roughly as a low-pass filter with its cutoff frequency equal to the inverse of the characteristic time. Documents with access frequencies lower than this cutoff frequency have good chances to pass through the cache without cache hits. This viewpoint enables us to take any branch of the cache tree as a tandem of low-pass filters at different cutoff frequencies, which further results in the finding of two fundamental design principles. Finally, to demonstrate how to use the principles to guide the caching algorithm design, we propose a cooperative hierarchical Web caching architecture based on these principles. Both model-based and real trace simulation studies show that the proposed cooperative architecture results in more than 50% memory saving and substantial central processing unit (CPU) power saving for the management and update of cache entries compared with the traditional uncooperative hierarchical caching architecture.     

In-network caching for energy efficiency in content-centric networking

Recently, Internet energy efficiency is paid more and more attention. New Internet architectures with more energy efficiency were proposed to promote the scalability in energy consumption. The eontent-eentrie networking （CCN） proposed a content-centric paradigm which was proven to have higher energy efficiency. Based on the energy optimization model of CCN with in-network caching, the authors derive expressions to tradeoff the caching energy and the transport energy, and then design a new energy efficiency cache scheme based on virtual round trip time （EV） in CCN. Simulation results show that the EV scheme is better than the least recently used （LRU） and popularity based cache policies on the network average energy consumption, and its average hop is also much better than LRU policy.     

一种降低末级高速缓存污染的软件控制插入策略

 现有高速缓存替换算法大多无法有效识别数据的局部性特征,导致高速缓存内即将被访问到的数据可能被未来不会被访问到的数据所替换,造成高速缓存污染问题.末级高速缓存污染引发的性能损失随着处理器和存储器之间性能差距的扩大而不断增大,成为制约系统性能提升的重要瓶颈之一.本文针对末级高速缓存污染问题,在剖视分析访存密集型程序的页一级访存行为基础上,提出一种软件控制末级高速缓存插入策略.本方法通过控制和指导页一级数据插入位置,限制局部性差的数据页在末级高速缓存中的访问空间,达到降低末级高速缓存污染的目的.实验结果表明,相对于LRU和DIP策略,本文方法能够有效降低末级高速缓存失效率,提高程序性能.     

Evaluation of performance enhancing proxies in internet over satellite

Performance enhancing proxies (PEPs) are widely used to improve the performance of TCP over high delay‐bandwidth product links and links with high error probability. In this paper we analyse the performance of using TCP connection splitting in combination with web caching via traces obtained from a commercial satellite system. We examine the resulting performance gain under different scenarios, including the effect of caching, congestion, random loss and file sizes. We show, via analysing our measurements, that the performance gain from using splitting is highly sensitive to random losses and the number of simultaneous connections, and that such sensitivity is alleviated by caching. On the other hand, the use of a splitting proxy enhances the value of web caching in that cache hits result in much more significant performance improvement over cache misses when TCP splitting is used. We also compare the performance of using different versions of HTTP in such a system. Copyright © 2003 John Wiley & Sons, Ltd.     

基于改进LRU替换策略的共享Cache划分

本文提出了一种基于改进的LRU替换策略划分最后一级共享Cache的算法,隔离了线程间的数据冲突,实现了改进的Cache替换策略,通过划分最后一级共享Cache也减少了访存延迟,提高了系统吞吐率.     

A Learning-Based Approach for Web Cache Management

Web caching has been widely used to alleviate Internet traffic congestion in World Wide Web (WWW) services. To reduce download throughput, an effective strategy on web cache management is needed to exploit web usage information in order to make a decision on evicting the document stored in case of cache saturation. This paper presents a so-called Learning Based Replacement algorithm (LBR), a hybrid approach towards an efficient replacement model for web caching by incorporating a machine learning technique (naive Bayes) into the LRU replacement method to improve prediction of possibility that an existing page will be revised by a succeeding request, from access history in a web log. The learned knowledge includes information on which URL objects in cache should be kept or evicted. The learning-based model is acquired to represent the hidden aspect of user request pattern for predicting the re-reference possibility. By a number of experiments, the LBR gains potential improvement of prediction on revisit probability, hit rate and byte hit rate overtraditional methods; LRU, LFU, and GDSF, respectively.     

Cooperative Caching Strategy in Mobile Ad Hoc Networks Based on Clusters

In this paper, we present a scheme, called Cluster Cooperative (CC) for caching in mobile ad hoc networks. In CC scheme, the network topology is partitioned into non-overlapping clusters based on the physical network proximity. For a local cache miss, each client looks for data item in the cluster. If no client inside the cluster has cached the requested item, the request is forwarded to the next client on the routing path towards server. A cache replacement policy, called Least Utility Value with Migration (LUV-Mi) is developed. The LUV-Mi policy is suitable for cooperation in clustered ad hoc environment because it considers the performance of an entire cluster along with the performance of local client. Simulation experiments show that CC caching mechanism achieves significant improvements in cache hit ratio and average query latency in comparison with other caching strategies.     

A zone co‐operation approach for efficient caching in mobile ad hoc networks

Mobile Ad hoc NETwork (MANET) presents a constrained communication environment due to fundamental limitations of client resources, insufficient wireless bandwidth and users' frequent mobility. Caching of frequently accessed data in such environment is a potential technique that can improve the data access performance and availability. Co‐operative caching, which allows the sharing and co‐ordination of cached data among clients, can further explore the potential of the caching techniques. In this paper, we propose a novel scheme, called zone co‐operative (ZC) for caching in MANETs. In ZC scheme, one‐hop neighbours of a mobile client form a co‐operative cache zone. For a data miss in the local cache, each client first searches the data in its zone before forwarding the request to the next client that lies along routing path towards server. As a part of cache management, cache admission control and value‐based replacement policy are developed to improve the data accessibility and reduce the local cache miss ratio. An analytical study of ZC based on data popularity, node density and transmission range is also performed. Simulation experiments show that the ZC caching mechanism achieves significant improvements in cache hit ratio and average query latency in comparison with other caching strategies. Copyright © 2006 John Wiley & Sons, Ltd.     

Fast convergence caching replacement algorithm based on dynamic classification for content-centric networks

One of the key research fields of content-centric networking （CCN） is to develop more efficient cache replacement policies to improve the hit ratio of CCN in-network caching. However, most of existing cache strategies designed mainly based on the time or frequency of content access, can not properly deal with the problem of the dynamicity of content popularity in the network. In this paper, we propose a fast convergence caching replacement algorithm based on dynamic classification method for CCN, named as FCDC. It develops a dynamic classification method to reduce the time complexity of cache inquiry, which achieves a higher caching hit rate in comparison to random classification method under dynamic change of content popularity. Meanwhile, in order to relieve the influence brought about by dynamic content popularity, it designs a weighting function to speed up cache hit rate convergence in the CCN router. Experimental results show that the proposed scheme outperforms the replacement policies related to least recently used （LRU） and recent usage frequency （RUF） in cache hit rate and resiliency when content popularity in the network varies.     

Dynamic Probabilistic Caching Algorithm with Content Priorities for Content‐Centric Networks

This paper presents a caching algorithm that offers better reconstructed data quality to the requesters than a probabilistic caching scheme while maintaining comparable network performance. It decides whether an incoming data packet must be cached based on the dynamic caching probability, which is adjusted according to the priorities of content carried by the data packet, the uncertainty of content popularities, and the records of cache events in the router. The adaptation of caching probability depends on the priorities of content, the multiplication factor adaptation, and the addition factor adaptation. The multiplication factor adaptation is computed from an instantaneous cache‐hit ratio, whereas the addition factor adaptation relies on a multiplication factor, popularities of requested contents, a cache‐hit ratio, and a cache‐miss ratio. We evaluate the performance of the caching algorithm by comparing it with previous caching schemes in network simulation. The simulation results indicate that our proposed caching algorithm surpasses previous schemes in terms of data quality and is comparable in terms of network performance.     

Cache Optimization on Hot‐Point Proxy Caching Using Weighted‐Rank Cache Replacement Policy

The development of proxy caching is essential in the area of video‐on‐demand (VoD) to meet users' expectations. VoD requires high bandwidth and creates high traffic due to the nature of media. Many researchers have developed proxy caching models to reduce bandwidth consumption and traffic. Proxy caching keeps part of a media object to meet the viewing expectations of users without delay and provides interactive playback. If the caching is done continuously, the entire cache space will be exhausted at one stage. Hence, the proxy server must apply cache replacement policies to replace existing objects and allocate the cache space for the incoming objects. Researchers have developed many cache replacement policies by considering several parameters, such as recency, access frequency, cost of retrieval, and size of the object. In this paper, the Weighted‐Rank Cache replacement Policy (WRCP) is proposed. This policy uses such parameters as access frequency, aging, and mean access gap ratio and such functions as size and cost of retrieval. The WRCP applies our previously developed proxy caching model, Hot‐Point Proxy, at four levels of replacement, depending on the cache requirement. Simulation results show that the WRCP outperforms our earlier model, the Dual Cache Replacement Policy.     

Analytical characterization of cache replacement policy impact on content delivery time in information‐centric networks

Information‐centric networking (ICN) has emerged as a promising candidate for designing content‐based future Internet paradigms. ICN increases the utilization of a network through location‐independent content naming and in‐network content caching. In routers, cache replacement policy determines which content to be replaced in the case of cache free space shortage. Thus, it has a direct influence on user experience, especially content delivery time. Meanwhile, content can be provided from different locations simultaneously because of the multi‐source property of the content in ICN. To the best of our knowledge, no work has yet studied the impact of cache replacement policy on the content delivery time considering multi‐source content delivery in ICN, an issue addressed in this paper. As our contribution, we analytically quantify the average content delivery time when different cache replacement policies, namely, least recently used (LRU) and random replacement (RR) policy, are employed. As an impressive result, we report the superiority of these policies in term of the popularity distribution of contents. The expected content delivery time in a supposed network topology was studied by both theoretical and experimental method. On the basis of the obtained results, some interesting findings of the performance of used cache replacement policies are provided.     

雾网络中基于统计分布的内容缓存与交付方案

作为5G中的一种重要模型，雾无线接入网络(Fog Radio Access Network, F-RAN)通过设备到设备通信和无线中继等技术获得了显著的性能增益，而边缘设备中合适的缓存则可以让内容缓存用户(Caching Users, CUs)向内容请求用户(Requesting Users, RUs)直接发送缓存内容，有效减小前传链路的负担和下载延迟。考虑一个F-RAN模型下用户发出请求并获得交付的场景，将每个CU的内容请求队列建模为独立的M/D/1模型，分析导出CUs缓存命中率和平均下载延迟关于内容缓存与交付方案的表达式，证明CUs缓存命中率与内容统计分布之间的联系有助于实现前者的近似最优解。针对在一段时间内的期望视角下建立的优化问题，提出了基于统计分布的算法并注意了执行时的交付控制。仿真结果表明，相较于现有缓存策略，优化内容整体统计分布的方案能够最大化CUs缓存命中率，同时减小平均下载延迟。     

An analytical model for the performance evaluation of stack‐based Web cache replacement algorithms

Web caching has been the solution of choice to web latency problems. The efficiency of a Web cache is strongly affected by the replacement algorithm used to decide which objects to evict once the cache is saturated. Numerous web cache replacement algorithms have appeared in the literature. Despite their diversity, a large number of them belong to a class known as stack‐based algorithms. These algorithms are evaluated mainly via trace‐driven simulation. The very few analytical models reported in the literature were targeted at one particular replacement algorithm, namely least recently used (LRU) or least frequently used (LFU). Further they provide a formula for the evaluation of the Hit Ratio only. The main contribution of this paper is an analytical model for the performance evaluation of any stack‐based web cache replacement algorithm. The model provides formulae for the prediction of the object Hit Ratio, the byte Hit Ratio, and the delay saving ratio. The model is validated against extensive discrete event trace‐driven simulations of the three popular stack‐based algorithms, LRU, LFU, and SIZE, using NLANR and DEC traces. Results show that the analytical model achieves very good accuracy. The mean error deviation between analytical and simulation results is at most 6% for LRU, 6% for the LFU, and 10% for the SIZE stack‐based algorithms. Copyright © 2009 John Wiley & Sons, Ltd.     

流媒体服务系统中一种基于数据预取的缓存策略

具有 VCR 功能的流媒体服务系统由于请求的随机性会影响用户的点播体验,该文结合数据预取机制以及基于分段的缓存策略计算出用户点播延迟的期望,给出一个较优的缓存管理策略,并通过在线计算逼近最优解,同时在缓存已知的情况下,给出相应的数据预取算法,利用缓存和预取两种数据获取方法的相互协作减小客户端点播延迟,提高缓存效率。仿真结果证实了所提算法的有效性。     

Community oriented in‐network caching and edge caching for over‐the‐top services in adaptive network conditions to improve performance

Over‐the‐top (OTT) services such as Netflix, Amazon Prime, and YouTube generate the most dominant form of traffic on the Internet today. There is increasingly high demand for resource intensive 3D contents, interactive media, 360 media, and user‐generated contents. As the amount of contents keep increasing in multiple folds, it is important to cache contents intelligently. Caching algorithm needs to exploit in‐network caching, community‐based pre‐caching, and a combined approach. Hence, we survey CDN‐based edge caching infrastructures including OpenConnect (Netflix) and Google Edge, followed by CCN based in‐network caching. We implement and compare four different approaches for caching contents including (1) in‐network caching, (2) edge caching, (3) community‐based in‐network caching, and (4) community‐based edge caching. We run our algorithms on adaptive network conditions with different topologies, cache size, content popularity, and request arrivals in and compared the delay for all these four approaches. We verify our model by calculating important performance parameters including hop count, redundancy, and hop count variances. Hopcount is an important performance parameter as it influences the processing, queuing, and transmission delays. We focus on determining if an in‐network caching approach is any better than edge caching. We reach several conclusions. First, in most of the scenarios, community‐based in‐network caching performs the best. Second, if the cache size is lesser than 30% of the total content size then community‐based edge caching is better for less popular contents. Finally, our statistical analysis also reveals that a community‐based edge caching mechanism is least affected by varying cache sizes and dynamic user behavior, which makes it a better choice for providing Service Level Agreement.     

带有特征感知的D2D内容缓存策略

设备到设备通信(D2D)可以有效地卸载基站流量,在D2D网络中不仅需要共享大众化内容还需要个性化内容缓存。该文对缓存内容选择问题进行了深入研究,提出一种结合特征感知的内容社交价值预测(CSVP)方法。价值预测不仅可以降低时延也可以减少缓存替换次数降低缓存成本。首先结合用户特征和内容特征计算内容当前价值,然后通过用户社交关系计算未来价值。微基站根据内容的价值为用户提供个性化内容缓存服务,宏基站则在每个微基站的缓存内容中选择价值较大部分的内容。仿真结果表明,该文提出的缓存策略可以有效缓解基站流量,与其他方法相比降低时延约20%～40%。     

基于随机几何理论的流行度匹配边缘缓存策略

异构网络边缘缓存机制是解决传统回程传输链路负载过大的可靠技术之一,但已有的缓存策略往往不能与被请求数据的流行度相匹配。为了解决这一问题,该文提出一种流行度匹配边缘缓存策略(PMCP),该策略能够根据流行度参数匹配对应的文件缓存概率以最大限度提升通信可靠性并降低回程带宽压力。基站的平面位置通过随机几何建模,文件的被请求概率则通过齐夫分布建模。蒙特卡罗仿真结果表明缓存机制能够有效降低回程带宽压力,且所提出缓存策略的可靠性优于对比策略。     

应用于协议无感知转发交换机的流缓存方法

协议无感知转发支持任意协议的解析和处理,增强了软件定义网络的可编程能力。为提高转发性能,该文提出一种应用于协议无感知转发交换机的流缓存方法,通过识别匹配和动作的依赖关系,得到匹配字段的绝对位置,用以预先解析报文。为确保流缓存的加速效果,根据匹配类型与表项数量选择应用流缓存的流表。此外,该文对比了单流表缓存与多流表缓存对转发性能的提升,并提出了根据网络流量实际情况的自适应切换策略。通过扩展POFSwitch实现所提方法,并用实际规则与骨干网流量进行验证,应用流缓存后,交换机报文转发速率提升了220%。流缓存可以为可编程数据平面提供更高的转发性能。