（计算机软件与理论专业论文）对nagle算法的进一步研究.pdf

对n a g l e 算法的进一步研究 第3 页共5 1 页 摘要 当前的t c p 实现都包含了所谓的n a g l e 算法，该算法可以避免大量小数据包的不必 要的传送。该算法被证明在防止i n t e m e t 因过量的包传输而导致带宽耗尽方面确实 很有用。然而，许多应用程序的性能却因为基于采用了传统的n a g l e 算法实现的t c p 而恶化了。原因是n a g l e 算法和t c p 的延迟确认策略间的交互会因一段暂时性的“死 锁”而使应用程序产生严重的性能下降。许多联网应用程序实现者因为n a g l e 算法 的这一缺陷而在t c p 中禁用了该算法，甚至当这样做并无必要也不明智时也禁用了 该算法。 我们将应用分成应该禁用和不应该禁用n a g l e 算法两类，而且对那些通常应该禁用 n a g l e 算法的应用，通过采用改进的n a g l e 算法实现，也能达到相同的性能。我们 阐述了五种可行改进，还有一种新方法，同时在基准测试的基础上对这几种方法的 性能进行了分析。我们还对接收方的延迟确认策略作了修改以期在某些条件下能够 对整个性能的提高有所帮助。 关键字：d l d e t 算法，n a g l e 算法，拥塞控制，延迟确认，t c p 。7 、j t 、f l 翌竺竺兰苎兰竺苎二生! 窒 要! 里苎! ! 墨 a b s t r a c t m o d e mt c pi m p l e m e n t a t i o n si n c l u d eam e c h a n i s m ，k n o w na st h en a g l ea l g o r i t h m ， w h i c hp r e v e n t st h eu n n e c e s s a r yt r a n s m i s s i o no fal a r g en u m b e ro fs m a l lp a c k e t s t h i s a l g o r i t h mh a sp r o v e du s e f u li np r o t e c t i n gt h ei n t e r a c ta g a i n s te x c e s s i v ep a c k e t l o a d s h o w e v e r ，m a n ya p p l i c a t i o n ss u f f e rp e r f o r m a n c ep r o b l e m sa sar e s u l to f t h et r a d i t i o n a l i m p l e m e n t a t i o no f t h en a g l ea l g o r i t h m a ni n t e r a c t i o nb e t w e e nt h en a g l ea l g o r i t h ma n d t c p sd e l a y e da c k n o w l e d g m e n tp o l i c yc a nc r e a t ea ne s p e c i a l l ys e v e r ep r o b l e m ，t h r o u g ha t e m p o r a r y “d e a d l o c k t h e s e f l a w si nt h e n a g l ea l g o r i t h m h a v e p r o m p t e dm a n y a p p l i c a t i o ni m p l e m e n t e r st od i s a b l ei t ，e v e ni nc a s e sw h e r et h i si sn e i t h e rn e c e s s a r yn o r w i s e w e c a t e g o r i z et h ea p p l i c a t i o n st h a ts h o u l da n ds h o u l dn o td i s a b l et h en a g l ea l g o r i t h m ， a n dw es h o wt h a tf o rs o m e a p p l i c a t i o n st h a to f t e nd i s a b l et h en a g l ea l g o r i t h m ，e q u i v a l e n t p e r f o r m a n c ec a nb eo b t a i n e dt h r o u g ha l li m p r o v e di m p l e m e n t a t i o no f t h ea l g o r i t h m w e d e s c r i b ef i v e p o s s i b l em o d i f i c a t i o n s ，b e s i d e o n en o v e l p r o p o s a l ，a n da n a l y z e t h e i r p e r f o r m a n c eo nb e n c h m a r kt e s t s w ea l s od e s c r i b ear e c e i v e r s i d em o d i f i c a t i o nt h a tc a n h e l pi ns o m e c i r c u m s t a n c e s k e y w o r d s ：d l d e ta l g o r i t h m ，n a g l ea l g o r i t h m ，c o n g e s t i o nc o n t r o l ，d e l a y e d a c k n o w l e d g e m e n t ，t c p 对n a g l e 算法的进一步研究 第5 页共5 1 页 第一章绪论 1 1 研究背景 假定有一共享的资源量很大，但毕竟有限，当只有一个用户可以完全不受限制 的使用时，假如他的需求增加n ，他所占用的资源一定得到n 的增长。然而， 假如所有用户的需求都增加n ，总的需求将大大超过资源的承受能力，结果就是 每个用户几乎没有资源的净增，甚至导致整个系统的崩溃。这就是所谓的“公用的 悲剧”( t r a g e d yo f c o m m o n ) ：一个用户所追求的个体利益与所有用户的整体利益相 冲突，而且最终可能会损害到自身的实际利益。 众所周知，i n t e r n e t 从一开始就是一个公用的资源，人们早就认识到在它上面很 容易发生“公用的悲剧”，由此提出很多建议来防止悲剧的发生，一般通过两种途径： 技术途径主要是限制对资源的消耗( 如接入控制) ，经济途径主要是使用户对资源的 消耗与其所花费用相联系。然而这些方法的适用范围都不广，因为i n t e r n e t 协议通 常也用于独立的内部网络( i n t r a n e t ) ，虽然这些网络上也存在着负载过高的可能性， 但在这些机构中通常由于管理上的或其他方面的限制而难以采用上述两方面的机 制。 幸运的是，受引导的自身利益对资源也能产生良好的消费模式。当前i n t e r n e t 上用的最多的一种机制就是j a c o b s o n 的“慢启动”( 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 ) 。虽然这些算法的初衷是用来防止共享网络因拥塞而崩溃， 但j a c o b s o n 发现它们还能够提高t c p 连接的性能而不会带来额外的网络流量。也就 是说，对于大多数用户，他们的自身利益和整个网络的利益通过这些算法都得到了 保证。 1 2 问题的提出 在j a c o b s o n 利用反馈机制从事拥塞避免方面的工作前，已经有几种t c p 算法可 以用于防止不必要的数据包在网络上传输了，一般把这些算法归入开环类拥塞避免 机制。1 9 8 4 年，n a g l e 发现t e l n e t 这种协议会产生大量的微小数据包( t i n y p a c k e t ) ， 而用户如果发送较少的大数据包也能得到相同的服务结果。为此他提出了一个简单 对n a g l e 算法的进一步研究 第6 页共5 1 页 的算法，就是在t c p 连接的发送端自动地减少不必要的小数据包的发送。这一所谓 的n a g l e 算法现在成了t c p 实现的标准要求之一。 当发送端的t c p 决定是否在一连接上传送一个数据包时就可以采用n a g l e 算法， 如果仅仅是“少量”数据要发送，根据n a g l e 算法，仅当所有已发送出去的数据包 都得到接收方t c p 的确认后，才能将此小数据包发出。这里的“小”数据包是指长 度小于t c p 最大分组长度( m s s ，m a x i m u ms e g m e n ts i z e ) 的数据包1 。 标准的t c p 还包括另一个1 9 8 2 年提出的限制小数据包传送的算法，这一延迟 确认策略用于防止接收方发送过多的确认数据包。传统的接收方t c p 会尽量推迟确 认的发送，目的是为了万一本方有数据要送给对方时能将该确认捎带回去。但同时 t c p 标准规定延迟不得超过5 0 0 毫秒，而且为了有效地估算往返时间( r 1 v r ， r o u n d t r i pt i m e ) ，标准建议每收到两个满长( 即2 * m s s 字节) 的数据分组后必须 发一次确认。接收端t c p 设有一个计时器，典型值是2 0 0 毫秒( 最大可以设为5 0 0 毫秒) ，可以用来防止确认被无限延迟。延迟确认策略所基于的假设是发送端t c p 在遵循流量和拥塞控制的前提下能够尽快地发出数据，这样我们就可以通过简单地 等待下一数据包来避免发送过多的确认包。 然而，实际应用中常常出现的一种情景会导致发送端的n a g l e 算法与接收端的 延迟确认策略问产生暂时性的死锁：发送端t c p 因n a g l e 算法需要收到新的确认才 能发送新的数据，而接收端t c p 因延迟确认算法在等待新数据的到来后才能发出新 的确认。最后，接收端t c p 因定时器超时而发出新的确认包，从而消除了死锁，结 果是本来可以迅速完成的操作多了几百毫秒的延迟。这些延迟给人的感觉在l a n 和地区网上尤其明显。 由于许多应用程序无法忍受这些延迟，t c p 实现就对应用程序员提供了一个禁 用n a g l e 算法的选项。许多网络应用的实现者充分利用了这一点。在本文中，我们 将会发现，虽然在某一类应用中的确应该禁用n a g l e 算法，但在其它几类应用中却 不宜禁用该算法。因为有些应用程序的输出缓冲区管理策略是有缺陷的，如果在其 实现时禁用了n a g l e 算法，会因此给网络带来严重的拥塞。 然而由于n a g l e 算法和延迟确认策略之间存在着公认的暂时性死锁，为保险起 本文中将长度为m s s 的数据分组称为“满长分组”，反之称为“非满长分组” 对n a g l e 算法的进一步研究 第7 页共5 1 页 见，许多实现者被迫在本不需要禁用n a g l e 算法的应用中也禁用了该算法。这就给 那些本来需要n a g l e 算法的应用程序留下了网络性能恶化的隐患。 为了解决该算法所存在的暂时性死锁问题，人们提出了几种改进的建议。本文 对这几种改进的算法进行了评估，同时还提出了一种直接解除死锁的新算法，这种 算法的基本思想是将死锁看作是一种优先级倒错，并由此产生了一种相应的解决办 法。所有这些评估是通过修改f r e e b s d 的t c p 实现来完成的，但是这些概念和思 想在其他版本的t c p 实现上同样适用。 1 3 研究的目的和实际意义 我们的目的是能够在不改变现有应用程序的前提下，为传统的n a g l e 算法找到 一种综合性能最优的改进，评价性能的标准是要能够使那些由于暂时性死锁导致的 时延最小化；之所以要求是综合性能最优，是考虑了应用程序的通用性。如果应用 程序的实现者必须根据自身的要求、底层的网络和一大堆应用或环境参数，来决定 在实现时采用哪一种改进算法，那么这样的应用程序就没有通用性，而且实现复杂。 我们发现虽然所有的算法都各有优缺点，但只有基于死锁检测的改进算法在我们的 测试基准下完全消除了暂时性的死锁，即使这样，该算法也有不适应的情况。我们 还发现只要对接收方的延迟确认机制作一个简单的改动就能提高一部分情况下的应 用性能。 n a g l e 算法提出时骨干网的共享带宽还很低，有人认为现在这种小数据包流量对 于现在的i n t e r n e t 来说已经无关紧要了，这种观点至少有下面三个问题： a )许多用户现在通过无线上网，而无线信道的带宽还是很低； b )即使是在高速的链路上，过度泛滥的小数据包会降低昂贵设备( 如路由器) 的使用效率： c )n a g l e 算法对于那些设计草率或隐含复杂错误的应用程序来说，它可以有效地 充当阻挡大量微小数据包的防火墙。 因此，那些主张放弃对n a g l e 算法进行改进的观点显然是错误的。 对n a g e 算法的进一步研究 第8 页麸5 1 页 第二章t c p 上的数据流 2 1 拥塞崩溃 拥塞崩溃出现的必要条件有三个： ( 1 ) 网络负载很重； ( 2 ) 必须是纯数据报网络： ( 3 ) 具有端到端的重传机制。 这样一来，当网络中的某一节点出现拥塞时，端到端的往返时间就增大了，对 于两端没有拥塞控制的t c p 连接来说，发送端还会不停地向网络中注入分组，结果 更多的数据包会加剧拥塞的出现，但只要在网络中的每个分组只有一个拷贝，拥塞 还是可以控制的。一旦发送端开始重传尚未到达的分组时，崩溃的危险就出现了。 2 1 1 往返时间的测量 t c p 超时与重传中最重要的部分就是对一个给定连接的往返时间( r t t ) 的测 量。由于路由器和网络流量均会变化，因此这个时间也经常会发生变化，t c p 应该 跟踪这些变化并相应地改变其超时时间。 首先t c p 必须测量在发送一个带有指定序号的字节和接收到包含该字节的确认 之间的r t t 。用m 表示所测量到的r 1 t 。r t o 表示重传超时时间( r e t r a n s m i s s i o n t i m e o u t ) 。最初的t c p 规范建议t c p 使用低通滤波器来更新一个被平滑的r 1 t 估 计器( 记为e ) 。 e 一五e + ( 1 一旯) m 这里的旯是一个推荐值为0 9 的平滑因子。每次进行新测量的时候，这个被平滑的 r t t 将得到更新。每个新估计的9 0 来自前一个估计，而1 0 则取自新的测量。 在此基础上r f c7 9 3 推荐的r t o 的值应该设置为： r t o = 口e 这里的口是一个推荐值为2 的时延离散因子。 对n a g l e 算法的进一步研究 第9 页共5 1 页 由于t c p 的确认只对字节流，而不是对某个报文，所以当发生重传时，对返回 的确认将产生二义性，即到底是以前传输的字节流的确认还是本次传输的字节流的 确认，因而估计r 1 阿并不象想象的那么容易。 如果假定返回的确认只属于最先传输的分组，则当该链路经常丢失分组时，对 r t t 的估计值将会越来越大，极端情况下，r t t 将变得任意大。 如果假定确认只跟最近传输的分组相联系，则当端到端延迟突然增大时，发送 方由于上次的传输超时而重传该分组，重传后很快收到了接收方对上次传输的分组 的确认，根据假定，新的i 玎t 值将使对超时的估计更小，最终超时值将稳定在一个 小于实际时延的值上。如下图： 发送方接收方 图1 种情况下的r t t 的估计 假定端一端延迟突然增大后一直为t d ，超时值为r t o ，m 为测量值。则 m = t d r t o = t o 一口e 而 e 。= a e + 1 + ( 1 2 ) m e 。= 旯e 。一l + ( 1 一五) ( t o 一卢e n ) 当n c o 时，有 e 。= e 。1 得e 2 高 r t 。2 南1 c 七8 对n a g l e 算法的进一步研究塑! ! 里苎! ! 里 因为p 值一般是2 ，所以r 1 o = 寺，即每个分组至少重传一次，此时的网络状况 j 已经稳定下来了。 j a c o b s o n 详细分析了在r t t 变化范围很大时，使用简单的倍率公式无法跟上这 种变化，从而引起不必要的重传，当网络已经处于饱和状态时，不必要的重传会增 加网络的负载，对网络而言这就像火上浇油一样。 除了被平滑的r 1 t 估计器，所需要的还有跟踪r 1 1 的方差。在往返时间变化起 伏很大时，基于均值和方差来计算r t o ，将比作为均值的常数倍数来计算r t o 更 能反映出网络状况的变化。 因为在t c p 中性能是一个主要的考虑因素，为了加快计算速度，j a c o b s o n 建议 用均值偏差来代替标准偏差 8 ，均值偏差是对标准偏差的一种很好的逼近，但却更 容易计算，而计算标准偏差需要一个开方运算。下面就是根据j a c o b s o n 的建议得到 的估计算法： d = m e e e + g d a 一a + h ( idl a ) r t 0 = e + 4 a 这里的e 是被平滑的r t t ( 均值的估计器) ，而a 则是被平滑的均值偏差。d 是刚 得到的测量结果与当前的r t t 估计器之差。e 和a 均被用于计算下一个r t o 。增 量g 起平均作用，取为l 8 ，偏差的增益是h ，取值l 4 。当r t t 变化时，较大的偏 差增益将使r t o 快速上升。 j a c o b s o n 指明了一种使用整数运算来计算这些公式的方法，并被许多实现所采 用。这也就是g ，h 和倍数4 均是2 的乘方的一个原因，这样一来计算就可以只通过 移位操作而不需要乘、除运算来完成。 2 1 2 崩溃的出现 主机t c p 实现会对没有收到的分组重传若干次，每次的间隔会越来越大( 一般 每次重传的间隔时间是上次间隔的翻倍，这个倍乘关系被称为“指数退避 ( e x p o n e n t i a lb a c k - o f f ) ”) ，当达到一个预设的上限时，就不再重传。通常来说，这 对n a g l e 算法的进一步研究 第1 i 页共5 1 页 一机制足以应付严重的拥塞问题。即使采用更好的重传算法，网络上突然的负载加 重还是可能造成往返时间增加过快以至于发送方来不及更新它所能测到的往返时 间。负载的这种突然变化一般出现在网络上开始一个新的文件传输时，这种传输会 一下子填满整个缓冲区，如果一个主机上测到的r t t 的超过了该主机上的最大超时 值，该主机就会向网络中不停地发送相同的数据报。最终，t c p 连接上的每个节点 的缓冲区都被耗尽，再有数据包来只能丢弃。此时那些送到的数据包的i m 已经达 到了最大值，主机对每个数据包都要传送好几次，而且很有可能被丢弃，此时的网 络已经发生了拥塞崩溃。 这一情况是不易被改变的，一旦达到了饱和，如果选择丢弃数据包的算法是公 平的，那么网络在这种极差的状况下还是可以运作的。在这种情况下，每个数据包 都要传送若干次，t c p 的吞吐量也只有正常情况下的几十分之一。我们通过实验有 意让网络进入崩溃状态，并且让其持续一段时间。就会发现连接的往返时间越来越 大，最后因为主机引发超时而中断了连接。 2 2t c p 上的数据流 一些有关t c p 通信量的研究发现，如果按照分组数量计算，约有一半的t c p 数 据包包含成块数据( 如f t p 、电子邮件和u s e n e t 新闻) ，另一半则包含交互数据( 如 t e l n e t 和r l o g i n ) 。如果按字节计算，则成块数据和交互数据的比例约为9 0 和1 0 。 这是因为成块数据的分组基本上是满长度的( f u l l s i z e d ) ，而交互数据n 4 得多，统 计表明t e l n e t 和r l o g i n 分组中通常约9 0 左右的用户数据小于1 0 个字节。 很明显，t c p 需要同时处理这两类数据，但使用的处理算法则有所不同。本节 将以r l o g i n 应用为例来观察交互数据的传输过程。将揭示延迟策略是如何工作的以 及n a g l e 算法怎样减少了通过网络传输的小分组的数目，这些算法也同样适用于 t e l n e t 应用。 2 2 1 交互数据流中的小数据报 我们特意使用r l o g i n 作为例子，因为它每次总是从客户端发送一个字节到服务 翌翌塑! 苎兰竺兰二兰! 窒一墨j 三里二三翌! l 器，而且，r l o g i n 需要远程系统( 服务程序) 回显客户键入的字符。这样就会产生 四个分组：( 1 ) 来自客户的交互按键；( 2 ) 来自服务程序的按键确认；( 3 ) 来自服务程序 的按键回显；( 4 ) 来自客户的按键回显确认。图2 表示了这个数据流。 客户 按键一 显示一 服务器 一服务程序 一回显 图2 一种可能的处理远程交互按键回显的方法 当前的系统普遍使用了延迟确认策略，因此服务器端的t c p 一般将分组2 和3 进行合并，对于上图，就是将按键确认与按键回显一起发送。 下表显示的是我们在b s d i 上r l o g i n 到服务器s v r 4 后，键入5 个字符d a t e n 时的 数据流，我们通过一个工具程序t c p d u m p 来捕获这些数据包，对t c p d u m p 的输出作 了变动，去掉了一些讨论中不需要的信息，并将这些信息表示成如下的时间序列表： 分组曲扶琢键分组j 羞分组收 确认教延 编号的时闻筹出时刻到时翱j r t t迟的时间教据包的内容 l( 开始键入)00 3 0 1 6 5 p s h0 ：l ( 1 ) a c k1 ( d ) 200 1 6 4 9 7 0 1 2 3 5p s h l ：2 ( 1 ) a c ki ( d 的回显) 3 03 1 8 l o 1 3 9 9 5 5a c k2 40 4 5 8 0 3 7 3 0 1 6 3 p s h1 ：2 ( 1 ) a c k2c a ) 60 4 7 3 8 6 0 00 6 5 6p s h 2 ：3 ( 1 ) a c k2 ( a 的回显) 6 0 2 7 4 6 + 05 3 9 9 4 3a c k3 70 8 1 4 5 8 2 00 1 6 5 p s h2 ：3 “) a c k3i t ) 808 3 1 1 0 8 01 0 9 gp s h3 ：4 ( n a c k3 ( t 的回显) 9 02 5 1 20 9 4 0 1 1 2 a c k4 1 01 1 9 1 2 8 7 00 t 6 4 p s h3 ：4 ( 1 ) a c k4 ( e ) 1 112 0 7 7 0 l 0 1 3 2 3p s h4 ：5 ( n a c k4 ( e 的回显) 1 2 0 3 4 0 7 + 13 3 9 9 9 4a c k5 1 3l6 8 0 6 4 6 30 1 7 3 p s h4 ：5 ( 1 ) a c k5 ( 新行) 1 4i 6 9 7 9 7 7 o 0 4 2 0 p s h5 ：7 ( 2 ) a c k5 ( c rl f 新行的回显是两个字符) 1 5+ 1 7 3 9 9 7 4 a c k7 1 617 9 9 8 4 1 0 1 4 0 3p s h7 ：3 7 3 0 ) a c k 5 ( s a ta o r90 7 ：5 2 ：0 7m s t2 6 0 2 ) 1 7+ l0 4 0 1 7 6 a c k3 7 1 8l ，9 4 4 3 3 8 0 1 9 5 gp s h3 7 ：4 4 ( 7 ) a c k5 ( s v r 4 ) 1 921 4 0 1 i 0 a c k4 4 表1 在r l o g i n 连接上键入d a t e 命令时的数据流时间序列 对n a g l e 算法的进一步研究 第1 3 页共5 1 页 表格中的时间单位是秒，从表中可以看出，只要在服务器端没有延迟，从客户 端发送的数据分组的往返时间变化很小，这主要是我们的测试网络的数据流量不大， 几乎不会产生拥塞。 如前所述，通常t c p 在接受到数据时并不立即发送a c k ；相反，它推迟发送， 以便将a c k 与需要沿该方向发送的数据一起发送( 这种现象也叫数据捎带a c k ) 。绝 大多数t c p 实现采用的延迟超时值为2 0 0 毫秒，也就是说，t c p 将以最大2 0 0 毫秒 的延迟等待是否有数据一起发送。 如果观察上表中b s d i 接收到的数据和发送a c k 之间的时间差，就会发现它们几 乎是随机的：1 2 3 5 、6 5 5 、1 0 9 0 、1 3 2 2 、4 3 0 、1 4 0 3 和1 9 5 8 毫秒。相反，观察到 发送a c k 的实际时间( 从0 开始) 为：1 3 9 9 、5 3 9 9 、9 4 0 1 、1 3 3 9 9 、1 7 3 9 7 、1 9 4 0 1 和2 1 4 0 1 毫秒( 在表中以星号标出) 。这些时间之间的差都是2 0 0 毫秒的整数倍， 这是因为t c p 使用了一个2 0 0 毫秒的定时器，该定时器以相对于内核基准的2 0 0 毫 秒的固定时间溢出。由于将要确认的数据是随机到达的( 在时刻1 6 4 、4 7 4 3 、8 3 1 1 等) ，t c p 在内核的2 0 0 毫秒定时器的下一次溢出时得到通知，这有可能是将来1 2 0 0 毫秒中的任一时刻。 如果观察s v r 4 为产生所收到的每个字符的回显所使用的时间，则这些时间分别 是1 6 5 、1 6 3 、1 6 5 、1 6 4 和1 7 3 毫秒。由于这个时间小于2 0 0 毫秒，因此我们在 另一端从来没有观察到一个被延迟的a c k 。因为字符回显可以在服务器端很快完成， 在内核的2 0 0 毫秒定时器超时之前总有数据要发送，所以看不到a c k 被延迟；但是 如果有一段等待时间刚好跨越了定时器2 0 0 毫秒超时的前后边界，则仍可看到被延 迟的a c k ，但在我们的试验中没有出现这样的情况。 在这个试验中我们看到，因为在一个r l o g i n 连接上客户每次一般发送一个字节 到服务器，这就产生了一些4 l 字节长的i p 数据包：2 0 字节的i p 首部、2 0 字节的 t c p 首部和1 个字节的数据。在局域网上，这些微小分组( t i n y g r a m ) 通常不会引 起麻烦，因为局域网一般不会出现拥塞。但在广域网上，因为负载较重，4 0 0 0 的 开销会极大地增加拥塞出现的可能，导致报文丢失和重传。 这一经典问题首次提出是在6 0 年代末的一个t y m n e t 网络中，当时的解决办法 是对单位时间内产生的报文数规定一个上限。为了保证这一点，对于小分组的传输 必须加以延迟，这一延迟时间一般在2 0 0 到5 0 0 毫秒之间，通过延迟来确保单位时 间内不达到上限，还可以累积更多的小数据，使其在一个数据包中发送出去。而且， 翌型竺生苎鳖竺兰二生竺垄 为了使响应时间能够让用户接受 迟的。 第1 4 页共5 i 页 这一解决方法对控制字符( 如回车键) 是不加延 这一技术曾被用于n c p 的t e l n e t ，x 2 5 的p a d 和t c p 的t e l n e t 中。它的优点 是易于理解，实现也不复杂。它的缺点是很难找到一个每个用户都满意的时间限制， 在一个1 0 me t h e r n e t 上能够产生很高的响应速度的短时间限制，在另一个平均往返 时间是5 秒的高负载网络上根本不能防止出现拥塞；相反，能够满足后者的时间限 制在1 0 m 的e t h e r n e t 上用户就根本无法忍受。 2 2 2 对小数据报的解决办法 对此显然要有一个自适应的算法。一个显而易见的想法是根据上节中估计出的 r t t 来产生一个自适应的时间限制。虽然这一方法肯定可以实现，但没有必要。n a g l e 提出了一个简单优美的自适应算法。 如果高层应用有数据需要发送，当操作系统把数据交给t c p 后，n a g l e 算法首 先检查前一个送出的分组是否已经收到了接收方的确认，如果没有，则禁止数据的 发送，这一禁止是无条件的，而且也不需要任何定时器，也用不着对收到的数据长 度进行比较测试以及任何其它条件。实现也很简单，只要在t c p 的实现程序中加一 两行而己。 虽然该算法的思想看上去对t c p 的行为会有激烈的影响，但其实不然。当用户 向一个t c p 连接( 在程序中是s o c k e t 连接) 写入数据时，t c p 会将数据保存到s o c k e t 输出缓冲区中。t c p 可以将这些数据立即发送，也可保留到以后发送。如果它当时 不传送这些数据，那就要等到发送方收到一个数据包导致系统状态改变后。系统状 态在两种条件下得以改变：收到的数据包中包含了对上次送出的数据的确认信息， 或者通告了接收方的可用的缓冲区空间大小。( 后者其实也叫“更新窗口通告”) 。对 连接上收到的每个数据包，发送方t c p 必须重新检查它当前的状态，如果状态改变， 它就必须发出数据包( 如果有数据要发送的话) 。因此，t c p 不立即发送用户应用 提供的数据是因为还没有收到从远程接收方的数据包。除非t c p 连接以前就已经空 闲( 双方已经没有任何数据需要传输和确认) 或与对方的通信已经中断，否则肯定 会收到对方的一个数据包。在前一种情况中，只要用户应用向t c p 连接写数据，t c p 会立即发送这些数据，不会有任何延迟。因此n a g l e 算法在空闲的连接上不会导致 对n a g l e 算法的进一步研究 第1 5 页共5 1 页 死锁；对于后一种情况，因为远程主机已经不可用，所以发送的任何数据都不会被 确认，由于n a g | e 算法并没有扰乱正常的t c p 重传策略，所以t c p 自己会处理数 据包的丢失。 该算法要求一个t c p 连接上最多只能有一个未被确认的未完成的小分组，在该 分组的确认到达之前不能发送其他的小分组。相反，t c p 收集这些少量的分组，并 在确认到来时以一个分组的方式发出去。该算法的优越之处在于它是自适应的：确 认到达得越快，数据也就发送得越快。而在希望减少微小分组数目的低速广域网上， 则会发送更少的分组。 2 2 3 n a g l e 算法在不同的网络状况上的应用 首先，该算法解决了面向字符的r l o g i n 类连接，假设有一e t h e m e t 的t c p 连接 用于r l o g i n ，该连接的l m 和远程服务程序的处理时间之和平均为5 0 毫秒，用户 每隔2 0 0 毫秒输入一个字符。如果对小数据包没有任何的拥塞避免措施，对用户输 入的每个字符都会产生一个数据包并且立即发送出去，因为r 1 r r 加处理的时间远小 于2 0 0 毫秒，所以每个字符都可以立即在用户终端上得到回显，此时的响应性能是 最好的。虽然传输的开销高达4 0 0 0 ，但在一个本地的e t h e m e t 上，这还是可以接 受的。如果使用最早提出的定时器方案，假定时间限制是5 0 0 毫秒，则每秒只能发 送2 个数据包，这将导致2 到3 个字符被累积到一个数据包中一起发送。这即使在 带宽较高的e t h e m e t 上也会使人感觉到响应速度的明显降低。因此虽然开销降到了 1 5 0 0 ，但在相比响应速度，这样的代价并不值得。在n a g l e 算法中，每次用户键 入字符时，t c p 都会发现当时的连接处于空闲状态，因为在e t h e r n e t 上2 0 0 毫秒对 于一个字符的传输和接收确认绰绰有余，因此每次都是立即发送，就好像没有实施 任何的拥塞避免措施，用户也不会感觉到有任何的响应延迟。这说明n a g l e 算法在 高带宽，低r t t 的网络连接上对面向字符的应用有很好的响应速度。 当通过长距离的连接进行r l o g i n 时，如果该链路的带宽较低，t c p 连接的r t t 因此就可能比较高，假定为5 秒。如果没有任何拥塞控制，在5 秒内将发出2 5 个小 数据包，开销也是4 0 0 0 ；如果使用与上面相同设定的定时器方案，5 秒钟内还会 有l o 个数据包发出，还是可能产生拥塞。当然，连续发送许多分组并不能缩短r t t ： 通常情况是这些分组还会争用一条连接上的带宽。虽然此时的开销下降到1 5 0 0 ， 对n a g l e 算法的进一步研究 第1 6 页共5 l 页 但是在这样的链路上，因为r t t 较大，r l o g i n 用户是不可能指望得到可以接受的 响应速度的，所以这种方案已经比第一种的效率高了许多。如果使用n a g l e 算法， 当用户键入第一个字符时，t c p 因为连接空闲而不加延迟的发送含有一个字节数据 的小数据包，随后由于第一个字符的确认还没到来，接下来用户以每秒5 个字符的 速度输入的字符都被t c p 缓冲起来，延迟发送。5 秒后，对第一个字符的确认收到 了，这段时间里t c p 一共收集了2 5 个字符，它立即将这些字符形成一个数据包发 出，结果性能并没有什么损失，开销却下降到了3 0 7 。一般来说，由于开销的降 低，响应速度通常会有提高。而且，网络上发生拥塞的可能性也因此而大大降低了； 同样平均i m 时间也会显著下降。 对于文件传输这类t c p 上的成块数据流，n a g l e 算法一样适用。( 略) 2 3 延迟确认策略 确认是由数据的接受者产生的，一旦确认到达发送方，发送方就必须对此进行 处理。显然发送方的这种开销是由接收方引发的，而且完全受接收方的控制。为了 减少发送方的处理开销，接收方可以考虑延缓确认的发送，但这样一来，就必须在 接收方设定时器，而处理定时器超时事件在操作系统中是一个很耗资源的行为。 对此，c l a r k 在r f c8 1 3 中提出了比较好的折衷方案，数据接收方会在特定的条 件下推迟确认的发送，此时必须设定个定时器来确保最终会把该确认送出。接收 方这样做是认为在定时器超时前肯定有另外的事件会打断它，使其不必要处理定时 器的超时中断，最可能发生的是又有新的数据到达接收方。因此，如果满足下面的 两个条件，就可以继续推迟发送确认：( 1 ) 数据报中没有设置p u s h 标记；( 2 ) 当前 没有新的窗口通告要发送。 该策略认为虽然设了一个定时器，但一般是用不到的，定时器的间隔一般是2 0 0 到3 0 0 毫秒。 但是如果一直不发送确认，会导致发送方认为以前的数据都被丢失而引发不必 要的重传，所以t c p 还规定收到2 * m s s 长的数据后必须发次确认。 对n a g l e 算法的进一步研究 第1 7 页共5 1 页 2 4n a g l e 算法和延迟确认算法之间的交互 如前所述，n a g l e 算法导致的延迟事实上是t c p 发送方的n a g l e 算法和t c p 接 收方的延迟确认策略之间的暂时性死锁。之所以说是暂时性的，是因为接收方发送 确认报文的延迟最大不超过5 0 0 毫秒，基于b s d 的系统将此值限制在2 0 0 毫秒。至 少在基于b s d 的系统中，由于t c p 实现中的几个原因，这种实际的交互比上述的 来得复杂。 下面举几个例子来说明这种交互。图中时间的流逝是从上到下的，左边是客户 机，由应用( a p p ) 和t c p 发送方组成；右边是服务器，只列出了接收方。消息数 据由标有a 、b 、c 、d 的长方形表示。虽然t c p 的计数序列是以字节为单位的， 但t c p 拥塞控制( 包括n a g l e 算法) 却是以m s s 长的分组来计数的，因此下图中 的分组长度都是i m s s 。时间的计算主要是以往返时间( r 盯) 来表示的。假设发 送端的初始拥塞窗口是2 * m s s ，因为通常当客户端的s y n 被确认后，拥塞窗口就 是这么大。( 假如拥塞窗口大于这个数值，我们只要在图中用更大的应用缓冲区来表 示即可) 。同时我们还假设网络的带宽足够高，对由此产生的时延忽略不计。 图3 示出了一次成功的( 无延迟) 交互过程。应用程序构造了一个缓冲区( a 、 b 、c 、d ) ，大小刚好是4 * m s s 字节，然后一次性放入t c p 的栈中( 在基于b s d 的系统中，这需要将数据复制到一个s o c k e t 缓冲区中) 。在0 r t t 时刻，t c p 发送端 送出两个分组( 因为此时的拥塞窗口是2 * m s s ) ，接收方立刻对这两个分组进行确 认，大约过了1 r 1 1 的时间，发送方收到了该确认，随后又将剩余的两个分组发出。 接收方的服务程序在收到这四个分组后进行处理，然后返回一个响应，响应到达发 送方的客户程序大约在( 2 * r t t + 服务时间) 这一时刻。 对n a g l e 算法的进一步研究 第1 8 页共5 1 页 客户端 t c p 服务器端 t c p 处理请求的 服务时间 图3 一次成功的传输过程 图4 示出了一次有延迟的交互，这次应用程序放入t c p 缓冲区的数据略少于 4 * m s s 字节，同样，第一次还是发送a 、b 两个分组，在1 r 1 1 时刻发送方收到了 确认，此时情况尚且正常，因此发送方立即发送出c 分组，但却将d 分组的发送推 迟了，因为d 不是满长分组，所以要收到对c 的确认才会发出d 。同时，接收方的 延迟确认策略推迟发送对c 的确认，因为它认为很快就会收到全长的d 分组，如此 僵持2 0 0 毫秒，接收方主动放弃等待，发出了对c 的确认，发送方收到该确认后立 即发送d 分组，等到发送方的客户程序收到服务程序返回来的响应时，已经是 ( 3 * r t t + 2 0 0 毫秒+ 服务时间) 时刻了，这比正常交互多花了r t t + 2 0 0 毫秒的时 间。 对n a g l e 算法的进一步研究 第1 9 页麸5 l 页 客户端 t c p 服务器端 t c p 叫a | 1 b 卜 。乡 叫c【 。竺一 百 l r 响应报文 9 4 t - - - - 一 十服务时间 因为延迟确认策略 而推迟发送对c 的 确认，最大时延 2 0 0 毫秒 处理请求 服务时间 图4 被n a g l e 算法延迟的传输过程 图4 中，我们注意到，c 和d 的传送被延迟是基于拥塞窗口的大小为2 * m s s 的 假设之上的，但在另外一些不限制拥塞窗口大小的情况下，n a g l e 算法也还会引发 相似的问题，至少在基于b s d 的实现中是这样的，这就不得不提到b s ds o c k e t 的 翌翌竺! ! 苎兰竺堂二生竺墅 缓冲区机制。 第2 0 页共5 1 页 当应用程序在t c p 连接上调用系统调用，如w r i t e 0 来发送一个缓冲区中的数据 时，内核通过s o s e n d o i 函数将数据从用户缓冲区复制到s o c k e t 缓冲区，然后调用 t c po u t p u t ( ) 函数。如果用户缓冲区大小超过一个页簇( m c l b y t e s ) ，s o s e n d o 就将 它复制到一串m c l b y t e s 长的空间中，对每个这样的缓冲空间调用一次 t c p _ o u t p u t o ，当接收到一个确认或传送超时时也会运行t c p o u t p u t o 。与t c p 的发送 策略一致，每次调用t c po u t p u t ( ) 时，它都发送尽量多的数据包。 真正的n a g l e 算法延迟发送小的分组，直到发送方没有未确认的数据要等待发 送( 即发送方i d l e ) 时，才会送出这种小分组。然而，b s d 实现中的t c p 函 数有些古怪：每当它被调用时它可以下子发送多个数据分组，但却只检_ o 测u t p “u t ( ) i d l e ” 状态一次。下图给出了t c p的部分伪代码。_output() t c p _ o u t p u t ( s t r u c tt c p c b + t p + 输入：t c p 控制块+ * 如果发送的所以数据都已确认，则连接处于空闲状态t i d l e2 ( t p 一 s n d _ m a x t p s n d _ u n a ) j g a i n ： + 缓冲区中第一个未发送字节的偏移量+ o f f 2 t p s n d _ n x t t p 一 s n d _ u n a ； + 流量控制和拥塞窗口的最小值+ w i n 。m i n ( t p 一 s n d _ w n d ，t p 一 s n d c w n d t 缓冲区中尚未发送的数据长* l e n = m i n ( s o 一 s os n d s bc c ，w i n ) 一o f f ； i f f l e n = t p 一 t _ m a x s e g ) g o t os e n d ； + 如果数据可以组成一个满长分组。则立即发送* t e m p t y i n g = 是否可以清空s o c k e t 缓冲区 e m p t y i n g = ( ( 1 e n + o f f ) = s o 一 s o s n d s b c c 对n a g l e 算法的进一步研究 第2 1 页麸5 1 页 图5 b s d 中t c p 有关 算法的伪代码o u t p u tn a g l e 既然s o s e n d 0 对每m c l b y t e s