TCP拥塞控制机制定量性能分析 毕业论文.doc

毕业设计（论文）题 目：tcp拥塞控制机制定量性能分析 指导教师： xxxx 职称： x教授 学生姓名： xxxx 学号： 专 业： 计算机科学与技术 院（系）： 信息工程学院 完成时间： 毕业设计（论文）任务书附表一 题目来源：指导老师推荐课题名称tcp拥塞控制机制定量性能分析设计人姓名学号xxxxxxx指导教师姓名、职称指导时间/地点每周2上午/ 新区教研室专业班级计算机8班一、设计（论文）内容l 了解ns2的体系结构；l 掌握ns2环境下，使用脚本语言otcl编制仿真程序的方法；l 了解tcp拥塞控制的工作机制，以及几种实现方法。l 在ns2环境下，编写脚本，模拟不同tcp拥塞控制方法。用模拟实例对三种拥塞控制方法进行性能分析。二、设计（论文）的主要技术指标l 熟悉ns2进行网络模拟的方法，深入理解tcp拥塞控制机制；l 要求用图表形式表示分析结果。l 对tcp拥塞控制机制有更深入的理解。并初步掌握ns2模拟方法，为将来应用ns2进行有益的探索，积累经验。l 按要求完成毕业设计任务，并提交下列内容： 毕业设计论文； 系统的源代码、安装运行环境说明； 系统使用说明书。三、进度安排第1周第2周：熟悉linux平台，学习其常用命令；了解ns的安装方法、运行和调试环境。第3周第4周：学习了解ns的体系结构；学习如何用脚本语言otcl编制仿真程序。通过实际编程，了解ns的工作情况。第5周第6周：学习网络知识，增强对网络传输协议的理解。参考ns说明手册，掌握在ns上实现网络协议动态模拟的基本过程。第7周第8周：编写简单的仿真程序，并实现在ns工具中的动态模拟过程。第9周 第10周：学习掌握tcp控制机制的原理及内容，并初步完成代码的实现。第11周第13周：实现代码，最终完成在ns工具下tcp拥塞控制的模拟实现，并对结果进行分析 。第14周第15周：完成毕业论文。四、毕业设计（论文）提交的文档及基本要求1毕业论文一份（包含封皮、目录、中英文摘要、内容及参考文献）2不少于5000汉字的科技翻译资料一份3、毕业论文简介（a4纸12页）（包含题目、专业、年级、姓名、指导教师、毕业论文所做的工作、解决的问题、创新之处等）4毕业设计任务书5开题报告6毕业设计工作中期检查表此表指导教师填后、复印，指导教师、学生各保存一份，交院教学办一份毕业设计（论文）开题报告附表二课题名称tcp拥塞控制机制定量性能分析学生姓名学号专业班级计算机8班一、选题的目的意义因特网最初源于美国国防部的arpanet，在过去的十几年中，因特网逐步发展成为互联全球的网络。从因特网诞生起网络拥塞就与其如影随形。随着信息传送量的逐渐增大和网络组成的日益复杂，网络发生拥塞的可能性也越来越大，网络拥塞问题正逐渐成为影响网络性能的重要因素之一，如果不对网络拥塞进行有效的控制和在网络发生拥塞时使网络恢复到正常状态，就会造成严重的网络拥塞。在因特网中，拥塞控制的大部分工作是由tcp来完成的。因此，tcp拥塞控制成为越来越重要和急待解决的问题，其相应的拥塞避免及控制算法的研究与改进也变得更加重要和急迫。二、国内外研究综述端到端的拥塞控制是目前internet的一个研究热点。在最初的tcp协议中只有流控制而没有拥塞控制，接收端利用tcp报头将接收能力通知发送端。这样的控制机制只考虑了接收端的接收能力，而没有考虑网络的传输能力，导致了网络崩溃的发生。为了解决网络拥塞问题，1988年，jacobson提出网络拥塞避免和网络拥塞控制理论，为此后网络拥塞控制的研究奠定了基础。在此之后，拥塞控制领域开展了大量的研究工作，研究实现了多种拥塞控制技术和拥塞控制算法。这些拥塞控制算法对保证internet的稳定具有十分重要的作用。三、毕业设计（论文）所用的方法本课题使用模拟方法来进行研究，即应用网络模拟软件ns2设计一个理论的网络系统模型，在计算机上运行这个模型，并分析运行的输出结果，以此来比较几种tcp拥塞控制机制在性能方面的优劣性。四、主要参考文献与资料获得情况1 李向丽，李磊，陈静等编著，计算机网络技术与应用，机械工业出版社，2006.82 谢希仁编著，计算机网络，第4版，电子工业出版社，2003年 3 林闯，单志广，任丰原等，计算机网络的服务质量，北京:清华大学出版社，2004. 04. 4 (美）tanenbauma.s.著. 熊桂喜译，计算机网络，第4版，清华大学出版社，2004年5 徐雷鸣, 庞博, 赵耀，ns与网络模拟，人民邮电出版社.，2003年6 /nsnam/ns/index.html五、指导教师审批意见这是一个理论与实验相结合的题目，对于选题者有较高的要求。不仅要理解各种拥塞控制算法的思想和实现思路，而且还需要学习新的操作系统，以及ns2模拟环境。不过，相信该同学一定能够按要求完成预定的任务。同意开题。签字： 2007 年 3 月 6 日毕业设计工作中期检查附表三 课题名称tcp拥塞控制机制定量性能分析姓 名专业和班级计算机8班指导教师 一、毕业设计具体内容、目标和可能遇到的问题具体内容：了解ns2的体系结构；掌握ns2环境下，使用脚本语言otcl编制仿真程序的方法；了解tcp拥塞控制机制，以及几种实现方法；在ns2环境下，编写脚本，模拟不同tcp拥塞控制方法。用模拟实例对三种拥塞控制方法进行性能分析。目标：熟悉ns2进行网络模拟的方法；深入理解tcp拥塞控制机制；要求用图表形式表示分析结果。可能遇到的问题：ns难于掌握，并且其机理也不易理解，在这种情况下很难编写出正确合适的tcl脚本来模拟不同的tcp拥塞控制方法。二、采取的研究方法、技术路线、实验方案及可行性分析进行网络协议的研究有很多研究方法，包括分析建模、实验测试和网络模拟等。它们各有其优缺点和适用范围。本文采用网络模拟的方法来研究网络协议。实验方案是理论与实践相结合，即在阅读大量的相关文献的同时，通过上机实践尽快熟悉ns2环境，以便早日能够编写出脚本来模拟几种tcp拥塞控制方法。方案是可行的，实验场地、设备和相关书籍都是非常齐全的，而且时间方面也是要保障的。三、指导教师对学生出勤、文献阅读等方面的评语能够按毕业设计进度认真完成相应的任务，并开始进行英文翻译工作。也阅读了指定的参考书，阅读了很多科技论文和研究生论文，并上网查阅了相关资料。作为本毕业设计小组的组长，尽心尽责，承担了很多联系和组织工作。签字： 此表学生填写，指导教师给出评语后，复印件于第五周交院教学办公室。毕业设计工作中期检查附表四 课题名称tcp拥塞控制机制定量性能分析姓 名专业和班级计算机8班指导教师一、阶段性结果1完成了两万多字的英文翻译。2对tcp拥塞控制机制也有了更深入的理解。3初步掌握了ns2模拟方法。二、存在的问题1对newreno和sack这两种tcp拥塞控制机制在个别细节上不是很理解。2对ns2模拟方法虽有了初步的认识，但要想编写出能够正确运行的tcl脚本还有些困难。三、后一步工作设想1仍需要多阅读有关tcp拥塞控制机制课题的文献，同时向老师多请教，一定要深入理解tcp拥塞控制机制。2在编写tcl脚本方面还需要更多的上机实践，要多与同学交流和沟通。3. 进一步抓紧时间，争取早日完成毕业设计。四、指导教师对学生出勤、论文进展方面的评语每周都能够召集本组学生讨论汇报工作，没有一次缺席见面会。课题的进展良好，基本实现了所规定的任务，对各种拥塞控制算法有了更深入的理解。英文翻译工作量大，基本完成了翻译工作，已经开始撰写论文。签字： 李向丽 指导教师组织学生口头汇报后，学生填写该表，教师给出评语后，于第十周交院教学办公室。tcp拥塞控制机制定量性能分析摘要：网络拥塞问题一直困扰着因特网，随着网络信息技术的迅速发展，新的网络应用对网络拥塞控制策略提出了更高的要求。目前，tcp协议承载着因特网超过70%的传输流量，tcp拥塞控制机制可以有效地改善网络拥塞现象。本文主要研究几种常见的tcp拥塞控制算法，借助于网络模拟器ns2，对这几种常用算法的性能进行定量分析，并给出相应的合理建议，以便改进算法，取得更好的网络性能。论文首先介绍了对tcp拥塞控制算法进行研究的必要性，接着阐述了tcp拥塞控制算法的相关基础知识，包括网络拥塞的定义、成因，以及tcp拥塞控制算法的思想。然后介绍了常用的tcp拥塞控制算法：tahoe、reno、newreno、sack和vegas tcp。并对这些拥塞控制算法进行了详细分析，剖析了这些算法对拥塞现象进行控制的机制，包括慢启动、拥塞避免、快速重传、快速恢复，以及加入pack (partial ack)和sack(selective ack)的快速恢复等等。为了比较这些算法的性能，在ns2网络模拟器环境下，我们以数据包丢失作为网络拥塞的信号，对tahoe、reno、newreno和sack算法进行了模拟实验。并且对仿真结果进行了分析和比较，结果证明：加入了pack和sack的快速恢复算法，可以使tcp更快地从网络拥塞中恢复到正常工作状态。最后，对tcp拥塞控制算法做了总结，并对将来的工作进行了展望。关键词：拥塞控制 慢启动 拥塞避免 快速重传 快速恢复quantitative analysis on the performance of tcp congestion control mechanismabstract: the internet has suffered from the long-term problem of congestion at all times. with the rapid development of information technology, more careful-designed network congestion control algorithm is required. according to the statistic collected in recent years, tcp carries over 70% internet traffic. and tcp congestion control mechanisms can improve congestion problem in the internet effectively. in the thesis, we research on several common tcp congestion control algorithms，analyze the performance of them quantitatively with the help of ns2(a network simulator),and give some reasonable suggestions in order to improve the algorithms and get better network performance.this thesis first introduces the necessity and importance of the network congestion control. and then, the thesis gives the basic concepts of network congestion, including the definition and cause of congestion and the thinking of tcp congestion control algorithms.then, the thesis introduces five common tcp congestion control algorithms: tahoe, reno, newreno, sack and vegas tcp, analyzes them in detail and discusses the congestion control mechanisms used in them, which are slow-start, congestion avoidance, fast retransmit, fast recovery, fast recovery with pack and sack.in order to compare the performance of these algorithms, we use the loss of packets as the signal of network congestion and do simulation on tahoe, reno, newreno and sack algorithms in the environment of ns2 network simulator. finally, we conclude that sack and newreno tcp perform better than reno and tahoe tcp, especially when multiple packets are dropped from a window of data. lastly, the thesis gives the conclusion and prospect.key words:congestion control slow start congestion avoidance fast retransmit fast recovery目录前言11绪论11.1 拥塞11.1.1 基本概念11.1.2 产生原因11.2 拥塞控制22tcp拥塞控制32.1 tcp协议简介32.2 tcp拥塞控制所要解决的主要问题42.3 tcp拥塞控制涉及到的参数42.4 tcp拥塞控制机制42.5 tcp拥塞控制算法52.5.1 tahoe52.5.2 reno62.5.3 newreno72.5.4 sack82.5.5 vegas92.6 tcp拥塞控制算法的特点92.7 tcp拥塞控制算法存在的主要问题92.8 tcp拥塞控制算法的改进103网络仿真软件ns-2113.1 ns-2简介113.2 使用ns-2进行网络模拟的方法和一般过程114仿真124.1 丢一个包情况下tcp实现的比较134.2 丢两个包情况下tcp实现的比较144.3 丢三个包情况下tcp实现的比较164.4 丢四个包情况下tcp实现的比较184.5 仿真小结205结论及今后的工作205.1 结论205.2 今后的工作21致谢22参考文献23附录24前言因特网最初源于美国国防部的arpanet，其最大特点是采用无连接的端到端的包交换服务。在过去的十年中，因特网逐步发展成为互联全球的网络，它使得用户在世界范围内进行通信成为可能。随着因特网的迅猛发展，它给人类社会带来了巨大的变革。但就在因特网深刻影响人类历史发展进程的同时，因特网自身的发展却面临着种种困难，其中之一就是网络拥塞。从因特网诞生起网络拥塞就与其如影随形。虽然因特网的相关技术日渐成熟，但网络拥塞却仍未很好解决，反而随着因特网的规模、用户和应用的急剧增加，网络拥塞问题日益突出。因此，如何进行网络拥塞避免及控制，提高网络服务质量是非常重要且亟待解决的问题。目前，端到端传输协议tcp承载着互联网的绝大多数业务，其拥塞避免和控制机制是保证因特网稳定性的重要因素，可以说，今天因特网的成功很大程度上得益于tcp拥塞控制算法的引进，因此，对tcp拥塞控制算法进行深入的研究具有重要的理论和应用价值。为了寻找拥塞控制的方案，科研工作者进行了不懈的努力:1988年jacobson针对tcp在网络拥塞控制方面的不足，提出了慢启动(slow start)和拥塞避免(congestion avoidance)算法；1990年出现的reno tcp版本则增加了快速重传(fast retransmit)和快速恢复(fast recovery)以提高tcp传输的顽健性；newreno tcp增加了恢复应答(recovery ack)以提高tcp带宽恢复能力等等。经过近二十年的发展，tcp拥塞控制算法己经拥有多个改进版本，tcp协议的传输性能也因此得到了不断的提高。在这样的背景下，通过某种途径对这些tcp拥塞控制算法进行分析比较，并针对比较过程中出现的问题进行研究以改善网络性能，就显得尤为重要。本文着重于深入理解几种常见的tcp拥塞控制算法，并针对拥塞控制算法暴露出的一些问题，提出合理的建议，以此来改善当前网络拥塞的状况。1绪论1.1 拥塞1.1.1 基本概念在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏，这种情况就叫做拥塞（congestion）。网络中发生拥塞，会导致吞吐量减小，如果用户仍不断提出对网络资源的需求，就会进一步增加网络的负担，严重时会发生“拥塞崩溃”(congestion collapse)现象。一般来说，拥塞崩溃往往发生在网络负载的增加导致网络效率降低的时候。1.1.2 产生原因拥塞发生的主要原因在于:网络提供的资源不足，以及网络资源使用不当，以至于不能满足用户对网络资源的需求。这些资源包括缓存空间、链路带宽容量和中间节点的处理能力等。下面将详细说明网络资源与网络拥塞的关系。(1) 存储空间不足。当一个端口收到几个输入端的报文时，接收的报文就会在这个端口的缓冲区中排队。如果没有足够的存储空间存储，当缓冲区占满时，报文就会被丢弃。适当增加存储空间可以缓解拥塞，如果过于增加存储空间，报文会因在缓冲区中排队时间过长而超时，导致源端重发，从而进一步加重网络拥塞。如图1-1描述了过多的分组访问同一个交换机的缓存所发生的拥塞现象。假设通信网络中节点2，3，5同时发送数据分组给节点1，且分组的聚合速率大于节点1往外发送分组的速率，则一定会有分组储存在节点1的缓冲区，若这种情况持续较长时间的话，节点1的缓冲区会被占满，随后的分组就被丢弃。当目的端发现有分组丢失时，要求源端重发，这样更多的分组涌向节点1，从而更加重拥塞。（2）带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道带宽最大值，即信道容量可以这样计算：c=blog2(1+s/n)(n为信道白噪声的平均功率，s为信源的平均功率，b为信道带宽)。所有信源发送的速率r必须小于或等于信道容量c。如果rc，则在理论上无差错传输就是不可能的，并会在网络低速链路处形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。（3）处理器处理能力弱、速度慢。如果路由器的cpu在执行排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速cpu也会产生拥塞。要避免拥塞的发生，对以上3点原因需综合考虑，合理分配和使用网络资源。例如，提高链路速率而不增强处理器的处理能力，只会转移网络瓶颈，而不能避免拥塞。所以拥塞往往也是网络系统各部分资源不匹配、不协调的结果。拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存，它就必须丢弃新到的数据包。当数据包丢弃时，源端超时计时器会超时，要求重传该包。由于没有得到确认，源端只能保留数据包，结果缓存会进一步消耗，加重拥塞。因此，拥塞控制是一个动态的、全局性的复杂过程，涉及到所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。1.2 拥塞控制为了最大限度地利用资源，使网络工作在轻度拥塞状态是最为理想的，但这增加了滑向拥塞崩溃的风险，因此需要一定的拥塞控制机制来加以约束和限制。为了便于阐述拥塞控制机制的内涵，我们首先用图1-2来描述拥塞现象。当网络负载较小时，吞吐量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一点称为knee。如果负载继续增加，路由器就开始丢包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为cliff。拥塞控制机制包含拥塞避免(congestion avoidance)和拥塞控制(congestion control)两种策略。前者的目的是使网络运行在knee附近，避免拥塞的发生；而后者则是使得网络运行在cliff的左侧区域。前者是一种“预防”措施，维持网络的高吞吐量、低延迟状态，避免进入拥塞；后者是一种“恢复”措施，使网络从拥塞中恢复过来，进入正常的运行状态。拥塞控制能够有效地预防死锁的发生，提高网络的性能，其作用不言而喻。在下一章节，我们将详细介绍tcp拥塞控制机制。2tcp拥塞控制2.1 tcp协议简介tcp(transmission control protocol)协议是完成端到端信息传输的传输层协议，是tcp/ip协议族的重要成员。tcp协议主要由差错控制机制和拥塞控制机制组成，它能够自动适应网络状况的变化。tcp协议引入差错控制机制的目的是保障端到端传输的可靠性，为无连接的ip网络提供基于连接的传输服务。tcp拥塞控制机制的意义更为重大，它可以根据网络状况对发送速率进行调节，避免拥塞的扩大，这使得互联网络的正常运行成为可能。它所采用的拥塞控制算法本质上是一种窗口上限可变的滑窗(sliding-window)式流量控制方法，是对滑窗流控算法的继承和发展。传统的滑窗式流控算法的窗口上限是固定的，发送端每发送一个报文其发送窗口减小一个单位，而每接收到一个报文的确认，发送窗口增加一个单位，这样终端在一个轮次中能够发送报文的最大个数是确定的，因此，在链路带宽充足的情况下，发送端的传输能力将受到发送窗口上限的限制。tcp流控算法对传统的滑窗算法进行了扩展，根据网络状况对窗口上限进行调节。在tcp算法中，窗口上限由发送端的发送窗口和接收端的通知窗口共同决定(取两者中的最小值)。这样，在网络正常工作时，tcp发送端可以通过增大窗口上限尽可能多地占用网络空闲带宽；而当网络发生拥塞时，tcp发送端可以通过减小发送窗口上限的方式降低发送速率，从而起到缓解拥塞的作用。2.2 tcp拥塞控制所要解决的主要问题要改善tcp传输的稳定性，减少拥塞的发生，或者要与非标准tcp应用在同一网络中共存，采取一定的tcp拥塞控制机制是必要的。tcp拥塞控制需要解决的主要问题有:第一、满足低的报文丢弃率的要求，提高带宽利用率。第二、高tcp传输的稳定性，减少网络状态的振荡。第三、保证tcp公平，即tcp友好特性。2.3 tcp拥塞控制涉及到的参数tcp拥塞控制机制是通过控制一些重要参数的改变来实现的。用于tcp拥塞控制的参数主要有:(1)拥塞窗口(cwnd)：是拥塞控制的关键参数。它描述发送端在拥塞控制情况下一次最多能发送的数据包数量。(2)通知窗口(awnd)：是接收端给发送端预设的发送窗口大小，它只在tcp连接建立的初始阶段起作用。(3)发送窗口(win)：是发送端每次实际发送数据的窗口大小。(4)慢启动门限(ssthresh)：是拥塞控制中用来限制发送窗口大小的门限值，它是慢启动阶段和拥塞避免阶段的分界点，初始值设为65535字节或awnd的大小。(5)回路响应时间(rtt)：一个tcp数据包从发送端发送直至发送端收到确认的时间间隔。(6)重传超时时长(rto)：描述数据包从发送到失效的时间间隔，是判断数据包丢失与否、网络是否拥塞的重要参数，通常设为2rtt或5rtt。下面将介绍tcp拥塞控制机制是如何改变上述参数以达到控制网络拥塞、提高网络性能的目的的。2.4 tcp拥塞控制机制tcp的拥塞控制机制是由慢启动、拥塞避免、快速重传和快速恢复四个核心算法组成的。慢启动阶段用于快速探测并占有网络可用带宽；拥塞避免阶段是数据传输的主要时段；快速重传则完成了丢失报文的重传；而快速恢复避免了由于过度地减小发送窗口而导致网络性能下降的发生，使得网络迅速从拥塞状态中恢复。图2-1描述了tcp拥塞控制中慢启动和拥塞避免两个阶段的动态情况。有关它们的具体实现将在下一节详细阐述。2.5 tcp拥塞控制算法tcp协议经过多年的发展，有了多种具体的实现，其中包括tahoe、reno、newreno、sack和vegas tcp。运行在主机中的这些实现使得tcp连接在网络发生拥塞时回退，并对网络中的拥塞信号进行响应，正是这些改进的tcp实现的拥塞避免和拥塞控制算法防止了今天网络的拥塞崩溃。下面详细介绍这些tcp实现以及运用于这些实现中的拥塞避免和拥塞控制算法。2.5.1 tahoetahoe算法是最早被提出来的tcp拥塞控制算法，虽然已历经近二十年，但至今仍被大多数tcp实现所采用。它的一些经典理论也被后来的大多数tcp拥塞控制算法所沿用，为后继算法奠定了基础。其核心思想是让cwnd以指数型增长方式迅速逼进可用信道容量，然后慢慢接近均衡。tahoe包括慢启动、拥塞避免和快速重传三个部分。(1)慢启动 初始时，cwnd值设置为1，每收到一个成功的ack，则：cwnd = cwnd + 1理想情况下，在一个rtt内，发送端会收到cwnd个成功的ack。这样，每隔一个rtt:cwnd = 2*cwnd即在慢启动阶段，cwnd以指数型增长，直到cwnd超过ssthresh值。当cwnd=ssthresh时，tahoe进入拥塞避免阶段。慢启动的目的是避免连接建立时大量突发数据流可能造成的拥塞。(2)拥塞避免 在拥塞避免阶段，每收到一个成功的ack，则：cwnd = cwnd + 1 / cwnd因此，每隔一个rtt， cwnd增1。即在拥塞避免阶段，cwnd线性增加。如果发生超时或者连续收到3个重复的ack（简称dup ack），tahoe就认为网络发生了拥塞。对于超时，ssthresh = max(cwnd/2，2)cwnd =1然后转入慢启动。若是收到连续3个dup ack，则tahoe进入快速重传阶段。可以看到，当算法进入拥塞避免阶段后，拥塞窗口的增长趋于平缓，避免了拥塞窗口持续快速增长可能导致的拥塞。(3)快速重传 在此阶段，首先立即重发丢失的分组，而不必等待重传定时器超时，同时设置:ssthresh=max(cwnd/2，2) cwnd =1然后，转入慢启动阶段。快速重传加快了算法的响应速度，减少了重传超时的发生。tahoe核心算法可简单描述为:for every ackif cwnd ssthresh thencwnd+ /慢速启动else cwnd +=1/cwnd /拥塞避免for every loss /快速重传ssthresh =max(cwnd/2，2)cwnd=1tahoe算法的提出使得tcp由以前的单纯流量控制转向拥塞控制，它明确地将tcp数据流的发送过程划分为三个阶段，慢启动避免了连接建立时突发数据流对网络的冲击；拥塞避免限制了在传输过程中无限制的速率增长，避免了由此可能导致的拥塞；快速重传则加快了发送端对拥塞的响应速度，使得拥塞能快速地消除。2.5.2 renoreno算法是对tahoe的改进，从上一小节我们可以看到，在收到连续3个dup ack或在超时的情况下，tahoe设置cwnd为l，然后进入慢启动阶段。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。针对这个问题，1990年jacobson在tahoe的基础上提出了reno算法。reno算法对tahoe的改进主要在两个方面。第一，收到连续3个dup ack后，算法不经过慢启动，而直接进入拥塞避免阶段。第二，增加了快速重传/快速恢复(fr/fr)机制。事实上，每一个dup ack表明已经有一个数据包离开了网络，不管它是不是我们所期望的。根据jacobson的数据守恒理论(见2.5.3小节)，发送端这时可以向网络发送下一个数据包。快速重传/快速恢复机制就是这样做的。具体过程为:(1)收到3个dup ack进入fr/fr ssthresh =max(cwnd/2，2)(2)重发丢失的数据包(3)窗口膨胀cwnd =ssthresh + ndupndup为收到的dup ack数。(4)当min(awnd， cwnd)足够大时，发送新的数据包(5)当收到非重复的ack时 cwnd =ssthresh(6)转入拥塞避免阶段经过分析，可以看出：reno在收到3个dup ack后，就转入fr/fr，而遇到超时后，reno和tahoe一样进入慢启动阶段。可以从reno状态转换图直观地看到reno的整个数据传输过程。reno目前被广泛采用，以其算法的简单、有效和鲁棒性成为tcp拥塞控制算法的主流。针对reno的局限性，一些新算法如：newreno，sack等对其进行了改进。2.5.3 newrenoreno tcp提出的快速恢复算法提高了报文丢失后tcp的吞吐量和顽健性，但是它仅考虑了每次拥塞发生时只丢失一个报文的情形。然而在实际网络中，一旦发生拥塞，路由器会丢弃大量的报文(对于采用drop tail的路由器而言，丢弃尤为严重)，tcp在一次拥塞中丢失多个报文的情形非常普遍。在这种情况下，采用reno tcp算法的发送端多次将cwnd和ssthresh减半，其结果是tcp的发送速率呈指数降低，系统吞吐量急剧下降，更有甚者，当发送窗口小于4 时无法有效地触发快速重传，reno tcp发送端会陷入仅通过传输超时来发现报文丢失的困境中。newreno在reno的基础上对快速恢复算法进行了修改，添加了恢复应答(recovery ack)判断功能，以增强tcp发送端通过ack报文信息分析报文传输状况的能力。newreno使tcp发送端可以把一次拥塞丢失多个报文的情形与多次拥塞的情形区分开来，进而在每一次拥塞发生后拥塞窗口仅减半一次，从而提高了tcp的顽健性和吞吐量。 恢复应答(recovery ack) 改进的快速恢复算法为了介绍newreno中改进的快速恢复算法，首先定义部分应答(partial ack，简称pack)和恢复应答(recovery ack，简称rack)报文。把tcp发送端恢复阶段中接收到的ack报文（非dup ack)记为ackx，在接收到ackx时tcp终端己发出的序列号(sn)最大的报文记为pkty，如果ackx不是pkty的应答报文则称报文ackx为部分应答，即pack报文；反之，若ackx恰好是pkty的应答报文，则报文ackx被称为恢复应答，即rack报文。tcp发送端接收到恢复应答表明：经过重传，tcp发送端发送的所有报文都己经被接收端正确接收，网络已经从拥塞中恢复。经过newreno改进的快速恢复算法可以描述为以下几个步骤:1. 重新定义“恢复阶段”，这里把从快速重传算法发现丢失报文到tcp发送端接收到rack报文的时段称为恢复阶段。2. 进入恢复阶段后，tcp发送端重传被认定为丢失的报文，并分别设置ssthresh和cwnd如下：ssthresh =max(cwnd/2，2) cwnd = ssthresh + 3*smss3. 当接收到dup ack后，tcp发送端按照式子cwnd =ssthresh + ndup对cwnd进行设定(与reno tcp的设定方式相似)。4. 当接收到pack后，tcp发送端立即重传pack所确认报文的下一个报文，拥塞窗口不受影响。5. 当接收到rack后，tcp发送端认为拥塞中所有被丢弃的报文均已被重传，拥塞结束，设置cwnd为发生拥塞时的cwnd的一半，最后退出恢复阶段，进入拥塞避免阶段。快速恢复是基于“数据包守恒”原则(conservation of packets principle) 的，即同一时刻在网络中传输的数据包数量是恒定的，只有当“旧”数据包离开网络后，才能发送“新”数据包进入网络。重传丢失的数据包后，不从慢启动开始的原因是，一个dup ack不仅意味着有一个包丢失了，而且表示有一个被发送的数据包离开了网络，己经在接收端的缓冲区中，它不再占有网络资源。2.5.4 sacksack tcp也是对reno tcp的扩展，在reno tcp的基础上增加了选择确认sack (selective acknowledgments)和选择重传(selective retransmission)。当一个窗口内有多个数据包丢失时，sack tcp增加了sack选项，允许接收端在ack中报告其接收到的不连续(no-sequential)的报文，这样，发送端就能准确地知道哪些数据包被接收端正确地接收。发送端使用选择性重传机制，可以在一个窗口中一次重传所有从一个窗口中丢失的数据包，从而减少了时延，提高了网络吞吐量，也使得tcp更快地从拥塞状态恢复。同样是一个窗口丢多个包的情况，如果没有sack，发送端或者在每个rtt的时间内最多只能重传一个丢失的包，或者连那些己经被正确接收的报文一起重传。reno tcp和newreno tcp采用的是第一种策略，而tahoe tcp则采用了第二种。为了详细介绍sack tcp，先引进两个概念：pipe变量和数据结构scoreboard。pipe的值为tcp发送端发出的未被确认的数据包数的估计值；数据结构scoreboard被保存在发送端，用来记录上一个sack选项中记录的确认报文。经过sack tcp改进的快速恢复算法如下:1. 在快速恢复阶段，只有当pipe的值小于cwnd时，发送端才发送新数据包或重传丢失的数据包。发送端发送或重传一个数据包后，pipe值加1；收到一个包含有sack选项用以报告新的数据被成功接收的dup ack后，pipe值减1。2. 当发送端可以发送数据包时，它根据scoreboard重传丢失的数据包，如果没有数据包丢失，则发送新的数据包。3. 如果发送端收到pack，pipe值减去2。因为pack表示两个数据包离开了网络，一个是丢失的数据包，另一个是重传的数据包。4. 当发送端收到rack后退出快速恢复阶段。2.5.5 vegasvegas tcp与上述算法有很大不同，它根据tcp连接中的回路响应时间rtt值的改变情况来控制cwnd的大小。如果发现rtt变大那么就认为网络发生拥塞，并开始减小cwnd；如果rtt变小，vegas就认为网络拥塞正在解除，则相应增加cwnd。vegas的最大优点在于拥塞机制的触发只与rtt的改变有关，而与数据包的具体传输时延无关。vegas采用的重传策略也与tahoe、reno不同。vegas能更加及时地重传丢失的数据包，它不是等到连续收到3个dup ack后才进行重传，而是当收到第一个dup ack后，比较数据包发出的时间和当前时间，然后决定是否重发，这就明显提高了响应速度。当达到均衡时，vegas具有零丢包率、稳定的窗口大小、满负荷使用效率等优点。但是vegas tcp并未能在互联网上大规模使用，主要原因是使用vegas tcp的流在带宽竞争能力方面不及未使用vegas tcp的流，从而导致网络资源使用不公平，而不是算法本身的问题。2.6 tcp拥塞控制算法的特点tcp算法最根本的特点是通过累积确认(cumulative acknowledgement)的方式获知已发送报文的传输情况，通过加增大乘减小(additive increase multiplicative decrease，即aimd)的拥塞控制策略对发送流量进行调节以避免拥塞的发生。累积确认方式使得tcp通信过程具有显明的周期性：tcp发送端在发送窗口允许的范围内尽可能地发送报文，在发送窗口闭合后则暂停发送处于等待状态，直至下一个轮次发送的开始。这种发送报文等待确认再发送报文的过程被形象地称为自时钟(self clock)。总之，tcp算法通过窗口增长探测网络可用的传输带宽，当传输出现报文丢失时，tcp算法即认为发送速率己经超过网络可用带宽，此时的发送速率将被作为以后速率调整的参考。tcp算法通过累积确认发现报文丢失，一旦发现有报文被丢弃，tcp终端将下调发送速率，直到丢弃报文被成功传输为止。这样的特性使得tcp的发送速率的变化具有周期性，同时也为tcp吞吐量的分析提供了便利。2.7 tcp拥塞控制算法存在的主要问题tcp拥塞控制机制在互联网中发挥了行之有效的作用，但tcp拥塞控制算法自身存在的问题也是不容忽视的:(1)端系统从发生拥塞到实施控制之间有着明显的时延，而且端系统缺乏对数据传输过程的动态性了解，无法预知网络资源的使用情况，目前主要是通过降低发送到网络的数据流量来减小网络负载，从而缓解拥塞。(2)慢启动算法中存在的问题尤为突出。首先，由于在慢启动阶段发送端无法了解瓶颈链路带宽，每个rtt内都会将cwnd增加一倍，如果ssthresh较大，那么发送端窗口增加到足够大时，会丢失接近一半的数据包；其次，慢启动是按照事先设定好的参数开始数据传输的，cwnd和 ssthresh一般分别取1个和64个数据包大小，tcp连接在经历拥塞后也使用慢启动算法重新开始通信，在网络可用带宽较大时，会造成网络资源利用率降低及延迟增加；再次，tcp基于窗口的拥塞控制机制对于传输大批量文件具有良好的适应性，但是为www应用等短小数据流服务时性能较差，往往需要几个rtt时间探测合适的网络带宽，传输延迟较大。(3)公平性问题。internet采取的基于源端的拥塞控制策略是不公平的，tcp拥塞控制中的公平性问题主要表现在以下两个方面:1)tcp中拥塞窗口大小可以表示为rtt的函数，比如，慢启动阶段cwnd随rtt呈指数增长，拥塞避免阶段cwnd随rtt线性增长，这样对于长延迟的连接来讲，由于其窗口增长速度慢，因而在同样的条件下获得的带宽也就越少，特别是在慢启动过程中，rtt长的连接的劣势就表现得更为明显；2)tcp提供端到端的可靠传输服务，在检测到拥塞后会自觉地降低发送速率，随着网络中不遵守tcp协议的各种数据流的出现，tcp流在与这些数据流共存时，其竞争力较弱，往往会丧失应有的带宽，因此公平地共享带宽也是一个需要迫切关注的问题。针对以上tcp拥塞控制中存在的问题，近年来，许多科研人员对这些问题进行了方方面面的研究和改进，以便更好地符合各种网络应用的需要，适应网络动态变化的特性，使网络运行在最佳状态。2.8 tcp拥塞控制算法的改进对于tcp拥塞控制存在的问题，目前主要针对以下几个方面进行了改进:(1)针对不必要的超时重传和快速重传当前的tcp应用主要有两种重传机制：快速重传和超时重传。当tcp发送端收到3个ack确认信息时就会触发快速重传机制，此时发送端重传丢失的数据包并且将cwnd减半。这种情况下，tcp流往往能够很快从丢包中恢复过来，重新回到原先的发送速率。但如果tcp发送端没有收到3个ack信号，例如cwnd值小于4，那么tcp发送端则需要等待相当长时间，以便超时重传。这样，小窗口的tcp流就很容易陷入不必要的超时重传，使其吞吐量大大下降。为了避免这种不必要的超时重传，一种改进办法就是只要tcp发送端收到一个或两个ack信号，并且如果通知窗口awnd允许，便继续发送新的数据包。这是因为只要收到ack信号，就表明有数据包已经离开网络被接收端接收了，而此时发送端还无法判断数据包是否被丢弃，根据“数据包守恒”原则，发送端就可以继续发送新的数据包。(2)针对乱序包和延迟包引起的重传在不少情况下，tcp发送端推断认为数据包被丢弃了，例如超时计时器过早到时了(事实上数据包或者ack并没有丢失，只要再等待一会便可收到)，发送端便毫无必要地重传了数据包，而实际上数据包并没有被丢弃。类似地，如果由于数据包的乱序导致发送端接收到3个ack信号，便会触发快速重传，tcp源端也没有必要地重发了数据包，并减小了拥塞窗口，对于前者，虽然可以通过更为精确地调节超时时钟来减少不必要的超时重传，但要完全避免却是不可能的。同样，对于后者，虽然可以通过提高快速重传算法的性能来减少不必要的快速重传，但也不可能完全避免。为了使得在不必要的超时重传和快速重传情况下，tcp性能更加具有鲁棒性，一种方法就是出现这些情况时向tcp发送端反馈有关的信息。这个工作已经由d-sack扩展(duplicate-sack extension)完成了。d-sack扩展允许tcp接收端利用sack选项来通报已收到的重复的数据包，从而tcp发送端能够正确地推断出接收端是否收到了重复的数据包，以此来避免不必要的重传。由此可见，目前还没有一种tcp拥塞控制算法的设计和实现在所有的环境中都是“最好的”。现有拥塞控制的思路、方法和技术在不同环境中面临着挑战，它们还有许多需要改进的地方。3网络仿真软件ns-2 由于网络的复杂性，目