（计算机应用技术专业论文）路由器缓存需求的研究.pdf

摘要 路由器作为一种存储转发设备，是不同网络之间互连的枢纽。然 而随着互联网流量与传输技术的快速发展，传统路由器缓存设置方法 逐渐暴露出一系列缺陷，成为限制网络性能提升的主要因素之一。到 目前为止，关于路由器的缓存需求问题的研究仍未有统一的结论。 本文首先介绍了路由器缓存需求问题的最新研究进展，重点讨论 了基于t c p 协议模型的五种典型的缓存设置方法，通过分析与比较 得出，基于不同假设前提和分析目标的缓存设置方法适应于不同的网 络环境。然后通过仿真进一步研究了影响缓存需求的几个主要因素， 着重分析了各种t c p 协议、队列管理机制与路由器缓存大小的相互 影响，得出在高带宽延迟网络下，当采用高速t c p 协议和主动队列 管理机制( a q m ) 时缓存需求大大减小。 针对现有固定大小的缓存设置方法无法适应流量复杂多变的网 络环境，本文结合吞吐量优化理论，提出了一种链路状态自适应的路 由器缓存设置算法b s l s 。该算法运用微分的思想引入一个判定因子， 采用乘性增加乘性减少( m i m d ) 一方式动态改变可用缓存阈值，通过 缓存阈值的调节实现网络吞吐量的优化。文中通过仿真验证了b s l s 算法在各种负载条件下都能保持高吞吐率，同时取得排队延迟和拥塞 丢包率的合理折中。 针对8 0 2 1 1 无线局域网下信道带宽的时变性和c s m a j c a 机制 的随机性，本文在a p 节点处设计一种自适应缓存设置算法a b s ，该 算法结合实时测量的m a c 队列空闲率，区分无线信道的竞争状况， 并采用加性增大加性减少( a i a d ) 的控制策略动态调整缓存阈值， a b s 算法实现吞吐量优化的同时有效减小传输延迟。 本文最后对所做研究工作进行了总结，并阐述了路由器缓存需求 问题下一步的研究思路。 关键词：缓存需求，t c p 协议模型，吞吐量优化，队列空闲率 a b s t r a c t w i t hr a p i dd e v e l o p m e n to fi n t e m e tt r a f ! f i ca n dt r a n s m i s s i o nt e c h n o l o g y , c u r r e n tr o u t e rb u f f e rs i z em a yh a v eam a jo rc h a l l e n g et oi t sp e r f o r m a n c e b u ts of a r , t h es t u d yo nt h er o u t e rb u f r e rs i z i n gh a sn ou n i f i e dc o n c l u s i o n f i r s t l y , t h et h e s i sr e v i e w st h er e s e a r c h e so fb u 髓rs i z i n gp r o b l e m m a i n l yf o c u s e so nf i v et y p i c a lb u f f e rs i z i n gm e t h o d sb a s e do nt h em o d e l o ft c p p r o t o c o l ，a n dt h e nc o n c l u d e sf r o mc o m p a r i s o nt h a tb u f f e rs i z i n g m e t h o d sb a s e do nd i f f e r e n ta s s u m p t i o n sa n do b j e c t i v e ss h o u l db ea d a p t e d t od if f e r e n tn e t w o r k s m e a n w h i l ew e s t u d ys e v e r a lp r i m a r yf a c t o r sw h i c h i n f l u e n c eb u f | f e rr e q u i r e m e n t ，a n dm a i n l ya n a l y z eh o wt c p p r o t o c o l sa n d q u e u em a n a g e m e n tm e c h a n is m si n t e r a c tw i t hb u 仃e rs i z e i nc o n c l u s i o n w ep o i n to u tw h e nh i g hs p e e dt c p p r o t o c o l sa n da q m a r eu s e di nh i g h b a n d w i d t h d e l a yn e t w o r k ，b u f f e rs i z ei ss u p p o s e dt ob er e d u c e dg r e a t l y c o m b i n e dw i t ht h r o u g h p u to p t i m i z a t i o nt h e o r y , t h i st h e s i sp r e s e n t sa n o v e la d a p t i v er o u t e rb u f f e rs i z i n ga l g o r i t h mb a s e do nl i n ks t a t e ( b s l s ) b s l si m p o r t sa j u d g i n gf a c t o rb yv i r t u eo fd i f f e r e n t i a li d e a ，a n da d o p t s t h em i m dm e c h a n i s mt oc h a n g et h ev a l u eo fa v a i l a b l eb u 虢rt h r e s h o l d d y n a m i c a l l y t h er e s u l t su n d e rd i v e r s i f i e dl o a dl e v e l ss h o w e dt h a t b s l s a l g o r i t h mc o u l dm a i n t a i nh i g ht h r o u g h p u t ，b ya c h i e v i n gp r o p e rt r a d e o f r b e t w e e nq u e u ed e l a ya n dc o n g e s t e dl o s sr a t e d u et ot h ef a c tt h a tc h a n n e lb a n d w i d t hi st i m e v a r y i n ga n dt h er a n d o m n a t u r eo fc s m a c a ，t h et h e s i sp r e s e n t san o v e la d a p t i v er o u t e rb u 虢r s i z i n ga l g o r i t h m ( a b s ) t h i sa l g o r i t h mc o m b i n e sw i t hi d l er a t eo fm a c q u e u et od i s t i n g u i s ht h el e v e lo fc h a n n e lc o n t e n t i o n a n dt h e nu s ea i a d m e c h a n i s mt oa d j u s ta v a i l a b l eb u 舵rt h r e s h o l d b yw h i c ht h i sa l g o r i t h m c a nm a i n t a i nh i g h t h r o u g h i p u tw h i l s ta c h i e v i n gl o wi n t e r - s e r v i c et i m e f i n a l l y , t h ed i s s e r t a t i o ns u m m a r i z e st h ec u r r e n te x i s t i n go p e ni s s u e s ， a n dp r o v i d e ss o m ef u r t h e ri n t e r e s t i n gd i r e c t i o n s k e yw o r d s ：b u f f e rs i z i n g ，t c pm o d e l ，t h r o u g h p u to p t i m i z a t i o n ， q u e u ei d l e n e s sr a t e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：挝日期：丑年上月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 期：盟年月一2 o f t 硕士学位论文第一章绪论 第一章绪论 本章首先介绍了网络向高带宽高延时发展的趋势，引出了路由器缓存需求成 为目前热点研究问题的原因，并进一步阐述了该问题的研究现状和面临的主要问 题，在此基础上提出了本文所做的主要工作和组织结构。 1 1 研究背景 在当今世界向信息时代迈进的过程中，高性能通信技术的应用成为主要的促 进因素。在过去的十年中，网络通信技术得到了飞速的发展，以互联网为代表的 信息网络已经逐渐渗透到当今社会的各个领域，成为了国家进步和社会发展的重 要支柱，以及知识经济的基础载体和支撑环境。 在网络发展的过程中，以i p 协议为基础的i n t e r a c t 已逐步成为全球性的信息 基础设施。i n t e m e t 的历史可以追溯到2 0 世纪6 0 年代末由美国高级研究计划局 资助建设的a r p a 网络，其最初的目的是互连分布在各地的计算机网络。在 i n t e r n e t 发展初期，网络用户主要来自研究机构和大学，网络应用主要是基与文 本的交互( 如t e l n e t ) 和文件传输( 如f t p ) 服务。但是，从2 0 世纪9 0 年代初 开始，随着万维网( w w w ) 技术的出现，各种商业机构、政府部门和个人开始 大量介入，引发了i n t e m e t 发展的高潮，其网络规模、用户数量和流量都呈指数 增长。现在，i n t e m e t 已从一个简单的试验网络发展成世界上覆盖面最广、规模 最大、信息资源最丰富的计算机信息网络。随着网络技术的飞速发展和接入性能 的不断提高，大规模的高速下一代互联网试验环境已经逐渐形成。同时随着各种 新型网络应用的产生，对网络的数据传输要求也将不断提高，现在已经有越来越 多的研究人员开始经常利用这些高速网络传输1 0 g b p s 1 t b p s 的数据来进行科学 研究，如量子物理学、地球观测学和射电天文学等方面的海量数据研究。在这种 发展背景下，如今全世界的互联主干网络开始逐渐呈现出一种高带宽高延时 ( h i g hb a n d w i d t h d e l a yp r o d u c tn e t w o r k s ) 的网络特性。 在i n t e m e t 中，路由器是最重要的网络设备，同时也是集中体现网络新技术 的设备。它以t c p i p 协议族中的一系列协议为基础，能够智能地适应复杂的网 络拓扑结构及其变化，并使得各种异构网之间的互连成为可能。路由器不仅能够 快速分析当前网络拓扑结构，并据此寻找最优的转发路径，而且在网络管理、网 络安全等方面也发挥了重要的作用。可以说，路由器技术就是i n t e m e t 技术的核 心，它的处理速度是网络通信的主要瓶颈之一，它的可靠性则直接影响着网络互 联的质量。 硕上学位论文第一章绪论 然而随着i n t e m e t 骨干网络的带宽和延时的迅速增长，对路由器的性能提出 更高的要求。目前i n t e m e t 骨干网络普遍采用密集波分复用( d w d m ) 技术，链 路带宽可达到1 0 g ( o c 1 9 2 ) 以上。如图卜1 所示，当前随着因特网流量平均以 每半年翻一番的速率快速增长，以超摩尔定律发展的光传输能力，正在沿着每7 个月传输带宽增大2 倍的速率发展，而骨干网路由器缓存容量的发展由于受摩尔 定理所限，其增长速度仅为每1 8 个月增大2 2 倍。从而使得网络发展的瓶颈逐 渐集中到路由器节点的缓存上来。在高速网络中，路由器缓存成为系统的瓶颈， 制约了路由器和网络性能的进一步发展。 l 2 i n 刀e c 啪a p n a c 。h i t v y 2 ，7 啪n t h s尸 沙 uslra卢? 12m o n t h s 形 ，l 2 2 肿m o n m 一乡t y 2 1 8 o n t h s 篓篇愚怒 鼍 箍 1 9 8 31 9 8 61 9 8 91 9 9 21 9 9 51 9 9 82 0 0 l2 0 0 4 图1 1 网络流量、路由器和器件技术的发展趋势图 高速路由器中支持q o s 是未来通信网络最重要和最根本的要求之一。传统 的i n t e m e t 路由器面向非实时的数据传输，只能提供单一的“尽力而为服务。 在这种结构下，路由器根据分组的到达顺序，按“先到先服务”的方式尽可能快 地转发分组，并不关心传输流的吞吐量、分组的延迟和抖动等性能指标。对f t p 、 e m a i l 等实时性要求不高的应用来说，这种机制是简单且高效的。但是，随着 i n t e m e t 的进一步发展，口电话、视频会议、远程教学、远程医疗等新的应用层 出不穷。这些以声音、图像传输为主的多媒体应用除了需要大量的带宽外，还有 实时性的要求。如视音频数据必须按其采样速率连续播放，如果分组不能在容许 的延迟范围内到达接收端，就会影响播放的质量；在应用模式方面，i n t e m e t 正 从主机模式、客户服务器模式向合作化、对等( p e e r - t o p e e r ) 和在线交互的方向 2 硕士学位论文 第一章绪论 发展。典型的应用包括在线游戏和视频点播( v i d e oo nd e m a n d ) 等。应用模式 的变化也需要路由器能提供实时的交互能力和对网络的变化做出快速的反应。怎 样在高性能路由器中同时支持多种服务类型，并能保证每项服务都达到性能要 求，这就是高速路由器q o s ( q u a l i t yo f s e r v i c e s ) 技术所要解决的问题。 对于高速路由器的q o s 性能评估方法，r f c l 2 4 2 1 】和r f c 2 5 4 4 2 】进行了详细 说明，其主要系统性能指标有吞吐率( t h r o u g h p u t ) 、利用率( u t i l i z a t i o n ) 、丢包 率( 1 0 s sr a t e ) 、延迟( d e l a y ) 、缓存大小( b u f f e rs i z e ) 和实现复杂性( c o m p l e x i t y ) 等。其中，缓存大小还直接影响其他的性能指标，具有特殊的地位。若路由器设 置大容量的缓存，有利的方面是能够更好地吸收链路上突发性变速率到达业务， 当链路上发生拥塞时能够对新进入的数据包进行缓存，从而降低丢包率，维持高 链路利用率；不利的方面是过大的缓存将导致延迟的增大，增加实现的复杂度。 与此相对的是，小的缓存能够降低延迟和实现复杂度，但是利用率、丢包率和吞 吐率指标将有所损失。因此我们需要研究路由器设置多大缓存空间才能使得网络 总体性能达到最佳。 1 2 研究现状及问题的提出 路由器内部的缓存是制约路由器性能及造成网络不确定性的主要因素之一。 缓存一方面还可以容纳网络中的突发流量，避免出现大量的丢包；另一方面在网 络拥塞时路由器缓存可以暂时存储过量的数据包，直至网络空闲再将其发送出 去，从而提高了链路利用率。因此缓存对提高路由器性能进而提高整个网络性能 起了关键作用。然而过量的缓存同时也会引入排队延迟和延迟抖动。到目前为止， 路由器缓存需求的研究仍未有统一的结论。 1 9 9 4 年，c v i n a m i z a r 等人分别对l 条、4 条和8 条t c p 流通过容量为4 0 m b s 链路进行了测试，通过改变缓存的大小，考察被测链路的利用率，并以测试结果 为依据，提出了著名的路由器缓存设置法则经验法则( r u l e o f - t h u m b ) 1 ) j 是 将缓存大小设置为网络瓶颈的带宽延迟乘积( b a n d w i d t hd e l a yp r o d u c t ，b d p ) ，即 b = r t t c ，其中b 为拥塞路由器所需的缓存，r 刀( r o u n dt r i pt i m e ) 为一个 t c p 连接的平均往返时间，c 为拥塞链路的带宽。这一路由器缓存设置原则由于 简单易行，多年以来一直指导着路由器的设计。然而随着当前网络带宽和延迟的 不断加大，这种设置方法逐渐暴露出一系列缺陷： ( 1 ) 随着网络带宽和延迟的增大，根据经验法则设置的缓存也相应的增大， 目前商用路由器中t c p 连接的i m 约为2 5 0 m s t 4 】，一个出口带宽约为4 0 g b s 的 路由器根据经验法则需要设置1 2 5 g b y t e s 大小的缓存空间。过大的缓存给路由器 的设计带来困难，比如散热，能耗和主板空间开销等等。此外保持路由器的高速 硕七学位论文第一章绪论 转发性能需要采用高速的队列存储芯片，在现有的工艺基础上制造这种高速大容 量缓存需要巨大的成本开销，在实际的工程设计中，路由器使用多个d r a m 并 行处理来获取所需要的数据速率，但这不能从根本上解决问题。如果能够尽可能 的减少路由器的缓存规模，使核心路由器摆脱对d r a m 的依赖，就有可能在核 心路由器中使用较少的s r a m 或仅使用芯片内部缓存实现路由器的高速转发， 那么路由器的性能将得到极大的提升。 ( 2 ) 当前光通信领域内的各项技术发展迅速，然而光技术引入路由器设计 的道路上，有一个难题一直未能得到有效解决，即光存储问题。在一个光电集成 芯片上可实现容量仅为几十个分组的光f c f s 缓存，即便采用笨拙的光纤迂回策 略，缓存容量也远远小于网络的带宽延迟乘积。因此大规模的缓存成为实现全光 交换的瓶颈。设计小缓存不仅能推动全光路由器的建设，而且能够提升核心路由 器的性能、降低路由器的设计复杂度、增加路由器的可扩展性。 ( 3 ) 缓存大小直接影响到各种网络性能指标。过大的缓存将导致延迟的增 大，严重影响实时交互性业务的性能，增加实现的复杂度。与此相对的是，小的 缓存能够降低延迟和实现复杂度，但是利用率、丢包率和吞吐率指标将有所损失。 综上可知，研究路由器的缓存需求是路由器优化设计的基础，是提高路由器 整体性能进而提高整个网络性能的关键。 近几年在各种网络环境下出现了一系列对经验法则改进的缓存设置方法。斯 坦福模型首先对经验法则提出改进【5 】，作者认为当前骨干路由器的流量呈现出一 种统计多路复用的特征，因此要保持出口链路的充分利用，缓存大小只需设置为 带宽延迟乘积除以共享瓶颈链路的长t c p 流数的平方根，显然采用这种设置方法 时，随着流数的增多缓存空间会逐渐减小。然而文献【6 ，7 ，8 】提出相反的观点，为 了避免过高的丢包率和频繁的超时重传，路由器缓存大小应该与t c p 流的数目成 比例，即至少为每流分配几个数据包的缓存空间。此外文献【9 】认为如果t c p 发送 端采用t c pp a c i n g 机制且愿意牺牲一部分链路利用率( 1 0 - - 1 5 ) i i o 】，缓存可以 减小到十几个数据包大小，这种设置方法满足了全光网络环境中核心路由器的缓 存需求。到目前为止，不同法则的结论差别巨大，未能形成统一。 1 3 路由器缓存需求面临的新问题与新发展 以上各种改进的缓存设置方法是基于不同的假设前提和应用场景提出的，然 而将这些方法应用到现实网络环境的过程中仍然存在一系列问题。具体表现在： ( 1 ) 各种缓存设置方法只考虑部分网络层性能的优化，比如利用率、丢包 率等等，却很少考虑传输层和应用层的性能指标，因此如何将不同的性能指标相 结合提出最优化的缓存设置方法是需要进一步研究的方向。 4 硕士学位论文第一章绪论 ( 2 ) 大部分缓存设置机制依赖于活跃流的数目、i u t 的分布等等，这些网 络参数都是变化的，而且由于当前网络中路由器与路由器之间以及路由器与端系 统之间缺乏广泛的交流，路由器很难对这些参数做出准确的估计。 ( 3 ) 这些缓存设置方法都是建立在严格假设的数学模型基础之上，并未考 虑现实网络中各种复杂时变的流量特征，例如大部分缓存机制基于固定数目的长 期t c p 流建模分析，而实际网络中往往混合了各种不同长度、不同r t t 的t c p 流，同时也包含了非响应的u d p 流，而且网络流量特征随时间变化也比较剧烈。 综合以上三点，在现实网络环境下采用固定大小的缓存设置方法必然存在一 系列的问题。在复杂时变的网络环境下要达到网络总体性能的优化，我们需要根 据网络的流量特征动态改变可用缓存大小。 1 4 本文的主要工作 本文系统研究了路由器缓存需求领域的最新研究成果，并通过仿真分析了现 有复杂时变的网络环境下采用固定大小的缓存方法所存在的问题，并针对其反映 出的问题，提出了一种链路状态自适应的路由器缓存设置算法。 本文首先对当前缓存需求的研究背景和现状进行综述，并通过n s 2 网络仿 真软件比较和分析了基于t c p 协议模型的五种典型的缓存设置方法，得出不同 的假设前提和分析目标导致各种缓存设置方法适应于不同的网络负载环境，缓存 机制的选择取决于网络带宽延迟乘积与t c p 流数的比值；并进一步总结了影响 缓存需求的几个主要因素。着重分析了各种t c p 协议、队列管理机制与路由器 缓存大小的相互影响，并得出在高带宽延迟网络下，当采用高速t c p 和主动队 列管理机制时缓存需求大大减小。 接下来，本文在总结前人工作的基础上，结合吞吐量优化理论，提出了一种 链路状态自适应的路由器缓存设置算法b s l s ( b u f f e rs i z i n ga l g o r i t h mb a s e do n l i n ks t a t e ) ，该算法根据网络吞吐量的变化动态改变可用缓存阈值，旨在以最小 的缓存空间实现网络吞吐量的优化。 针对无线局域网环境下信道带宽的时变性和c s m a c a 机制的随机性，本文 提出了一种自适应缓存设置算法a b s ，该算法结合a p 节点的m a c 队列空闲率， 有效区分无线信道的竞争状况，并根据不同的链路竞争程度采用a i a d 策略动态 调整缓存阈值，本文通过仿真验证了该算法在无线局域网环境下维持高吞吐量的 同时有效减小了平均服务间隔。 5 硕士学位论文第一章绪论 1 5 论文组织 论文全文共分为五章。 第一章绪论，首先介绍了路由器在网络发展中的核心作用，并分析了路由器 缓存需求问题成为目前热点研究问题的主要原因，同时给出了研究的必要性和重 要意义。 第二章总结、分析和比较了当前基于t c p 协议模型的五种典型的路由器缓 存设置法则，指出经验法则及各种改进方案在利用率、时延、丢包率、功耗和成 本等方面的不足，同时给出了各种缓存方法在现实网络中存在的开放性问题，为 该课题的进一步研究提供了参考依据和研究思路。 第三章主要通过n s 2 网络仿真软件，结合不同的网络负载、较为全面的比 较和评价了各种高速t c p 协议和路由器主动队列管理算法对现有五种典型的缓 存设置方法的影响，并进一步总结了影响缓存需求的几个主要因素。 第四章在总结前人工作的基础上，结合吞吐量优化理论，提出了一种根据实 时链路状态动态改变缓存大小的b s l s 算法。算法运用微分的思想引入一个判定 因子，并采用乘性增加乘性减少( m i m d ) 的方式动态调节可用缓存阈值。并通 过实验结果证明了b s l s 算法在各种负载条件下都能保持高吞吐率，同时取得排 队延迟和拥塞丢包率的合理折中。 第五章提出了一种无线局域网中a p 节点的自适应缓存算法a b s ，该算法根 据实时测量的m a c 队列空闲率动态改变可用缓存大小，并通过缓存阈值的调节 维持高吞吐量的同时，有效降低了m a c 层传输延迟。 第六章为结束语。对本文的研究工作进行了总结，指出了目前研究中还存在 的一些问题和不足，并阐述了路由器缓存需求下一步的研究课题。 6 硕一f ：学位论文第二章缓存需求研究现状 第二章缓存需求研究现状 本章首先简要介绍了影响路由器性能的主要指标，接下来给出了当前路由器 缓存需求问题的理论描述，重点讨论了基于t c p 协议模型的五种典型的缓存设置 方法：经验法则( r u l e o f - t h u m b ) 、斯坦福模型( s t a n f o r dm o d e l ) 、基于丢包率 的缓存法则( d r o p b a s e db u f f e rr u l e ) 、极小缓存法则( t i n yb u f f e rr u l e ) 和自适 应丢尾算法( a d a p t i v ed r o p t a i l ) 。通过比较分析指出现行法则及各种改进方案 在时延、丢包率和利用率等方面的不足，由此引出本文后续的研究内容。 2 1 影响路由器性能的主要指标 影响路由器性能的主要指标有链路利用率、吞吐量、丢包率和端到端延迟， 为便于理解，下面分别对这四个性能指标作简要说明： 利用率( u t i l i z a t i o n ) ：路由器转发原始比特流的速率与可用带宽的比率。利 用率的计算如公式( 2 1 ) 所示。 墨 洲切砌，2 2 苦 ( 2 - 1 ) 其中，s 是目的端收到第f 个流的总数据量，c 是网络带宽，f 是仿真时间。 吞吐量( t h r o u g h p u t ) ：网络吞吐量在网络性能评价中是一个重要的参数。 指的是一定时间间隔内，某段网络链路正确传输和接收到的原始比特流的数目 ( 不包括重传的比特数) 除以传输时间的比率。这个概念通俗点讲，就是除掉 t c p 因为丢包和超时重发的数据，实际的每秒有效传输率，由此我们可以得出网 络利用率的计算公式： utflization=(segments_acked)*(segment_size)( 2 2 ) ( 1 i n kr a t e ) t i m e 、。 吞吐量决定路由器处理数据包的能力，下文将论证适当的缓存容量可以使得网络 吞吐量最大化。 丢包率( l o s sr a t e ) ：路由器丢弃的数据包与所有转发到该路由器上的数据 包数目的比值。数据包丢失一般是由网络拥塞引起的，所以，丢包率也是一项极 其重要的性能指标，它的计算方法如公式( 2 3 ) 所示。 7 硕上学位论文第二章缓存需求研究现状 n s d r o p = 1 一j 卜 ( 2 - 3 ) 耳 i = 1 其中，s 是目的端收到第f 个流的总数据量，g 是发送端发出第f 个流的总数据 量。 端到端延迟( e n d t o e n dd e l a y ) ：描述的是分组从源端丌始传输直到被成功 地传送到目的端所需要的时间。端到端的延迟包括：节点处理延迟( p r o c e s s i n g d e l a y ) 、排队延迟( q u e u i n gd e l a y ) 、传播延迟( p r o p a g a t i o nd e l a y ) ，其中排队 延迟是指数据包第一个比特进入路由器到最后一个比特从路由器输出的时间间 隔。下面给出端到端延时的计算如公式( 2 4 ) 所示。 s 。鸬 d e l a y = 号广一 ( 2 4 ) s ， i = 1 其中，s j 是目的端收到第f 个流的总数据量，鸬平均延时，以的计算如公式( 2 5 ) 所示。 v 。 4 ，p 鸬2 上 ( 2 - 5 ) 其中，n j 是目的端接收到第f 个流的分组个数，s i , p 是第f 个流的第p 个分组的 大小，z p 是第i 个流的第p 个分组的端到端延时。 我们认为缓存设置问题的评价标准是以最小的信号量实现网络吞吐量的最 优化，同时达到利用率、丢包率和排队延迟的合理折中。在后文多瓶颈复杂网络 的仿真中，我们还考察了各种应用程序的性能指标：其中包括基于c b r 流的交 互式流媒体应用的单向传输延迟、基于长期t c p 流的文件传输应用的有效吞吐 量和基于短期t c p 流的w e b 页面下载的完成时间。 2 2 路由器缓存需求的理论模型 已有许多学者对路由器的缓存需求的相关研究都是建立在两类模型基础上， 一种是描述队列的动态特性，而另一种是描述t c p 协议的动态特性。概括来说， 这些研究包括以下两大类理论分析方法： 第一，利用随机服务理论，也称为排队论的方法f l l j 。即给定输入流量模型、 3 硕士学位论文第二章缓存需求研究现状 服务模型，利用排队理论分析排队的队长分布( 缓存大小) ，计算丢包率、时延 等关键性能参数。这类方法不考虑输入流量的网络反馈( 网络反馈包括由所观察 到的链路往返时间和丢包率来触发的t c p 自适应窗口机制和路由器中的拥塞避 免策略) ，是一种开环方式的分析方法。该方法基于m a r k o v 的输入过程得到关于 缓存大小和丢包率、平均等待时间等性能参数的关系，由于输入流量模型的共同 特点是只能描述网络流量序列的短相关性，因此，本文称其为短相关( s h o r t r a n g e d e p e n d e n c e ，简称s r d ) 排队分析法。 在短相关排队分析法中，我们通常采用泊松分布对进入队列的网络流量特性 进行拟合。这首先是由于理论上随着流数目的增多，聚合到达过程在短时间尺度 上服从泊松分布；其次经验和测量显示互联网上的流量在短时间内近c a l l 从泊松 过程；同时经典排队理论指出如果队列服务速率较快且缓存较小时，队列会频繁 溢出。此时排队系统溢出概率与缓冲器容量呈负指数关系，丢包率随缓存的增加 快速降低并趋近于0 ，这样小数量的缓存便可以满足丢包率要求。但在流量高度 统计复用的现实网络下，包的达到过程呈现较高的相关性和突发性，虽然在短时 间尺度上网络流量服从泊松分布，但是在大时间尺度上呈现长相关( l o n g r a n g e d e p e n d e n c e ，简称l r d ) 特性，因此如何将数学模型扩展到复杂的真实网络环 境需要进一步研究。 第二，以传输控制协议- t c p 协议模型为基础进行分析。当前骨干网络中， 基于t c p 的流量占到网络总流量的8 5 9 5 ，u d p 所占比例不足1 0 ，其他类型协 议所占比例更少【1 2 】，鉴于t c p 流量在网络中的主导地位，众多学者基于t c p 协议 模型探讨路由器的缓存容量需求，比较有代表性的分析结论包括：经验法则、斯 坦福模型、基于丢包率的缓存法则和极小缓存法则。由于t c p 机制本身是一种闭 环的反馈系统，因此，该类分析方法本质上是一种闭环分析方法。 首先，我们考虑一条长t c p 流，其丢包率为p ，往返时延为r 刀。根据经典 的t c p 吞吐量公式【1 3 】，平均发送速率可表示为： x ：竺( 2 - 6 )x = 芦 r r r x p 假定各队列的丢包率分别为q j ，g 疗，那么端到端丢包率p = l 一兀( 1 - - q ，) 。由 于队列的丢包概率q 取决于入队聚合速率y 、出口带宽c 和缓存大小b ，因此可 表示为q - - l 如, c ) 1 4 l ，其中尸d ，。联立以上各式，我们可以同时解出每流吞吐量 z 和丢包率p ，这被称为的不动点方法【l 5 1 ，其成立的前提在于t c p 机制总能使聚 合发送速率与链路可用带宽相匹配。下文将详细介绍和比较五种典型的基于t c p 协议模型的缓存设置法则。 9 硕士学位论文第二章缓存需求研究现状 2 3 各种缓存设置方法的比较分析 自经验法则提出至今的十多年来，路由器缓存大小设置依然遵循这一法则， 随着时间的推移和技术的突飞猛进，网络的带宽和延迟不断增大，经验法则表现 出了明显的不适应性。从0 4 年至今，已有学者对经验法则提出了质疑并提出了 改进方案。下面将对经验法则和最近提出的缓存设置法则做必要的回顾和简要的 介绍。 2 3 1 经验法则 1 9 9 4 年，c v i l l a m i z a r 等人分别对l 条、4 条和8 条t c p 流通过容量为4 0 m b s 链路进行了测试。通过改变缓存的大小，测量目标链路的利用率变化，从而提出 了著名的路由器缓存设置法则经验法则( r u l e o f t h u m b ) ，指出缓存的大小 应与带宽时延积相等( b a n d w i d t hd e l a yp r o d u c t ，b d p ) ，即b = r t t x c ，其中b 为拥塞路由器所需的缓存，r 刀( r o u n dt r i pt i m e ) 为一个t c p 连接的平均往返 时间，c 为拥塞链路的带宽。这一路由器缓存设置原则多年以来一直指导着路由 器的设计。 经验法则源自t c p 拥塞控制算法的动态特性。假设拥塞链路上存在一条长 t c p 流( 我们粗略地认为大部分时间处于慢启动阶段的t c p 流为短t c p 流，反之 则为长t c p 流) ，其窗口在稳态下呈锯齿状变化，如图2 1 所示。当丢包事件发 生时，最大拥塞窗口形躲为c t + b ，其中c 为瓶颈带宽，r 为往返时延，b 为 瓶颈链路的缓存大小。源端的拥塞控制机制对丢包事件做出反应后，此时拥塞窗 口退避为( c t + b ) 2 。这种机制要求即使在拥塞窗口最小时也要保持瓶颈链路的 充分利用，即( c 丁+ b ) 2 c t ，显然b c t 。 戤 2 图2 1 拥塞避免阶段t c p 拥塞窗口随时间的变化曲线 经验法则只适应于单流或者流数很少的网络环境，然而当前骨干链路上往往 1 0 硕上学位论文 第二章缓存需求研究现状 存在几万条流。在多流条件下，如果流与流之间完全同步，每流的丢包事件几乎 同时发生，导致了聚合窗口依旧遵循锯齿状变化，此时经验法则仍然成立；反之 当流与流异步时，一些文献【5 , 1 6 , 1 7 1 认为缓存可以大大减小。 随着传输技术的飞速发展，路由器的接口速率越来越高，对路由器处理分组 的速率要求也越高，继续遵循经验法则会给路由器的设计带来相当大的困难。目 前，商用路由器中t c p 连接的r 1 盯约为2 5 0 m s ，这就意味着当链路速率为4 0 g b s 时，需要1 0 g b i t s ( 1 2 5 g b y t e s ) 的缓存规模。实现如此大的缓存，若使用功耗为 2 5 0 m w m b i t 、容量为3 2 m b i t s 的静态随机存取存储器( s t a t i cr a n d o ma c c e s s m e m o r y ，简称s r a m ) ，那么，4 0 g b s 的线卡对s r a m 需求在3 0 0 片以上，总功耗 高达2 5 k w ；如果换用功耗为4 m w m b i t 、容量为1 g b i t 的动态随机存取存储器 ( d y n a m i cr a n d o ma c c e s sm e m o r y ，简称d r a m ) ，1 0 片就能满足要求，其功耗 为4 0 w 。这不仅增加了路由器设计的复杂度、成本和功耗，而且当拥塞发生时， 还将增大端到端的延迟。 在实际的工程设计中，路由器使用多个d r a m 并行处理来获取所需要的数 据速率，分组以自组织统计行为分散到各个存储器上【l 引。即便如此，也不能从根 本上解决问题。如果能够尽可能减少路由器的缓存规模，使路由器摆脱对d r a m 的依赖，就有可能使在核心路由器中使用较少的s r a m 或仅使用芯片内部缓存。 由于f p g a 对片内存储器的读取速率明显高于片外存储器的读取速率，若能使其 摆脱对片外存储器的依赖( 或仅使用极少的s r a m ) ，那么路由器的性能将得到 极大的提升。如何能够摆脱或尽可能的减小这种由于片外存储设备读取速率造成 的困境，已越来越受到业界的关注。2 0 0 4 年以来，一些学者陆续对经验法则提 出了改进方案。 2 3 2 斯坦福模型 2 0 0 4 年，g a p e n z e l l e r 首先在文献【3 】中对经验法则提出改进，指出当多条t c p 持续流共享一条骨干链路时，在保证出口链路带宽充分利用情况下，缓存大小仅 需满足： 曰：r t l t x c ( 2 - 7 ) 心n 斯坦福模型指出，多条独立的t c p 长流共享一条链路时，根据中心极限定理， 汇聚后的拥塞窗口的变化服从正态分布( 如图2 2 所示) ；当( 5 0 0 ) 条t c p 流通过一条链路时，同步发生的概率低于1 0 ，在实际网络中，同步发生的概率 更小，可以近似认为真实网络中同步现象不发生，因此每一次拥塞事件中，只有 小部分流量产生丢包退避。 硕上学位论文 第二章缓存需求研究现状 图2 - 2 聚合后的t c p 拥塞窗i ：1 分布 g a p e n z e l l e r 进一步指出，缓存中的队列也服从正态分布，其均值( m e a n ) 和标准偏差( s t a n d a r dd e v i a t i o n ) 与t c p 流的数量，带宽延迟乘积以及缓存大 小b 有关，标准偏差为： = 唧去等 亿8 ， 并得出链路利用率的下界表达式为： u t i l i z a t i o n e r f 3 4 3 b 2 压2 乙。c + b 石 ( 2 - 9 ) 文中还指出短期t c p 流的缓存需求只取决于链路负载和流量到达的突发性。 在短流与长流混合的网络环境下缓存大小只取决于长流，短流对缓存需求的影响 可以忽略不计。斯坦福模型主要目的是在路由器中使用尽可能少的缓存，使队列 时延尽可能减小的同时，获得1 0 0 的链路利用率。在速率为2 5 g b s 或者1 0 g b s 的典型骨干链路上，小缓存法则可将经验法则的路由器缓存需求降低2 个数量 级，而且能够使路由器具有更好的时延特性。由于1 0 0 的链路利用率是首要的 考虑因素，c u a p p e n z e l l e r 忽视了该缓存设置方案对丢包率的影响。因此，有学者 认为斯坦福模型只考虑保持高链路利用率，可能导致接入网络中路由器的丢包率 明显上升( 高达5 1 5 ) 【1 7 1 。 尽管仿真和实验都表明：当t c p 流数目巨大时，t c p 是非同步传输的。但至 目前为止，在这一结论上还未能形成一致的认识。为了理解t c p 流数目和同步化 之间的关系，r a i n a 和w i s c h i k 在文献 1 9 中对不同缓存值下的网络进行了模拟， 1 2 窖童口 硕士学位论文第二章缓存需求研究现状 认为t c p 流的同步将导致聚合窗口的周期性变化，斯坦福模型将导致网络的不稳 定性增加，吞吐量降低。与此相对的是，g a n i a l i 等人的仿真却发现，斯坦福模型 虽然对网络的稳定性产生了一定的影响，但其影响仅在一定的限度内，并不像 r a i n a 和w i s c h i k 所认为的那样显著【2 们。导致这两种不同结论的原因可能在于： r a i n a 的数学模型中丢包率指标是公平性的，而实际中，当t c p r e n o 和丢尾策略 ( d r o p t a i l ) 共同实现时，丢包将是非公平性的。 斯坦福模型中，链路上t c p 长流数目和短t c p 流数目的比例如何? 长t c p 流 数目如何确定? 这些问题至目前为止也无明确的结论。因此，关于斯坦福模型 比较慎重的结论应该是：当链路上t c p 流数目巨大时，路由器缓存需求可至少降 低至经验法则的1 1 0 ，并且能够保证网络性能不因缓存数量的减少而产生降低， 而且随着缓存的减少，网络时延和时延抖动性能也能得到提高。 2 3 3 基于丢包率的缓存法则 基于丢包率的缓存法则【8 l ：d h a r n d h e r e 和d o v r o l i s 通过对边缘网络中一条拥塞 严重的低容量瓶颈链路的研究发现“斯坦福模型法则容易使丢包率明显上升，最 高可达1 7 ，并认为路由器中应该设置更大容量( 在某些情况下甚至大于经验法 则的缓存需求) 的缓存”。m o r r i s 通过仿真发现，丢包率的上升会引起吞吐量的 下降t c p 流传输时延的增大，同时会引起带宽的分布不均匀，严重影响路由器的 性能和网络的稳定。 m o r r i s 给出了重负载条件下缓存大小对丢包率的影响。当多个t c p 流共享瓶 颈链路，丢包率，与t c p 流数的平方成正比，可表示为： ，一。邢等 倍聊 其中s 为所有t c p 流发送窗口的总和。为了避免在重负载时因每流所分配的缓 存空间过小而引起