Improving proxy cache performance: analysis of three replacementpolicies

Web cache replacement policy choice affects network bandwidth demand and object hit rate, which affect page load time. Two new policies implemented in the Squid cache server show marked improvement over the standard mechanism     

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.     

利用缓存优化基于ASP.NET的Web GIS性能

随着WebGIS的快速发展和广泛应用,对WebGIS的性能提出了更高的要求。ASP.NET是微软推出的新一代动态网页技术,它提供了强大的Web应用开发功能,依托ActiveX技术,开发基于ASP.NET的WebGIS是当前实现WebGIS的较佳方案。基于ASP.NET的WebGIS的优点在于其灵活性和动态特性,但是在获得这种灵活性和动态特性的同时却导致WebGIS性能降低。加之ASP.NET属于ActiveX技术中的Server端技术,对于ASP.NET而言,所有的一切都是在服务器端运行的,这就更增加了服务器的负载,同时,虽然ASP.NET页面是编译型的,但页面中的许多操作将占用大量的服务器资源。因此有必要用运ASP.NET的缓存技术,降低WebGIS服务器的负载,使得设计和实现的WebGIS性能更优,效率更高。     

Proxy cache algorithms: design, implementation, and performance

Caching at proxy servers is one of the ways to reduce the response time perceived by World Wide Web users. Cache replacement algorithms play a central role in the response time reduction by selecting a subset of documents for caching, so that a given performance metric is maximized. At the same time, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate guarantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-WS-U, which integrates both cache replacement and consistency algorithms. The LNC-R-WS-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. Consequently, the documents that took a long time to fetch are preferentially kept in the cache. The LNC-R-W3-U algorithm also considers in the eviction consideration the validation rate of each document, as provided by the cache consistency component of LNC-R-WS-U. Consequently, documents that are infrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-driven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance     

The Gecko NFS Web proxy

The World-Wide Web provides remote access to pages using its own naming scheme (URLs), transfer protocol (HTTP), and cache algorithms. Not only does using these special-purpose mechanisms have performance implications, but they make it impossible for standard Unix applications to access the Web. Gecko is a system that provides access to the Web via the NFS protocol. URLs are mapped to Unix file names, providing unmodified applications access to Web pages; pages are transferred from the Gecko server to the clients using NFS instead of HTTP, significantly improving performance; and NFS's cache consistency mechanism ensures that all clients have the same version of a page. Applications access pages as they would Unix files. A client-side proxy translates HTTP requests into file accesses, allowing existing Web applications to use Gecko. Experiments performed on our prototype show that Gecko is able to provide this additional functionality at a performance level that exceeds that of HTTP.     

基于高斯混合模型的Web代理服务器缓存替换策略

Web代理服务器缓存能够在一定程度上解决用户访问延迟和网络拥塞问题,Web代理缓存的缓存替换策略直接影响缓存的命中率,从而影响网络请求响应的效果;为此,使用一种通过固定大小的循环滑动窗口提取Web日志数据的多项特征,并使用高斯混合模型对Web日志数据进行聚类分析,预测在窗口时间内可能再次访问到Web对象,结合最近最少使用(LRU)算法,提出一种新的基于高斯混合模型的Web代理服务器缓存替换策略;实验结果表明,与传统的缓存替换策略LRU、LFU、FIFO、GDSF相比,该策略有效提高了Web代理缓存的请求命中率和字节命中率。     

AJAX在基于NC机网络中的应用

在基于无盘的NC机网络中,如果采用传统的同步交互式Web服务,会造成服务器的负担过重,并使用户等待时间过长。该文提出一种新的方法,将AJAX技术引入NC网络,在用户与服务器之间通过AJAX引擎异步调用XML以实现动态加载数据,使用户与程序异步交互而无须等待服务器的通信。在实例中,Web页面通过JavaScript调用AJAX引擎并异步加载数据,减轻了服务器和带宽的负担,使用户在浏览Web网页时所能感受到的程序反应灵敏度有所提高。     

Faster Web page allocation with neural networks

To maintain quality of service, some heavily trafficked Web sites use multiple servers, which share information through a shared file system or data space. The Andrews file system (AFS) and distributed file system (DFS), for example, can facilitate this sharing. In other sites, each server might have its own independent file system. Although scheduling algorithms for traditional distributed systems do not address the special needs of Web server clusters well, a significant evolution in the computational approach to artificial intelligence and cognitive engineering shows promise for Web request scheduling. Not only is this transformation - from discrete symbolic reasoning to massively parallel and connectionist neural modeling - of compelling scientific interest, but also of considerable practical value. Our novel application of connectionist neural modeling to map Web page requests to Web server caches maximizes hit ratio while load balancing among caches. In particular, we have developed a new learning algorithm for fast Web page allocation on a server using the self-organizing properties of the neural network (NN).     

