文章目录
前言摘要背景知识拥塞控制简介慢启动拥塞避免快速恢复TCP拥塞控制算法TCP Tahoe与Reno 运行机制对比分析TCP NewReno与SACK 运行机制对比分析TCP Vegas和Reno运行问题分析计网中的相关论文前言
今天是12月16号,也是全国硕士研究生招生考试的日子。当年我的运气很好,恰好有保研的名额,也有点怂工作。所以,我最后来到了一所历史人文底蕴很好的学校。目前,我也挺喜欢这里的环境。
大三之后,计划工作or读研,每个人的处境不同,没有合适的参考,很难判断,至少我当年的环境是这样。老话说的好,’大学生不紧张高三生的高考‘。同样,我不紧张大四学生的研究生招生考试。我期望学弟学妹们可以去想去的学校,毕竟他们中一部分人耐性、踏实,品性相当不错。
目前,我的研一上学期接近尾声,最近也要期末考试了。上了一个学期的研究生课程,我对研究生课程可以有一丁点自己的看法。当然,我的描述,仅仅从学生的角度,对本校本学期的课程有效。
首先是选课,选自己方向相关的课程,还是开拓知识面的课程?我倾向于中庸的思想。和自己知识体系相适应方向的课程,可以轻松很多。开拓视野的基础课,可以站在在本科的基础上,对一些问题有更高的角度。
之后是上课。上课的时候会发现,半数以上的课程是水课,讲的烂的很。有的课是很不错的。这里点名表扬计算机网络。东哥的计网课我基本没听懂。但它确实是一门好课。因为它不违背下面的课程的评价指标。这个评价指标是我杜撰的,哈哈:
老师要牛皮,自己课程的内容要随手拈来。老师至少要站在课程内容层次乃至上一个层次。非基础课程,按照本科的层次教学,讲”是什么“。因为对于新内容,研究生和本科生没啥差别。相对于本校的本科生,研究生的基础可能还更弱点。基础课程,按照研究生的层次教育,讲”为什么“。因为之前的基础,使得有些内容,即使忘记了,自己也可以捡起来,不妨讲些好玩的东西。当然,可能对于跨考的同学不太友好。作业要少而精。少而精使得有时间大体弄明白其中一个问题就好。其他的相关内容,听一听,读些综述论文就好。论文报告,不妨,就其中的一个小点,讲讲它的入门级理解。有的课就是扯淡。上完水课,讲不是自己知识体系的论文。说者不知所云or听者不知所云。
言归正传。我的文笔确实烂:句子不通畅,主谓宾缺失乱序是常态。有必要,捯饬下该如何遣词造句写文章了。刚好把TCP拥塞控制的作业搞定,顺手整理下。所以下文是正题。
摘要
从《自顶向下》书中复制过来TCP的拥塞控制。介绍了TCP拥塞控制的相关算法:Tahoe、Reno、NewReno、SACK、Vegas。这些算法的区别,我不是特别清楚,所以这里不写他们之间的对比区别。完。
背景知识
通常,对于程序员而言,”TCP的三次握手“是搬砖的必备技能。可以参看下我之前整理的文章:chapter02_传输层_TCP_UDP_SCTP | MAC首部 IP首部 TCP首部介绍
但是计算机网络中的运输层中的TCP包含的内容可远远不止三次握手。这篇文章关心的是,当网络传输过程中出现拥塞,TCP该如何处理。
我看了一遍《自顶向下》第三章运输层之后,才开始做实验的。
背景知识,书上系统的介绍,是最好不过的了,我把书上这一章节的部分内容复制过来。
拥塞控制简介
在本节中,我们再次来学习TCP。如我们在3.5节所见,TCP为运行在不同主机上的两个进程之间提供了可靠传输服务。TCP的另一个关键部分就是其拥塞控制机制。如在前一节所指出,TCP必须使用端到端拥塞控制而不是使网络辅助的拥塞控制,因为IP层不向端系统提供显式的网络拥塞反馈。
TCP所采用的方法是让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率。如果一个TCP发送方感知从它到目的地之间的路径上没什么拥塞,则TCP发送方增加其发送速率;如果发送方感知沿着该路径有拥塞,则发送方就会降低其发送速率。但是这种方法提出了三个问题。第一,一个TCP发送方如何限制它向其连接发送流量的速率呢?第二,一个TCP发送方如何感知从它到目的地之间的路径上存在拥塞呢?第三,当发送方感知到端到端的拥塞时,采用何种算法来改变其发送速率呢?
我们首先分析一下TCP发送方是如何限制向其连接发送流量的。在3.5节中我们看TCP连接的每一端都是由一个接收缓存、一个发送缓存和几个变量( Last Read、rwnd等)组成。运行在发送方的TCP拥塞控制机制跟踪一个额外的变量,即拥塞窗口( congestion window)。拥塞窗口表示为cwnd,它对一个TCP发送方能向网络中发送流量的速率进行了限制。特别是,在一个发送方中未被确认的数据量不会超过cwnd与rwnd中的最小值,即
Lastbytesent−lastByteackedsmin<={cwnd,rwnd}Lastbytesent-last Byteackedsmin <= \{ cwnd, rwnd\} Lastbytesent−lastByteackedsmin<={cwnd,rwnd}
为了关注拥塞控制(与流量控制形成对比),我们后面假设TCP接收缓存足够大,以至可以忽略接收窗口的限制;因此在发送方中未被确认的数据量仅受限于cwnd。我们还假设发送方总是有数据要发送,即在拥塞窗口中的所有报文段要被发送。
上面的约東限制了发送方中未被确认的数据量,因此间接地限制了发送方的发送速率。为了理解这一点,我们来考虑一个丢包和发送时延均可以忽略不计的连接。因此粗略地讲,在每个往返时间(RTT)的起始点,上面的限制条件允许发送方向该连接发送cwnd个字节的数据,在该RTT结東时发送方接收对数据的确认报文。因此,该发送方的发送速率大概是cwnd/RTT字节/秒。通过调节ewnd的值,发送方因此能调整它向连接发送数据的速率。
我们接下来考虑TCP发送方是如何感知在它与目的地之间的路径上出现了拥塞的。我们将一个TCP发送方的“丢包事件”定义为:要么出现超时,要么收到来自接收方的3个冗余ACK。(回想我们在3.5.4节有关图3-33中的超时事件的讨论和收到3个冗余ACK后包括快速重传的后继修改。)当出现过度的拥塞时,在沿着这条路径上的一台(或多台)路由器的缓存会溢出,引起一个数据报(包含一个TCP报文段)被丢弃。丢弃的数据报接着会引起发送方的丢包事件(要么超时或收到3个冗余ACK),发送方就认为在发送方到接收方的路径上出现了拥塞的指示。
考虑了拥塞检测问题后,我们接下来考虑网络没有拥塞这种更为乐观的情况,即没有出现丢包事件的情况。在此情况下,在TCP的发送方将收到对于以前未确认报文段的确认。如我们将看到的那样,TCP将这些确认的到达作为一切正常的指示,即在网络上传输的报文段正被成功地交付给目的地,并使用确认来增加窗口的长度(及其传输速率)。注意到如果确认以相当慢的速率到达(例如,如果该端到端路径具有高时延或包含一段低带宽链路),则该拥塞窗口将以相当慢的速率增加。在另一方面,如果确认以高速率到达,则该拥塞窗口将会更为迅速地增大。因为TCP使用确认来触发(或计时)增大它的拥塞窗口长度,TCP被说成是自计时(sel- clocking)的。
给定调节cwnd值以控制发送速率的机制,关键的问题依然存在:TCP发送方怎样确定它应当发送的速率呢? 如果众多TCP发送方总体上发送太快,它们能够拥塞网络,导致我们在图3-48中看到的拥塞崩溃。事实上,为了应对在较早TCP版本下观察到的因特网拥塞崩溃[ Jacobson1988],研发了该版本的TCP(我们马上将学习它)。然而,如果TCP发送方过于谨慎,发送太慢,它们不能充分利用网络的带宽;这就是说,TCP发送方能够以更高的速率发送而不会使网络拥塞。那么TCP发送方如何确定它们的发送速率,既使得网络不会拥塞,与此同时又能充分利用所有可用的带宽?TCP发送方是显式地协作,或存在一种分布式方法使TCP发送方能够仅基于本地信息设置它们的发送速率?TCP使用下列指导性原则回答这些问题:
一个丢失的报文段表意味着拥塞,因此当丢失报文段时应当降低TCP发送方的速率。回想在3.5.4节中的讨论,对于给定报文段,一个超时事件或四个确认(个初始ACK和其后的三个究余ACK)被解释为跟随该四个ACK的报文段的“丢包事件”的一种隐含的指示。从拥塞控制的观点看,该问题是TCP发送方应当如何减小它的拥塞窗口长度,即减小其发送速率,以应对这种推测的丢包事件。一个确认报文段指示该网络正在向接收方交付发送方的报文段,因此,当对先前未确认报文段的确认到达时,能够増加发送方的速率。确认的到达被认为是一切顺利的隐含指示,即报文段正从发送方成功地交付给接收方,因此该网络不拥塞。拥塞窗口长度因此能够增加。带宽探测。给定ACK指示源到目的地路径无拥塞,而丢包事件指示路径拥塞,TCP调节其传输速率的策略是增加其速率以响应到达的ACK,除非出现丢包事件,此时才减小传输速率。因此,为探测拥塞开始出现的速率,TCP发送方增加它的传输速率,从该速率后退,进而再次开始探测,看看拥塞开始速率是否发生了变化。TCP发送方的行为也许类似于要求(并得到)越来越多糖果的孩子,直到最后告知他/她“不行!”,孩子后退一点,然后过一会儿再次开始提出请求。注意到网络中没有明确的拥塞状态信令,即ACK和丢包事件充当了隐式信号,并且每个TCP发送方根据昇异步于其他TCP发送方的本地信息而行动。
概述了TCP拥塞控制后,现在是我们考虑广受赞誉的TCP拥塞控制算法( TCP con-gestion control algorithm)细节的时候了,该算法首先在[ Jacobson1988]中描述并且在[RFC5681]中标准化。该算法包括3个主要部分:①慢启动;②拥塞避免;③快速恢复。慢启动和拥塞避免是TCP的强制部分,两者的差异在于对收到的ACK做出反应时增加cwnd长度的方式。我们很快将会看到慢启动比拥塞避免能更快地增加cwnd的长度(不要被名称所迷惑!)。快速恢复是推荐部分,对TCP发送方并非是必需的。
慢启动
当一条TCP连接开始时, cwnd的值通常初始置为一个MSS的较小值[RFC 3390],这就使得初始发送速率大约为MSS /RTT。例如,如果MSS=500字节且RTT=200ms,则得到的初始发送速率大约只有20kbps。由于对TCP发送方而言,可用带宽可能比MSS/RTT大得多,TCP发送方希望迅速找到可用带宽的数量。因此,在慢启动(slow- start)状态,cwnd的值以1个MSS开始并且每当传输的报文段首次被确认就增加1个MSS。在图3-51所示的例子中,TCP向网络发送第一个报文段并等待一个确认。当该确认到达时,TCP发送方将拥塞窗口增加个MSS,并发送出两个最大长度的报文段。这两个报文段被确认,则发送方对每个确认报文段将拥塞窗口增加一个MSS,使得拥塞窗口变为4个MSS,并这样下去。这过程每过一个RTT,发送速率就翻番。因此,TCP发送速率起始慢,但在慢启动阶段以指数增长。
但是,何时结束这种指数增长呢? 慢启动对这个问题提供了几种答案。首先,如果存在一个由超时指示的丢包事件(即拥塞),TCP发送方将 cwnd设置为1并重新开始慢启动过程。它还将第二个状态变量的值 ssthresh(“慢启动阈值”的速记)设置为cwnd/2,即当检测到拥塞时将 ssthresh置为拥塞窗口值的一半。慢启动结束的第二种方式是直接与 ssthresh的值相关联。因为当检测到拥塞时 ssthresh设为cwnd的值一半,当到达或超过ssthresh的值时,继续使cwnd翻番可能有些鲁莽。因此,当cwnd的值等于 ssthresh时,结束慢启动并且TCP转移到拥塞避免模式。我们将会看到,当进入拥塞避免模式时,TCP更为谨慎地增加cwnd。最结束慢启动的方式是,如果检测到3个冗余ACK,这时TCP执行一种快速重传(参见3.5.4节)并进入快速恢复状态,后面将讨论相关内容。慢启动中的TCP行为总结在图3-52中的TCP拥塞控制的FSM描述中。慢启动算法最早源于[ Jacobson19881;在[Jain1986]中独立地提出了一种类似于慢启动的方法。
拥塞避免
一旦进入拥塞避免状态,cwnd的值大约是上次遇到拥塞时的值的一半,即距离拥塞可能并不遥远!因此,TCP无法每过一个RTT再将cwnd的值翻番,而是采用了一种较为保守的方法,每个RTT只将cwnd的值增加一个MSS[RFC5681]。这能够以几种方式完成。一种通用的方法是对于TCP发送方无论何时到达一个新的确认,就将cwnd增加一MSS(MSS/cwnd)字节。例如,如果MSS是1460字节并且cwnd是14600字节,则在个RTT内发送10个报文段。每个到达ACK(假定每个报文段一个ACK)增加1/10Ms的拥塞窗口长度,因此在收到对所有10个报文段的确认后,拥塞窗口的值将增加了一个MSS。
但是何时应当结束拥塞避免的线性增长(每 RTT 1MSS)呢?当出现超时时,TCP的拥塞避免算法行为相同。与慢启动的情况一样,cwnd的值被设置为1个MSS,当丢包事件出现时, ssthresh的值被更新为cwnd值的一半。然而,前面讲过丢包事件也能由个三个冗余ACK事件触发。在这种情况下,网络继续从发送方向接收方交付报文段(就像由收到冗余ACK所指示的那样)。因此TCP对这种丢包事件的行为,相比于超时指示的丢包应当不那么剧烈:TCP将cwnd的值减半(为使测量结果更好,计及已收到的3个冗余的ACK要加上3个MSS),并且当收到3个冗余的ACK,将 ssthresh的值记录为cwnd的值的半。接下来进入快速恢复状态。
快速恢复
在快速恢复中,对于引起TCP进入快速恢复状态的缺失报文段,对收到的每个冗余的ACK,cwnd的值増加一个MSS。最终,当对丢失报文段的一个ACK到达时,TCP在降低cwnd后进入拥塞避免状态。如果出现超时事件」快速恢复在执行如同在慢启动和拥塞避免中相同的动作后,迁移到慢启动状态:当丢包事件出现时,cwnd的值被设置为1个MSS,并且 ssthresh的值设置为cwnd值的一半。
快速恢复是TCP推荐的而非必需的构件[RFC5681]。有趣的是,一种称为TCP Tahoe的TCP早期版本,不管是发生超时指示的丢包事件,还是发生3个冗余ACK指示的丢包事件,都无条件地将其拥塞窗口减至1个MSS,并进入慢启动阶段。TCP的较新版本 TCP Reno,则综合了快速恢复。
图3-53图示了Reno版TCP与 Tahoe版TCP的拥塞控制窗口的演化情况。在该图中,阈值初始等于8个MSS。在前8个传输回合, Tahoe和Reno采取了相同的动作。拥塞窗口在慢启动阶段以指数速度快速爬升,在第4轮传输时到达了阈值。然后拥塞窗口以线性速度爬升,直到在第8轮传输后出现3个冗余ACK。注意到当该丢包事件发生时,拥塞窗口值为12×MSS。于是 ssthresh的值被设置为0.5 x cwnd=6xMSS。在 TCP Reno下,拥塞窗口被设置为cwnd=9MSS,然后线性地增长。在 TCP Tahoe下,拥塞窗口被设置为1个MSS,然后呈指数增长,直至到达 ssthresh值为止,在这个点它开始线性增长。
图3-52表示了TCP拥塞控制算法(即慢启动、拥塞避免和快速恢复)的完整FSM描述。该图也指示了新报文段的传输或重传的报文段可能出现的位置。尽管区分TCP差错控制/重传与TCP拥塞控制非常重要,但是注意到TCP这两个方面交织链接的方式也很重要。
(我们老师说上面这张图是错的,下面会给出正确的图。关于TCP的拥塞控制,书上还有些内容,可以自行阅读)
TCP拥塞控制算法
TCP Tahoe与Reno 运行机制对比分析
TCP Tahoe的快速重传
快速重传就是基于以下机制:如果假设重复阈值为3,当发送方收到4次相同确认号的分段确认(第1次收到确认期望序列号,加3次重复的期望序列号确认)时,则可以认为继续发送更高序列号的分段将会被接受方丢弃,而且会无法有序送达。发送方应该忽略超时计时器的等待重发,立即重发重复分段确认中确认号对应序列号的分段。
此时Tahoe,在重传之后,ssthresh
变为当前cwnd
一半,cwnd
变为1。从新进入慢启动。(这个变化的过程中,对于快速重传发送包的应答,来了收下便收下,对过程没有影响。)
Reno的快速重传和快速恢复
step1:
if ( dupacks >= 3 ) {
ssthresh = max( 2 , cwnd / 2 ) ;
cwnd = ssthresh + 3 * MSS ;
}
step2:重传丢失的分组
step3:此后每收到一个重复的ACK确认时,cwnd++
step4:当收到对新发送数据的ACK确认时,cwnd = ssthresh,这个ACK能够对那些在丢失的分组之后,第一个重复ACK之前发送的所有包进行确认。
可以看到最终,在进入拥塞避免的时候,cwnd是原来的一半。所以说,《自定向下》那本书上的图不对。在课件中找到这张图,画的比较准确。
小结:Tahoe每次丢包(超时)的时候,cwnd从1开始,并重新开始慢启动算法;Reno每次丢包(超时)的时候,cwnd从变为原来的一半。
TCP NewReno与SACK 运行机制对比分析
Reno算法的缺点:Reno快速恢复算法中发送方收到一个新的ACK就退出快速恢复状态。但是在传送过程中,可能有多个包丢失。因为Reno仅仅更正了第一个包丢失的错误。在进入拥塞避免后,可能还要给上次没有完全修正的错误擦屁股。可能导致累计的错误在增多,而窗口在减小。终究导致窗口减少不够Duplicate ACK,从而超时。New Reno算法:New Reno算法中只有当所有报文都被应答后才退出快速恢复状态。NewReno算法中有变量recover,其值为检测到丢包时的最大发送序列号。只有当recover之前的数据报都确认完后,才能退出快速恢复,进入拥塞避免阶段。New Reno算法的缺点:每一个RTT时间内至多重传一个丢弃的包。这个是累计确认的锅。因为累计确认机制,当接收方接收到第一个缺失的包后,ACK第二个缺失的包,直到ACK的值等于recover才退出快速恢复计算,进入拥塞避免阶段。SACK算法:可以进行选择重传和选择确认。传送端可以很明确地知道哪些封包已经被接收到了,并且直接针对遗失部分重传。灵活是有代价的,相对于3而言,正常情况要多传很多ACK。实验出来的New Reno的cwnd图和SAC的cwndK图看起来差不多。Simulation-basedComparisonsofTahoe,Reno,andSACKTCP 这篇论文里面有答案,但我没看。TCP Vegas和Reno运行问题分析
TCP Reno算法会有周期性遭遇封包遗失的问题。那能不能在将发送窗口维持在一个较高的值,避免周期性封包丢失。
TCP Vegas算法:Vegas根据预期传送率和实际传送率之间的差异值来调整cwnd的大小。
Diff=Expected-Actual= WindowSize/BaseRTT – Bytes Transmitted/Measured RTTBaseRTT=minimum of all measured RTTCongestion window:Linearly increases during next RTT, Diff<αLinearly decreases during next RTT, Diff>βUnchange
当Diff的值大于β值时,意味着传送的速率太快,因此应该减低cwnd的值以减缓传送的速率,反之当Diff的值大于α值时,则加大cwnd的值,以增加传送的速率。(Vegas的使用和TCP Reno大致相同,只是在使用时要另外再设置的α和β值)
但是Vegas算法可能会出现不公平现象:在同构型的环境下,当网络上持续都有其它流量存在时,较晚进入网络流量速率较低。有时候某些连接的cwnd可能总是会维持在一个较高的地方,有些则总是在比较低的地方。
当网络上同时有TCP Reno和TCP Vegas的时候。使用TCP Vegas的流量比较吃亏。这是因为TCP Vegas采取较为保守的避免封包遗失,并以此提高网络的执行效果。但遗憾的是,当TCP Vegas和Reno并存时,TCP Vegas并没有办法与TCP Reno公平地竞争频宽。造成这个问题的主要原因是,就比较而言,Reno使用了较具侵略性(Aggressive)的拥塞控制方法,TCP Reno的传送端会持续地将封包送到网络上直到发生拥塞。比较之下,Vegas的传送端在网络开始拥塞时就将传送端的传送速度降慢,以避免拥塞的情形发生。因此,当TCP Vegas与TCP Reno共存时,Vegas在效果上的表现总是会比较差。
相对于TCP Reno,为了补偿TCP Vegas,可以提高α和β的值 or 尽早的检测出拥塞。
计网中的相关论文
端到端的系统设计
End-to-end arguments in system design
Rethinking the design of the Internet: the end-to-end arguments vs. the brave new world
对《End-to-End Arguments in System Design》理解文章的整理
基于仿真的Tahoe,Reno和SACKTCP的比较
Simulation-basedComparisonsofTahoe,Reno,andSACKTCP
自组网路由协议综述
自组网路由协议综述 – 通信学报 – 2001年11月 – 史美林,英 春
802.11效果异常现象
基于N S2的802.1 1效果异常现象仿真研究 – 计算机时代 – 2月 – 马元飞,王顺利