（计算机软件与理论专业论文）tcp重传超时机制优化的研究.pdf

摘要 摘要 在如今的网络应用中，t c p ，口协议占有重要的地位，最近的研究表明8 3 9 5 的网络流量是由t c p 控制的，而其中1 3 的t c p 包需要重传。但是在网络 中重传的包有将近一半是没有必要的。造成这种现象的原因是目前绝大多数t c p 所采用的算法只适用于网络流量很小的情况。随着t c p 流的增加，直至接近到 拥塞i f 笛界点时，这个算法就变得不尽如人意，甚至加重网络拥塞状况，极大的影 响网络吞吐量和网络性能。 本文首先介绍了传统的重传超时算法的基本概念，然后通过多个试验对传统 算法进行了分析并指出它的一些局限性。由于其算法本身的缺陷造成了不精确， 很容易造成预测的重传超时值( r t o ) 偏大或偏小。如果r t o 偏大，可能包很 早就已经丢失了，可是却要等到重传计时器超时才能被判断为超时，这样就造成 了系统性能的下降；如果r t o 值偏小，可能包还没有传送到目的端，发送端得 重传计时器已经超时了，而产生了不必要的重传，这样对网络性能的影响也是很 大的。我们针对这些局限性，提出一个新的算法f a r t o 算法，它能提高 t c p 的性能，特别是在传统算法不能很好工作的环境下，由于这个算法中重传超 时值的计算是根据网络的流量而实时调整的，所以能提供比j a c o b s o n 算法更为 准确的重传值。 本文最后在实验室环境下通过一系列的仿真实验对f a r t o 算法和传统的 j a c o b s o n 算法进行对比分析，通过对几个重要性能因素的分析，发现f a r t o 算 法能更好的反映网络中的流量变化情况，特别是在网络流量大甚至产生拥塞的情 况下，效果更好。因此本文中提出的算法能够在一定程度上减少不必要的重传和 空闲的等待时问，进而提高系统的性能和吞吐量。 关键词t c p ；r t o ；r t t ；重传超时 a b s t r a c t r e s e a r c hs h o w st h a t8 3 9 5 o fi pt r a m ea t t r i b u t e st ot c pf l o w s 1 3 o f t c p p a c k e t sa r er e t r a n s m i t t e da n dh a l fo ft h et c pr e t r a n s m i s s i o n sa l eu n n e c e s s a r i l y w e n o t i c e dt h r o u 曲a n a l y s i sa n de x p e r i m e n t st h a tt r a d i t i o n a lc o n t r o la l g o r i t h m su s e di n t h et c p p r o t o e n lw o r ke r i e e t i v e l yi na ne l l v i r o n m e n tw h e r et h en u m b e ro f t c pf l o w s i ss m a l i w ea l s on o t i c e d , h o w e v e r , t h a tw h e nt h en u m b e ro ft c pf l o w si l l e l e a s 9 8 a p p r o a c h i n gt h ep o i n to fc o n g e s t i o n ，t h e s ec o n t r o la l g o r i t h m sf 砌t ow o r kw e l l ， n e g a t i v e l yi m p a c t i n gn e t w o r kt h r o u g h p u ta n dt h u sn e t w o r kp e r f o r m a n c e u n n e c e s s a r y t c pr e t r a n s m i s s i o n sw o u l dm a k en e t w o r kc o n g e s t i o ne v e nw o r s e i i lt h ed i s c u s s i o n w ef i r s tr e v i e wt h et r a d i t i o n a lt c pr e t r a n s m i s s i o nt i n l e o u t a l g o r i t h ma n dp o i n to u ts o m es h o r t c o m i n g sa s s o e i a t e dw i t hi tt h r o u g hs o m e e x p e r i m e h t s b e c a u s eo ft h i s i tw i l lc a u s et h er t o v a l u eb i go rs m a l l i f t h er t ot o o b i gt ot h et r u ev a l u e ，t h ep a c k e tm a yb el o s se a r l y , b u tt h et c pm u s tw a i tf o rt h e r e t r a n s m i s s i o nt i m e rt i m e o u t t h a tw i l lw o r kt h ep e r f o r m a n c eo f t h es y s t e md o w n a n d i ft h er t 0t o os m a l lt ot h et r u eo n e ，m a y b et h ep a c k e tc a l ln o ta r r i v ea tt h ea i mp o r t t h er e t r a u s m i s s i o nt i m e ro ft h es e n d i n g ni st i m e o u t , 8 0i tw i l lc a u s eu n n e c e s s a r y r e t r a n s m i s s i o n , t h i sw i l la l s om a k et h ep e r f o r m a n c es y s t e r nd o w n w ea i ma t t h i s l i m i t a t i o nt op u tf o r w a r dan g va l g o r i t h m - - 一f a r t o t i l i so n ec a ni m p r o v et h e p e r f o r m a n c eo ft h es y s t e m ，e s p e c i a l l yw h e nt h et r a d i t i o n a lo n ec a l ln o tw o r kw e l l ， b e c a u s et h er e t r a n s m i s s i o nv a l u ec a l c u l a t e db vt h i sa l g o r i t h mc a na d j u s tb yf l u xi nt h e n e t w o r k , s ot h en e wo n ec a np r o v i d et h ev a l u em o r ee x a c tt h a l lt h et r a d i t i o n a io n e a tl a s t w eh a v ed o n es o m ee x t e n s i v ee x p e r i m e n t sw i t l lt h e a l g o r i t h m w e p r o p o s e da n dc o m p a r e di tw i t ht h et r a d i t i o n a la l g o r i t h m o u re x p e r i m e n t ss h o wt h a t o u ra l g o r i t h mc a na d j u s tt h et c pr e t r a n s m i s s i o nt i m o o u tv a l u ei nr e s p o n s et ot h e a m o u n to fn e t w o r kt r a f f i c i np a r t i c u l a r , o u ra l g o r i t h mw o r k sm u c hb e t t e rt h a n 山e t r a d i t i o n a la l g o r i t h mw h e nn e t w o r kt r a f f i ci sh e a v yo re v e na p p r o a c h i n gc o n g e s t i o n ，i t a l s ow o r k sw e l lw h e nn e t w o r kt r a f f i ci sl i g h t c o n s e q u e n t l y , o u ra l g o r i t h mc a n o v e r c o m et h es h o r t c o m i n g so f t c pt i m c o u te a r l yt os o m ee x t e n ta n dt h u sc a l li m p r o v e t c p p e r f o r m a n c ea sw e l la sl i n ku t i l i z a t i o n i j 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 魏滥鲜隰章，t 日 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：趁婢导师签名：匝d 虹日期：掣曰 第1 章绪论 第1 章绪论 1 1t c p 重传超时算法研究的意义 1 1 1 互联网现状 因特网最初源于美国国防部的a 肚a n e t ，其最大特点是采用无连接的端到 端的包交换服务。在过去的十年中，因特网逐步发展成为互联全球的网络，它使 得用户在世界范围内进行通信成为可能。随着因特网的迅猛发展，它给人类社会 带来了巨大的变革。但就在因特网深刻影响人类历史发展进程的同时，因特网自 身的发展却面临着种种困难，其中之一就是网络拥塞i i j 。从因特网诞生起网络拥 塞就与其如影随形。虽然因特网的相关技术日渐成熟，但网络拥塞却仍没有很好 的解决方法，反而随着因特网的规模、用户和应用的急剧增加，网络拥塞问题日 益突出。造成网络拥塞现象的原因除了硬件方面的问题，其实很多都是可以通过 优化软件部分来获得一定程度上的缓解，其中最重要的就是对t c p 重传超时算 法的优化。 据统计因特网上9 5 的数据流使用的是t c p i p 协议【2 l ，并通过传输层协议 保障通信双方数据传输的可靠性，t c p p 传输层最主要的协议是t c p 和u d p 。 t c p 是一种通过累计确认来判断报文传输成功与否，并以此为依据调整发送行为 ( 调节发送速率或进行重传) ，保障通信数据完整性的协议。t c p 为通信双方提 供可靠的数据连接，t c p 协议包括端到端的流量控制和错误检测机制，使它能够 自动适应网上的各种变化，保证了传输的有效性、可靠性和稳定性。u d p 则是 一种简单的，不进行接收确认和流量控制的协议。这两种传输协议具有不同的特 性，在网络中承载不同的业务，前者多用于数据的可靠传输，后者则主要应用子 实时业务的承载。 一 t c p i p 传输层协议虽然可以简单高效地完成通信数据的传输，但由于端到 端控制策略自身的局限性以及m 层路由的不确定性，无论t c p 协议还是u d p 协议，都会给网络带来难以预期的拥塞。最近的研究表明因特网中8 3 9 5 的数据量是由t c p 控制的1 3 】，而其中1 3 的t c p 包需要重传【4 】。但是在网络中 重传的包中有几乎一半是没有必要的。正是由于存在的问题很大一部分是由t c p 协议自身的缺陷引起的。因此在传输层上，基于现有的t c p 协议，人们进行了 多种改进，用来缓解网络拥塞，提高网络性能。 1 1 2t c p 重传超时算法研究与改善的必要性 最近的研究表明8 3 9 5 的i p 流量是由t c p 控制的f 3 】，而1 3 的t c p 包需要进行重传 4 1 。由此可见网络中存在的数据包丢失现象是普遍存在的，而且 _ - i 北荥工业大学工学碗上学位论文 它的存在极大地影响了某些网络应用的正常运行，因此是不容忽视的。各种论文 在提及包丢失时，都将其定义为由源地址发往目的地址的数据包，但是目的地址 并未接收到，丢包率的定义是：丢失的i p 包与所有的i p 包的比值【5 1 。所谓丢失 其实就是指在一定的时间范围内，发送的数据包没有到达目的地址的行为。判断 包是否丢失有两种方法m 】： l 、收到重复的应答包 2 、t c p 重传超时( r t o ) r t o 是指发送端将一个报文段发送出去到发送端认为该报文段已经丢失而 重传该报文段的时间间隔。它是重传计时器状态( r e x m t ) 的初始值( 在发生 报文段超时前一直由r e x m t 维持时间值) ，也是r t t 的上限值推测。 虽然有两种判断超时的方法，但是出于对安全的考虑绝大多数的超时还是由 r t o 触发的，这个值是由t c p 的重传计时器来规定的。发送端发出报文段后， 在规定的时间内没有能够收到接收端返回的a c k 信令，从而使得发送端认为该 报文段丢失，并触发其拥塞控制策略。在这里主要涉及到t c p 的重传计时器 ( r e t r a n s m i s s i o n1 协e r ) ，它是t c p 协议中最重要的计时器。当报文段发出后， 重传计时器启动并开始计时，如果发送端在计时器超时前得到a c k 信令，则重 传计时器停止计时。 对于这种机制来说对初始r t o 值的选择是至关重要的。 l 、如果这个初始值太大，对于拥有小延迟的数据流是存在问题的，问题表 现在可能包很早就已经丢失了，可是却要等到重传计时器超时才能被判 断为超时，这样就造成了系统性能的下降： 2 、如果r t o 初始值太小，t c p 容易过早超时，致使t c p 启动拥塞控制机 制，而且还可能导致不必要的重传，增加了不必要的网络流量，也能导 致系统性能的下降用。 但是传统的计算方法由于其自身的缺陷造成了不精确，很容易造成预测的 r t o 值偏大或偏小。这样对网络性能的影响是非常巨大的。 再者，传统的算法在计算r t o 时，没有考虑网络中流量的变化对r t o 的影 响。因此在实际应用中是非常不准确的。我们每个人都会这样的经历：发出去的 信息，别人收不到或者很久以后才收到；发一封邮件，如果附件稍微大一点，别 人也收不到。这种延时和丢失对每个人的生活都会带来或多或少的影响。以前一 旦发生这种情况，人们就认为是带宽不够等硬件问题，当然硬件问题是存在的， 但是网络中的其他非硬件问题也是不容忽视的。这就给我们以启事，怎样才能把 非硬件问题带来的影响降到最低。这个问题的出现和闩益迫切也就给我改进优化 这个算法提供了一个好的机遇。t c p 超时与重传中最重要的部分就是对一个给定 连接的往返时白j ( r ，丌) 的测量。由于路由器和网络流量均会变化，因此这个 r 1 广r 时间经常会发生变化，t c p 应该跟踪这些变化并相应地改变其超时时间。 第1 章绪论 如果设计出一个能够适应流量变化而变化的算法将极大的提高网络的吞吐量，进 而提高整个网络的性能，对网络的健康发现是非常有裨益的。 1 2 重传超时的基本概念 1 2 1 重传和超时的基本概念 t c - p 采用肯定确认a c k 和重传来保证数据的可靠传输。正常情况下，接收 方为正确接收的数据向发送方返回确认( a c k ) ；发送方发出报文段的同时，将 其副本放入重传队列，并启动超时重传定时器。如果定时器超时还没有收到该报 文段的确认，发送方就认为此报文段已经丢失，并从重传队列中取出相应的报文 段进行重传。 1 2 2 超时产生的原因 超时产生的原因除了线路问题以外，绝大部分都是由于网络拥塞引起的。” 特别是在如今网络设备的升级的情况下，线路问题已经基本可以忽略了。下面我 们从需求和供给的角度来分析这个问题。发送方要发送数据必定要占用一定的带 宽，这就是需求，而带宽的大小是有限度的，这就是供给。在网络中，所有发送 方所要求占用的带宽之和决定了当前的总需求。当资源的需求超过供给的时候， 也就是当网络中流量增加的时候，由于有限的供给，有些数据包就会丢失【扪。这 时候发送方就会通过计时器的超时来反映数据包的丢失情况，之后就该是重传超 时算法起作用了。 1 2 3t c p 重传超时需要解决的主要问题 t c p 的重传超时算法中最关键的就是超时时间值( r 1 o ) 的确定。一方面重 传计时器r t o 设置得过小，t c p 容易过早超时，致使t c p 启动拥塞控制机制， 降低吞吐量；另一方面r t o 设置过大，报文段丢失时又会造成长时间的空闲等 待，这同样降低了吞吐量。 重传超时值要能随流量的变化而做出相应的调整，同时要满足在流量大的情 况下，甚至是拥塞发生的时候，能够较好的反映网络情况，减轻网络负担，缓解 拥塞状况；而在流量小的情况也应有很好的表现。具体的表现就是减少了t c p 重传计时器的空闲等待时间和不必要的重传。 1 3 国内外研究现状 1 3 1 国外研究现状 l z h a n g 讨论了标准t c pr t o 存在的一系列缺陷，包括在测试重传数据包 北京工业大学工学颀上学位论文 所经历的往返时间( r 1 r r ) 时的不精确；指出在一个r t t 内只重传一个丢失包 的策略过于保守；选择一个初始值时显得很困难；在拥塞发生时不能及时根据快 速增加的r 1 丁而改变r t o 值1 9 1 。k a r n 和p a r t r i d g e 通过使i 盯r 的测量更加准确 解决了l z h a n g 提出的第一个问题l io 】。j a c o b s o n 通过算法更迸一步精确了r t o 值，定义： r t 0 = s r t t + k x r r r 、，a r 这里s r t t 是r t t 的平滑估计器，r t t v a r 是平滑的r t t 偏差的估计器， 在最开始时设置k = 2 1 1 1 1 ，但是后来j a c o b s o n 通过大量的实验发现k = 2 不够准确， 而将k 设置为4 【1 2 】比较合适。 在目前的标准f 1 3 】中，r t o 的实施如下： l 、当没测i 盯t 、s r t t 时，应将r t o 设置为3 秒； 2 、当测到第一个r t t 的值为r 时，发送端设置s r t t r ，r ：i t v a r r 2 ， r t 0 r t o s r t t + m a x ( 4 r 下r 、，a r ， 2 x t i c k e t s ) ； 3 、当测到2 个及其以上，发送端必须设置： d e u a = r t t s r t t s r t t = s r t r + 1 8d e i j r a r t t v a r = r t t v a r + 1 4 ( i d e l t a i r i t v a r ) r t o = m a x ( s r t t + 4 x p , t i v a p , , 2 t i c k e t s ) 4 、如果r t o 小于1 秒，应将r t o 补充到1 秒：r t o 最大值至多为6 0 秒 但是这个算法也存在很多缺陷，所以国内外很多人针对这些缺陷提出了很多 算法，m h a e r i 1 4 】提出使用系统鉴定( s y s t e mi d e n t i f i c a t i o n ) 的机制计算r t o ， t c p 使用一个简单的递归系统鉴定算法来捕获时间变量( t i m ev a r i a n t ) 和时间常 量( t i m ei n v a r i a n t ) ，提供一个动态的r t t 预测。文章傲了3 个假设： l 、所有的包丢失都是由t i m e o u t 触发的 2 、所有的包都分别被确认 3 、所有的包都具有相同的大小 递归系统鉴定算法是用来处理网络的时间变化行为的。一个简单的基于r t t 的系统鉴定比较合适用来预测r t o 。用一个新的闭环模型来模拟现实网络，通 过这个方法可以有效的提高r t t 预测质量，减少了3 3 7 的不必要重传，减少 了2 5 的重传空闲等待时间。但是该方法由于前面的3 个假设而过于理想化， 结果不太精确。 l m a 等人于2 0 0 4 年提出使用基于递归权重中值过滤器( r e c u r s i v ew e i g h t e d m e d i a n ( r w m ) f i l t e r s ) 的重传超时算法【1 5 】，目前t c p 采用的j a c o b s o n 算法是基于 递归线性过滤( r e c u r s i v el i n e a rf i l t e r i n g ) 的，当线性过滤器应用于高斯信号环境时， 由往返时间( r t t ) 信号过滤得到的r t o 值通常过于激进。这个基于r w m 过 滤器的算法改善了t c p 的性能，仿真结果显示这个方法使r t o 值随m 的变化 第1 章绪论 而很快的作出相应的改变。 l m a 等人又于2 0 0 6 年提出一个基于统计分析( s t a t i s t i c a la n a l y s i s ) 的重传 超时算法。在文章中作者为基于实验结果的r 1 _ r 过程构造了一个自动回归模型 ( a u t o r e g r e s s i v e ) ，显示r t t 在网络中的变化是沿一条确定的路径，这种变化是 可以通过一个移位g a m m a 分布( s h i f t e d g a m m a d i s t r i b u t i o n ) 来模拟的。这个模 型用来确定重传超时算法中的平均反应时间和超时概率【1 6 】。 1 3 2 国内研究现状 国内的王敏杰提出了无线网络下t c p 重传超时的算法，因为无线网络中的 误码率比较高，用有线网络中的t c p 重传超时算法就存在很多问题，她基于实 验将标准算法中的固定系数改为一组自适应系数来提高无线网络的吞吐量【1 - q 。 章淼针对x i n u 操作系统中t c p 重传计时器管理和往返时间r t t 的测量两 方面问题进行了分析，并提出了改进的方案。x i l l u 的初衷是希望重传计时器同 时肩负两个作用：如果收到应答报文前重传计时器超时，则触发数据报文的重传 事件；如果收到应答时重传计时器未超时，则返回r t t 的测量值。事实证明， 重传计时器无法同时完成这两个任务。原来的做法只是简单的将设置重传计时器 与应答报文出现之间的时间间隔作为r t t 的测量值，而许多被应答的报文并不 是在设置重传计时器时发送出去的，这样就造成了r t t 测量上相当大的偏差。 为了解决这个问题，章淼提出使用一个单独的计时器来测量r 1 _ r ，并且使用了一 个标志变量来表示现在是否处于“测量状态”u ”。 ” ，o 1 4 论文结构说明 本论文主要是以t c p 重传计时器的重传超时算法为研究对象，展开广泛而 深入的探讨研究与大量的实现仿真工作。它首先是对目前广泛使用的j a e o b s o n 算法的原理机制和运行性能进行了简要介绍和分析，然后在此基础上引入了一种 新的重传超时算法戳r t o 我们将从理论构思，算法实现以及仿真实验几个 环节对其作深入探讨和研究。 全文的内容组织如下： 第一章概述了互联网的发展现状以及t c p 重传超时算法研究与改善的必要 性，对随后几章的分析研究起引导作用。 第二章主要介绍了t c p 的原理和t c p 采用的一些跟本文有关的算法介绍， 包括滑动窗口协议，t c p 的定时器管理以及t c p 中主流的拥塞控制算法的介绍。 第三章主要介绍了网络性能测试相关的知识，包括网络性能的概念、结构模 型、测试方法以及性能指标的测量与分析，对理解后面几章很有帮助。 第四章主要分析了t c p 重传超时算法的历史，并通过对j a c o b s o n 算法进行 北京工业大学工学五贞士学位论文 仿真来进一步评估。 第五章和第六章是本文的重点，第五章通过对传统算法在流量很大的网络环 境下所存在的问题，我们引出了基于流量的f a r t o 算法，并对f a r t o 算法进 行了理论分析。 第六章利用实验室环境对f a r t o 算法和目前普遍采用传统的j a o o b s o n 算法 进行了一系列的仿真对比实验，利用仿真结果验证f a r t o 算法的性能和测试改 进方案。 最后是全文的总结。 第2 章t c p 的原理和实现机制 第2 章t c p 的原理和实现机制 2 1t c p 协议简介 t c p ( t r a n s m i s s i o n c o n t r o lp r o t o c o l ，传输控制协议) 是专门为了在不可靠的 互联网络上提供一个可靠的端到端字节流而设计的。互联网络与单个网络不同， 因为互联网络的不同部分可能有截然不同的拓扑、带宽、延迟、分组大小和其他 的参数。t c p 的设计目标是能够动态地适应互联网络的这些特性，而且当面对多 种失败的时候仍然足够健壮【1 9 1 。 t c p 的原始正式定义位于r f c 7 9 3 中。t c p 是因特网中的传输层协议，位于 o s i 参考模型网络层协议口之上( 如图2 1 所示) 。 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 ：国：国 数据链路i 一- 数据链路k 一| 物理层 一 物理层i 图2 - 1o s i 参考模型 f i g u r e2 - 1o s ir e f e r e n c em o d e l 传输控制协议具有以下特征： 1 、t c p 向应用层提供可靠的服务，即t c p 保证高层应用的数据有序、无误 地送到目的地。 2 、t c p 提供全双工，面向流地通信，即信息可以同时在两个通信节点问双 向传送。 3 、t c p 是面向连接地，也就说一次通信设计三个步骤：建立连接，数据传 输和拆除连接。 4 、t c p 具有流量控制机制，即接收方能够限制发送方在给定时间内所能发 送的数据量。 5 、t c p 具有拥塞控制机制，即发送方可根据网络的拥塞状况自适应调整发 送的速率【2 0 】。 注意，因为对拥塞控制和流量控制容易造成混淆，这里加以澄清。流量控制 北京工业大学工掌硕士学位论文 是用来防止发送方超限额使用接收方的容量。拥塞控制是用来防止过多的数据送 往网络，造成交换和链路的负担过重。所以，流量控制是处理端到端的问题，而 拥塞控制是处理主机和网络交互的问题。 t c p 内部协调工作，以达到向应用层提供可靠服务的目的。t c p 使用的算 法和一些实现机制在下面各节中详细介绍。 2 2 滑动窗口协议 首先讲一下滑动窗口算法工作过程。首先，发送方为每一帧指定一个序列号。 暂时，我们忽略序列号是用报头中有限长度域表示的这一事实，假设序列号可无 限大。发送方保持三个变量：发送窗口大d , ( s w s ) 、最后接收到的应答序列号( l a r ) 和最后发送的帧的序列号( l f s ) 【2 l 】。s w s 给出了发送方可以发送的未应答帧的最 大数目。发送方应保持下面的不等式始终成立： l f s l a r s w s 当应答到来时，发送方将l 幔向右移，这样，发送方就可以发送另一帧。 发送方每发送一帧，就启动一个相应的计时器，如果计时器超时而相应帧的应答 还没有返回，就重传这个帧。发送方的三个变量之间的关系如图2 - 2 所示： s w s 图2 - 2 发送方的滑动窗口 f i g u r e2 - 2t h eg l i d cw i n d o wo f t h es e a d i a gp o r t 接收方也保持三个变量：接收窗口大小( r ) 、最大可接收帧序列号( u 心) 和最后接收到帧序列号( l f r ) 。r w s 给出了接收方可以接收的非按顺序到达的 帧的序列号的最大值。接收方应该保持下面的不等式始终成立： l a f i j r r w s 当一个序列号为s e x l n u m 的帧到来时，接收方采取如下动作：如果s e q n u m 一 l a f ，那么该帧在接收窗口的范围之外，将被丢弃。如果l f r s w s 是没有意义的，因为不可能有多于s w s 的帧会发生乱序。 2 2 1t c p 采用的滑动窗 t c p 采用了滑动窗口的算法，并对之进行了演变，来实现以下3 个目的： 1 、确保数据的可靠传送。 一 2 、确保数据的有序传送。 3 、在发送和接收方之间引入流量控制机制。 这三项功能中的前两项，与前面介绍的滑动窗口相同，t c p 与前面的算法不 同之处是引入了流量控制功能。特别是，发送方使用的滑动窗口大小不再是固定 的了，而是根据接收方通告的滑动窗口大小来调整。这通过t c p 报头中的 a d v e r t i s e d w m d o w 域来实现。这样，就限制发送方在给定时间内，发送的还未 接受到应答的包的数目不能超过a d v e r t i s e d w i n d o w 所规定的值。接收方根据分 配给连接的用于缓存数据的内存空间的大小，为a d v e r t i s e d w i n d o w 选择一个合 适的值。这样做的目的是防止发送方超限额使用接收方的缓存空自j 【2 2 j 。 北京工业大学工学硕士学位论文 2 2 2t c p 中的流量控制 t c p 的发送缓冲器和接收缓冲器之间的关系如图2 4 所示： f l a s t b y t e v v i 黪黝辨“p 湖 l陵繇瓣g 瓣簿l 硝潮 l 甏陵辫l 燃燃溺黼 l a s t b y t e a c k e d l a s t b y t e s e n t n e x t b y t e e x p e c t e dl a s t b y t e r c v d 图2 4t c p 发送缓冲( a ) 和接收缓冲( b ) 之间的关系 f i g u r e2 - 4t h er e l a t i o n s h i pb e t w - nt c ps d m gb u f f e r ( a ) a n dr e c e i v i n gb u f f e r ( b ) 首先看发送方，在发送缓冲中，保持有三个指针，l a s t b y t e a e k ，l a s t b y t e s e n t 和l a s t b y t e w r i t t e n ，每个都有明确的含义。很显然有： l a s t b y t e a c k e d l a s t b y t e s e n t 因为接收方不可能对未接收到的字节做出应答，还有： l a s t b y t e s e n t l a s t b y t e w d t t e n 因为t c p 不可能发送一个应用进程还未写到缓冲的字节。 在接收方，保持有相似的一组指针，分别是l a s t b y t e r e a d 、n e x t b y t e e x p e c t e d 和l a s t b y t e r e v d ，它们之间有如下的关系： l a s t b y t e r e a d m a x s e n d b u f f e r 则t c p 阻塞发送进程并禁止其产生更多的数据。 2 3t c p 计时器管理 ，“。在t c p 使用了多个计时器来完成它的工作。其中最重要的是重传定时器 ( 蕾e t r a n s m i s s i o n t i m e r ) 。当t c p 实体发送一个数据段的时候，它同时也启动一个 重传定时器。如果在定时器过期之前该数据段被确认的话，则定时器被停止。另 一方面，如果在确认到来之前定时器先到期，则数据段被重传幽】。可是问题是这 个超时间隔应该设置为多少。 这个问题在i n t e m e t 的传输层上比一般数据链路层协议中更加困难。在数据 链路层协议中，期望的延迟是高度可预测的，所以，定时器可以被设置到期望的 确认到达时间之后再稍微过一点即可。由于在数据链路层中确认极少被延迟，因 为不存在拥塞，所以，如果在预期的时间点上确认没有到来，则往往意味着原始 帧或者确认帧已经丢失了。 t c p 面临截然不同的环境。要想确定到达目标端的往返时间是非常复杂的， 即使知道了这一段时间，要确认超时间隔也是非常困难的。如果超时间隔被设置 得太短，则会发生大量不必要的重传，从而许多无用分组反而堵塞i n t e m e t 。如 果超时间隔被设置得太长，则一旦分组丢失之后，由于太长的重传延迟，所以性 能会受到影响。而且，确认到达时间分布的均值和方差也会随着拥塞的发生或者 解决而在几秒钟时间内迅速地改变。 解决方案是使用一个高度动态的算法，它根据网络性能的连续测量情况，不 断地调整超时间隔。t c p 通常采用的算法是j a c o b s o n ( 1 9 8 8 ) 算法，其工作原理 如下所述。对于每一个连接，t c p 维护一个变量r t t ，它代表了到达连接目标 端她往返时间的当前最佳估计值。当一个数据段被发送出去的时候，t c p 启动一 北京工业大学工学硕j 二学位论文 个定时器，该定时器有两个作用，一是看需要多长时问该数据段被确认；二是若 时间太长的话，则触发重传动作。如果在定时器过期之前确认数据段回来的话， 则t c p 测量一下这次确认所花的时间，然后根据算法更新r t t ，并求得重传超 时值( r t o ) ：关于重传超时算法将在第四章具体讲述。 2 4 t c p 拥塞控制 2 4 1 拥塞的基本概念 当一个子网或者子网的一部分中出现太多分组的时候，网络的性能就开始下 降。这种情况称为拥塞( c o n g e s t i o n ) 1 2 4 】。下图描述了这种现象。当主机传送到 子网中的分组数量在子网的容量范围内的时候所有这些分组都可以被递交到目 的端。但是，随着流量的快速递增，路由器不可能处理所有的分组，于是网络中 开始丢失分组。而且这将会使事情更加糟糕。在流量很高的时候，性能将严重恶 化，几乎没有分组能够被递交( 如图2 5 所示) ”9 1 。 递 交 的 分 组 图2 - 5 拥塞发生时的网络性能 f i g u r e2 - 5t h ep e 椭o r m a n c eu n d e rt h ec o n g e s t i o n 2 4 2 拥塞产生的原因 引起拥塞现象的因素有很多。如果突然之间在三条或者四条输入线路上开始 有分组流到达，而且这些分组流都需要同样的输出线路，也就是说这些分组要共 享带宽有限的线路，那么，路由器将建立一个排队队列。如果路由器没有足够的 内存来存放所有这些分组，那么有的分组就会丢失。多增加一些内存可能有助于 将路由器的性能提升到一定的点上，但是，n a g l e ( 1 9 8 7 ) 发现，如果路由器有 无限数量的内存，那么，拥塞现象会变得更差，而不是更好，因为当分组到达队 列前端的时候，这些分组已经超时了，重复分组也已经被发送出来了【i 】。所有这 些分组都将被尽职地转发给下一台路由器，从而增加了到达目标及整条路径的负 载。 第2 章t c p 的原理和实现机制 慢速的处理器也可能引起拥塞。如果路由器的c p u 非常慢，以至于难以完 成必要的维护工作( 如缓冲区排队、更新路由表等等) ，那么，即使有多余的线 路容量，分组也需要进入到队列之中。仅仅对线路进行升级而不改变处理器，或 者反过来，通常不会有很明显的效果，这样的做法往往只是转移了瓶颈而己。 2 4 3 慢启动 当源在接近网络提供的带宽容量操作时，使用适当增加算法是很合适的。但 是，当源在从容量很小的情况下到达提供的容量时，使用该算法将需要一个较长 的时间。为此，t c p 提供了另外的一种算法，称为“慢启动”算法，该算法用于 在冷启动时快速增加拥塞窗的大小。冷启动以指数增长方式来有效增加拥塞窗大 小，而不是以线性增长方式。 实际上，有两种不同的情况，需要运行慢启动。第一种是在一个连接开始建 立的时候，这时，源并不知道在给定的时间内，它应发送多少个包。在这种情况 下，慢启动连续在每个i m 中加倍拥塞窗口，直到出现包丢失。这时，超时将触 发快速降低算法，使拥塞窗口的大小降为原来的一半。 第二种情况是，当等待超时发生使连接进入死状态时。先回忆一下，t c p 滑 动窗口是如何工作的。当包丢失时，源最终达到这样一点，它已经发送了通告窗 口所允许的最多包，所以在等待应答时处于阻塞状态，而该应答由于某种原因可 能是不会到达的。最终，超时发生了。这时，没有包在发送中，意味着源将不会 接收到应答，也就不会同步新的包的发送。源将接收到一个应答来重新打开整个 通告窗口，但正象前面解释的那样，源将使用慢启动来重新启动数据流，而不是 将整个窗口的数据都一次性的放到网络上去嗍 2 4 4 快速重传和快速恢复 快速重传机制有时可以较常规超时机制更早地重传丢掉的数据包。快速重传 机制不是取代常规的超时机制，而是对其作用的加强。 快速重传的想法很简单。每次一个数据包到达接收方，接收方都产生一个应 答，即使这个序列号已经应答过了。这样，当一个包没能按顺序到达时，也就是 说，t c p 不能对该包的数据做出应答，因为前面的数据还没有到来时，t c p 重送 它上次发送的应答。对相同应答的第二次发送称为“同一应答”。当发送方看到 同一应答时，就知道接收方一定接收到一个没有按顺序到达的包，这也暗示前面 的包有可能已经丢失了。因为前面的包也可能只是被延迟了，而不是丢失了，所 以发送方还要等待，直到又见到若干个同一应答。这时，发送方就认为该包已经 丢失，并重传该包。在实际中，t c p 一般见到三个相同应答，才重传数据包。 最后，快速重传还带来一个好处。当快速重传机制检测到拥塞发生时，不是 北京工业大学工学硕士学位论文 减小拥塞窗口到一个包再进行慢启动，而是仍有可能利用应答来同步包的发送。 这种机制称为快速恢复。快速恢复有效地改善了介于快速重传检测到包丢失和适 当增加开始之间的慢启动阶段。例如，快速恢复可以避免慢启动阶段，而只是将 拥塞窗口的大小减半并启动适当增加。换句话说，慢启动仅仅用在连接的开始和 超时发生时。在其他时间，拥塞窗口遵循纯粹的适当增加快速降低模式【冽。 需要指出，当拥塞发生时，t c p 才会采取相应的处理措施，而不是t c p 能够 预先避免拥塞的发生。所以我们称这种策略为拥塞控制，而不是拥塞避免。但是， 在t c p 窗口的发展过程中，有拥塞避免阶段。在慢启动阶段后，就进入了拥塞避 免阶段。 2 5t c p 拥塞控制算法介绍 2 5 1 几种常用的拥塞控制算法 t c p 协议经过多年的发展，有了多种具体的实现。其中包括t a h o et c p ，r e n o t c p ，n e w r e n ot c p ，s a c kt c p 和v e g a st c p 。运行在主机中的这些实现使得 t c p 连接在网络发生拥塞时回退，并对网络中的拥塞信号进行响应，正是这些改 进的t c p 实现的拥塞避免和拥塞控制的算法防止了今天网络的拥塞崩溃。下面详 细介绍这些t c p 实现以及运用于这些实现中的拥塞避免和拥塞控制算法。 l 、t a h o e t c p t a h o et c p 的主要内容包括：引入了指数阶回退( e x p o n e n t i a lb a c k o f 0 的传输 超时时长估计方法；规范了慢启动( s l o ws t a r t ) 和拥塞避免( c o n g e s t i o na v o i d a n c e ) 算法；提出了快速重传( f a s t r e t r a n s m i s s i o n ) 机制以有效地检测报文丢失并合理 地调整拥塞窗f 3 1 2 v 。 2 、r e n o t c p 由于后面的实验部分采用的就是r e n ot c p 拥塞控制算法，因此，在这里对 r e n ot c p 进行详细的讲述。由于t a l l o e t c p 算法在重传丢失报文后要将拥塞窗口 重新设置为初始窗口大小，这样，t c p 发送端需要若干轮次才能恢复到报文丢失 前的发送速率。这种特性造成网络发生拥塞后多个t c p 之间出现“呼吸”效应， 而这一过程中网络资源无法被充分利用。为了提高拥塞发生后t c p 算法的吞吐 量，j a c o b s o n 等人在t a h o et c p 算法的基础上加入了快速恢复( f a s tr e c o v e r y ) 形成 t r e n ot c p 算法【2 8 】。快速恢复