网站浏览路径预测

用户浏览因特网网站点击某个链接后,该链接的网页往往需要一段时间才能传送到用户端.为了缩短用户的等待时间,利用网站服务器的空闲CPU时间,对用户下一个HTTP请求进行预测,以便预处理下一个网页是一种可能途径.使用已分类的网页信息、用户配置文件和网站日志进行预测,介绍并且分析了16种预测算法.实验结果证明某些算法是比较有效可信的.     

Automatic fragment detection in dynamic Web pages and its impact on caching

Constructing Web pages from fragments has been shown to provide significant benefits for both content generation and caching. In order for a Web site to use fragment-based content generation, however, good methods are needed for fragmenting the Web pages. Manual fragmentation of Web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in Web sites serving dynamic content. Our approach analyzes Web pages with respect to their information sharing behavior, personalization characteristics, and change patterns. We identify fragments which are shared among multiple documents or have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a framework for fragment detection, which includes a hierarchical and fragment-aware model for dynamic Web pages and a compact and effective data structure for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. This paper shows the results when the algorithms are applied to real Web sites. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of using the fragments detected by our system on key parameters such as disk space utilization, network bandwidth consumption, and load on the origin servers.     

Performance evaluation of Web proxy cache replacement policies

The continued growth of the World-Wide Web and the emergence of new end-user technologies such as cable modems necessitate the use of proxy caches to reduce latency, network traffic and Web server loads. In this paper we analyze the importance of different Web proxy workload characteristics in making good cache replacement decisions. We evaluate workload characteristics such as object size, recency of reference, frequency of reference, and turnover in the active set of objects. Trace-driven simulation is used to evaluate the effectiveness of various replacement policies for Web proxy caches. The extended duration of the trace (117 million requests collected over 5 months) allows long term side effects of replacement policies to be identified and quantified.

Our results indicate that higher cache hit rates are achieved using size-based replacement policies. These policies store a large number of small objects in the cache, thus increasing the probability of an object being in the cache when requested. To achieve higher byte hit rates a few larger files must be retained in the cache. We found frequency-based policies to work best for this metric, as they keep the most popular files, regardless of size, in the cache. With either approach it is important that inactive objects be removed from the cache to prevent performance degradation due to pollution.     

动态网页加速技术

综述了动态网页加速技术的最新发展，首先介绍了主动缓存，它通过在代理服务器上运行原始服务器提供的Applets以完成必要的处理，并返回结果给用户而不用连接服务器，接着介绍了服务器加速器，它放置于Web Server前端或内部以加速服务器访问速度，最后重点介绍了一种简单的标记语言ESI（Edge Side Includes)，用于定义网页片段，使得在因特网边缘可以动态地组装和分发Web应用。     

Automatic identification of informative sections of Web pages

Web pages - especially dynamically generated ones - contain several items that cannot be classified as the "primary content," e.g., navigation sidebars, advertisements, copyright notices, etc. Most clients and end-users search for the primary content, and largely do not seek the noninformative content. A tool that assists an end-user or application to search and process information from Web pages automatically, must separate the "primary content sections" from the other content sections. We call these sections as "Web page blocks" or just "blocks." First, a tool must segment the Web pages into Web page blocks and, second, the tool must separate the primary content blocks from the noninformative content blocks. In this paper, we formally define Web page blocks and devise a new algorithm to partition an HTML page into constituent Web page blocks. We then propose four new algorithms, ContentExtractor, FeatureExtractor, K-FeatureExtractor, and L-Extractor. These algorithms identify primary content blocks by 1) looking for blocks that do not occur a large number of times across Web pages, by 2) looking for blocks with desired features, and by 3) using classifiers, trained with block-features, respectively. While operating on several thousand Web pages obtained from various Web sites, our algorithms outperform several existing algorithms with respect to runtime and/or accuracy. Furthermore, we show that a Web cache system that applies our algorithms to remove noninformative content blocks and to identify similar blocks across Web pages can achieve significant storage savings.     

Predictive Prefetching on the Web and Its Potential Impact in the Wide Area

