毕业设计（论文）-TCP拥塞控制算法研究.docx

南京邮电大学 毕 业 设 计（论 文）题 目TCP拥塞控制算法研究专 业网络工程学生姓名班级学号指导教师指导单位物联网学院 日期：2017年1月15日至2017年6月16日毕业设计（论文）原创性声明本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 月 日摘 要随着互联网的发展，TCP（Transmission Control Protocol）的使用场景也越来越多，TCP协议最初实现为一个停等协议，即发送端发送数据报文段，接收端回送确认报文段，随着越来越多对实时性要求较高的应用的出现，简单的停等协议已经不能满足日常需求，TCP拥塞控制研究变得越来越重要。TCP拥塞控制通过cwnd来控制数据报文段的发送速度，cwnd（congestion window）即当前能够发送但还未收到确认报文段的报文的数量。本文通过研究Reno算法、CUBIC算法和BBR（Bottleneck Bandwidth and Round-trip）算法并对这三种算法进行仿真，通过仿真来分析各算法的cwnd增长曲线以及各个算法的优劣势，进而分析各个算法的适用场景。Reno算法有“慢开始”、“拥塞避免”、“快重传”、“快恢复”四个阶段，通过收到重复的ACK（ACKnowledgement）报文段或者RTO（Retransmissino TimeOut）计时器超时来判断网络出现拥塞，然后对cwnd采取乘法减小加法增大的策略。CUBIC算法改进了Reno算法的拥塞避免阶段，通过一个三次函数来控制cwnd的增加。BBR算法不判断网络何时出现拥塞，而是通过跟踪当前网络的最大带宽来动态地调整cwnd。在仿真部分，本文通过基于Linux系统的Ubuntu系统和iperf模块搭建仿真平台，然后gnuplot工具将仿真得到的数据绘制成曲线图。仿真结果符合预期，Reno算法的带宽抢占性较弱，CUBIC算法的带宽抢占性较好，但是不稳定，BBR算法的拥塞窗口比较稳定。关键词：TCP协议；拥塞控制；CUBIC算法；Reno算法；BBR算法ABSTRACTWith the development of the Internet, more and more applications are using TCP (Transmission Control Protocol) as their forth-layer protocol. TCP is initially implemented as a stop protocol, that is, the transmitter sends data segment, the receiver echoes the confirmation section. As more and more applications using real-time transmission, a stop-wait protocol cannot meet the daily needs. Researches about TCP congestion control have become hotter and hotter. TCP congestion control uses cwnd (congestion window) to control the transmission speed of the data segment. Cwnd refers to the number of segments which are in flight. In this paper, we researched the Reno algorithm, the CUBIC algorithm and the BBR (Bottleneck Bandwidth and Round-trip) algorithm. And we simulated these three algorithms. The cwnd growth curve of each algorithm and the advantages and disadvantages of each algorithm were analyzed by simulation, and then the applicable scenarios of each algorithm were analyzed.Reno algorithm includes slow start, congestion avoidance, fast retransmission, fast recovery, by receiving duplicate ACK (ACKnowledgement) segment or RTO (Retransmissino TimeOut) timer timeout to determine the network congestion, and then cwnd take the AIMD strategy. The CUBIC algorithm improves the congestion avoidance phase of the Reno algorithm, and controls the increase of cwnd by a cubic function. The BBR algorithm does not care about when the network is congested, but dynamically adjusts cwnd by tracking the maximum bandwidth of the current network.In the simulation section, the paper builds the simulation platform through Ubuntu operating system based on Linux kernel and iperf module, and then the gnuplot tool draws the simulated data into a graph. Simulation results are in line with expectations, Reno algorithm bandwidth preemption is weak, CUBIC algorithm bandwidth preemption is better, but is unstable, BBR algorithm congestion window is relatively stable.Key words: TCP; congestion control; CUBIC algorithm; Reno algorithm; BBR algorithm目 录第一章 绪论11.1 课题研究背景和意义11.2 国内外研究现状11.3 主要研究内容和章节安排2第二章 TCP协议和TCP拥塞控制算法概述32.1 TCP协议简介32.1.1 创建连接32.1.2 数据传输42.1.3 TCP报文段的格式42.1.4 SACK52.2 TCP拥塞控制的历史62.2.1 拥塞的概述62.2.2 TCP拥塞控制算法举例82.3 本章小结9第三章 RENO算法简介与仿真113.1 TCP Reno算法的四个阶段简介113.1.1慢开始113.1.2拥塞避免113.1.3快速重传113.1.4快速恢复113.2 Reno算法研究123.2.1 慢开始阶段123.2.2 拥塞避免123.2.3快重传133.2.4快恢复133.3 TCP Reno算法仿真143.3.1 仿真工具简介143.3.2 仿真步骤153.3.3 仿真结果及分析153.4 本章小结16第四章 CUBIC算法简介与仿真184.1 BIC算法184.1.1 BIC算法的历史背景184.1.2 BIC算法内容184.2 CUBIC算法204.2.1 CUBIC算法的实现细节214.3 CUBIC算法的仿真264.4 本章小节27第五章 BBR算法简介与仿真285.1 BBR算法与传统的TCP拥塞控制算法的区别285.2 BBR算法的创新性285.2.1 BBR可以尽可能地避免排队285.2.2BBR算法的各个运行阶段305.3BBR算法的仿真315.4 本章小结33结束语35致 谢36参考文献37南京邮电大学2017届本科生毕业设计（论文）第一章 绪论1.1 课题研究背景和意义随着互联网的发展，像Abilene和RESNet这样的提供了从1Mbps到10Gbps带宽的网络环境正在扩展到世界各地的许多研究机构。这些网络遍布世界各地，互相之间距离很大，它们的往返延时可能超过200ms。高速互联网的发展推动了高性能计算的前沿技术的发展，这些技术需要访问大量的数据，同时它们需要高速的数据计算能力，像科学协作，远程医疗和实时环境监控从这些前沿技术都要求传输实时数据、图像和从远程传感器捕获的视频。这些应用中的大部分都用TCP作为它们的四层传输协议。然而，正如文献1-4中介绍的，TCP大大低估了这些高速连接上的网络利用率。TCP每隔一个往返时延（Round-Trip Time, RTT）将拥塞窗口（congestion window，cwnd）增加1，并且在发生丢包时将cwnd减小一半。如果按照最大传输单元（Maximum Transmission Unit, MTU）值为1500字节来算，TCP想要充分利用一个10Gbps的网络，需要至少83333个RTT，按照RTT为100ms来计算，那么至少需要1.5个小时才能充分利用一个10Gbps的网络，而且在这1.5个小时中，不允许发生丢包或者网络抖动。微调TCP参数，比如说接收窗口或者正如文献5-8中提到的网卡接收缓存区的大小可以减轻这个问题，还有一个解决方法就是文献9-12中提到的采用TCP的扩展选项，使用包大小选项，并且使用多个TCP连接。这样导致的一个问题是，TCP流的友好性会降低。TCP流的友好性是指，在与其他数据流竞争资源的过程中，TCP数据流不会过分地退让资源也不会一味地抢占资源。所以既要保证TCP流的友好性，又要保证一定的带宽利用率是一项十分有挑战性的工作。在认识到TCP的局限性之后，网络研究机构迅速做出回应，提出了几个新的协议，比如说高速TCP协议（High Speed TCP，HSTCP），可扩展TCP协议（Scalable TCP，STCP）。这些协议基于当前窗口来动态地调整cwnd增长趋势，当前的窗口越大，cwnd增长越快，在高丢包率的环境中表现出良好的友好性，在低丢包率的环境中表现出高可扩展性。研究TCP拥塞控制算法，可以在理解拥塞控制的根本原理的同时，通过控制cwnd的增长趋势，来达到更好的网络利用率，降低网络延时，这对当前互联网有着重要的意义。1.2 国内外研究现状自从互联网高速发展以来，TCP数据流一直占据主导地位，越来越多的应用进程选择TCP来做为它们的第四层协议，但是随着因特网的壮大，远距离数据传输越来越多，报文段的传输延时也越来越大，渐渐地TCP拥塞控制进入人们的视线13。TCP拥塞控制理论以Reno算法的四个阶段：慢开始、拥塞避免、快重传和快恢复四个阶段为核心阶段，基本思想为加性增加乘性减少（Additive Increase Multiplicative Decrease，AIMD）来调整cwnd14，以达到控制数据流的传输速度的目的。绝大部分的拥塞控制算法都是基于源端的控制，即TCP发送端会动态地根据cwnd来调整其发送窗口。要进行拥塞控制，首先要能感知到网络出现拥塞，TCP拥塞控制算法通过两个方法来感知网络拥塞，即报文段丢失或者是RTT增大。基于这两个方向，TCP研究者提出了很多算法。比如说基于丢包的BIC算法、CUBIC算法和基于RTT增减的BBR（Bottleneck Bandwidth and Round-trip）算法。1.3 主要研究内容和章节安排目前广泛应用的TCP拥塞控制算法都是基于丢包的拥塞控制算法，比如说大部分Linux内核采用的默认拥塞控制算法CUBIC算法。直到谷歌公司提出了基于RTT的动态探测带宽来调整cwnd的BBR算法之后，TCP拥塞控制算法进入了一个全新的领域。本文在介绍TCP协议的基础上，提出了TCP拥塞控制的概念和原理，深入研究了Reno算法，CUBIC算法和BBR算法对TCP cwnd的控制算法。然后利用基于Linux内核的Ubuntu系统和iperf内核模块对这三种算法进行仿真，观察其cwnd的变化情况，随后用gnuplot工具将收集到的数据绘制成曲线图，根据曲线图分析其带宽利用率以及友好性，看是否符合预期。本文第一章是绪论部分，介绍了TCP拥塞控制研究的背景和意义，以及国内外的研究现状，第二章简要介绍TCP协议以及拥塞控制的原理。第三章、第四章、第五章分别介绍了Reno算法、CUBIC算法和BBR算法以及对它们的仿真。38第二章 TCP协议和TCP拥塞控制算法概述2.1 TCP协议简介传输控制协议（Transmission Control Protocol, TCP）是Internet协议簇的主要协议之一，它起源于初始的网络实现，补充了因特网议（Internet Protocol，IP），是一种可靠的、面向连接的、基于字节流的传输层协议。在计算机网络操作系统互联（Open System Interconnection, OSI）模型中，它和用户数据报协议（User Datagram Protocol, UDP）协议一样，都是完成第四层传输层所指定的功能。在因特网协议簇中，TCP层位于应用层之下，用来在为应用层应用在主机间建立连接，应用层的数据向下递交给TCP层的时候，TCP层会对应用层数据进行分片、封装，然后继续向下递交给位于第三层的IP层，IP层并不提供可靠的数据传输机制。应用层向TCP层发送它需要在互联网上传输的数据字节流，然后TCP把数据字节流进行分片，分成适合在互联网上传播的报文段，这个报文段的长度受最大报文分段大小（Maximum Segment Size, MSS）的限制，通常MSS的长度受OSI七层模型中的第二层数据链路层的MTU的限制。之后TCP把数据包包向下发送传给OSI七层模型的第三层IP层，由IP层来通过网络将包传送给接收端的IP层。TCP会给每个包一个序号，这个编号保证了TCP协议的可靠性，根据这个序号，接收端可以将收到的报文段按照顺序重新组装起来，同时为了保证可靠性，TCP有用来防止丢包的机制，即接收端实体会对已成功收到的包发回一个确认（Acknowledgement, ACK）报文段，这个报文段有一个序号即ACK序号；如果发送端实体在一定的时间内内没有收到来自接受端的确认，那么TCP会认定对应的报文段已经丢失并且重传丢失的报文段。TCP用校验和函数来检验数据是否有错误；在发送和接收时都要检验校验和。TCP连接包括三个状态：连接创建、数据传送和连接终止。TCP通过三路握手来建立连接，在建立好的连接上通过每报文段的ACK来传送数据，保证数据传输的可靠性，通过四次挥手来终止连接。应用程序用TCP连接的套接字来调用TCP协议。2.1.1 创建连接TCP通过三路握手15的方式来创建一个连接。在连接创建过程中，会初始化很多参数，例如MSS被初始化来确保分片的正确进行，同时尽可能地减少数据在IP层的分片。TCP三路握手的过程如图1.1所示。图 1.1 TCP三路握手过程TCP连接通过三路握手来创建，通常是由服务端打开一个套接字然后监听来自客户端的连接，这就是通常所指的被动打开。服务器端开始监听来自客户端的连接之后，客户端就开始主动连接服务端监听的端口。（1）客户端通过向服务器端发送一个SYN（SYNchronous）报文段来创建一个主动打开，然后客户端进入SYN-SENT状态，同时客户端把这段连接的序号初始化为随机数M。（2）服务器端将接收到的SYN包发送给应用进程，如果报文段合法，服务器端会回送一个SYN/ACK报文段，然后服务器端进入SYN-RECEVIVED状态，该SYN/ACK报文段中包含确认码为M+1的ACK和序号为随机数字N的SYN。（3）最后，客户端再发送一个ACK。当客户端发送完这个ACK之后，就进入ESTABLISH状态，服务端收到这个ACK的时候，也进入ESTABLISH状态。2.1.2 数据传输在TCP在传输数据时，很多机制保证了TCP的强壮性和可靠性，这也是TCP协议区别于UDP协议最主要的地方。它们包括：对收到的TCP报文段根据其编号进行排序重组；使用校验和来检测报文段的错误；使用确认报文段来检测丢包；使用计时器来检测延时。下面分别论述一下这些特性是如何保证TCP的可靠性和强壮性的。2.1.3 TCP报文段的格式TCP报文段由TCP头部和数据部分组成，TCP头部包括10个必要字段和一个可选字段，必要字段为：占用16位比特位的源始端口、占用16位比特位的目的端口、占用32位的数据序号、占用32位的ACK序号、占用4位的数据偏移字段、还有占用9位的标志位和占用四位的保留字段，以及占用16位的窗口字段、各占16位的校验和字段和紧急指针字段，紧接着是TCP报文段的数据部分，格式如表1.1所示。表 1.1 TCP报文段的格式1161732源始端口目的端口数据序号确认序号偏移保留UAPRSF窗口字段包校验和紧急指针可选选项填充用户数据（1）序号和确认序号和确认的设计确保了TCP的可靠性。在TCP进行三路握手的时候，服务端和客户端会交换各自在这个TCP连接中的初始TCP序号，这个序号表示这个TCP报文段在整个应用层报文段中的位置，对于客户端来说，这个序号会被TCP用来重组接收到的报文段，重组后的报文段供应用层读取。（2）校验和TCP协议的设计初衷是在互联网上提供端对端的可靠数据传输，为了达到这个目的，TCP协议做了很多扩展，这些扩展预防了绝大部分在网络中可能出现的不可靠性。TCP的16位校验和就是用来对TCP报文段的头部和数据部分进行校验和检错，防止TCP报文段在传输过程中被篡改而接收端的TCP协议无感知的情况发生。TCP校验和的计算过程如下：发送者在发送报文段前，将报文段的头部和数据部分加总，然后对其求反码，将得到的结果填入报文段的校验和字段。接收端在接收到报文段以后，直接对报文段的头部，数据部分还有校验和字段加总，如果计算结果全部为1，那么说明报文段在传输过程中没有被篡改。2.1.4 SACK一个窗口内的多个报文段的丢失会影响TCP的吞吐量，TCP使用累计确认，即如果收到不在接收窗口左边缘的报文段就不会发送ACK报文段，这强制要求TCP等待一个RTT来找出丢失的报文段，否则会造成不必要的重传。累计确认会造成不必要的等待，降低TCP的吞吐率。选择确认（SACK）是用来修正这个错误的一个策略，通过SACK，TCP允许接收端只确认收到的报文段，然后发送端根据ACK报文段来确认哪些包丢失了需要重发。SACK扩展需要使用两个TCP选项，一个是启用选项，即“SACK permitted”，用来与对端协商建立允许使用SACK的连接。另一个是SACK选项本身。2.2 TCP拥塞控制的历史在上一章中，我们介绍了TCP协议的报文段格式和几个保证可靠性的重要概念，比如说用于建立连接的三路握手，可以防止报文段丢失的序号和确认号，以及可以防止报文段被篡改的校验和字段。最初的TCP设计只有这样，而且可以很好地为应用层提供服务，后来随着互联网的飞速发展，在Internet上传输的报文段越来越多，网络的负载也越来越高，但是TCP的设计初衷并没有考虑这些问题，只是一味地占用带宽，结果是链路中的报文段的队列越来越多，由于发生拥堵，网络的吞吐量会急剧下降，这个问题在1986年从美国LBL到UC Berkeley的数据吞吐量从32Kbps下降到40bps这件事情发生之后被重视起立，从此，TCP拥塞控制也成为了一个重要的研究课题。2.2.1 拥塞的概述在数据网络和排队理论中的网络拥塞是指，当网络节点传输的报文段超过其实际的处理能力后导致的服务质量急剧下降的现象。网络拥塞的结果是，当负载增量增加时，吞吐量增加很缓慢甚至下降，TCP协议会对超时的报文段进行重传，这样会使已经出现拥塞的网络更加拥塞。图 2.2 TCP报文段响应时间和吞吐量随负载的变化曲线图2.2展示了TCP报文段的响应时间和吞吐量随网络负载的变化曲线。从图中可以看出，当负载较小时，吞吐量基本上与负载呈线性关系增长，响应时间增长也很缓慢，但是当负载达到一定的值以后，吞吐量增长开始变得平缓，响应时间开始呈线性增长，当负载超过第二个转折点之后吞吐量甚至开始下降，但是反而响应时间骤增。TCP拥塞控制的目标就是通过控制TCP报文段的发送速度，使得网络的负载保持在第一个转折点附近，使网络的利用率达到最大化。TCP报文段中的窗口大小字段是接收端用来向发送端通告窗口大小的，发送端会根据这个字段来调整自己的发送窗口的大小，即发送端会考虑接收端的接收能力，并且根据接收端的接收能力来进行流量控制，而拥塞控制不同于流量控制的是，拥塞控制会考虑整个网络的情况，不单单是接收端的接收能力，还包括当前连接中网络设备的传输能力，当前网络的容量以及负载等等。显而易见的是，绝大部分的网络拥塞出现的原因都是因为网络中需要传输的报文段的数量超过了其本身能承载的报文段的数量，即“需求”大于“供给”。拥塞控制算法包括两个部分：拥塞避免和拥塞控制，前者用于避免拥塞，使得“需求”尽可能地接近“供给”，后者用于出现拥塞时进行恢复。本文后面所讨论的三个算法都是在用不同的方法来进行拥塞控制和拥塞避免。由于Internet发展飞速而且较为庞大，遍布世界各个角落，而网络环境千差万别，而TCP能通过报文段获取的信息很少，所以TCP拥塞控制并没有描述起来那么容易，具体原因可以分为下面四个方面：（1）当前互联网采用的是报文交换，报文交换不同于电话系统采用的电路交换。报文交换的中间设备会根据报文中的目的地址来路由报文段，这使得网络的可扩展性更好，所以，当前的互联网模型是分布式的。分布式就有一个问题，每个节点只能获得它需要知道的信息，对其他信息一无所知，所以TCP也只能根据这一点点信息来进行拥塞控制，调整发送速度。（2）互联网遍布世界各地，各个地方的网络环境千差万别，带宽可以从几兆到几百兆跨越十几个数量级，不同的网络环境瓶颈不一样，比如说有的网络是带宽较低，有的是因为物理层连接不好导致丢包严重，有的是因为网络拥塞严重导致延时较大，这就要求拥塞控制算法有较好的适应性，可以根据这几种情况动态地调整数据发送速度。（3）由于网络中传输的数据流各有不同，各种各样的数据流都在竞争网络资源，为了保证各数据流对带宽的占用尽可能地公平，防止一条连接不断地向链路中发送报文段把带宽占满而别的连接几乎无法发送数据的情况发生，同时TCP又希望拥塞控制算法可以尽快地收敛到合理的拥塞窗口，而不要因为害怕造成拥塞而一直以较低的速率发送报文段，造成网络利用率较低，所以TCP拥塞控制算法对算法的性能要求也很高，希望算法可以尽可能地保证网络利用率，各数据流之间资源竞争要尽可能地公平。（4）算法的开销要尽可能地小，TCP希望其拥塞控制可以尽可能少地占用计算资源，而把计算机的计算资源节省下来留给应用层应用，因为TCP仅仅是为应用层服务的，同时TCP还希望可以尽可能少地增加TCP额外需要传输的信息来实现拥塞控制，毕竟拥塞控制的最终目的就是使得网络的利用率最大化，而更多的额外的数据开销反而会降低网络的利用率。以上种种原因使得算法的设计尤其困难，但是迄今为止，TCP拥塞控制还是取得了不小的成就。TCP拥塞控制算法主要通过cwnd来控制数据的发送速度，TCP的发送窗口等于min(rwnd,cwnd)，其中接收窗口（receiver window，rwnd）是接收端通告的接收窗口的大小，发送窗口代表所允许的已经发送但是还没有被确认数据的多少。窗口值较大时，数据发送速度较快，但是过快的数据发送速度可能造成网络节点中队列的增大，或者网络中负载的增加，窗口值较小时，数据发送速度较慢，虽然不会造成队列增大或者负载增加，但是会降低网络利用率与数据的发送速度，TCP拥塞控制算法需要通过控制cwnd的大小来平衡两者之间的关系。2.2.2 TCP拥塞控制算法举例如上一小节提到的，尽管TCP拥塞控制算法的研究有很多限制，但是优秀的拥塞控制算法还是层出不穷。下面列举几个常见的TCP拥塞控制算法。（1）TCP Tahoe和Reno算法TCP Tahoe和Reno算法都是通过丢包事件来定义网络拥塞，当重传计时器（Retransmissino TimeOut，RTO）超时或者收到三个重复的ACK报文段时，Tahoe和Reno认为网络出现了拥塞。当RTO超时时，这两个算法都会重传超时的报文段，并且重新进入慢开始阶段，同时将cwnd置为1，但是当收到三个重复的ACK报文段时，这两个算法采取的策略不同：Tahoe进入快重传阶段，将当前的慢开始门限（slow start threshold，ssthresh）设为当前cwnd的一半，将cwnd减小为1，重新进入慢开始阶段；Reno算法用快速恢复阶段取代了Tahoe的将cwnd减小为1的阶段，主要策略是，当收到三个重复的报文段时，将ssthresh设为cwnd的一半，然后然后进入快速恢复阶段，快速恢复会重传丢失的报文段，然后等待所有已经发送但是没有被接收的报文段被确认后再进入拥塞避免阶段，如果在RTO超时时还没有收到ACK，那么进入慢开始阶段。（2）TCP Vegas算法21直到20世纪90年代初，所有的TCP拥塞控制算法判断拥塞都是基于丢包的，TCP Vegas采用另外一个角度来定义拥塞，即RTT的增加或者减少，当RTT增加时，TCP Vegas认为网络出现了拥塞，从而减小cwnd，降低报文段的发送速度，当RTT减小时，说明当前网络利用率还没有达到最大化，于是增大cwnd，加快报文段的发送速度，这样做很合理。但是TCP Vegas忽略了一个重要的问题，就是RTT增大的原因不仅仅只有网络出现拥塞，也有可能是因为网络中某一个节点缓存了报文段导致某一个报文段的RTT增大，或者是某一段链路的带宽较低。TCP Vegas算法相对于基于丢包的拥塞控制算法来说，竞争能力较弱，因为基于丢包的拥塞控制算法只要不发生丢包，就不会让出网络资源，但是不发生丢包时，RTT可能在增大，这在无线网络中尤其明显17，这个时候TCP Vegas相对于其他算法来说占用的带宽较少，竞争能力较弱，这个原因直接导致了TCP Vegas算法没有被广泛采用，但是当所有的数据流都是TCP Vegas时，TCP Vegas可以达到很好的公平性。2.3 本章小结本章通过介绍TCP协议的内容引出了TCP拥塞控制的概念和最终目的，进而引入了TCP拥塞控制的原理，通过控制cwnd的大小来动态地调整TCP报文段的发送速度，同时引入了ssthresh、cwnd、rwnd以及RTO的概念，指出TCP拥塞控制算法的两种类型，即基于丢包的算法和基于延时的算法。指出TCP拥塞控制算法的设计思想，即既要尽可能少地额外占用资源，又要尽可能准群地判断拥塞，而且算法还需要考虑其竞争能力，抢占性既不能太强，过多地占用其他数据流的资源，也不能太弱，让出太多网络资源。同时还讨论了TCP拥塞控制算法设计的难点，即当前互联网模型是基于报文交换的，即网络拓扑是分布式的，这样每一个节点只能得到自己路由报文段时需要的信息，而仅仅利用这些信息来设计一个稳定、快速而又友好的TCP拥塞控制算法来说是比较困难的。最后，本章列举了几个拥塞控制算法的实现原理，分别是基于丢包进行拥塞控制的的Tahoe算法和Reno算法以及基于延时进行拥塞控制Vegas算法。第三章 RENO算法简介与仿真3.1 TCP Reno算法的四个阶段简介3.1.1慢开始当应用层采用TCP传输协议初始化一个连接，并且通过TCP三路握手建立连接之后，该连接便进入慢开始18阶段。TCP三路握手过程中会初始化连接的序号和确认号，随后便进入慢开始阶段。慢开始阶段将cwnd初始化为1，并且每收到一个ACK报文段，cwnd便增加1倍，即cwnd呈指数形式的增长。当cwnd增长超过预定义的ssthresh或者发生报文段重传时，慢开始阶段结束，TCP连接进入拥塞避免或者快恢复阶段。当cwnd增长到超过ssthresh而导致慢开始阶段结束时，Reno算法会进入拥塞避免阶段，当由于发生报文段重传而导致慢开始阶段结束时，进入快速恢复阶段。3.1.2拥塞避免当慢开始过程中，cwnd增长超过ssthresh后，Reno算法进入拥塞避免阶段12。拥塞避免是一个慢收敛过程，通过每次使cwnd增加1来慢慢地探测网络最大容量，此时cwnd呈线性增长。当出现超时重传或者收到三个重复的ACK报文段之后拥塞避免阶段结束。3.1.3快速重传快速重传是对超时重传的改进。由于TCP是一个基于停等模型的协议，即发送端发送数据，接收端接收到数据之后回送对数据的ACK报文段，表示接收端已经正确接收报文段。TCP报文段的接收端在收到乱序的报文段时，会向发送端发送一个ACK报文段，这个报文段的ACK序号是到现在为止已经正确收到的报文段的序列号加1，这样，如果接收端收到乱序的报文段，发送端会连续收到重复的ACK报文段，当发送端收到三个重复的ACK报文段时，Reno算法会认为当前网络出现了丢包，相应的，Reno会认为当前网络出现了拥塞，随后立即重传丢失的报文段，并将当前的ssthresh置为cwnd的一半，随后进入快速恢复阶段19。3.1.4快速恢复快速恢复阶段是Reno算法相对于Tahoe算法新增加的功能，当因为收到三个重复的报文段而导致报文段重传的现象发生时，Reno进入快速恢复阶段而不是重新进入慢开始阶段，这样减少了cwnd的收敛速度，提高了网络利用率。在快速恢复阶段，置ssthresh=cwnd2、cwnd=sshresh+3，进入拥塞避免阶段。3.2 Reno算法研究3.2.1 慢开始阶段本文在第二章介绍TCP拥塞控制原理的时候引入了cwnd的概念，cwnd和rwnd共同确定了当前TCP的发送窗口的大小。本小节将讨论如何控制cwnd的增长。如何对网络容量进行初步猜测，进而确定cwnd的初始大小，同时又要防止一次性向互联网中发送过多的报文段，是Reno算法慢开始阶段的主要工作。Reno算法在慢开始阶段，首先置cwnd=1，然后每收到一个ACK报文段，将cwnd增加1倍，慢慢探测当前网络的容量，直到cwndssthresh，结束慢开始阶段，进入拥塞避免阶段。可以看出的是，慢开始阶段cwnd呈指数形式的增长，这个增长速度其实并不缓慢，可以使cwnd很快地增长到一个适合当前网络容量的一个值，但是这样的增长速度有一定的几率会给当前网络中的设备造成队列堆积。此时，TCP发送端会检测到拥塞，并且做出相应的策略。具体的策略是，当出现丢包时，ssthresh=cwnd/2，cwnd=1。Reno算法的慢开始阶段几乎是所有TCP拥塞控制算法都会经历的第一个阶段。3.2.2 拥塞避免从3.2.1节中针对Reno算法的慢开始阶段的探究中，可以看到，cwnd会呈指数形式增长，如果没有任何条件来阻止这个指数形式的增长，那么cwnd会一直增长下去，直到网络出现严重拥塞。这样以拥塞为代价来结束慢开始阶段显然是不可取的，Reno用ssthresh的概念来限制慢开始阶段cwnd的增长。当cwnd增长到cwndssthresh时，结束慢开始阶段，进入拥塞避免阶段。ssthresh是用户预定义的一个值。在拥塞避免阶段，cwnd呈线性增长，每经过一个RTT，cwnd增加1，开始加法增加。这样可以有效地避免cwnd增长过快而导致链路中间的网络设备的队列被填满，同时可以使cwnd慢慢调整到最佳值。Reno算法通过收到重复的ACK报文段或者RTO超时来判断网络拥塞现象是否发生23。当收到三个重复的ACK报文段或者RTO计时器超时时，Reno算法判断网络出现了丢包，即发生了拥塞，Reno算法会立即重传丢失的报文段，并且做出一系列的策略，来恢复拥塞。具体策略如下：（1）ssthresh=cwnd/2；（2）cwnd=1；（3）重新进入慢开始阶段。从整体上来讲，TCP拥塞窗口变化的原则是AIMD11原则，即加法增大、乘法减小。可以看出TCP的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半退避，可以给其他新建的流留有足够的空间，从而保证TCP的流间公平性。3.2.3快重传正如之前提到的，TCP有一个重要特征，即TCP ACK是累加的，接收端发送给客户端的报文段中的确认序列号代表这个序号之前（包括这个序号）的所有的报文段都已经被接收端正确地接收。试想一下这种情况，如图3.1所示，当接收端收到Data1时，Data3也到达了，因为接收端没有收到Data2，所以接收端只能给发送端发送另外一个ACK2，此时发送端就收到了重复的ACK。图 3.1 报文段重传示意图快重传采取的策略是，当发送端接收到超过3个由接收端发来的重复的ACK时，就会判定网络中有报文段丢失了，此时不用等待RTO超时就直接将报文段重新发送。因为不需要等待RTO溢出，所以叫快重传。3.2.4快恢复Reno算法是在Theno算法的基础上改进的，Reno算法在其基础上增加了快恢复算法。Theno算法的快重传阶段会将ssthread设为cwnd/2，同时将cwnd设为1。Reno的快恢复算法的原理是，利用Estimated FlightSize（EFS）的概念来衡量何时可以继续发送报文段，EFS即当前正在传输的报文段的个数。当当前的网络没有出现任何问题的时候，EFS的大小等于cwnd的大小，假设当前的cwnd是N，当某个发送窗口中有报文段丢失（在发送方看来就是收到3个重复的ACK包），EFS变为N-4，这个4包括一个丢失的报文段和3个已经抵达的报文段（这3个抵达的报文段触发了3个重复的ACK），然后由于TCP Reno算法中的快重传，所以TCP会立刻重传这个丢失的报文段，并且将当前的cwnd设置为N/2，然后每多收到一个重复的ACK，EFS增加1，直到EFS /tmp/tcpbbr.outRootubuntu:# iperf i 0.1 t 100 c 127.0.0.1 Z bbrRootubuntu:# gnuplog set terminal postscript eps set outpu “Reno.eps” plot “/tmp/tcpReno.out” using 1:4 titile snd_cwnd with lines EOF3.3.3 仿真结果及分析仿真所得到的原始数据如表3.2所示，仿真得到的拥塞窗口变化曲线如图3.3示。由仿真结果可以看出，除了开始的慢开始阶段窗口增长速度较快以外，其他时间的窗口增长速度都比较缓慢，出现丢包时窗口又乘法减小，导致后期的窗口大小一直保持在较低的0-15之间，这对TCP流的带宽占用是非常不利的，正如前文理论分析所示，TCP Reno算法的抢占性很弱，窗口收敛速度很慢，带宽占用率很低。表3.2 Reno算法仿真数据表格节选时间戳源地址目标地址cwnd大小7.120317308127.0.0.1:35184127.0.0.1:5001157.120384129127.0.0.1:35184127.0.0.1:5001177.170099916127.0.0.1:35184127.0.0.1:5001217.170130834127.0.0.1:35184127.0.0.1:5001237.170152994127.0.0.1:35184127.0.0.1:50012570.0.1:35184127.0.0.1:5001277.170191394127.0.0.1:35184127.0.0.1:5001297.170665946127.0.0.1:35184127.0.0.1:5001387.170732618127.0.0.1:35184127.0.0.1:5001407.170796696127.0.0.1:35184127.0.0.1:500161图 3.3 Reno算法cwnd随时间的变化曲线3.4 本章小结本章首先对TCP拥塞控制的Reno算法的四个阶段进行了理论研究，TCP先在慢开始阶段设置cwnd的初始值为1并且保持倍增的趋势，直到cwndssthresh时，进入拥塞避免阶段，当网络出现拥塞时，即当RTO超时时或者收到重复的ACK报文段时，前者将ssthresh减半，cwnd设置为1，并且重新进入慢开始阶段；后者则将cwnd减半，并且进入拥塞避免阶段。TCP Reno的拥塞避免阶段是一个线性增长的过程，每收到一个ACK报文段，cwnd增长1，使网络保持在一个良好的状态。当发送端收到3个重复的ACK报文段时，TCP认为网络中该ACK之后的报文段发生了丢失，由于快重传算法，TCP会立即重传这个丢失的报文段而不等待RTO超时。随后TCP进入快速恢复阶段。根据上面的分析做出的整个TCP拥塞控制阶段的cwnd 和ssthresh随时间变化的折线图如图3.2所示。据此，我们提出了Reno算法的优势与劣势，优势便是快速恢复阶段减小了窗口收敛速度，劣势是这个收敛速度还是不够快，因此致使的TCP Reno算法的抢占性较低，带宽利用率较低。第三小节，在仿真部分，我们用iperf模块观察了一个TCP Reno数据流的拥塞窗口的变化趋势，证实了我们之前的论证，在一个不稳定的网络环境中，TCP Reno算法的带宽占用率较低，主要体现在cwnd一直保持在一个不稳定的状态，而且大小一直保持在20以下。第四章 CUBIC算法简介与仿真4.1 BIC算法4.1.1 BIC算法的历史背景20世纪90年代中后期到21世纪以来，Internet得到了迅猛的发展，网络拥塞