（计算机应用技术专业论文）基于控制的web预取的分析与研究.pdf

摘要 本文的主要研究目的就是为了解决互联网中浏览速度慢的问题，但是解决力 法如果不恰当，反而使问题更恶化。直接和贪心的网络预取方法会增大网络业务 的突发性，导致网络利用率下降，甚至导致网络拥塞。所以本文研究了网络预取 的控制问题。预取控制将决定网络预取能否全面推广而不对网络的性能广生严重 的负面影响。 考虑到w e b 代理服务器业务的自相似性特征，对于网络预取的控制，本文 采用了基于网络性能测量的平滑退避算法。这种算法的核心就是依据网络性能的 测量把预取请求在整个请求传输中分散，它可以在不改变预取请求的情况下，改 ，叟预取请求的传输模式，使得预取请求的传输变得比较分散。 本文还总结了网络性能中关于网络带宽和网络往返时问的各种测量方法，并 对其进行了比较。仿真中采用了网络中真实的t r a c e 记录，所以仿真的结果比较 可信和具有说服力。 最后，本文把预取方法和预取控制推到了无线网络中，提出了一种适f e | j 于 无线移动网络环境的预取方法，这是一种以网页内容和客户端记录，以及服务器 端对特殊结构网页的分析，用户倾向记录文件和过去群体使用者存取行为为基础 的方法。 关键词：预取预取控制 网络带宽仿真 用户访问模式群集 蹦络性能测量 用户倾向记录文件 a b s t r a c t t h ep u r p o s eo ft h i st h e s i sm a i n l yr e s e a r c h e sh o wt os o l v et h ep r o b l e mt h a tt h e s p e e d o fb r o w s i n gi s v e r ys l o w i nt h ei n t e r n e t h o w e v e r , i ft h e m e t h o di sn o t a p p r o p r i a t e ，m a y b ei t w i l lm a k et h i n g sw o r s et h em e t h o do fs t r a i g h t f o r w a r da n d a g g r e s s i v ep r e f e t c h i n gp r o b a b l y i n c r e a s e st h eb u r s t i n e s sa n dc a u s e st h en e t w o r k u t i l i z a t i o nd o w ns o m e t i m e si te v e nl e a d st on e t w o r k c o n g e s t i o nt h e r e f o r et h et h e s i s r e s e a r c h e st h ei s s u eo f p r e f e c h i n gc o n t r o lp r e f e c h i n gc o n t r o lw i l ld e t e r m i n ew h e t h e r p r e f e t c h i n gc o u l db ep o p u l a r i z e do rn o t ，w h i c h i td o e s n ta f f e c tt h ep e r f o r m a n c eo f t h e n e t w o r k n e g a t i v e l y c o n s i d e r i n gt h es e l f - s i m i l a r i t yc h a r a c t e rw h i c hw e bp r o x ys e v e rt r a f f i ch a s ，f o r p r e f e t e c h i n gc o n t r o l ，t h et h e s i sa d o p t st h en e t w o r km e a s u r e m e n t b a s e ds m o o t h i n g a n db a c ko f fa l g o r i t h mt h ek e r n e lo ft h i s a l g o r i t h mi s t h a tw ec o u l dd i s p e r s e p r e f e t c h i n gr e q u e s t so v e r t h ew h o l e r e q u e s t st r a n s f e ra c c o r d i n g t ot h em e a s u r e m e n to f t h en e t w o r kp e r f o r m a n c ei tc o u l dc h a n g et h et r a n s f e rm o d e lo f p r e f e t c h i n gr e q u e s t r a t h e rt h a nc h a n g ep r e f e t c h i n g r e q u e s t ，t h i sw i l l m a k et h et r a n s f e ro fp r e f e t c h i n g r e q u e s td i s p e r s e d t h et h e s i sa l s os u m m a r i z e sa n dc o m p a r e ss e v e r a lm e t h o d sa s s o c i a t e dw i t ht h e m e a s u r e m e n to ft h en e t w o r kb a n d w i d t ha n dt h en e t w o r kr o u n dt r i pt i m eo nt h e n e t w o r k p e r f o r m a n c e i nt h es i m u l a t i o nt h er e a lt r a c er e c o r di su s e d ，s ot h er e s u l t so f t h es i m u l a t i o na r ec o n v i n c i b l ea n db e l i e v a b l e f i n a l l y , t h et h e s i se x t e n d st h ep r e f e t c h i n gm e t h o da n dp r e f e t c h i n gc o n t r o li n t o t h ew i r e l e s sn e t w o r ka n dp r e s e n t sap r e f t e c h i n gm e t h o dt h a tc o u l db ea p p l i e di nt h e w i r e l e s sn e t w o r ke n v i r o n m e n t ，w h i c hi sb a s e do nc o n t e n t so ft h ew e b p a g e s ，u s e r s t e r m i n a lr e c o r d ，st h ea n a l y s i so ft h ew e b p a g e sw i t hs p e c i a ls t r u c t u r eo nt h es e r v e r s ， f i l e st h a tu s e r sa r e l i k e l yt or e c o r da n d t h eb e h a v i o r so ft h eo l du s e rg r o u p s k e y w o r d s ： p r e f e t c hc o n t r o l b a s e dp r e f e t c h b a n d w i d t h m e a s u r e m e n to fn e t w o r k p e r f o r m e n c e s i m u l a t i o n u s e r s t e r m i n a lr e c o r dt h e g r o u p o f u s e ra c c e s sm o d e i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 一 学位论文作者签名：曩互z 签字日期： 2 。p3 年2 月7 日 学位论文版权使用授权书 本学位论文作者完全了解苤洼盘堂有关保留、使用学位论文的规定。 特授权墨盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) ， 学位论文作者签名：琶、丢2导师签名： 私向司 签字日期：知。；年2 月fr 日 签字日期：。、年2 一月，夕同 第一章绪论 第一章绪论弟一早三百1 = 匕 1 1 互联网的起源和发展 人们一直对全球信息数据库这1 概念存有梦想，希望足不出户就可以奄找到 自己需要的信息，并且希望相关的信息实现互联，从而能够迅速地找到重要的数 据。现在我们终1 二拥有了在全球范围实现这一梦想的技术一全球互联网( 简称 w w w 、w e b 或w 3 ) 。w w w 通常是建赢于i n t e r n e t 上，两者虽然并不是一回事，但 是人们总是把它们等同看待。 i n t e r n e t 指的是全球范围内由众多计算机组成的巨大网络，单词原意为“网 络的网络”或“网问网”，由分布在世界各地数以千计的小型区域嘲构成。i n t c r n e t 起源j ：美国国防部支持研究的网络一a r p a n e t 。在最初建立a r p a n e t 时( 1 9 6 9 年 1 2 月) ，a r p a n e t 只有设在美国国内的4 台主机。截止到1 9 9 8 年，i n t e r n e l 已 经发展成为拥有超过3 千万台主机、遍布世界1 8 0 多个国家的全球性计算机网络。 i n t e r n e t直维持着指数增长速率，而且到目前为止还没有表现出任何减慢的 迹象“。从图l l 中能够明显的看出主机( h o s t ) 和w e b 服务器( w e bs e r v e r ) 的 这种发展趋势。根据1 9 9 9 年4 月份公布的一项统汁数据表明，我国i n t e r n e l 的 发展非常迅速，自1 9 9 4 年与国际互联网实现直接连接，5 年来上网用户己达2 1 0 万。i n t e r n e t 发展如此迅猛，几乎没有人能预测它今后的发展规模会有多大。 髓扭l 攀l 档聃矬l 枉，亨攀辅掣 图i - li n t e r n e t 增长趋势图4 如果说i n t e r n e t 就是全球网络的实体一一大堆电缆和计算机，那么w w w 就是一个抽象的知识空间一一信息的集合。w w w 的正式定义是“广域超媒体信息 墓。誊羹孳誊瓷嚣l藿玺誊艟 第章绪论 的集合，对全球海量文档提供的一种访问方法”。也有将w w w 定义成“i n t e r n e t 上支持w w w 网络协议的客户机和服务器的集合”，从这个意义上讲，w w w 和 i n t e r n e t 是密不可分的。 w w wr 程是1 9 8 9 年由c e i “( e u r o p e a no r g a n i z a t i o nf o rn u c l e a rr e s e a r c h ) 提出构建的，目的在于建寺一个分布式多媒体的l 删络信息系统，为网络用户提供 一个统一的方法，以简便的方式访问各种媒体。w w w 改变了人们浏览和创建信息 的方法，创造出第一个真正的全球多媒体网络。 w w w ( w o r l dw i d ew e b ) 是由w e b 服务器( w e bs e r v e r ) 、w e b 代理服务器( p r o x y s e r v e r ) 和客户机( c l i e n t ) 组成的分布在整个i n t e r n e t 上的大型分布式系统，图 卜2 为w w w 的结构示意图。在这样的分布式系统中，w e b 服务器是储存信息的仓 库，是信息的提供者；w e b 代理服务器常用在设有防火墙的网络机器上，可以说 是防火墙网络中所有w e b 客户的代理人。在一个受到防火墙保护的环境里，代理 服务器为内部客户提供访问i n t e r n e t 的机会。客户机是信息的使用者，客户机 向服务器请求或通过代理服务器向服务器请求并提取信息。 图1 2w w w 结构示意图 w e b 服务器和客户机之间的通讯使用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 l l ) 定义了一系列的方法，其中最经常使用的方法是g e t 。客户机发m 。 个g e t 请求，向服务器请求某种资源。在这里所说的资源可以是保存在服务器上 的静态文件或者是脚本( s c r i p t ) 在服务器上执行的结果。g e t 请求用 u r l ( u n i f o r mr e s o u r c el o c a t o r ) 来确定所请求的资源。 代理服务器需要完成的基本任务是对客户机提交的请求报文按照h t t p 协议 进行解释和重组，并代表源客户机向w w w 服务器请求资源( g e t ) 或提交数据 ( p o s7 r ) ，然后将w w w 服务器的响应转发给源客户机。 籀一章绪论 近年来，i n t e r n e t 的发展非常迅速，图卜i 显示了主机和服务器的增长趋 势。w w w 页面( p a g e s ) 数量也以大约每个月增加1 5 的速度增长，图i - 3 表示了 w w w 页面数量的增长趋势。由于在w w w 中，总是将w e b 数据划分成一个个页而， 一个页面是w e b 数据的一个逻辑单位。因此，w w w 中页面数罱的增长趋势可以反 映出洲的发展趋势。 t ；j t 一”，n ；? t 甜，sm 卅一v 、j 图1 3w e b 页面数量的增长趋势f 4 w w w 是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 浏览速度的缓慢，使用者从w e b 服务器上查找文件经常要经历长时间的等待。 虽然引起w e b 浏览速度缓慢的因素很多，但其中主要因素有： ( 1 ) w e b 服务器吞吐能力不足所引起的服务时间的延长； ( 2 ) 网络带宽不足所引起的传输时问的延长； ( 3 ) 不完善的网络协议引起传输时间的延长。 解决浏览速度慢的问题主要有两类方法，虽然两类方法所要解决的问题利所 要达到的目的相同，但是解决问题的着眼点和解决途径却大不相同。第一类方法 是提高w e b 服务器的处理能力和网络带宽；第二类方法是设法提高现有系统的利 用率。 很明显，第一类方法是解决浏览速度慢的最根本的途径。但是从i n t e r n e l 的发展过程中不难看出，尽管服务器的处理能力越来越强，网络带宽也在逐步提 第一章绪论 高，i n t e r n e t 主干网的容量著不多以每年提i 苛6 0 的速度在扩充”1 。町是l 删络 系统能力的提高始终跟不上网络应用和网络用户的快速增长。出现这种被动局面 的主要原因是网络基础设施建设需要大量的投资并且建设周期k 。因此，w e b 浏 览速度慢便成为w e b 中长期存在并需要不断解决的重要问题。 第二类方法是通过提高系统的利用率，达到减少使用者等待时间的目的，这 类方法主要包括： 提高网络协议的效率提高网络协议的效率的基本依据和出发点是：由于 不完善网络协议将消耗掉部分网络带宽，从而加剧网络带宽的不足。由网络协议 本身引起的问题最好是通过研究改进网络协议得到解决。目前w e b 中使用的 1 l t t p lo 协议”1 在解决系统延迟方面并没有进行特另i j 白优化。些研究者已经分 析了h t t p 协议存在的低效能o ，并且提出了一些减少延迟的修改方法，如 h t t p t 1 ”j 的提出和使用就是从网络协议的角度对网络系统性能的改进。 设置镜像服务器w e b 服务器镜像方法的基本依据和出发点是：在i 删络的 不同位置设置w e b 服务器的镜像服务器，客户的w e b 请求总是从距离客户最近的 服务器或镜像服务器得到响应，从而减少客户的等待时问。 数据压缩传输数据压缩传输方法的基本依据和出发点是：w e b 中的许多 信息，特别是大量的文本信息，是以未压缩的形式存放和传输的。这样的信息在 传输过程中就会花费比较多的时间，同时会占用比较多的网络带宽；如果传输的 信息都是经过压缩的信息，那么就会减少传输时间，也会减少网络带宽的占用。 设置w e b 缓存( w e bc a c h i n g ) w e b 缓存方法的基本依据和出发点是：如 果一个文件有可能被使用两次或两次以上，那么在这个文件被第一次使用时，将 其付本保存在客户机或本地服务器中，以便后续的访问能够从客户机或本地服务 器中获得，不必访问远地的w e b 服务器，显然可以大大地缩短访问的距离。一方 面可以减少信息的传输时间，另一方面可以减少网络和w e b 服务器负载。 增加w e b 预取功能( w e bp r e f e t c h i n g ) w e b 预取方法的基本依据和出发 点是：在一个浏览会话中连续两个页面的下载之间，常常有一段空闲时间称为使 j j 者思考时间( u s e rt h i n k i n gt i m e ) ，这个空闲时间的长度范围可以从几秒钟到 几分钟，预取就是利用这个空闲时间提前把使用者不久将要使用到的文件取回， 并存放到缓存中。这样就可以减少实际访问时的等待时间。 1 2 w e b 预取研究的现状与分析 对w e b 特性的研究，包括w e b 文件特性、使用者的浏览特性、网络特性等方 4 第一章绪论 面的研究构成了w e b 缓存和w e b 预取研究的理论基础，因此受到了许多研究者的 关注。 w e b 预取的基本思想是将用户不久可能访问的某些贝面，在用户还没有发送 请求前就职到 w 户的缓存中。如果用户后米确实请求了预取页面中的某个页面， 由j ：这个页面已经在本地的缓存中，所以能够将等待时间减少到最小。预取山法 是缓存机制的有效补充。 预取既可以由服务器发起，预取也可以由客户端发起。预取方法可以分为两 类：一种是基于本地信息的预测方法，另一种是基于服务器信息的预测方法。其 巾又可以划分为基于链接的方法和基于访问历史的预测方法。 当前，对于预取控制的研究比对预取的研究少了很多。而这是本文的重点。 1 3 研究课题描述 对于w e b 业务的迅速膨胀，预取的使用是减小w e b 浏览延迟的有效方法之 ， 但是预取技术的实际应用还有很多问题，例如预取对于网络性能具有很大的负面 影响，如果预取被广泛采用会使本来已经非常繁忙的网络更加不堪重负，甚至出 现严重的网络拥塞。而预取控制可以限制预取对网络性能的负面影响。考虑到网 络业务的自相似特性，本文研究了适合于这种特性的基于网络性能测量的预取控 制方法。 本文的主要工作是： 1 实现了基于网络性能测量的预取控制算法，并对其进行了仿真的实 现。发现预取控制的确有很好的效果。 2 对各种网络性能的测量方法进行了总结和对比，利用其中效率比较 高的算法来进行网络性能的测量。 3 最后，针对当前无线网络的发展，提出了适合无线网络的预耿和预 取控制方法，这个方法还有待于进一步的仿真实验的验证。 本文的内容大致安排如下：第二章w e b 代理服务器的预取方法，第三章w 髓 业务的自相似性，第四章代理服务器的预取控制策略及优化，第五章网络性能测 量，第六章仿真数据和结果，第七章无线网络的预取和预取控制。 第二章w e b 代理服务器的预取方法 第二章w e b 代理服务器的预取方法 减少用户上网浏览时所感觉到的延迟是w e b 研究中的一个重要方面。这方面 的技术之一就是缓存和预取技术，由于缓存的存在，能够以更快的速度获取经常 访问的文档，从而能够减少等待时间。然而，由于在w e b 中存在着动态的文梢和 大量变化着的文档，这种变化着的文档使得缓存的性能下降。所以在w e b 研究中 在增加缓存技术的基础上引入了预取( p r e f e t c h i n g ) 方法。 w e b 预取的基本思想是将用户不久可能访问的某些页面，在用户还没有发送 请求前就取到用户的缓存中。如果用户后来确实请求了预取页面中的某个页面， 由于这个页面已经在本地的缓存中，所以能够将等待时间减少到最小。预取方法 是缓存机制的有效补充。预取可以利用系统输入输出的空闲时间，如果预测比较 准确的话，缓存的性能将得到明显改进。 2 1 w e b 预取方法概述 使用者利用浏览器检索w e b 信息的方式，通常是先下载一个w e b 页面，然后 再一i 击该页面中的超链接，以获得另一个w e b 页面。在这样的使用方式下，一个 浏览会话中连续两个w e b 页面的下载之间就会有一段的空闲时间，这段空闲时问 称为使用者思考时间，空闲时问的长度范围可以从几秒钟到几分钟。 下面简单说明请求的时间关系。 设t 。是使用者发第i 次w e b 请求的时刻：t + 。是代理服务器预测的使用者将 会发第i + 1 次w e b 请求的时刻；t 。是系统响应使用者第i 次请求后，完成请求对 象传输的时刻。t ，是预取请求发出的时刻，如图2 - i 所示： t，t。t ft 。+ i 图2 - i 请求响应的时间事列 我们知道文件传输之间的传输间隔可以理解为客户对于二上一次传输文件的 阅读和处理时间。相对于文件传输时间，传输间隔时问( t 。，t 。) 是相当长的。 w e b 预取方法就是利用连续两个w e b 页面下载之间的空闲时间，把使用者不 第二章w e b 代理服务器的预取方法 久将要使用到的文件提前取回，并存放到代理服务器或本机缓存t h 在w e b 中增 加预取功能，虽然不能减少w e b 页面的实际传输时间，但是由于预取贝面的传输 利用了系统的空闲时问，使得w e b 页面的传输与使用者的阅读和思考时间能够并 行进行。w e b 预取所改善的足使用者所感觉到的延迟时间。 预取是用向前看的方法减少使用者所感觉到的延迟时问。只有在能够预料使 用者不久将要访问的w e b 页面的前提下，才有可能在这些页面被请求之前预先为 使f _ f j 者下载这些页面。因此w e b 预取的效果取决于使用者访问w e b 页面的过程是 否具有一定的可预测性。 研究表明，用户进行w e b 浏览的行为具有某些规律性。因为w w w 是基于超文 本的信息系统，所以许多w e b 页面是由超链接紧密的联系在一起。而且在w e b 页 面设计时超链接的安排基本上都与特定内容相关。因此w e b 页面中的超链接以及 超链接被点击的顺序都可以作为预测的基本信息。另外，w e b 服务器中小同的文 件有着不| _ j 的受欢迎程度( 或者说是流行程度) ，使用者经常访问w e b 服务器中的 些文件，却很少访问另一些文件。w e h 服务器中文件受欢迎的程度也日j 以作为 预测的基本信息。 预取可以由服务器发起。当一个页面被请求时，服务器可以预料随后可能被 点击的超链接，并且提前把相关的页面下载到客户端。所以当使用者点击页面中 的一个超链接时，相关的w e b 页面可能已经传送完或者正在传送。 预取也可以由客户端发起，预测的依据可以是使用者对特定的页面的过去的 访问模式。客户端发起的预取可以由客户端单独完成，对服务器来说预取是透明 的。 静态预取的预测是根据最近的访问记录计算出w e b 页面之间的相互依赖程 度，通常设置一个预取门限值，当预测结果高出门限值时执行预取操作。但是， 由于预测准确性的原因，会造成一些带宽的浪费，所以静态预取可能会增加总的 带宽消耗。因此需要在带宽和延迟之间进行折衷，当降低静态预取门限时，延迟 时间可能会得到改善，但是这种改善是以增加带宽消耗为代价的。然而，在大多 数网络中带宽仍然是很缺乏的资源，特别是在长距离线路中更是如此。另外，虽 然对于已经预取到w e b 缓存中的文件来说，使用者访问它们时的延迟时间非常 短，但是对于那些非预取文件的检索时间实际上可能是增加了，这是因为预取增 加了额外的业务量。当业务量很重时，贪心的预取( a g g r e s s i v ep r e f e t c h i n g ) ， 比如预取w e b 页面中的所有超链接的预取方法，实际巴会使所有访问的平均延迟 时间增加。简单的预取算法将会对网络l 生能产生严重的负面影响，引起平均包延 迟的增加。 第二章w e b 代理服务器的预取方法 实际上预取研究的内容包括预测方法研究和预取控制方法研究。而且在某种 意义上，预取控制方法的研究更加重要。 2 2 预测算法 预测算法是预取方法的核心，准确的或比较准确的预测算法将能够明疆改善 缓存的性能。 如何减少用户上网浏览时所感觉到的时间延迟是w e b 研究中的一个重要方 面。缓存技术已经应用于w e b 中，由于缓存的存在，能够以更快的速度获取经常 访问的文件，因此能够减少等待时问。然而，由于在w e b 中有大量变化着的文件， 而且变化的很快，这种变化着的文件使得缓存的性能下降。所以在w e b 研究中引 入了预取( p r e f e t c h i n g ) 和预推( p r e - p u s h ) 方法。 w e b 预取( 预推) 方法的基本思想是将用户不久可能访问的某些页面，在用户 还没有请求前就取( 送) 到缓存中。如果用j 。确实请求了预取( 预推) 页面中的某个 页面，由于这个页面已经在缓存中，所以能够减少等待时间。预取( 预推) 方法是 缓存机制的有效补充手段。预取( 预推) 可以利用t 0 系统空闲的时问，如果预 测足够准确的话，缓存的性能将得到明显改进。已经提出的预测方法，可以分为 两类”1 ： 基于本地信息的预测方法 基于服务器信息的预测方法 下面分别对这两类预测方法进行简要介绍。 2 2 1 基于本地信息的预测方法 基0 二本地信息的预测方法是指预测预取对象时只根据客户浏览器或代理服 务器提供的信息，并不借助于w e b 服务器的任何信息。骜于本地信息的预测方法 又可以分为基于链接的方法和基于访问历史的方法。 2 21 1 基于链接的方法 基于链接的方法是把当前页面中的所有的或前若干个“热链接”作为预取的 内容。 w w w 可以被看做为面向页面的服务。页面用h t m l 语言编写，页面中通常包 第二章w e b 代理服务器的碗取方法 ：) p 啦口* ：錾。删一m 。 图2 - 2w e b 页面组成圈 括文本、图象和对其它页而的引用。在与 w 唧的交互中，客户请求h t m l 资源和图象， 并以页面形式显示它们。预取通常是提前 取回那些与客户所检索显示页面相关的贝 面。例如，如果页面a 被检索，则预取系 统收集页面b 、页面c 以及页而中所包含的 图象。在有些系统中为使用者提供了设置 某些预取属性的交互方浊，这样预取系统 可以根据使用者事先指定的内容或属性选 择预取目标资源。 研究表明，如果预取系统收集包含在客户所检索页面中的所有页面，能够达 到6 9 的命中率。然而，预取系统会加重主机的负载。对于交互方法而言，随 着预取目标资源的增加，命中率和负载都随着增加。3 。 2 2 12 基于访问历史的预测方法 基于访问历史的预测方法比较复杂，目前所采用的研究方法基本上是通过研 究用户的w e b 访问历史，建立访问预测模型。 根据预测模型所使用的历史信息的不同，访问历史的预测模型可分为三类： 基r 某个客户( w e b 客户) 访问历史的预测模型 对基于某个客户( w e b 客户) 访问历史的预测模型而言，由于预测的依据仅有 某个特定的客户，因此，当客户初次访问某个文件或访问该文件次数较少时系统 将无法做出预测。 基于某个群体( w e b 代理) 访问历史的预测模型 通常同一个工作组的成员对w e b 有相似的兴趣和访问习惯，也就是说，他们 访问的页面有可能是相关的或是相同的。因此根据群体访问历史进行预测将会得 到较高的命中率。在基于访问历史的预测算法中，规定时间段的氏短对预测的命 中率有一定的影响。如果规定的时间段较长，系统将对客户兴趣点的转移不敏感： 而规定的时间段较短，系统将难以记录客户一贯的兴趣点。 基于条件概率的预测 访问概率p ( b a ) 被定义为条件概率，即假定文件a 正在被使用者查看而文 件b 将被使用者请求的概率。计算访问概率的依据是在规定时问段内所记录的访 第二章w e b 代理服务器的预取方法 问文件a 的次数和由文件a 进而访问文件b 的次数计算得出的。预测算法中设置 了两种计数器，即文件计数器和连接计数器，每个文件a 与一个文件计数器c a 相关。如果文件b 能够直接从文件a 访问，即在文件a 中存在一个指向文件b 的 琏接，则对 二a 、b 有一个连接计数器c ( a ，b ) 。最初，所有计数器都被置为0 。 只要文件a 被下载，则c a 加1 。如果在文件a 中点击厂相应的连接访问了文件b ， 那么计数器c ( a ，b ) 也加l 。只要文件a 被查看，文件b 将被访问的概率就可以由 f 式给出： p ( b a ) = c ( a ，b ) c a 因此p ( b a ) 就表示从页面a 到页面b 的可能性。 基于m 阶p p _ 方法的预测 p p m ( p r e d i c t i o nb y p a r t i a lm a t c h ) 是一种上f 文关系模型( c o n t e x t m o d e l ) 。这种上f 文关系模型在压缩通讯中已经表明能够达到很好的性能。p p m 使用多重高阶马尔科夫模型( m u t i p l eh i g h o r d e rm a r k e r ) 来存储上下文关系， 并利用上下文关系进行预测。上下文关系的长度称为阶，同样如果预测模型使用 长度为n l 的上下文关系，那么就称这种模型为i l l 阶模型。在w e b 上下文关系模型 中，模型元素是对w e b 页面的访问事件，并且上下文关系依赖于这些事件的顺序。 所以，如果a 、b 和c 是三个页面，那么上下文关系( a b c ) 就说明至少有一个客户 已经按照特定的顺序访问了这三个页面。 要实现m 阶的预测模型就要维护长度从0 到m 的上下文关系。树是描述这种 模型的一种方法，它可以把不同长度的上f 文关系混合在单一的结构中。校拟结 果显示，有1 8 一2 3 的预测达到8 0 一9 0 的准确性“。 基于转移网络的预测 c u n h a 和j a c c o u d 等人提出了一种使用转移网络进行预测的方法。转移刚络 中的每个结点是一个对象表示一个文档，结点之间的连线表示从一个对象到另 个对象的转移。而且对象间的转移具有不同的权重。对象之间的转移分为三类： 嵌入对象、遍历对象( t r a v e r s a lo b j e c t s ) 和无关对象。嵌入对象可以通过查看 基本对象来决定；遍历对象和无关对象由设置的门限决定，转移时问小于门限值 的就是遍历对象；转移时间大于门限值的所有对象就是无关对象。调整门限值可 以控制转移网络中结点的数量。虽然可以考虑用所有使用者访问过的所有文档建 立个巨大的图，但是这样的图将会包含太多的使用者的选择，而且预取对象的 数量电很大，反而降低r 性能。转移网络随着使用者的每次访问而更新。 第二章w e b 代理服务器的预取方法 2 2 2 基于服务器信息的预测方法 基于服务器信息的预测方法是指预测预取对象时只根据w e b 服务器提供的 信息，比如由大量访问者大量访闽所表现出的访问模式等。7 f o p l o 方法是 m a r k a t o s 和c h r o n a k i 等人提出的预测方法。这种方法的依据是客户对w e b 服务 器的绝大多数请求常常集中于很少一部分文件，可以认为这些文件是这个w 。b 服 务器中最流行的文件，也就是客户的兴趣点所在，这些文件称为t o p 一1 0 。t o p 一1 0 方法认为只有在访问最流行的文档时才考虑预取，预取的对象就是w e b 服务器中 最流行的那部分文件“。 各种各样的预取和预测算法还有很多种，在此我们就不一一介绍了，每种预 取算法都有各自的特点和适用性，但是由于用户访问行为的复杂性，使得预测的 准确度有限。已有研究表明，本地代理缓存最大可以减少2 6 的访问延迟，而 预取最多可以减少5 7 的延迟时间，将预取技术和缓存技术结合起来使用时， 其效率的上限是减少6 0 的访问延迟时间”。 本文中，我们关注预取的另一特性：增加了网络的延迟。研究表明，即使预 取的内容都有效，它也会影响网络的整体性能。这是因为预取改变了应用程序对 网络的请求模式，进而增加了网络的负载的变化和突发性，这就增加了网络上数 据包的排队延迟。总之，直接的预取增加了数据包处理时间。 第三章w e b 业务的自相似性 第三章w e b 业务的自相似性 为了管理通过网络的通信量，必须要理解如何描述通信量以及各种不同通信 量类型的性能含义。 有许多参数对描述数据通信量很重要： ( 1 ) 吞吐量特性 平均速率一一表示信源在较长的时间里持续发出的流量。信源提供的平均负 载对于确定分配给该信源的总量是十分关键的。 峰值速率一这个参数报告网络通信量最大的速率是多少，以便网络能够通 过预留足够的数据传输容量和缓存空间接纳此通信量。 可变性一一可变性衡量一个信源的突发性，它是在统计复用中用于提高资源 利用率的一个度量。峰值是可变性的一种度量；一种更直接的度量是吞吐量的变 化。 ( 2 ) 时延特性 传输时延一这个参数度量数据从信源到目的地过程中网络所施加的时延。 最大传输时延乜常常被应用程序作为一项需求提出来。 时延偏差一一传输时延的偏差大小是实时应用的一个重要参数。在实时应用 中，目的端应该以平滑连续的速率播放收到的数据，该速率与信源产生的速率匹 配。这对于网络配置和协议设计有深远的影响。 排队分析提供了一个简单的且容易处理的方法来得到有用的结果，这些结果 可以用来指导网络的设计和发展。几十年来，基于泊松( p o s s i o n ) 通信量假设 的排队分析，一直是网络性能分析人员的应用工具。然而，近些年来出现了一个 惊人的结果：至少在某些情况下，数据通信量实际上并不是泊松( p o s s i o n ) 分 布的，而是自相似( s e l f - s i m i l a r ) 或分形( f r a c t a l ) 分布的。对于这种通信 量，网络的性能不能再用排队分析的公式来描述，网络的时延比预期的更大，吞 吐量也更低。自从最初发现这一结果之后，许多通信自相似的结果多次得到证实。 下面讨论通信量的自相关特性及其对网络性能和建模的影响。 3 1 现代通信业务的自相似特性 第三章w e b 业务的自相似性 近年来，随着网络测量技术的发展，人们己能够获得大景的业务数据进行分 析研究。2 0 世纪9 0 年代初期，美国贝尔通信研究中心( b e 1 c o r e ) 的研究人员 采集了大量关于以太网和可变比特率v b r ( v a r i a b l eb i tr a t e ) 的视频业务数 据，并使用分形( f r a c t a l ) 思想进行了详尽的分析研究，证实真实的网络业务 具有统计上的自相似性( s e l fs i m i l i a r i t y ) 。各国研究人员也对世界上现有的 一些网络进行了测量和分析，例如， ( 1 ) p a x o n 和f l o y d 采集了大量有关广域网业务的数据，其中包括许多t c p 到达过程。p a x o n 对这些数据进行了详尽的分析。 ( 2 ) a d d i e 等观测分析了澳大利亚高速数据网f a s t p a c ，该网可提供速率为 2 l _ o m b s 的服务，连接了澳大利亚的主要城市。 ( 3 ) c r o v e l l a 等观测分析了w w w 业务，这些业务反映了数以万计的文档请 求。 所有这些测量均证实，高速网络业务具有自相似性。自相似性反映了业务在 所有( 或至少一个较大范围) 时间标度上的统计相似性，突出表现为突发( b u r s t ) 没有明确的长度，我们不可能将他们平滑掉。从传统模型得到的结论是，当业务 源数据增加时，突发性会被吸收，聚集业务将变得越来越平滑；而对于自相似模 型，其聚集业务的突发性将更突出而不是减少。 加拿大s a s k a t c h e w a n 大学( u n i v e r s i t yo fs a s k a t c h e w a n ) 的a r l i t t 利 w 订1 i a m s o n 收集了三个w e b 服务器业务数据，三组数据分别来自：w a t e r l o o 大 学计算机科学系的系级w e b 服务器，s a s k a t c h e w a n 大学校园网的w e b 服务器和 c 1 a r k n e t 一个商业i n t e r n e t 提供商的w e b 服务器。研究发现在三组w e b 服务器 业务数据中：c l a r k n e t 的h u r s t 参数约为0 ，6 5 ；s a s k a t c h e w a n 的h u r s t 参数约 为0 5 3 ；w a t e r l o o 的h u r s t 参数小于0 5 。因此，在三个w e b 服务器中：一个 有自相似性，一个自相似性很弱，一个没有自相似性。研究初步表明自相似性并 不是w e b 服务器业务的不变特征，只是在w e b 服务器负载较重时其业务具有自相 似- 陉。 近年来的研究结果表明，自相似性对网络性能产生一些意想不到的影响，它 直接影响网络的设计、控制、分析和管理。目前，国外围绕这一新课题的研究工 作刚刚开始，取得了一些成果，大量的问题有待解决。主要的困难在于，传统排 队论耩本上是在短相关的假设下研究队列性能，目前还没有一套完整的技术能解 决k 相关下队列性能的分析问题。 3 2 自相似性的定义和性质 第三章w e b 业务的白相似性 3 2 1 自相似性的定义 首先，对于自相似性的数学描述，简单地说明如下。 以f 是自相似性的定义。 对于广义平稳随机变量序列x = ( x ，x 2 ) ，设其均值为u = e x t ，自相 似函数为 r ( k ) = e ( x i u ) ( x i + k u ) e ( x j u ) 2 ( 3 - 1 ) 定义x ” ( x ( 1 i ) ( m 1 ) + + x n i 】)( 3 - 2 ) 对于广义平稳随机变量序列x 。= ( x ? ，x ：，) ，r “( k ) 为过程x 。的自 相似函数。如果r ( k ) 满足r ( k ) = 一，则称随机变量序列x 为长相关( 自 k = o 相似) 的。如果 v a r ( x 1 + x 2 + + x n ) 的增长速度为n 2 ”，则参数h 称为随机变鼍 x 的h u r s t 参数( h = 1 1 ：3 2 ) 。自相似随机变量序列可阱分为严格自相似序列 和渐进自相似序列。如果对所有k ，满足 r ( k ) = = 1 【( k + 1 ) “一2 k 2 h + ( k 1 ) 2 ” ( 3 - 3 ) 则随机变量序列x 称为具有h u r s t 参数h 的严格自相似序列。如果对所有k ， 满足 l i r a ，( k ) l i r a 普 c ( 3 5 ) 则过程x 称为渐进自相似序列。 自相似参数h 又称为h u r s t 参数，是描述自相似特性的唯一参数。h 的取值 范围是( 1 2 ，1 ) ，h 越大，过程自相似程度越高。 第三章w e b 业务的自相似性 3 2 2 自相似性的- 性质 ( 1 ) 自相似过程是长相关的 长相关眭意味着距离较远的数据相关性不可忽略不计，而传统模型的自相关 函数随问隔呈指数方式衰减，从而是短相关的。 ( 2 ) 自相似过程具有j l u r s t 效应 当h o 5 时，h u r s t 效应表明样本中极端值的持续时期应比较长，即所谓的 持续性( p e r s i s t e n c e ) 。如果这种极端值持续时期理解为网络业务的突发性，则 h 可以用来描述业务突发性的强度。而且，自相似性使得这种突发性不会因聚集 而被平滑掉，即突发性呈现嵌套特点。 ( 3 ) 衰减缓慢的方差 方差随着过程聚集而缓慢衰减，表明自相似过程的波动剧烈。 ( 4 ) 指数特性的谱密度 当我们在频域上考察自相似过程时，由于它的持续性，低频处的谱密度非常 大，表现为在频率 的零点附近谱密度函数服从幂指数函数。因此从谱分析的角 度来看，长相关意味着当频率趋于0 时，其谱密度将趋于正无穷。而埘短相关 性而言，在频率 的零点附近，谱密度函数是一个有限正数o “。