（计算机应用技术专业论文）基于enroute的缓存策略研究.pdf

孽 o7 、 南京邮电大学 硕士学位论文摘要 学科、专业：工科、计算机应用技术 研究方向：计算机通信与网间互连技术 作者：2 0 0 7研究生堑垦 指导教师：杨庚教授博导 题1 7 t ：基于e n - r o u t e 的缓存策略研究 英文题目：r e s e a r c h o ne n - r o u t ec a c h i n gs t r a t e g y 主题词：e n r o u t e ；网络缓存；p 2 p 网络；动态协作； f i i i ii iii i ii iii iii i i i ii y 17 5 5 0 2 3 k e y w o r d s ：e n r o u t e ；w e b c a c h i n g ；p 2 pn e t w o r k ；d y n a m i cc o o p e r a t i o n ； 课题来源：江苏省自然科学基金项目( 0 8 k j b 5 2 0 0 0 6 ) 江苏省研究生培养创新工程( c x 0 7 b 一1 0 9 z ) 南京邮电大学青蓝计划( x k 0 0 7 0 9 0 6 0 5 2 ) 矗 江苏省“六大人才高峰”基金资助项目( 0 6 一e 一0 4 4 ) 南京邮电大学硕士研究生学位论文 摘要 摘要 随着因特网技术的发展，用户对带宽需求的增加造成了骨干链路拥塞以及响应时间过 长的问题。缓存技术应用在节省网络开销，提高用户查找命中率，减轻初始资源服务器的 负载等方面发挥着巨大作用。然而，缓存技术是一个复杂的课题，它需要解决一致性策略、 替换策略、体系结构、缓存内容选择等关键技术问题，因此根据现有网络的特点，设计出 一种适合特定环境的缓存策略来提高用户查询的性能，是一项富有挑战性的研究课题。 p 2 p 网络通过终端设备进行大规模协作计算和资源共享。为提升性能，缓存技术被广 泛应用于p 2 p 网络存储系统中。由于资源定位是通过p 2 p 路由机制进行的，其缓存策略与 传统的分布式文件存储系统有很大区别，在提高缓存命中率、确保数据一致性方面也有着 独到的特点。 本文从现有的缓存策略入手，在研究c n r o u t e 缓存技术基础上，分析了p 2 p 文件存储 系统中典型缓存策略，针对现有的缓存策略的不足，将e n r o u t e 思想应用于p 2 p 缓存策略 设计上，提出应用于p 2 p 网络的基于统计的动态协作缓存( d p f r ) 策略。 本文提出的d p f r 策略，是以放置缓存带来的收益和损失为评价标准，以优化系统代 价为计算方法，利用动态规划法求最优解原理，给出在整个网络中缓存放置和替换的策略。 仿真实现了d p f r 在p 2 p 网络中的应用，分别从系统代价，节省跳数，缓存大小三个方面 对算法的性能进行了实验比较，证明了算法的有效性。最后，对d p f r 策略进行了客观的 评价，并确定下一步的研究方向。 关键词：p 2 p 网络；e n r o u t e 算法；动态协作 口 a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yi ni n t e r n e t , t h eu s e r sw h o d e m a n df o rm o r eb a n d w i d t h h a v eb r o u g h tt h eb a c k b o n el i n kc o n g e g i o n a n dt h el o n gr e s p o n s et i m e c a c h ep l a y sas i g n i f i c a n t r 0 1 ei ns a v i n gc o s t s ，i m p r o v i n gh i tr a t e ，r e d u c i n gt h e i n i t i a lr e s o u r c e so ft h es e r v e rl o a d ，e t c c o r r e s p o n d i n g l y , c a c h ei sac o m p l e x i s s u e a sy o uk n o w , c o n s i s t e n c y , p l a c e m e n t ，r e p l a c e m e n t , a r c h i t e c t u r ea n dp r e f e t c h i n ga r ea l li n v o l v e di ni t s o ，h o w t od e s i g nap a r t i c u l a rc a c h es t r a t e g y t oi m p r o v et h ep e r f o r m a n c eo fu s e rq u e r i e sb a s e do nt h ec h a r a c t e r i s t i c s o fn e t w o r ki sa c h a l l e n g i n gr e s e a r c ht o p i c p 2 pn e t 、o r km a k e sl a r g e s c a l ec o l l a b o r a t i v ec o m p u t i n ga n d r e s o u r c es h a r i n gc o m et r u eb y u s i n gt 二m i n a ld e v i c e s i no r d e rt oe n h a n c ep e r f o r m a n c e , c a c h i n g i sw i d e l yu s e di np 2 pn e 似。r k s t o m g es y s t e m s i th a sab i gd i f f e r e n c eb e t w e e np 2 pc a c h i n gs t r a t e g ya n d t r a d i t i o n a ld i s t r i b u t e d f i l es t o r a g es y s t e md u et ot h er e s o u r c ep o s i t i o n e dt h r o u g ht h er o u t i n gm e c h a n i s m i t h a su n i q u e f e a t u r e si ni m p r o v i n gt h ec a c h e h i tr a t ea n dk e e p i n gd a t ac o n s i s t e n c y f i r s t , i ta n a l y s e st h et y p i c a lp 2 pc a c h i n gs t r a t e g yi nf i l es t o r a g es y s t e mw h i c hi sb a s e d o n t h er e s e a r c ho fe n r o u t ea l g o r i t h m s e c o n d ，b e c a u s eo fs h o r t c o m i n g so fe x i s t i n gc a c h i n gs t r a t e g y , ad y n a m i cc o o p e r a t i v ec a c h i n gs t r a t e g yb a s e do ns t a t i s t i c s ( d p f r ) w h i c hs u i t a b l e f o rp 2 p s y s t e mi sp r o p o s e di nt h i st h e s i s d p f rs t r a t e g y , p r o p o s e di nt h i st h e s i s ，t a k e st h eb e n e f i t sa n d l o s s e sb yp a l c i n gt h ec a c h ea s t h ee v a l u a t i o nc r i t e r i a i ti l l u s t r a t e st h es t r a t e g yo fc a c h i n gp l a c e m e n ta n dr e p l a c e m e n ta c r o s st h e n e t w o r kb yu s i n gd y n a m i cp r o g r a m m i n gp r i n c i p l eo fo p t i m a l i t ya n do p t i m i z e st h es y s t e mb y c a l c u l a t i n gt h ec o s t s i m u l a t i o nr e s u l tp r o v e st h ee f f e c t i v e so f t h es t r a t e g yb yc o m p a r i n gw i t ht h e f o l l o w i n gt h r e ea s p e c t so fp e r f o r m a n c e ，s y s t e mc o s t , s a v i n gh o p s ，t h ec a c h es i z e f i n a l l y , i t m a k e s a no b j e c t i v ee v a l u a t i o no fd p f ra n da l s op o i n t so u tt h er e s e a r c hd i r e c t i o n si nt h ef u t u r e k e yw o r d s ：p 2 pn e t w o r k ；e n - r o u t e ；d y n a m i cc o o p e r a t i o n i i 堕京邮电大学硕= 墅壁壅竺堂垡垒茎 一一旦墅 - - - - - _ _ _ _ _ - _ - - _ _ _ _ _ _ - _ _ _ _ _ - _ _ _ 一一 目录 摘要i a b s t r a c t i i 目录i i i 第一章绪论：l 1 1 课题研究背景及意义1 i 1 1 课题背景1 1 1 2 研究现状“2 1 1 3 课题意义4 1 2 本文主要工作5 i 3 本文组织叩5 第二章网络缓存概述7 2 1 缓存原理8 2 2 缓存实现9 2 3 网络缓存布局1 0 2 3 1 层次式1 0 2 3 2 分布式1 2 2 3 3 混合式l5 2 4p 2 p 缓存l5 2 4 1p 2 p 缓存系统原理1 5 2 4 2p 2 p 网络现状分析1 6 2 4 3p 2 p 存储系统特性18 2 4 4p 2 p 存储系统面临的问题2 0 2 5 本章小结。2l 第三章p 2 p 网络缓存策略分析2 2 3 1p 2 p 网络缓存放置策略2 2 3 1 1 基于查询频率2 2 3 1 2 基于概率2 3 3 1 3 启发式算法2 4 3 1 4 基于对象特征值。旦2 5 3 2p 2 p 网络缓存替换策略：2 6 3 2 1 传统替换算法及其演化2 6 3 2 2 基于缓存内容关键特征2 7 3 2 3 基于效用函数策略2 8 3 3p 2 p 网络缓存一致性策略：2 9 3 4 缓存策略性能评价标准3l i i i 南京邮电大学硕士研究生学位论文 目录 3 4 1 缓存命中率3 l 3 4 2 平均访问延迟3 2 3 4 3 空间利用率3 2 3 5p 2 p 缓存算法的不足3 3 3 6 本章小结3 4 第四章结构化p 2 p 网络动态协作缓存3 5 4 1e n r o u t e 算法3 5 4 2c h o r d 网络“。3 7 4 3d p f r 缓存策略3 9 4 3 1 算法设计3 9 4 3 2 算法实现流程4 5 4 3 3 复杂度分析4 8 4 4 动态协作机制论述4 8 4 5 本章小结5 0 第五章仿真分析5l 5 1 仿真系统概述。5l 5 1 1z i p f 法则6l 5 1 2 仿真环境5 2 5 2 仿真内容5 3 5 2 1 主要仿真参数设置5 4 5 2 2 仿真结果分析5 4 5 3 本章小结5 7 第六章总结与展望5 9 致 射6 0 参考文献6l 攻读硕士期间发表的学术论文6 6 鼍 i v 南京邮电大学硕士研究皇堂垡堡茎 二塞二童! i ! 生 第一章绪论 1 1 课题研究背景及意义 1 1 1 课题背景 随着互联网的普及，网络应用的蓬勃发展使互联网己成为不可或缺的重要的信息平台 和业务平台，网络己经深入到人们生活中，人们也越来越依赖网络来获取信息。同时，在 i n t e m e t 上传输的数据量也随之与日俱增，图片、文件，多媒体等汇聚成了互联网这个信息 的海洋。数据以超文本形式组织，再用超链接相互联系起来，位于世界各地的网络用户和 提供网络内容的服务器通过超文本传输协议( h t t p ，h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) 完成通讯。 网络用户如果需要网络服务器中的某些内容，就会发出一个h t t p 请求，服务器接收到这 个请求后，找到所需的信息，把结果发给用户，由于友好的用户接口和有效的信息共享能 力，使互联网的发展非常迅速。 然而，正是此快速发展的需求凸现了i n t e m e t 目前存在的问题：虽然用户可以得到的 网络带宽得以增加，但这些硬件设施的发展速度远远跟不上网络用户爆炸式增长的速度， 以及由此造成的网络流量对带宽的巨大需求。在有限的带宽条件下，为了获取w e b 服务 器上的数据，用户不得不忍受较长的时延和更多的通信费用，网络服务质量受到了严重的 影响。据调查显示，网站的响应时间小于7 秒钟，用户放弃访问的比例是7 ，网站的响 应时间超过1 2 秒钟，用户放弃访问的比例急剧增加到7 0 ，可见减少用户等待时间是网 站建设者和用户的迫切要求。这些问题都促使人们想办法提高网络性能。 能提供原始信息的服务器毕竟是有限的，如果所有的用户都通过原始服务器获取息， 那势必造成服务器负担增加、用户等待时间延长的后果。“一次取来，多次使用”，将网络 中大量重复数据的交换最小化，提高网络效率著提高对用户服务的质量。网络缓存技术就 是在这种需求下应运而生的，它把访问过的网络对象( 网页、嵌入对象、流媒体等) 保存在 缓存服务器上，当同样的访问请求再次发生时，就可以直接从缓存服务器获取所需的网络 对象，从而达到缩短用户等待时间、节省网络带宽，提高用户感知的目的。 网络应用不断发展伴随着服务内容数据量的迅速增长，进而导致存储容量的需求急剧 1 南京邮哇达学硕主堡壅竺兰篁堡奎 笙二童堑堕 _-_。_-_。_l。_-。_。_-_。-。_-。_-_。_。_。_-_-_-。_-。_。一一一一 膨胀，对存储系统的存储容量和扩展性提出了更高的要求；数据量的增长促使计算机存储 技术不断地向纵深方向发展，传统的客户机月艮务器模式已经不堪重负，一场新的存储革命 呼之欲出，由此应运而生的基于p 2 p 计算模式的存储技术初步显示了强大的威力，受到了 学术界和产业界的广泛关注。在p 2 p 计算模式的存储系统，每台计算机既是客户机也是服 务器，他们之间可以直接交换信息，而不需要中间服务器，这种对等的体系结构使得p 2 p 存储系统在扩展性上面有着天然的优势，系统的存储容量不再受服务器硬件条件的限制， 可以利用现有的计算设备，将闲散的存储资源整合起来，实现高质量的网络存储服务。 随着p 2 p 网络的共享资源量剧增，分布式存储系统向海量存储发展，系统所存储的对 象数目极其可观。然而研究表明，大多数的访问集中在少数热点对象，部分对象只得到很 少的访问量。系统的重复查询必然会产生大量相同数据传输，从而导致p 2 p 网络负载不均， 带宽资源大量浪费，除了增强各对等点性能、提高网络带宽以外，采用缓存机制无疑是解 决这一问题的有效途径。 作为存储系统重要技术之一的缓存技术正在被逐渐应用于基于p 2 p 网络的新型大规模 分布式存储系统中，以解决信息传输中存在瓶颈，网络负载不均衡，带宽开销大等一系列 问题，从而提升系统性能。然而，由于p 2 p 系统资源定位是通过p 2 p 路由机制来进行，与 传统分布式文件存储系统通过查找集中索引服务器的方式有很大不同。因而其缓存策略与 传统的分布式文件存储系统的缓存策略也有很大区别，在提高缓存命中率、确保数据一致 性等方面有着独到的特点。作为现代计算中所采用的经典和基本技术之一，缓存算法领域 实质性的进展将会影响整个时代的计算机发展和变革。p 2 p 网络中的缓存技术已成为网络 缓存技术研究的重点应用领域。 1 1 2 研究现状 缓存技术的应用在节省服务提供商的开销，提高用户查找命中率，减轻初始资源服务 器的负载等方面发挥着巨大作用。同样基于因特网缓存技术是一个复杂的课题，它需要解 决一致性策略、替换策略、体系结构、缓存内容选择和预取等诸多关键技术问题，在国际 上已经形成一个独立的主流研究领域。当缓存的剩余空间不足以存放新请求的网页融本 时，就需要进行换出和换人操作，决定何时发生替换操作以及选择哪个缓存副本换出将成 为研究的一个关键点，文章从这两个方面介绍缓存策略的研究现状。 在放置方法方面主要是基于对象不同的因素进行研究，其代表的有基于查询频率，基 于概率和基于对象特征值的算法，还有基于此的启发式算法等。文献 1 】提出了基于文件被 2 南京邮电大学硕士研究生堂垡笙茎 兰二童堕 - _ _ - 一一。 访问频率的统计算法，把文件被访问频率作为衡量的关键标准，此算法研究的环境是结构 化的c h o r d 网络，缓存副本分布在网络中存储原始资源节点的逻辑邻居节点上，这里简称 为临近源节点算法( n r ，肫口，r e s o u r c e ) ，对于此种算法在整个大规模网络中的应用文献中 并没有给出分析结果。文献【2 】 3 】在单纯依据文件访问频率之外，延伸出依据阀值( t h r e s h o m v a l u e l 的放置策略，其根据文件的被访问频率来将系统中的文件分为热点文件和非热点文 件，当一个文件被访问的频率超过设定的阀值的时就把这个文件成为热点文件，反之则称 为非热点文件。既然网络中访问频率并不是完全一致的，换言之也就是说这些对象并不是 以等概率被访问的，这就为基于概率的缓存策略提供了理论基础，基于s m a l l - w o r l d 的分 布式缓存系统就是其中的一个代表【4 】，其利用社会网络中“六度分离”理论，定义了网络 中在两个节点中建立随机长连接的概率，缓存副本存在请求资源节点维护的随机长连接 上。除了上述国内外研究比较多的算法，在p 2 p 网络缓存分布算法上，也有基于语义等网 络特征值的算法【5 】，此算法最初被用于w e b 缓存，近来被逐步应用于p 2 p 缓存系统。其合 理性来自于贝叶斯假设组成文本的字或词在确定文本类别的作用上相互独立，可以用文本 的字或词来代替文本，在计算方面主要采用矢量模v s m 嗍，其本质都是定义一组通用的词 汇并给出相关对象的语意信息描述，此类结构化或半结构化的文档描述使得计算机处理语 意信息成为可能，但是此算法是在已有缓存表基础上进行缓存，不可避免会造成p e e r 节点 对新的缓存对象的丢弃。 在替换策略方面，传统替换算法有先进先出策略，最近最少使用策略，最少使用频率 策略等。除此之外，能够标志文件关键特征的属性也可作为替换的标准，如缓存的大小， 基于阀值缓存策略里的阀值大小，以及量化以后的流行度值等。g r e e d yd u a l s i z e ( g d s ) p 】 提出基于效用函数的缓存策略，是一种策略的集合体，它考虑了局域性、对象大小、延迟、 代价等因素，g d s 相对于其他的置换方法如衄u 胆阴s i z e 等方法在缓存字节命中率、 字节缓存命中率、网络开销等方面具有更多的优势【| 7 1 ，算法本身并没有规定其函数的类型 和元素个数，其方法思想的提出旨在使设计者能够充分利用网络元素，更好的反映所使用 算法的针对性。 以上缓存放置秤替换算法仅仅考虑缓存内容的单一属性，并没有从网络整体的角度去 设计缓存算法，然而一个要应用于网络中的缓存算法，其性能的好坏必须从算法对整个网 络的影响来衡量。在1 9 9 7 年h e d d 缈a 和坳砌1 提出了使用运行时代码生成技术，动态 地下载高性能的数据包的概念。为了使网络缓存的效用最大化，网络缓存研究的重点转向 了缓存之间的协作，包括分级缓存以及分布式缓存的协同工作【9 】【1 0 】【l l 】，透明缓存概念的提 1 南京邮电奎兰堡主堑窒竺兰堡笙茎 塑二童堡垒 出使得网络缓存有了长足的进步，文献【1 2 】中透明缓存第一次被命名为e n - r o u t e 缓存，网 络缓存和路由绑定实现，e 1 1 r o u t ec a c h e 成为网络缓存研究的一个重要方向。e l l r o u t e 系统 中每一节点收到查询请求，如果当前节点缓存了查询的资源，则提供资源并应答此请求， 否则将此请求按照路由路径转发，直到到达服务器节点。x u e y a nt a n g ，s a m u e lz c h a n s o nu 州 提出协同合作的e n r o u t e 缓存算法，以缓存的引入给整个网络带来收益和损耗为标准，决 定是否在当前节点缓存该资源，给出整个网络中缓存副本的如何分布的动态算法，但此算 法仅仅应用于线性网络中。基于此，文献【1 4 】中，l i k q ，s h e n h 提出了应网于树形网络的 缓存算法，与线性网络不同，树形网络的应用更加广泛。由于多媒体文件文本格式的特殊 性，文献 1 5 】提出了应用于多媒体网络的e n r o u t e 算法，此算法的改进在于其把多媒体文 件的转换代价作为影响缓存策略的一个因素，充分考虑了多媒体的多样性。文献 1 6 1 对树 形网络的缓存算法做了改进，提出应用于自制系统的e n r o u t e 算法，自制系统的内部多样 性决定了算法的复杂性。e 1 1 r o u t e 算法的改进在于其算法在各个不同网络中的应用，算法 在p 2 p 网络环境中的改进也将成为研究的一个重点方向。 1 1 3 课题意义 缓存机制对大规模分布式存储系统中应用的重要技术之一，对缓存策略的研究和改 善，将会有效地提升分布式存储系统性能。然而，p 2 p 分布式存储系统的缓存策略目前还 存在着一些不足，在一定程度上制约了系统性能的进一步改善。 一个问题是，目前大多数p 2 p 存储系统中所采用的主要缓存置换策略是最近最少使用 ( l r u ，l e a s tr e c e n t l yu s e d ) 策略，但研究证明，这一传统策略并不完全适用于p 2 p 环境下 的分布式存储系统，存在着效率相对较低的问题。 另一个问题是，在大多数采用了缓存技术的p 2 p 存储系统中，依据缓存副本分布策略， 被请求对象的缓存副本要分布到参与对象查询过程的全部结点上。该类型的缓存副本分布 策略是基于以下假设：对一次成功的对象查询做出过贡献的结点，也较易于在短期内对同 一个对象产生请求。实践表明，在应用领域的p 2 p 文件存储系统中，对象请求规律很少遵 循这一假设。从而导致了该缓存副本分布策略易于产生存储窒间浪费问题。 t 可见，缓存机制对大规模分布式存储系统性能有着不可忽视的影响。针对现有p 2 p 文 件存储系统缓存策略的不足，研究出一种p 2 p 文件存储系统中的新型缓存策略，从而改善 现有缓存策略的性能，将会有助于分布式存储系统性能的提升，具有重要的现实意义。 4 南京邮电大学硕士研究生学位论文 第一章绪论 1 2 本文主要工作 为了解决缓存策略中导致效率低下的问题，降低网络带宽消耗，同时在参与p 2 p 文件 存储系统的各个结点间均衡负载，本文在p 2 p 路由机制和经典缓存技术基础上，将e l l r o u t e 缓存策略针对p 2 p 环境进行改进，提出了一种p 2 p 文件存储系统中改进的缓存策略基 于文件访问频率的动态协作缓存策略缓存策略。该策略意义在于改善传统的缓存策略的效 率，提升分布式存储系统性能。与传统缓存策略不同，此动态协作缓存策略在缓存置换与 缓存副本分布上更多的考虑了网络代价，是一种动态全局的算法。 本文的工作总结如下： ( 1 ) 研究了基于p 2 p 网络的分布式存储系统理论及应用。 ( 2 ) 研究了分布式存储系统中的缓存理论及p 2 p 文件存储系统中典型缓存策略的应用。 ( 3 ) 针对已有的缓存策略模型的不足，将e n r o u t e 理论应用于缓存策略设计上，提出了 基于文件访问频率的动态协作缓存策略缓存策略。 ( 4 ) 实现了动态协作缓存策略在p 2 p 文件存储系统中的应用。 ( 5 ) 从系统性能的改善角度对提出的动态协作换粗存策略进行了评估，证明其有效性。 ( 6 ) 对动态协作缓存策略的改进和功能的扩展给出了展望。 1 3 本文组织结构 本文结构组织如下： 第一章介绍了缓存策略研究的学术背景、国内外研究现状以及本文的主要工作和组织 结构。 第二章概述了网络缓存，介绍了网络缓存的原理及缓存的实现方式，分析了高速缓存 _ 如何优化p 2 p 流量，引入了p 2 p 存储系统面临的问题。 算 t 第三章着眼于对缓存策略框架的各个组成部分进行分析，作为第四章提出动态协作缓 存策略设计方案的依据。在分析缓存策略框架的基础上，本章结合应用领域的几种p 2 p 分 布式存储系统中的缓存策略实例，分析了缓存策略各个组成部分在实例中的体现方式及其 异同点，说明了各个组成部分所扮演的角色及当前存在的不足。 s 南京邮电大学硕士研究生学位论文 第一章绪论 第四章介绍了e n r o u t e 缓存策略的理论基础，主要描述了将该理论应用于缓存设计后， 基于文件访问频率的动态协作缓存放置策略以及替换策略的实现。 第五章阐述了概率性缓存策略仿真实验及结果分析，介绍了z i p f 法则、仿真实验平台 结构，并用实验数据表明了概率性缓存策略对p 2 p 文件存储系统性能的改善。 第六章针对本文算法在缓存策略应用领域的不足进行了总结，并提出了展望。 6 南京邮电大学硕士研究生学位论文 第二章网络缓存概述 第二章网络缓存概述 随着i n t e r n e t 的迅速发展及其应用的日益广泛，网上需要传输的信息不再仅仅局限于普 通文本，声音、动画、视频等大容量的多媒体信息也有了更多的传输需求，导致网络流量 以指数的速度增加( 在网络流量中以h ”田流量增长最快，根据近几年的统计h t t p 流量已 占了网络总流量的7 5 0 0 - 8 0 ) 。但是目前在网络带宽资源受限的情况下，要传输这些大容 量的信息往往会出现诸如网上w 曲服务器的拥塞、i n t e m e t _ l 众多路由机器带来的数据延迟 等现象，最终的结果是网络传输速度变得象蜗牛一样爬行，使人们对i n t e r n e 望而生畏。 图2 1 缓存宏观架构 为解决访问速度这一问题，单纯靠增加网络带宽是不够的，因为在访i h - i n t e m e t 信息时， 各个连接环节都存在延迟，而且这些延迟是由许多综合因素造成的；靠增加网站的硬件投 资也是不够的，为加快w e b 访问的速度，有许多流行的w 曲站点试图在各埴建立镜像网站， 但是建立镜像网站即不经济在管理上也非常困难，在现实中是很难行得通。 很显然，因特网需要一种新的体系结构，该结构应具有以下特点：灵活、不需要服务 器和带宽的持续升级、它的配置与维护费用不大而且易管理、存储经常访问的内容，并使 7 壹京邮电大学硕主堡塞竺兰垡垒奎 蔓三兰旦堑堡查塑堕 _ - _ _ _ _ - _ _ _ _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ - - - _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 一 之尽可能地靠近用户端，这就是所谓的缓存。缓存技术是一种在互联网关键节点( 包括本地) 存储经常访问的信息的一种技术。通过减少w a n 链路和w 曲服务器上的传输量来达到高速 传输的目的。如图2 1 所示，网络缓存系统可存储最近访问过的信息，通过主干网络与主干 网络的协同工作，为用户提供低延迟高质量的服务。 2 1 缓存原理 通常在处理器芯片上使用缓存的内存来访问最近使用过的数据，虽然这种内存容量相 对有限并且比较昂贵，但是因此而使速度提高仍然是非常有价值的。同样，w e b 网络缓存 系统也可存储最近访问过的信息。通常，用户对w e b 对象的请求需要在i n t e m e t 路由经过多 次跳跃到达原始服务器，再从原始服务器取得所请求的对象返回给用户。每一跳都会给用 户增加额外的延迟，并且连接的速度还总是受到路径中最慢的链路的限制。w e b 网络缓存 系统的主要思想就是将w e b 对象( 页面、图像及其它i n t e m e t l 内容) 进行关键节点( 包括本地) f 存储，使得这些被访问过的w e b 对象更靠近需要使用它们的用户，从而大大提高用户w e b 访问的速度。 客 ! 仁= _ ( 9 存服务器 w e b 服务器 图2 2w e b 缓存工作原理 w e b 高速缓存服务器通常是网络中的一个专用的计算机系统，它监视w e b 对象请求， 获得这些对象，然后存储这些对象。其工作原理如图2 2 所示。图中，为缓存服务器接受 浏览器请求；和为缓存服务器从原始服务器获得缓存中的未存储对象( c a c h em i s s ) ； 为缓存服务器存储获得的对象，并将拷贝发送给浏览器。 此后，当用户对相同的对象提出访问请求时，就由缓存服务器来满足其要求，将已存 储对象 a c h eh i t ) 的拷贝发送给浏览器。w e b 网络缓存系统使得用户请求不必再通过 i n t e m e t 路由到达原始服务器而取回所请求的对象，从而降低了可能引起的服务延迟。同时， w e b 高速缓存技术的应用还可以缓解w r e b 服务器的负担。因为大量的用户请求不再需要原 始服务器进行处理，可见w e b 高速缓存技术能够提供一种廉价而可靠的w e b j 报务器负载分 担方案。 8 南京邮电大学硕士研究生兰垡堡奎 兰三兰塑鳖堡查堡堕 一一 当然实际上，w 曲高速缓存的功用远不止存储和提供数据这么简单。缓存是作为基于 软件的代理服务器的一部分或专门的硬件( 容器a p p l i a n c e s ) 出现的，常见产品的高速缓存服 务器一般是以硬件方式提供，但也有纯软件方式提供的。硬件产品是将软件预置成功能服 务器，通过源代码与硬件的紧密集成使性能更加优越，安装和使用更简便。 2 2 缓存实现 根据实现方式的不同缓存可以分为：代理缓存( p r o x yc a c h i n g ) 、自适应缓存( a d a p t i v e c a c h i n g ) 、推式缓存( p u s hc a c h i n g ) 以及主动式缓存( a c t i v ec a c h i n g ) 。 代理服务器的基本功能就是在内部网络与i n t e m e t 之间充当中间代理机构。它负责转发 合理的网络信息，并对转发进行控制。图2 3 显示了利用第四层交换机实现透明代理的原理。 j 皤 客户浏览 图2 3 利用第四层交换机实现透明代理 为用户浏览器向原始服务器发出网页请求，第四层交换机探测到该请求为h 1 v r p 请 求，并将其转发给透明代理服务器；为透明代理服务器从域名服务器获得原始服务器的 i p 地址；为透明代理服务器从原始服务器获得w e b 对象；为透明代理服务器存储获得 的对象，并将拷贝发送给用户浏览器；从网络配置的角度来看，透明代理比转发代理略复 杂，这是因为透明代理可能包含网络路由设置，但是透明代理不需要在用户端进行特殊配 置。另外，透明代理需要安装在网络中用户的所有流量都要经过的一点。 “ 反向代理是一种原始服务器端的加速方法。谴行反向代理的原因是原始服务器处理的 对象请求中大部分是静态对象，所以反向代理可以大大缓解原始服务器的负载。要实现这 种缓存技术，只要将w e b 高速缓存服务器作为原始服务器的前端即可。从用户的角度来看， w e b 高速缓存服务器就是原始服务器，其访问请求直接发送到w e b 网络缓存系统，而不是 原始服务器，只有无法缓存的请求被w e b 高速缓存服务器转发给原始服务器处理。 9 南京邮电大学硕士研究生学位论文第二章网络缓查概述 自适应缓存着眼于全局数据的分发，它包含多个分布式的缓存，这些缓存可以按照内 容的要求动态的加入和离开被称为缓存网络( c a c h em e s h e s ) l 拘缓存组。缓存网络利用缓存 组管理协议( c a c h eg r o u pm a n a g e m e n tp r o t o c o l ，c g m p ) 和内容路由协议( c o n t e n tr o u t i n g p r o t o c o l ，c r p ) 做到自适应和自我组织。c g m p 用来动态管理缓存的进出；c r p 用来定位缓 存内容。 推式缓存的主要思想是把缓存数据传输到靠近希望得到该信息的用户上，数据被动态 镜像。比如：由于时差的关系，当亚洲处在白天的时候，亚洲用户访问美国站点的请求会 增长，而此时该美国主站就会启动事先已经更新( 推) 过的位于亚洲的缓存服务器，以提 高对亚洲用户的响应速度。 主动式缓存是由美国w i s c o n s i n 大学m a d i s o n 分校的w i s ew e b 项e l 提出的，它的目的是 研究对动态页面的缓存问题。主动式缓存使用缓存中j a v a d , 程序( a p p l e t s ) 来定制那些用其 它方法无法缓存的对象。当用户第一次发出个性化请求时原始服务器会连同被请求的对象 及其相关联的a p p l e t s - - 起提供给缓存服务器。此后用户提交的相同的个性化请求将由缓存 上的a p p l e t s 完成响应。 2 - 3 网络缓存布局 网络缓存被组织成层次式、分布式和混合式三种结构，其不同的组织结构在p 2 p 网络 中都有相应的缓存布局对应研究。经过布局的网络缓存可以通过多个缓存服务器协同工 作，充分利用彼此的缓存空间，提高缓存命中率，同时分散关键点数据，均衡各服务器的 负载，避免单点出错和瓶颈问题。在p 2 p 网络中，其层次式、分布式和混合式都有体现， 本节将具体介绍这三种结构以及在p 2 p 环境中的应用。 2 3 1 层次式 h a r v e s t t 3 3 1 项目首先先提出了层次式缓存体系结构。在层次式网络缓存系统中，缓存被 布置在网络中的不同层次中，如图2 4 所示，在这个网络中有四个层次的缓存：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 。在层次式管理中，缓存被组织成树状的形式，同一层和 上下层的服务器之间可以进行协同的数据共享，代表系统有己陋n 憾s f 【2 8 1 和勋甜胁2 9 1 。 1 0 南京邮电大学硕士研究生学位论文 第二章网络缓存概述 源节点 n a t i o n a l r c 百o n a l i n s t i t u t i o n a l b o t t o m 图2 - 4 层次式缓存 缓存资源节点 。用户节点 用户的缓存就处于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 一级。如果所需 的文件在任何一级缓存都没有找到，最后一级的缓存服务器就会与保存所需内容的原始服 务器通讯。当文件被找到后，在把文件传给用户的途中，处于中介位置的各级缓存都会保 存一份这个文件的拷贝，以后对这同一个文件的访问请求就可以在某一级缓存中找到。 层次型缓存有良好的带宽利用能力，经常被访问的页面可以很快地发送给需要它的用 户。不过这种模型也有以下问题： 每一层都会引入额外的延迟。 处于高层的缓存可能成为整个系统的瓶颈，可能有更长的查询延迟。 在不同层次的缓存都保存同一份文件的拷贝会浪费很多存储空间。 图2 5 基于超级节点的p 2 p 网络 目前层次式缓存主要应用在超节点p 2 p 网络中，其拓扑结构如图2 5 所示。因为超节 l l 南京邮电大学硕士研究生学位论文 第二章网络缓存概述 点p 2 p 网络有明显的层次概念，所以很多系统的缓存管理沿用了层次式协同缓存管理机制， 超节点p 2 p 系统中，超节点除了具有弱节点的所有