（计算机应用技术专业论文）网络环境下enroute缓存算法的性能改进.pdf

英文题目：p e r f o r m a n c ei m p r o v e m e n t 。fe n 。r o u t e c a c h i n ga l g o r i t h m b a s e do nw e br e q u e s t c h a r a c t e r i s t i c s 一1 主题词： 英文关键词： 课题来源： l ii 南京邮电大学硕士研究生学位论文 摘要 摘要 i n t e r n p t 技术和耽6 服务的迅猛发展，导致网络拥塞和服务器负载过大成为用户面临 的两大问题。在网络中设置缓存，以空间换取时间己成为降低用户感知延时的主流方法之 一。勘加“t e 网络缓存技术利用缓存服务器，也称作代理缓存，将内容从中心服务器推向 网络的边缘，使得内容距离用户只有一步之遥，大大减少了主干网络的缓存流量，减轻了 网络负担，有着广泛的应用前景。 砌加“t e 网络缓存技术主要包括缓存的位置选定，代理缓存替换算法，代理缓存一致 性策略和代码转换网络缓存等几个核心问题。国内外学者针对这几个方面都做了大量的工 作，并提出了一系列的算法。本文旨在前人研究的基础上，提出更为高效，更能反映网络 环境的算法。替换策略以某一项或几项性能指标为标准，将价值较低的副本替换出缓存的 算法。传统替换算法有先进先出策略，最近最少使用策略，最少使用频率策略等，被广泛 应用于缓存策略中。除此之外，能够标志文件的关键特征的属性也被用于替换的标准，如 缓存的大小，基于阀值缓存策略里的阀值大小，以及量化以后的流行度值等。一致性策略 和替换策略对减少代理缓存的成本影响很大。在替换策略中加入一致性策略能提高代理缓 存系统的整体性能；好的一致性策略和好的替换策略相结合能减少网络成本。然而，很少 有人将一致性算法融入到替换算法中。 为了进一步提升代理缓存系统的整体性能，将一致性策略有机的融入到替换策略中， 本文提出一种高效的自适应代理缓存一致性替换算法a c r a ( a d a p t i v ec o n s i s t e n c ya n d r e p l a c e m e n ta l g o r i t h m ) 。本算法中的致性策略采用了自适应t t l 机制，替换策略是在分 析了w e b 轨迹的基础上，找出用户访问w e b 内容的访问特性：访问再次发生的概率和访问 内容大小的分布情况，并以此建立相应代价公式，作为替换标准中计算缓存内容价值的要 素。 通过仿真模拟实验，表明了a c r a 在命中陈旧比上优于传统的几命替换算法。 关键词：e n - r o u t e ，w e b 缓存，缓存替换算法，一致性策略，访问特性 今 ， h ， t l a b s t r a c t t h er a p i dd e v e l o p m e n to fi n t e m e ta n dw e bs e r v i c e sr e s u l ti nn e t w o r kc o n g e s t i o n a n ds e r v e r s o v e r l o a d i tt r o u b l e st h eu s e r sal o t c a c h ei nt h en e t w o r ks e t t i n g si n o r d e rt ot r a d es p a c ef o rt i m et or e d u c et h eu s e rp e r c e i v e dl a t e n c yh a sb e c o m et h e m a i n s t r e a mm e t h o d s e n - r o u t ew e bc a c h i n gu s ec a c h es e r v e rw h i c ha l s ok n o w na s p r o x yc a c h i n g ，t op u s ht h ew a n t e dc o n t e n tf r o mac e n t r a ls e r v e rt ot h en e t w o r ke d g e w i t ht h ep u r p o s eo fm a k i n gt h ec o n t e n t sn e a r e rt ot h eu s e r s i tg r e a t l yr e d u c e st h e b a c k b o n en e t w o r kc a c h et r a f f i ca n dr e l e a s e st h eb u r d e no nt h en e t w o r ki th a sb r o a d a p p l i c a t i o np r o s p e c t s e n r o u t ew e bc a c h i n gi n c l u d e ss e v e r a lc o r ei s s u e s ：c a c h el o c a t i o n ，r e p l a c e m e n t t a l g o r i t h m ，c o n s i s t e n c ys t r a t e g ya n dt r a n s c o d i n gw e bc a c h i n g al o to fw o r kh a sb e e n d o n eb yt h es c h o l a r sd o m e s t i ca n df o r e i g n t h i st h e s i sa i m sa tm a k i n gt h e s e a l g o r i t h m sm o r ee f f i c i e n t t h er e p l a c e m e n ta l g o r i t h m sd e l e t et h el o w - v a l u eo b j e c t r e p l a c e m e n ta l g o r i t h m sa n dc o n s i s t e n c ys t r a t e g i e sh a v eag r e a ti m p a c ti nr e d u c i n g t h ec o s to fp r o x yw e bc a c h i n g a d d i n gc o n s i s t e n c ys t r a t e g yi nr e p l a c e m e n ta l g o r i t h m w i l li m p r o v et h eo v e r a l lp e r f o r m a n c eo fp r o x yc a c h e h o w e v e rf e wp e o p l eg e tt h e m t o g e t h e r i no r d e rt oi m p r o v et h eo v e r a l lp e r f o r m a n c eo fp r o x yc a c h ei nt h ec o n t e n t d e l i v e r yn e t w o r k ，t h ec a c h ec o n s i s t e n c yp o l i c yi sc o m b i n e dw i t ht h ec a c h e r e p l a c e m e n tp o l i c ya n da ne f f i c i e n ta d a p t i v ec o n s i s t e n c y r e p l a c e m e n ta l g o r i t h mi s p r o p o s e dc a l l e da c r a ( a d a p t i v ec o n s i s t e n c ya n dr e p l a c e m e n ta l g o r i t h m ) t h e c a c h ec o n s i s t e n c yp o l i c yo fo u ra l g o r i t h mi s a d a p t i v et t lm e c h a n i s m ，w h i l et h e r e p l a c e m e n tp o l i c yi sb a s e do nt h ea n a l y s i so fw e bt r a c e t h ec h a r a c t e r i s t i c so f d c u g t o m e r sv i s i tt ow e ba r ef o u n d ，w h i c hi n c l u d et h er a t i oo f t h er e q u e s to n c ea g a i na t t h ew e bc o n t e n ta n dt h ed i s t r i b u t i o no ft h ec o n t e n ts i z e t h er e p l a c e m e n tp o l i c yi s b a s e do nt h e s ee l e m e n t s u s i n gt r a c e d r i v e ns i m u l m i o n ，t h er e s u l t ss h o wt h a tt h ea c r a p e r f o r m sb e t t e r - a i i i ， 南京邮电大学硕士研究生学位论文目录 目录 摘要i a b s t r a c t i i 目录i v 第一章绪论1 1 1 课题研究背景及意义1 1 1 1 课题背景1 1 1 2 研究现状2 1 1 3 课题意义4 1 2 本文主要工作4 第二章e n r o u t e 网络缓存系统6 2 1 内容分发网络c d n 6 2 2 网络缓存7 2 2 1 缓存的实现原理7 2 2 2 缓存的分类9 2 3 网络缓存布局1 1 2 3 1 层次式j l l 2 3 1 分布式1 4 2 3 1 混合式1 7 2 4 网络缓存放置方法，1 8 2 4 1 基于查询频率：1 学 2 4 2 基于概率1 9 2 4 3 启发式算法2 0 2 4 4 基于对象特征值：2 l 第三章缓存算法2 3 i v 南京邮电大学硕：匕研究生学位论文 目录 3 1 一致性策略2 3 3 2 替换策略2 5 3 3 缓存性能2 9 3 3 1 用户感知延迟2 9 3 3 2 缓存空间利用率3 0 3 3 3w e b 缓存系统理想特性3 0 第四章a c r a 算法3 3 4 1w e b 访问特性3 3 4 1 1 用户访问的时序性3 3 4 1 2 用户访问的内容大小分布3 4 4 2 算法思想3 6 4 2 1 一致性策略的选择3 6 4 2 2 替换策略的数学模型3 6 4 2 3 算法处理流程3 7 4 3 算法设计3 8 4 3 1t t l 机制3 8 4 3 2 替换策略3 9 第五章算法的实现和性能分析4 l 5 1 性能指标4 l 5 1 1 陈旧率4 1 5 1 2 命中率字节命中率4 l 5 1 3 命中陈旧比4 2 5 2 模拟运行环境4 2 5 2 1 服务器端4 2 5 2 2 鼎系统4 3 5 2 3 客户端4 3 5 2 4 程序执行过程4 4 5 3 仿真结果4 5 v 南京邮电大学f i 贞上研究生学位论文 目录 第六章总结与展望4 8 致谢4 9 攻读硕士期间的学术论文5 0 攻读硕士期间参与的项目5 1 参考文献5 2 南京邮电人学硕士研究生学位论文 第一章绪论 第一章绪论 1 1 课题研究背景及意义 1 1 1 课题背景 i n t e r n e t 的高速发展，给人们的工作和生活带来了极大的便利，它用一种简 单的方式获取大量的信息和服务。今天，i n t e r n e t 已连接6 0 0 0 0 多个网络，正式 连接8 6 个国家，电子信箱能通达1 5 0 多个国家，有4 8 0 多万台主机通过它连接 在一起，用户有2 5 0 0 多万，每天的信息流量达到万亿比特以上，每月的电子信 件突破1 0 亿封。同时，i n t e r n e t 的应用已经渗透到了各个领域，从学术研究到股 票交易、从学校教育到娱乐游戏、从联机信息检索到在线居家购物等，都有长足 的进步。因此人们对i n t e r n e t 的服务品质和访问速度要求也越来越高。虽然带 宽不断增加，用户数量也在不断增加，受w e b 服务器的负荷和传输距离等因素 的影响而导致的响应速度慢甚至无法响应的情况，还是经常困扰用户。对于电子 商务类网站，有所谓8 秒定律，即用户访问一个网站时，如果等待网页打开的 时间超过8 秒，会有超过3 0 的用户放弃等待。据资料显示，估计每年由于网 络问题( 缓慢甚至不通) 导致电子商务方面的损失高达4 4 亿美元，那么怎样才能 够最大限度地降低由于网络访问缓慢带来的直接或者间接的经济损失呢? 解决 方案就是在网络传输上利用缓存技术使得w e b 服务数据流能就近访问，优化网 络数据传输非常有效的技术，从而获得高速的体验和品质保证。 为了解决这些问题，提出了一种新型的内容分发网络( c o n t e n td e l i v e r y n e t w o r k ，c d n ) ，利用缓存服务器，也称作代理缓存，将内容从中心服务器推向 网络的边缘，使得内容距离用户只有一步之遥。网络缓存技术，其目的就是减少 _ 网络中冗余数据的重复传输，使之最小化，将广域传输转为本地或就近访问。互 联网上传递的内容，大部分为重复的数据，c a c h e 服务器及应用c a c h i n g 技术 的网络设备，可大大优化数据链路性能，消除数据峰值访问造成的结点设备阻塞。 c a c h e 服务器具有缓存功能，所以大部分网页对象( w e b p a g eo b j e c t ) ，如h t m l 、 h t m 、p h p 等页面文件，g i f , t i f , p n g 、b m p 等图片文件，以及其他格式的文件， 1 南京邮电人学颂：e 研究生学位论文 第一章绪论 在有效期( r r l ) 内，对于重复的访问，不必从原始网站重新传送文件实体，只需 通过简单的认证( f r e s h n e s sv a l i d a t i o n ) 一传送几十字节的h e a d e r ，即可将本地 的副本直接传送给访问者。由于缓存服务器通常部署在靠近用户端，所以能获得 近似局域网的响应速度，并有效减少广域带宽的消耗。据统计，i n t e r n e t 上超过 8 0 的用户重复访问2 0 的信息资源，给缓存技术的应用提供了先决的条件。 缓存服务器的体系结构与w e b 服务器不同，缓存服务器能比w e b 服务器获得更 高的性能，缓存服务器不仅能提高响应速度，节约带宽，对于加速w e b 服务器， 有效减轻源服务器的负荷是非常有效的。 1 1 2 研究现状 为了达到减少用户感知延时的目的，越来越多的御( 英特网服务提供商) 致力于增加网络带宽，完善网络状况。这在一定程度上缓解了网络的压力，也起 到了一定的效果，然而，随着网络用户的增加，w e b 网络业务的不断多元化， 用户对网络的流量要求越来越高，使得我们不得不改变视角，另辟蹊径来解决这 个问题。 e n r o u t e 来自法文，意思是“o n t h e w a y ”。就是在客户端和服务器之间设置 网络代理缓存系统，每个e n r o u t e 网络缓存监听通信线路上发向服务器的并即将 通过该缓存的资源请求，并尽最大努力响应。 e n r o u t e 缓存算法的研究方向主要包括： 1 网络缓存的放置策略。沈红等人对基于线性结构的，基于树状结构的算法 做了深入的研究。用动态规划法在可调节网络缓存中提出了针对树状网络结构和 自治系统的最优算法。 2 网络缓存的替换策略。缓存替换策略的研究并不是一个很新的课题，前人 已经提出很多替换策略，传统替换算法有先进先出策略，最近最少使用策略，最 少使用频率策略等，被广泛应用于锾存策略中。除此之外，能够标志文件的关键 特征的属性也被用于替换的标准，如缓存的大小，基于阀值缓存策略里的阀值大 小，以及量化以后的流行度值等。g r e e d yd u a l s i z e ( g d s ) 提出基于效用函数 的缓存策略，是一种策略的集合体，它考虑了局域性、对象大小、延迟、代价等 因素，g d - s 相对于其他的置换方法如l r u ，l f u ，s i z e 等方法在缓存字节命中 南京邮电大学硕士研究生学位论文 第一章绪论 率、字节缓存命中率、网络丌销等方面具有更多的优势，算法本身并没有规定其 函数的类型和元素个数，其方法思想的提出旨在使设计者能够充分利用网络元 素，更好的反映所使用算法的针对性。然而，很少有人将一致性算法融入到替换 算法中。迄今为止，我们发现国内外的研究中仅有几篇有将这两种策略结合起来 的想法：j s h i m 等人基于最优化模型提出了l n c r 1 4 1 3 u 算法f 2 】。该算法包括 缓存二致性策略和缓存替换算法两部分，它根据代价函数来考虑取回每一网页放 入缓存的延迟和用t t l ( t i m e t o 1 i v e ) 来验证每一网页的新鲜程度以决定是否替换。 通过t r a c e d r i v e n 模拟验证了其能取得较好的性能。不过，l n c - r w 3 u 只考 虑网页的大小和访问延迟，并且计算相当复杂，一些参数设置要非常小心。丑 k r i s h n a m u r t h y 等人分别用两种一致性策略和两种替换策略的4 种组合通过 t r a c e d r i v e n 模拟来研究缓存一致性策略和替换策略之间的相互影响 4 1 。他们的 主要研究成果有：一致性策略和替换策略对减少代理缓存的成本影响很大；在替 换策略中加入一致性策略能提高代理缓存系统的整体性能；好的一致性策略和好 的替换策略相结合能减少网络成本。j a g u i l a r 等人提出了缓存自适应一致性一 替换机制( 3 】。这种机制将一致性策略和替换策略结合起来，在保证缓存一致性的 自订提下，利用共享缓存存储单元的状态信息来察觉用户的访问行为，在替换阶段 对不同的访问对象采用不同的替换策略。但是，因为这种机制要考虑很多参数， 实现起来很困难，所以，他们没有任何实验依据，只是理论上的探讨。由这3 篇 文献取得的研究成果可以概括地说：一致性策略和替换策略对代理缓存系统的性 能影响很大，如果这两种策略能很好地结合起来，代理缓存系统可以获得更好的 整体性能。但时至今日，这两种策略还没有很好地结合起来。 3 代码转换网络缓存。k e q i u l i 等人提出了代码转换网络缓存的基本模型【9 1 ， 即通过转换缓存中已有的副本成为客户请求资源，已达到节省网络流量的目的。 李春红等人在沈红的基础上对e n - r o u t et r a n s c o d i n g 缓存中的缓存路由和协同 i 放置及替换问题进行了研究提出了c c r a ( c o s t - a w a r ec a c h er o u t i n g 口伽r i t h m ) 缓存路由算法， 能以可控的探测开销来发现潜在的、具有最小访问开销的缓存 对象。在此基础上，建立了e n r o u t et r a n s c o d i n g 缓存的分析模型，将缓存放置和 替换问题形式化为一个最优化问题，并利用一种基于动态规划的方法来求解最佳 1 南京邮电火学硕士研究生学位论文 第一章绪论 缓存放置策略。 1 1 3 课题意义 研究e n r o u t e 代理缓存系统的主要目的就是为了减少网络冗余，缓解网络负 担，提高网络性能，降低用户感知延时。在网络中如何放置代理缓存，即代理缓 存的设置位置是一个值得研究的问题。而除此之外，网络缓存的一致性策略和替 换策略的研究是提高代理缓存系统性能的另外两个不容忽视的研究方向。而以往 的研究往往局限于将这两种策略作为两种独立的机制分开研究，虽然取得了不少 成果，也局部的提高了缓存的性能，然而没有将两者结合起来，从而不能完美的 提升代理缓存系统的整体性能。本文考虑如何将这两种策略有机地结合起来，并 拟合能反应用户访问模式的访问特性，探讨了代理缓存一致性策略和替换策略的 处理流程、性能评价指标和研究现状，进而提出将这两种策略结合起来的一致性 ， 一替换算法的处理流程和主要性能评价指标。 1 2 本文主要工作 本课题的目标是研究适应于用户访问特性的快速、准确、高效的自适应代理 缓存一致性替换策略，用以缓解日益严重网络负载，减少用户感知延时。 本文在分析用户w e b 访问特性的基础上，找出用户对w e b 访问在时间和空 间上的特性，通过对轨迹文件的分析显示w e b 访问具有很强的时间局部性，时间 局部性是代理缓存系统所看到的w e b 业务普遍具有的一个性质。也就是说用户 都倾向于再次访问近来访问过的内容。其主要原因一是用户对网络内容的访问在 时间上呈现局部性，另外一个重要原因是用户对内容的兴趣重叠。另外，许多臃6 访问特性的研究发现：耽6 对象的大小分布服从p a r e t o 分布，这就在空间大小 上为w e b 访问特性做出了归纳。 针对以往将一致性策略和替换策略分开研究从而导致两者不能很好融合的 ： 现状，本课题将一致性策略融入到替换策略中，完美的将两者结合了起来，旨在 更好的发挥缓存系统的整体性能。最后给出了模拟运行环境和仿真结果，并对结 果加以分析。 全文分为六章，具体安排如下： 4 南京邮电大学硕士研究生学位论文 第一帝绪论 第一章绪论：介绍了课题研究的背景、现状及意义，并列出了全文的组织 结构。 第二章e n r o u t e 网络缓存系统：详细介绍了应用e n r o u t e 缓存算法的网络 缓存系统的布局，结构，放置方法以及w e b 缓存系统的理想特性。 第三章缓存算法：系统介绍了几种常见的一致性替换策略和目前使用较多 的一些替换策略，并进行了分析，列出各算法的优劣。 第四章a c r a 算法：自适应一致性替换算法的详细介绍。包括w e b 访问特 性，算法的思想和设计流程。 第五章算法的实现和性能分析：模拟算法运行环境，通过实验和性能分析 比较，标明a c r a 算法在命中陈旧比上由于传统的几个算法。 第六章总结与展望：对本文工作进行了总结，并指出需要进一步改进的内 容。 南京邮电大学硕士研究生学位论文 第二章e n r o u t e 网络缓存系统 第二章e n r o u t e 网络缓存系统 2 1 内容分发网络c d n c d n 的全称是c o n t e n td e l i v e r yn e t w o r k ，即内容分发网络。其目的是通过在 现有的i n t e r n e t 中增加一层新的网络架构，将网站的内容发布到最接近用户的网 络”边缘”，使用户可以就近取得所需的内容，解决i n t e r n e t 网络拥塞状况，提高 用户访问网站的响应速度。从技术上全面解决由于网络带宽小、用户访问量大、 网点分布不均等原因，解决用户访问网站的响应速度慢的根本原因。 狭义地讲，内容分发网络( c d n ) 是一种新型的网络构建方式，它是为能在传 统的伊网发布宽带丰富媒体而特别优化的网络覆盖层；而从广义的角度，c d n 代表了一种基于质量与秩序的网络服务模式。简单地说，内容分发网是一个经策 略性部署的整体系统，包括分布式存储、负载均衡、网络请求的重定向和内容管 理四个要件，而内容管理和全局的网络流量管理( t r a f f i cm a n a g e m e n o 是c d n 的 核心所在。通过用户就近性和服务器负载的判断，c d n 确保内容以一种极为高 效的方式为用户的请求提供服务。总的来说，内容服务基于缓存服务器，也称作 代理缓存( p r o x yc a c h i n g ) ，它位于网络的边缘，距用户仅有”一跳”( s i n g l eh o p ) 之 遥。同时，代理缓存是内容提供商源服务器( 通常位于c d n 服务提供商的数据 中心) 的一个透明镜像。这样的架构使得c d n 服务提供商能够代表他们客户， 即内容供应商，向最终用户提供尽可能好的体验，而这些用户是不能容忍请求响 应时间有任何延迟的。据统计，采用c d n 技术，能处理整个网站页面的7 0 - - - - , 9 5 的内容访问量，减轻服务器的压力，提升了网站的性能和可扩展性。 与目前现有的内容发御模式相比较，c d n 强调了网络在内容发布中的重要 性。通过引入主动的内容管理层的和全局负载均衡，c d n 从根本上区别于传统 的内容发布模式。在传统的内容发布模式中，内容的发布由庀- 尸的应用服务器 完成，而网络只表现为一个透明的数据传输通道，这种透明性表现在网络的质量 保证仅仅停留在数据包的层面，而不能根据内容对象的不同区分服务质量。此外， 由于i p 网的”尽力而为”的特性使得其质量保证是依靠在用户和应用服务器之间 端到端地提供充分的、远大于实际所需的带宽通量来实现的。在这样的内容发布 f ； 南京邮电火学硕士研究生学位论文第二章e n r o u t e 网络缓存系统 模式下，不仅大量宝贵的骨干带宽被占用，同时脚的应用服务器的负载也变 得非常重，而且不可预计。当发生一些热点事件和出现浪涌流量时，会产生局部 热点效应，从而使应用服务器过载退出服务。这种基于中心的应用服务器的内容 发布模式的另外一个缺陷在于个性化服务的缺失和对宽带服务价值链的扭曲，内 容提供商承担了他们不该干也干不好的内容发布服务。 纵观整个宽带服务的价值链，内容提供商和用户位于整个价值链的两端，中 间依靠网络服务提供商将其串接起来。随着互联网工业的成熟和商业模式的变 革，在这条价值链上的角色越来越多也越来越细分。比如内容应用的运营商、 托管服务提供商、骨干网络服务提供商、接入服务提供商等等。在这一条价值链 上的每一个角色都要分工合作、各司其职才能为客户提供良好的服务，从而带来 多赢的局面。从内容与网络的结合模式上看，内容的发布已经走过了i c p 的内 容( 应用) 服务器和i d c 这两个阶段。i d c 的热潮也催生了托管服务提供商这 一角色。但是，i d c 并不能解决内容的有效发布问题。内容位于网络的中心并不 能解决骨干带宽的占用和建立i p 网络上的流量秩序。因此将内容推到网络的边 缘，为用户提供就近性的边缘服务，从而保证服务的质量和整个网络上的访问秩 序就成了一种显而易见的选择。而这就是内容发布网服务模式。c d n 的建立解 决了困扰内容运营商的内容”集中与分散”的两难选择。无疑对于构建良好的互联 网价值链是有价值的，也是不可或缺的。 2 2 网络缓存 代理缓存在e n - r o u t e 缓存系统中扮演着重要的角色，左右着网络的整体性 能。然而代理缓存究竟是什么? 它如何工作? 怎样提升代理缓存的性能? 本节将 讨论这一系列的问题。 2 2 1 缓存的实现原理 9 i 随着i n t e r n e t 的迅速发展及其应用的日益广泛，网上需要传输的信息不再 仅仅局限于普通文本，声音、动画、视频等大容量的多媒体信息也有了更多的传 输需求，导致网络流量以指数的速度增加( 在网络流量中以胁p 流量增长最快， 根据近几年的统计而印流量已占了网络总流量的7 5 8 0 ) 。但是目前在网络 7 南京邮电大学硕：l ：研究生学位论文 第二章e n r o u t e 网络缓存系统 带宽资源受限的情况下，要传输这些大容量的信息往往会出现诸如网上阮6 服务 器的拥塞、i n t e r n e t 上众多路由机器带来的数据延迟等现象，最终的结果是网络 传输速度变得像蜗牛一样爬行，使人们对i n t e r n e t 望而生畏。 为解决这一问题，单纯靠增加网络带宽是不够的，因为在访问i n t e r n e t 信息 时，各个连接环节都存在延迟，而且这些延迟是由许多综合因素造成的；靠增加 网站的硬件投资也是不够的，为加快w e b 访问的速度，有许多流行的w e b 站点试 图在各地建立镜像网站，但是建立镜像网站即不经济在管理上也非常困难，在现 实中是很难行得通。 圈2 1w e b 缓存的宏观架构 很显然，因特网需要一种新的体系结构，该结构应具有以下特点：灵活、不 需要服务器和带宽的持续升级、它的配置与维护费用不大而且易管理、存储经常 访问的内容，并使之尽可能地靠近用户端，这就是所谓的缓存。缓存技术是一种 在互联网关键节点( 包括本地) 存储经常访问的信息的一种技术。通过减少w a n 链路和w e b 服务器上的传输量来达到高速传输的目的。如图2 1 ，w e b 缓存的 宏观架构所示，网络缓存系统可存储最近访问过的信息，通道主干网络与主干网 络的协同工作，为用户提供低延迟高质量的服务。 缓存技术在互联网广泛使用，但并不是其独有的。在计算机机系统设计中， 通常在处理器芯片上使用缓存的内存来访问最近使用过的数据，虽然这种内存容 量相对有限并且比较昂贵，但是因此而使速度提高仍然是非常有价值的。 r 南京邮电大学顾十研究生学位论文 第二章e n r o u t e 网络缓存系统 同样，w e b 网络缓存系统可存储最近访问过的信息。通常，用户对w e b 对象 的请求需要在i n t e r n e t 路由经过多次跳跃到达原始服务器，再从原始服务器取得 所请求的对象返回给用户。每一跳都会给用户增加额外的延迟，并且连接的速度 还总是受到路径中最慢的链路的限制。w e b 网络缓存系统的主要思想就是将r r e b 对象( 页面、图像及其它i n t e r n e t 内容) 进行关键节点( 包括本地) 存储，使得 这些被访问过的w e b 对象更靠近需要使用它们的用户，从而大大提高用户w e b 访 问的速度。 w e b 高速缓存服务器通常是网络中的一个专用的计算机系统，它监视w e b 对象请求，获得这些对象，然后存储这些对象。此后，当用户对相同的对象( 网站) 提出访问请求时，就由缓存服务器来满足其要求，将已存储对象( c a c h eh i o 的拷 贝发送给浏览器。w e b 网络缓存系统使得用户请求不必再通过i n t e r n e t 路由到达 原始服务器而取回所请求的对象，从而降低了可能引起的服务延迟。同时，w e b t 高速缓存技术的应用还可以缓解w e b 服务器的负担。因为大量的用户请求不再 需要原始服务器进行处理。w e b 高速缓存技术能够提供一种廉价而可靠的w e b 服务器负载分担方案。 2 2 2 缓存的分类 根据网络缓存的实现方式的不同，网络缓存类型分为四种： l ：代理缓存( p r o x yc a c h i n g ) ，其服务器能够截取客户的册请求，如果在 缓存中保存有该请求的对象就直接把它发给客户。反之则把该请求发送出去，从 源端服务器获取所需数据并传送给客户。至于是否将该对象添加到缓存中取决于 网络缓存的替代策略。代理缓存通常配置在网络的边缘如网关和防火墙处以便为 全体内部用户提供服务。通常使用代理缓存可以达到节省带宽、缩短响应时间和 提高静态网络数据和对象可用性的目的。代理缓存分为以下三种类型： d( 1 ) 孤立型代理缓存：孤立型代理缓存属于第一代网络缓存技术。这种设计的 缺陷在于缓存本身有可能成为造成网络失效的环节。当缓存不可用的时候，用户 将同时失去与网络的连接。孤立型代理缓存的可扩充性也非常差，几乎没有办法 根据需要动态扩展缓存的容量，并且缓存的每次变动都要求所有的用户对w e b 浏览器的配置进行手动的改动。尽管饱伊最近在浏览器自动配置方面取得了很 南京邮电大学硕二f ：研究生学位论文 第二章e n r o u t e 网络缓存系统 大的进展，但孤立型缓存仍然不是一种令人满意的万案。 ( 2 ) 反向代理缓存：反向代理缓存配置在服务器的前面，通过截取和分析所有 到来的请求，缓存像个筛子一样，对包含在自己存储区中的对象的请求直接进行 响应，其余的部分才发给服务器处理。对于服务器来说，这显然是一种提高访问 请求处理能力和服务质量的有效方法。而事实上反向代理缓存已经被越来越多的 i s p 所接受，并同益成为一种必需的配置。 ( 3 ) 透明缓存：透明缓存属于第二代网络缓存技术。它重点解决第一代产品的 两个缺点，减少了配置的复杂性。并采用分层和集群技术提高可扩展性。在使用 透明缓存的情况下，由路由器或交换机检查每一个数据包，将所有朋7 p 流量重 定向到网络缓存。用户无须对w e b 浏览器进行配置，但路由器或交换机必须被 设置为具备重定向功能，也就是说用户浏览器看不到缓存，但路由器或交换机看 得到。透明代理缓存有两种形式，基于路由器( r o u t e r b a s e d ) 和基于交换机 ( s w i t c h b a s e d ) 。基于路由器的缓存使用基于策略( p o l i c y - b a s e d ) 路由法则将用户 的请求重定向到特定的缓存。而在基于交换机的缓存中不仅能够避免因单一的缓 存承载所有请求而造成的性能下降，而且提高了缓存的可扩展性。 2 ：适用性网络缓存似d a p t i v ew e bc a c h i n g ) 着重解决的问题是“热点”现象， 即由于某些短期的网络内容突然变得十分流行而带来的巨大需求量。适应性缓存 由众多分散的缓存组成，这些缓存能够根据需要动态地加入或离开缓存组。缓存 组具有自适应和自组织特性，能够对需求的渐变或突变做出反应。自适应缓存使 用缓存管理协议( c g m p ) 和内容路由协议( e r r ) 。c g m p 定义缓存组如何组织以 及单个缓存如何参加和离开缓存组。通常缓存组使用投票和反馈技术决定单一缓 存的去留。c r p 决定在缓存组内部如何放置缓存的内容。这项技术有赖于缓存 组成员之间的多播通信并利用u r l 表智能化地决定如何分配用户的请求。 3 ：推进是缓存( p u s hc a c h i n g ) 的核心思想是保待缓存的数据靠近有需求的用 户。当源数据所在的服务器识别出请求产生的地址后，数据就被动态地镜像。例 如，因此推进式缓存的特点之一就是跨越行政边界启动异地缓存的能力。与自适 应缓存不同，推进式缓存并不为所有内容提供商的各类内容的分发提供通用的解 决方案，而是只服务于采用了该推进式缓存的站点。 4 ：活性缓存( a c t i v ec a c h i n g ) 的产生源于网上个人内容在不断增加，而传统 南京邮电火学硕：j ：研究生学位论文 第二章e n r o u t e 网络缓存系统 缓存技术又很难处理这些动态的文件。 根据网络缓存的速度的不同，网络缓存类型可以分为代理型缓存和容器型缓 存。代理型缓存在通用的平台上用软件来实现缓存功能，而典型的容器型缓存则 包含有运行于专用硬件平台上的缓存软件。相比较而言，容器型的缓存速度更快， 性能也更好。理论上，使用代理服务器也可以提供像容器缓存那样的性能，不过 需要添置极为昂贵的多处理服务器硬件。到目前为止，至少有1 6 家生产商推出 了他们各自的w e b 缓存产品，其中有几家把缓存作为代理服务器的一部分进行 销售，例如c s m - u s a 、d e e r f i e l dc o m m u n i c a t i o n 、m i c r o s o f t 、n e t s c a p ec o m f n u n i c a t i o n s 、e n t e r a 、e o l i a n 、i b m , i n f o l o b r i a 和l n k t o m i 则把缓存作为容器进行销售。 只有n e t w o r ka p p l i a n c e 和p a c k e t s t o r mt e c h n o l o g i e s 两家公司同时销售以上两种 类型的缓存。 2 3 网络缓存布局 量 括 络 导 十 在 过 分 绍 设置网络缓存被认为是一种有效地机制。它可以缓解网络负载，降低网络流 南京邮电大学硕十研究生学位论文 第二章e n r o u t e 网络缓存系统 缓存被布置在网络中的不同层次中1 ，如图2 2 所示，在这个网络中有四个层次 的缓存：b o t t o m 、i n s t i t u t i o n a l 、r e g i o n a l 和n a t i o n a l 。 在层次式管理中，缓存被组织成树状的形式，同一层和上下层的服务器之间 可以进行协同的数据共享，代表系统有h a r v e s t t l 3 1 和s q u i d m l 缓存资源节点 o j 户节点 图2 2 层次式缓存 用户的缓存就处于b o t t o m 一级，当用户的缓存无法满足一个访问请求时， 这个请求就被重定位到了i n s t i t u t i o n a l 一级的缓存去。如果被请求的访问对象在 i n s t i t u t i o n a l 一层也没有找到，请求就被发往r e g i o n a l 一级，如果仍然没有就继续 发往n a t i o n a l 一级。如果所需的文件在任何一级缓存都没有找到，最后一级的缓 存服务器就会与保存所需内容的原始服务器通讯。当文件被找到后，在把文件传 给用户的途中，处于中介位置的各级缓存都会保存一份这个文件的拷贝，以后对 这同一个文件的访问请求就可以在某一级缓存中找到。 层次型缓存有良好的带宽利用能力，经常被访问的页面可以很快地发送给需 要它的用户。不过这种模型也有以下问题： 每一层都会引入额外的延迟。 处于高层的缓存可能成为整个系统的瓶颈，可能有更长的查询延迟。 在不同层次的缓存都保存同一份文件的拷贝会浪费很多存储空间。 南京邮电大学硕士研究生学位论文 第二章e n r o u t e 网络缓存系统 计算机 图2 3 基于超级节点的p 2 p 网络 目前层次式缓存主要应用在超节点j p 卯网络中，其拓扑结构如图2 3 所示。 因为超节点尸2 尸网络有明显的层次概念，所以很多系统的缓存管理沿用了层次 式协同缓存管理机制【1 ；j 【l6 1 。超节点尸2 尸系统中，超节点除了具有弱节点的所有 能力外还具有组内管理和转发功能。当某个节点发出查询请求时，先查本地缓存， 若未命中则访问超节点，由超节点决定是否在本组内查询其他节点的缓存，还是 转发给文档原来的存放点。 n a p s t e r 是最为典型的集中目录式对等网络模型。在n a p s t e r 模型中，一群 高性能的中央服务器保存着网络中所有活动对等机地址信息及其共享资源的目 录信息。当需要查询某个文件时，对等机会向一台中央服务器发出文件查询请 求。中央服务器进行相应的检索和查询后，会返回符合查询要求的对等机地址信 息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择， 和合适的对等机直接建立连接，并开始文件传输。n a p s t e r 的工作原理如图2 4 所 示。 南京邮电大学硕士研究生学位论文 第二章e n r o u t e 网络缓存系统 怀的计算机 图2 4 n a p s t e r 的工作原理 以此网络结构为参考的缓存也应用层次缓存模式，其缓存模型引入多级缓存 表的概念为核心，建立起分级式缓存网络体系结构。通过建立多级缓存体系是提 高系统可扩展性的重要手段。这种方法不同于盲目搜索很大的地方在与它在每个 节点上，不管是中央节点还是简单节点都存有路径信息，这就是c a c h e 的思路。