Web代理缓存替换策略和预取技术优化问题研究 毕业论文.pdf

分类号 密级UDC由堂暧2大学NANJING UNIVERSITY OF SCIENCE&TECHNOLOGY博士学位论文Web代理缓存替换策略和预取技术_优化问题研究 学位类别 工学博士学科名称 计算机科学与技术研究方向 计算机网络论文提交时间 2022年3月 _万方数据万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究摘 要在互联网飞速发展的今日，互联网已成为人们日常生活中不可或缺的一部分，近年来，互联网信息总量和用户数量急剧膨胀，虽然互联网硬件基础设施建设有了长 足发展，但其能提供的网络带宽和网络服务能力还是有限的。于是人们开始积极研究 在现有的硬件条件下如何提高网络服务质量。从而Web缓存（Web caching）技术应运 而生，Web缓存的基本思想是利用互联网访问时间和空间的局部特性，实现多次多 访问Web对象“取一次，用多次”的目的，将用户访问频率高的Web对象或未来可 能被访问的Web对象，缓存到离用户较近的Web缓存中，当用户访问时就可快速获 取，这样就可以减少冗余数据的传输，节约网络带宽资源、缓解服务器的网络负载压 力和缩短用户感知延迟的时间。由此，如何能更好得管理Web缓存成为了新的研 究热点，国内外研究归纳起来主要有两条技术路线：Web缓存替换策略和Web预取 技术。本文在两条技术路线上都进行了深入研究，然后融合两条技术路进一步展开研 究，取得了一些有意义的成果。本文的主要研究工作和创新点如下：1）在Web缓存替换策略技术路线上，提出一种基于计数布谷鸟过滤器的热探测 方案，该方案具有良好的空间和时间效率。同时还提出了一种自适应两级LRU方案,可以利用热探测方案自适应调节两级LRU链长度。最后将计数布谷鸟过滤器热探测 方案和自适应两级LRU相结合，形成一种新的基于热探测方案的Web缓存替换策略。实验结果表明，该策略相比其它基于热探测方案的Web缓存替换策略，时间复杂度 和空间复杂度更小，缓存命中率良好的表现。2）在Web缓存替换策略技术路线上，还提出了一种适用于Web代理缓存的智能 缓存替换策略。该策略将逻辑回归算法与LRU相结合，形成一种新的智能缓存替换 策略。通过对Web代理缓存日志的挖掘，获取影响Web缓存对象访问概率的特征值,利用逻辑回归算法建立模型，预测Web对象未来被访问的概率。同时引入L1正则化,来缩减特征值系数的绝对值，使得部分对模型影响较小的特征值系数接近于0,达到 筛选特征值的目的。实验结果表明，所提出的智能Web代理缓存替换策略对比经典 缓存替换策略和其它智能Web代理缓存替换策略，都能显著提高Web代理缓存性能。3）在Web预取技术路线上，提出一种基于分层分类算法的Web缓存预取模型，该模型能够在线学习，可以在现有层次结构中学习并更新分类模型，也可以自主增加 新的层次结构。同时还引入了输入向量在线归一化和先验附加标签。输入向量在线归 一化，可以在不知道输入向量整体的情况下，在线归一化输入向量，使其赋值范围在。到1之间。同时采用先验标签的附加过程，可以反映层次之间类的依赖关系。实验 万方数据摘要博士学位论文结果表明，所提基于分层分类算法的缓存预取模型在时间复杂度、缓存命中率和预取 命中率上都要优于其它的预取模型。4）融合Web缓存替换策略和Web预取技术路线，提出了一种集成Web预取技术 和Web缓存替换策略的缓存方案，通过制定了一个规范化的利润函数，来确定缓存 Web对象的标准化的利润，通过利润大小结合Web缓存替换策略来确定预取和驱逐 Web对象的方案。实验结果表明，在缓存命中率和预取命中率上，所提方案能有效 提高Web预取模型的性能。关键词：Web缓存替换策略、Web预取技术、布谷鸟过滤器、逻辑回归算法、Fuzzy ARTMAP算法、利润函数万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究AbstractWith the rapid development of the Internet,the Internet has become an indispensable part of peoples daily life.In recent years,the total amount of Internet information and the number of users have expanded rapidly.Although the construction of Internet hardware infrastructure has made great progress,the network bandwidth and network service capacity can be provided are still limited.So people began to actively study how to improve the quality of network service under the existing hardware conditions.Thus Web caching technology emerges.The basic idea of Web caching is Htake once,use more than once”.By using the local characteristics of Internet access time and space,users can cache web objects with high frequency of access or web objects that may be accessed in the future into the web cache near users,which can be obtained quickly when users access,In this way,redundant data transmission can be reduced,network bandwidth resources can be saved,network load pressure of server can be relieved and the time of user perception delay can be shortened.Therefore,how to manage Web cache better has become a new research hotspot.There are two main technical routes in domestic and foreign research:Web cache replacement strategy and web prefetch technology.In this paper,the two technical routes are studied in depth,and then the integration of the two technical routes for further research,and achieved some meaningful results.The main research work and innovation of this paper are as follows1)On the technical route of Web cache replacement strategy,a counting cuckoo filter hot-probe method is proposed,which exhibits a high space and time efficiency.At the same time,an adaptive two-level LRU scheme is proposed,which can adaptively adjust the length of two-level LRU chain by using the hot-probe method.Finally,a new web cache replacement strategy based on hot-probe method is formed by combining counting cuckoo filter hot-probe method with adaptive two-level LRU.Experimental results show that compared with other web cache replacement strategies based on t hot-probe method,this strategy has less time complexity and space complexity,and higher cache hit rate.2)On the technical route of Web cache replacement strategy,an intelligent cache replacement strategy suitable for web proxy cache is proposed.This strategy combines the LRU with the logistic regression algorithm to form a new intelligent cache replacement strategy.Through the mining of web proxy cache logs,the eigenvalues that affect the accessin 万方数据Abstract博士学位论文probability of Web cache objects are obtained,and the model is established by using logistic regression algorithm to predict the future access probability of Web objects.At the same time,LI regularization is introduced to reduce the absolute value of the eigenvalue coefficients,so that some of the eigenvalue coefficients which have little influence on the model are close to 0,so as to achieve the purpose of screening eigenvalues.Experimental results show that the proposed intelligent web proxy cache replacement strategy can significantly improve the performance of web proxy cache compared with the classic cache replacement strategy and other intelligent web proxy cache replacement strategies.3)On the technical route of Web Prefetching,a web cache prefetching model based on hierarchical classification algorithm is proposed.The model can learn online,learn and update the classification model in the existing hierarchy,and add new hierarchy independently.At the same time,the online normalization of input vectors and a priori tag are introduced.Input vector online normalization can normalize the input vector online without knowing the whole input vector,so that its assignment range is between 0 and 1.At the same time,the additional process of a priori label can reflect the dependency relationship between classes.Experimental results show that the proposed cache prefetching model based on hierarchical classification algorithm is superior to other prefetching models in time complexity,cache hit rate and prefetching hit rate.4)Integrating web cache replacement strategy and Web Prefetching technology route,a caching scheme integrating Web Prefetching technology and Web cache replacement strategy is proposed.A standardized profit function is formulated to determine the standardized profit of caching web objects,and the scheme of prefetching and expelling web objects is determined by profit size combined with Web cache replacement strategy.Experimental results show that the proposed scheme can effectively improve the performance of Web Prefetching model in terms of cache hit rate and prefetching hit rate.Key word：Web cache replacement strategy,Web Prefetching technology,Cuckoo filter,Logical regression algorithm,Fuzzy ARTMAP algorithm,Profit functionIV万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究目 录摘 要.IAbstract.Ill目 录.V图表目录.IX1绪论.11.1 研究背景与意义.11.2 Web 缓存.21.3 Web缓存替换策略.41.3.1 Web缓存替换策略.41.3.2 经典Web缓存替换策略分类.51.3.3 智能Web缓存替换策略.71.4 Web缓存预取技术.71.4.1 Web缓存预取技术分类.81.4.2 Web代理缓存预取技术.91.4.3 Web代理缓存预取模型分类.101.5 本文涉及数据集介绍.121.6 本文研究主要内容.121.7 本文结构安排.142基于计数布谷鸟过滤器热探测方案的Web代理缓存替换策略.172.1 弓I 言.172.2 相关工作.182.2.1 基于计数布隆过滤器的热探测机制.192.2.2 布谷鸟过滤器.202.2.3 LRU缓存替换策略.212.3 模型设计.212.3.1 基于计数布谷鸟过滤器热探测方案.212.3.2 CCF-LRU缓存替换策略.242.4 CBF和CCF错误率分析与参数设置.262.5 性能评估.282.5.1 缓存替换策略评价指标.28v万方数据目录博士学位论文2.5.2 CCF-LRU 性能分析.282.5.3 CCF-LRU和其它类型LRU改进算法对比.342.6 本章小结.343基于逻辑回归算法的智能Web代理缓存替换策略.373.1 弓I 言.373.2 LR-LRU智能缓存替换策略.383.2.1 L1正则化LR算法.383.2.2 LR-LRU智能缓存替换策略.403.2.3 LR-LRU智能缓存替换策略框架.403.3 数据预处理和特征值提取.413.3.1 数据预处理.413.3.2 特征值提取.423.4 L1-LR模型建立.433.4.1 模型训练.433.4.2 L1-LR特征值筛选和模型建立.433.5 效果评估与探讨.463.5.1 L1-LR 模型验证.463.5.2 替换策略评价指标.473.5.3 LR-LRU缓存替换策略和经典缓存替换策略对比.483.5.4 LR-LRU缓存替换策略和其它智能缓存替换策略对比.513.6 本章小结.524基于分层分类Fuzzy ARTMAP算法Web代理缓存预取技术.534.1 弓|言.534.2 相关工作.544.2.1 ART自适应共振网络.554.2.2 ART网络运行原理.574.2.3 Fuzzy ARTMAP 网络.584.3 HC-FAM 算法.624.3.1 层次分类.634.3.2 HC-FAM 算法框架.644.3.3 在线归一化.654.3.4 附加先前标签.664.3.5 HC-FAM算法学习过程.674.4 HC-FAM预取模型.68VI万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究4.4.1 数据预处理.684.4.2 HC-FAM 预取模型.694.5 效果评估与探讨.704.5.1 在线归一化验证.704.5.2 预取策略评价指标.704.5.3 HC-FAM预取模型参数设置.714.5.4 HC-FAM预取模型效果评价.734.6 本章小结.755基于利润函数集成Web预取技术的Web缓存替换策略.775.1 引言.775.2 设计动机.785.3 基于利润函数集成Web预取技术的Web缓存替换策略.805.3.1 预取算法定义.805.3.2 标准化的禾（J润函数.805.3.3 ICP缓存预取模型.835.3.4 ICP缓存预取标准化利润函数计算流程.835.3.5 ICP策略工作流程示例说明.865.4 效果评估与探讨.875.4.1 预取策略评价指标.875.4.2 ICP预取效果评价.875.5 本章小结.906总结与展望.936.1 本文工作总结.936.2 未来工作展望.94致 谢.97参考文献.99附 录.111VII万方数据万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究图表目录图1.1 Web缓存三种部署节点位置的示意图.2图1.2用户端缓存模型示意图.3图1.3反向Web代理缓存模型示意图.3图1.4 Web代理缓存模型示意图.4图1.5 Web缓存替换策略流程图.5图1.6 Web代理缓存预取技术流程图.9图1.7用户请求、候选预取Web对象和预取Web对象之间的集合关系.10图1.8本文章节结构图.14图2.1计数布隆滤器热探测方案示意图.19图2.2布谷鸟过滤器示意图.21图2.3 LRU缓存替换策略示意图.21图2.4计数布谷鸟过滤器热探测方案示意图.22图2.5 CCF-LRU缓存替换策略两级LRU链.25图2.6 CCF-LRU缓存替换策略示意图.25图2.7自适应两级LRU链.26图2.8计数链表示意图.29图2.9四种缓存替换策略HR比较.30图2.10 CCF-LRU和其它类型LRU改进算法比较.34图3.1智能缓存替换策略框架.41图3.2 Web代理缓存日志示例.41图3.3十折交叉验证法示意图.43图3.4特征值相关矩阵.45图3.5三种模型ROC曲线比较.47图3.6 LR-LRU策略和经典策略HR对比.49图3.7 LR-LRU和经典缓存替换策略BHR对比.49图3.8 LR-LRU和其它智能缓存替换策略对比.51图4.1 ART网络系统结构.55图4.2 ART网络系统C层结构示意图.56图4.3 ART网络系统R层结构示意图.56图4.4 Fuzzy ARTMAP网络算法主要流程图.60IX万方数据图表目录博士学位论文图4.5 Fuzzy ARTMAP网络拓扑结构示意图.62图4.6两种层次分类器示意图.63图4.7简化后的Fuzzy ARTMAP网络拓扑图.64图4.8 HC-FAM算法框架.65图4.9 URLs和Cluster之间的权重.69图4.10不同警戒值p和预取阈值c下的HR热力图.72图4.11三种预取模型和LRU策略的HR对比.74图4.12三种预取模型和LRU策略的BHR对比.74图5.1示例2示意图.78图5.2示例3和4示意图.79图5.3算法说明示例.84图5.4 ICP算法工作流程示例图.86图5.5六种策略的HR比对图.88图5.6六种策略的PHR比对图.89表1.1经典Web缓存替换策略优缺点.7表1.2不同类型Web缓存预取技术对比.8表1.3 Web日志数据集基本信息统计.12表2.1模型参数符号及其含义.18表 2.2 CBF-LRU、CCF-LRU 和 CLL-LRU 对于 LRU 的 IR.31表2.3 CBF、CCF和CLL三种热探测方案空间复杂度.32表2.4 CBF、CCF和CLL三种热探测方案时间复杂度.33表3.1包裹式特征值筛选后的特征值.45表3.2分类结果混淆矩阵.46表3.3在DEC数据集中LR-LRU和经典策略的IR统计.50表3.4在NLANR数据集中LR-LRU和经典策略的IR统计.50表4.1在线归一化效果评估.70表4.2不同参数条件下HC-FAM预取模型时间复杂度.73表4.3三种预取模型的性能比较.75表5.1使用符号含义.81表5.2 ICP算法示例预取规则表.86表5.3结合ICP算法预取模型和原预取模型HR的IR.89表5.4结合ICP算法预取模型和原预取模型PHR的IR.90 x万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究1绪论1.1 研究背景与意义在互联网飞速发展的今日，互联网已成为人与人之间互动的重要平台，是人 们日常生活中不可或缺的一部分。近年来，互联网上信息总量和用户数量急居U膨胀，虽然互联网硬件基础设施建设有了长足发展，但其能提供的网络带宽和网络服务能力 还是有限的。由于互联网应用服务的多样化、用户量剧增以及Web服务和网络固有 的延迟等，在硬件层面，用户的访问延迟、网络服务质量很难进一步改善山。软件层 面，通过Web缓存技术（Web Caching）来提升网络服务质量，Web缓存的基本思 想是利用互联网访问时间和空间的局部特性，实现多次多访问Web对象“取一次，用多次”的目的，将用户访问频率较高的Web对象和未来可能被访问的Web对 象，缓存在离用户较近的缓存中，当用户访问时就可快速获取，这样就可以减 少冗余数据的传输，节约网络带宽资源、缓解服务器的网络负载压力并缩短用 户感知延迟的时间。Web缓存可以在互联网中的各个节点部署：在客户端、Web源服务器端（反向Web缓存代理）或Web代理服务器端（Web缓存代理）,图1.1图1.6描述了三种部署节点的位置示意图。本文主要研究的是在Web代理服务器端的Web缓存优化问题。Web代理服 务器通常部署在互联网靠近用户端的地方，用户请求到达 Web代理服务器后，Web代理服务器查询Web缓存是否命中，如命中则从Web缓存中返回给用户，如未命中则Web代理用户端从源Web服务器获取Web对象，缓存后返回Web 对象给用户。这样就能降低用户的访问延迟、提高网络的服务质量。此时如何才能更好得管理Web代理缓存就成为了研究热点问题。为优化 Web代理缓存，多年来国内外的学者提出了很多方案，归纳起来主要有两条技 术路线：Web缓存替换策略和Web预取技术。Web缓存替换策略和Web预取技 术分别通过缓存热点Web对象和预取将来可能被访问的Web对象，来实现对 Web缓存的管理。Web缓存替换策略利用了时间局部性，而Web预取技术利用 了 Web对象的空间局部性。本文针对Web缓存优化问题，深入研究了 Web缓存替换策略和Web预取 技术两条技术路线。在Web缓存替换策略技术路线上提出了基于计数布谷鸟过 滤器热探测方案的Web代理缓存替换策略和基于逻辑回归算法的智能Web代理 缓存替换策略，在Web预取技术路线上提出了基于分层分类的Fuzzy ARTMAP 算法Web代理缓存预取技术，最后融合两条技术路线提出了基于利润函数集成1万方数据1绪论博士学位论文Web预取技术的Web缓存替换策略。1.2 Web缓存缓存技术是计算机体系中应用较早、较成熟的技术。其基本原理是在内存（或高速存储介质）中开辟一块存储空间，用来存储用户访问过的数据或用户 未来可能会访问的数据，当用户请求这些数据时可以直接从Web缓存中返回给 用户，而不需要从外存（或低速存储介质）中读取。根据所处的位置不同，可将Web缓存分为三类：用户端缓存、Web服务器 端缓存（反向Web代理缓存）和Web代理服务器端（Web缓存代理），其位置 分别处于用户浏览器端、靠近用户路由端和靠近源 Web服务器路由端，具体 位置如图1.1所示。网户图1.1 Web缓存三种部署节点位置的示意图1）用户端缓存用户端缓存部署在用户的浏览器上，用户端缓存占用用户系统一部分的存 储空间，缓存热点Web对象，也可以理解为浏览器自带的高速缓存。用户端缓 存包括长期性缓存（如用户账户信息、用户配置、首页信息等）和临时缓存（如用户表单、热点Web对象、当前打开网页等）。由于用户端存储容量不会太大，所以用户端缓存容量通常较小，能够缓存 的Web对象不会太多，这导致缓存命中率偏低。而用户可能会同时使用多个浏 览器，不同浏览器之间的缓存不能进行互通和贡献，也在一定程度上造成了不 必要的浪费。用户端缓存是私有的，一般不会多用户共享。这些都使用户端缓 存对互联网整体性能提升有限。如图1.2所示，是用户端缓存模型示意图。2万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究图1.2用户端缓存模型示意图2)反向Web代理缓存反向Web代理缓存部署在靠近Web源服务器路由端，主要服务对象是Web 源服务器，主要依据和Web源服务器达成的协议，缓存静态资源，动态资源一 般不缓存。反向Web代理服务器能够分担Web源服务器的压力，在网络负载压 力很高的情况下，即使Web源服务器使用了自身缓存，但仍然无法应对巨大的 负载，因此需要反向Web代理服务器的协助。Web代理服务器收到请求后，如 果请求的是缓存数据或静态数据，则直接返回给用户，而无需再访问Web源服 务器，从而缓解Web源服务器的压力。如图1.3是反向Web代理缓存模型示意 图。图1.3反向Web代理缓存模型示意图3)Web代理缓存Web代理服务器部署在用户端与Web源服务器之间，靠近用户路由器附近。用户的访问请求首先到达Web代理服务器，如果Web代理缓存命中，直接返回 给用户，如果没有命中，Web代理服务器代替用户向Web源服务器发起请求。3万方数据1绪论博士学位论文如图1.4是Web代理缓存模型示意图。Web代理服务器是用户端和Web源服务器端的桥梁，Web代理服务器既可 以看作是用户，又可以看作是Web服务器，同时为多个用户和Web源服务器提 供网络服务。Web代理缓存对比其它模型具有如下优势：Web代理缓存比用户缓存具有更大缓存容量，可以存储更多的Web对象，同 时可以服务多个用户，实现了数据共享。Web代理缓存能够有效的减少相同页 面的重复请求和传输，节约了有限的带宽和流量。Web代理服务器比Web源服务器和反向Web代理服务器离用户端更近，当 用户发送请求时，距离更近的Web代理服务器可以直接响应请求，比反向Web 代理缓存模型更能减小用户访问延时。Web代理服务器可以作为Web源服务器分流，能够有效的减轻Web源服务 器的访问负担，尤其是对于热点数据访问请求。Web代理服务器还能提高了网络服务的稳定性，当Web源服务器发生故障导 致用户不能访问时，可以通过Web代理服务器缓存的数据响应用户请求。Web代理缓存是最常用的Web缓存模型，如何更好得管理Web代理缓存是是近 年研究的热点，本文研究的Web缓存就建立在Web代理缓存模型上。图1.4 Web代理缓存模型示意图1.3 Web缓存替换策略1.3.1 Web缓存替换策略Web缓存的基本思想是利用互联网访问时间和空间的局部特性，实现多次多访 问Web对象“取一次，用多次”的目的，将用户访问频率高的Web对象和未来可能 被访问的Web对象，缓存到离用户较近的Web代理缓存中，当用户再次访问时就可 快速获取，这样就可以减少冗余数据的传输，节约网络带宽资源、缓解服务器的网络 负载压力和缩短用户感知延迟的时间。4万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究Web缓存替换策略主要任务是管理Web缓存，当Web缓存容量将达上限，新的 Web对象缓存到Web缓存时，根据Web缓存替换策略替换，将Web缓存中一部分 Web对象驱逐出去Web缓存，为新的Web对象腾出空间。一般被驱逐的Web对象为:时间较为久远、访问次数较少或命中率较低的Web对象。Web缓存替换策略流程图 如图1.5所示。获取用户请 求对象图1.5 Web缓存替换策略流程图1.3.2 经典Web缓存替换策略分类经典的Web缓存替换策略，主要分为以下五种类型：1)基于随机的策略基于随机的策略(Random algorithm,RAND)策略是基于随机的代表策略，该类 5万方数据1绪论博士学位论文策略利用软件或硬件的随机数发生器来确定主存储器中被替换的对象。这类策略最简 单，最容易实现。但这类策略完全没有考虑对象各种影响因素，因此命中率比较低，主要用户缓存较小的或计算能力较低的应用中，RAND策略使用现实中使用较少，在用户端Web缓存中有所应用。2)基于访问时间的策略基于访问时间的策略(Least Recently Used algorithm,LRU)是基于访问时间的代 表策略，该策略把近期最久没有被访问过的对象作为被替换的对象。优点是比较容易 实现，时间复杂度低，但它忽略对象的频率、大小等因素，存在缓存污染的问题。LRU策略是最常用的Web缓存替换策略。3)基于访问频率的策略基于访问频率的策略(Least Frequently Used algorithm,LFU)是基于访问频率代 表策略，该类策略选择近期最少访问的对象作为被替换的对象，可以避免缓存污染的 问题。显然，这是一种非常合理的策略。但是，该策略实现起来非常困难，它要为每 个对象设置一个计数器，并且要选择一个固定的时钟为每个计数器定时计数。同样其 仅考虑缓存对象的频率因素，忽略缓存对象其他因素。LFU策略一般用在Web对象 尺寸较大的特定的反向Web代理缓存中。4)基于对象尺寸的策略SIZE策略是基于对象尺寸代表策略，该类策略在新对象需要空间时从缓存中 替换尺寸最大对象。该策略简单易行。但缓存可以被小对象污染，这些小对象不会再 次被访问，却很难被替换。其缓存命中率高，但字节命中率低。5)基于函数评价的策略。(Greedy Dual Size,GDS)和 GDSF(Greedy Dual-Size Frequency,GDSF)策略口】是 基于函数评价的代表策略，这策略可以通过选择合适的加权参数，来优化缓存性能。可以考虑多个影响因素来处理不同应用场景。但这策略如何选择合适的加权参数，是 一个十分困难的任务，其次在对函数值的计算中可能会引入新的问题。表1.1总结了经典Web缓存替换策略的优缺点。6万方数据博士学位论文Web代理缓存替换策略和预取技术优化问题研究表1.1经典Web缓存替换策略优缺点策略简介优点缺点RAND利用随机数发生器确定优先驱逐Web对象算法实现最简单未考虑任何因素，性能不稳定；命中率低。LRU优先驱逐最近最少使用的Web对象算法实现较简单，命 中率较好只考虑了时间因素，忽略了其他因素；存在缓存污染。LFU优先驱逐最不常用的Web 对象可以防止缓存污染仅考虑频率因素，忽略其他因素；算法空间复杂度高。SIZE优先驱逐尺寸最大的Web 对象易于实现，优先保留 小尺寸Web对象，缓 存命中率高优先存储小尺寸Web对象，即使这些对象再也不会被访问；低字节命中率。GDSF综合了频率和尺寸因素，引入了老化函数和时间因 素确定优先驱逐Web对象通过删除用户不再请 求的对象，克服SIZE 策略的弱点计算成本高，参数调整复杂；字节命中率低。1.3.3智能Web缓存替换策略从表1.1中可以看出经典的缓存策略通常只考虑一个因素，或者结合数学公式附 加考虑两个因素，但由于Web缓存环境不断变化，实际应用中，经典缓存策略效率 并不高。为了提高Web缓存性能，国内外很多研究者提出许多智能缓存替换策略。最近的研究表明，与经典Web缓存替换策略相比，智能Web缓存替换策略不但能体 高Web缓存性能，还更能适应网络环境变化。Akbari Bengar等口”提出了一种基于聚类算法的智能Web缓存替换策略，该策略使用包含最近访问时间，频率和参考速率三个参数的Fuzzy means算法。定义每个簇最小数量为缓存对象的10%。优先驱逐不在簇中的Web对象。Im.Y等口21提出了一种可刺激神经网络SNN-Cache的智能Web缓存替换策略，利 用可刺激神经网络分析用户请求序列关系，建立模型预测Web对象的访问序列。SNN-Cache将缓存过程划分为数据接收、数据预处理、SNN滤波器和驱逐计算 模块的四阶段。Hoang and Bui等1提出了一种基于语义感知缓存(FSA)的智能 Web缓存替换策略。使用语义距离作为指标。同时基于函数度量组合访问频率和 Web尺寸大小以行串联，最终选择驱逐 Web对象。Zhang”旬提出了一种基于 K-Means聚类算法的智能Web缓存替换策略，利用K-Means聚类算法RFS模 型进行分段，得到分段值，并对段内数据进行排序，以确定驱逐Web对象。1.4 Web缓存预取技术7万方数据1绪论博士学位论文Web预取技术是另一种行之有效得解决Web缓存问题的方案，Web预取技术的 基本思想是：是基于预取规则或算法，预测用户未来可能会访问的Web对象，并提 前将Web对象预取到缓存中。这样未来当用户需要访问时，Web对象已经在缓存中,从而增加Web缓存的命中率，并极大减少了用户访问延迟。Web预取技术充分利用 Web对象的空间局部性，有效地减少用户感知的延迟，提高了网络服务质量。1.4.1 Web缓存预取技术分类和Web缓存分类一样，Web缓存预取技术根据不同部署位置可分为三类：用户 端、Web代理缓存端和Web源服务器端类型。基于用户端的预取类型，是单一用户 浏览多个Web服务器的导航模式。基于代理缓存端的预取类型，是于一组用户在多 个Web服务器上的导航模式15口6口7。基于服务器端的预取类型，是访问单个网站的 所有用户的导航模式。表L2总结了不同类型的Web缓存预取技术优缺点。表1.2不同类型Web缓存预取技术对比预取位置预测模型