The rapid increase of World Wide Web users and the development of services with high bandwidth requirements have caused the substantial increase of response times for users on the Internet. Web latency would be significantly reduced, if browser, proxy or Web server software could make predictions about the pages that a user is most likely to request next, while the user is viewing the current page, and prefetch their content.In this paper we study Predictive Prefetching on a totally new Web system architecture. This is a system that provides two levels of caching before information reaches the clients. This work analyses prefetching on a Wide Area Network with the above mentioned characteristics. We first provide a structured overview of predictive prefetching and show its wide applicability to various computer systems. The WAN that we refer to is the GRNET academic network in Greece. We rely on log files collected at the network's Transparent cache (primary caching point), located at GRNET's edge connection to the Internet. We present the parameters that are most important for prefetching on GRNET's architecture and provide preliminary results of an experimental study, quantifying the benefits of prefetching on the WAN. Our experimental study includes the evaluation of two prediction algorithms: an n most popular document algorithm and a variation of the PPM (Prediction by Partial Matching) prediction algorithm. Our analysis clearly shows that Predictive prefetching can improve Web response times inside the GRNET WAN without substantial increase in network traffic due to prefetching.     

P2P流媒体Cache的置换算法

P2P流媒体cache是一种有效减少带宽开销、提高对象利用率的技术,通常采用FIFO,LRU等算法置换内容.然而,流媒体不同于Web对象,P2P网络也有别于客户/服务器模式.在分布式应用中这些算法可能影响系统的性能,为此,分析了FIFO和LRU置换算法,提出了基于供求关系的SD算法,以及基于分片副本数量的REP算法,并对其进行评估和比较.针对不同的节点到达间隔,将SD和REP同FIFO,LRU进行比较,发现在启动延迟、媒体副本数量和根节点依赖度方面SD和REP几乎均优于FIFO和LRU.同LSB(least sent bytes)算法相比,某些场景中SD的启动延迟减少了约40%,而REP在副本数量方面远远超过LSB的结果,说明在P2P网络流媒体服务中使用SD和REP缓存置换算法有助于提高系统性能.     

基于对象角色的高精度缓存替换算法*

现有的Web缓存器的实现主要是基于传统的内存缓存算法,由于Web业务请求的异质性,传统的替换算法不能在Web环境中有效工作。研究了Web缓存替换操作的依据,分析了以往替换算法的不足,考虑到Web文档的大小、访问代价、访问频率、访问兴趣度以及最近一次被访问的时间对缓存替换的影响,提出了Web缓存对象角色的概念,建立了一种新的基于对象角色的高精度Web缓存替换算法(ORB算法);并以NASA和DEC的代理服务器数据为例,将该算法与LRU、LFU、SIZE、Hybrid算法进行了仿真实验对比,结果证明,ORB算     

合作式Web缓存系统的性能分析

共享不同代理的缓存文件是减少Web通信量和减轻网络瓶颈的重要方法．在分析现有合作式缓存系统的基础上，提出一种基于混合管理的合作式Web缓存系统(HMCS）．HMCS采用重定向的方法将请求从未命中的代理转发给缓存了请求文件的代理．采用这种方法可以减少缓存文件的冗余度，从而提高了缓存系统的存储利用率，进而提高系统的命中率．性能分析和仿真结果表明HMCS系统性能要优于CRISP和ICPS系统．     

图像转换代理服务器及其在Internet中的应用

在Web服务器和客户机之间设置代理服务器，可以使不同性能的客户机浏览Internet的内容。通过分析图像在网页源文件中的表示方法，可以推断出图像在网页中的意义。根据图像在网页中的意义、客户机的性能、网络带宽和用户设置，代理服务器采用不同的转换方法和策略进行图像的转换，对图像重新编码，使转换后的图像适应于不同的客户机。     

一种基于分散协作的Web缓存集群体系结构

Web对象缓存技术是一种减少Web访问通信量和访问延迟的重要手段，该文通过分析现有的各种Web缓存系统，提出了一种基于分散协作的Web缓存集群体系结构。该体系结构克服了集中式系统需要额外配备一台管理服务器的缺陷，消除了管理服务器瓶颈失效造成系统瘫痪的危险，减少由于管理服务器带来的延迟；同时消除了分散系统的缓存不命中情况下的多级转发的延迟和缓存内容重叠，提高了资源利用率和系统效率，具有良好的可扩展性和健壮性。     

基于标记的缓存协作分布式Web服务器系统

介绍了提高Web服务器性能的前沿技术--分布式Web服务器系统,讨论了现有各种方案的优缺点,在此基础上提出一种新的分布式Web服务器系统.该系统使用基于标记的缓存协作用户请求分发方法(tag based cache cooperative Web requests distribution,简称TB-CCRD),通过前端机把系统中各个Web服务器的缓存组织成一个大的虚拟缓存系统,提高系统的整体缓存命中率,缩短了请求的响应时间;通过分布式处理TCP连接转交来消除前端机的性能瓶颈;利用标记通告URL在缓存中的位置,避免了额外的系统内部通信.从而得到了一个可扩展的高性能分布式Web服务器系统.