1、ABSTRACT As the information tide spreads wide and the Internet blooms splendidly, the congestion of networks turns into a inevitable problem. Nowadays the basic infrastructure of networks is the suite of TCP/IP , so institutions mainly take a focus on TCP congestion control. The mechanism dynamicall
2、y adjusts the sliding window according to internal signs for the load of networks. TCP sender which is the source end-point accordingly shrinks the sending window in order to delay and control the congestion when detecting the rise of the congestion which takes packet loss as signals. The traditiona
3、l TCP congestion control mechanism comes into a challenge with the transformation of service types on networks. The thesis is centered on the Multi Phase algorithm, that is, the phase-divided asymptote algorithm. Firstly, the TCP versions including Tahoe, Reno, Vegas referred to have lack of flexibi
4、lity on parameters configurations and adaptive capability, so the proposal discussed adopts the bandwidth estimation based on the networks measurement which provides references for congestion control to meet requirements for fluctuation of networks capacity ; then, the exponential increase law in th
5、e slow start mechanism referred to takes an impact to networks streaming and results in the drain of available capacity, so the scheme advanced introduces the phase-divided asymptote algorithm to alleviate the sudden flooding transmit and avoid the frequent turns of the congestion; at last, the Mult
6、i Phase algorithm described above in some cases such as the download of Java Applet and Flash on Web pages it takes a low efficiency and a long wait, so the improvement brought forward amplifies the expanding extent of the congestion window in the control of increase key value resulting in adoptions
7、 to the demands of different service types and enhanced performance of transmission which is the tradeoff between fair and efficiency.The thesis takes an emulation experiment of the Multi Phase algorithm on the NS-2 simulator running under the Linux box. From an angle of determining the nature, the
8、algorithm put forward takes the expected effects and improves the capacity and efficiency, which is the most important, achieves the innovation to some extent.KEY WORDS TCP congestion control; slow start phase;bandwidth estimation; phase-divided asymptote algorithm绪 论 本课题来源于指导老师所进行的TCP协议的优化与改进研究。该研究
9、对当前网络环境下出现的突出问题进行了全面而详细的分析与检验。并且其在国际国内的研究成果上进行了对比与探索，提出了具有前瞻性的独创性意见，取得了阶段性的成果。 自从ARPNET诞生以后，全球的信息化步伐进一步加快，Internet的发展也以超乎想象的速度进行扩张。越来越多的联网主机加剧了网络资源的竞争与分配，这也直接恶化了网络服务质量，使得网络拥塞状况成为广泛为人关注的话题。在Internet上95的数据流都采用TCP/IP协议作为其通信手段的环境中，研究和改进TCP（Transmission Control Protocol）协议的拥塞控制机制无疑显得特别紧迫和重要。本课题要求广泛查阅资料，了
10、解TCP协议的基本原理及协议设计的基本方法和相关研究国内外发展现状，针对目前TCP协议算法的局限性，对TCP协议进行优化设计，并通过仿真实验加以验证。针对当前网络面临的实际问题，在着眼于Internet网络体系结构的分析下，进行了有益的探索。其一方面促进了课题研究者对于TCP协议设计与实现的深入理解，而另一方面也锻炼了学习能力与创新能力，从而使得研究者具备了从事相关领域研究的理论知识与实践才能。 经过十多年的发展，目前TCP协议主要包含有四个版本：TCP Tahoe、TCP Reno、TCP New Reno和TCP SACK。TCP Tahoe是早期的TCP版本，它包括了3个最基本的拥塞控制
11、算法“慢启动”、“拥塞避免”和“快速重传”。TCP Reno在TCP Tahoe基础上增加了“快速恢复”算法。TCP New Reno对TCP Reno中的“快速恢复”算法进行了修正，它考虑了一个发送窗口内多个数据包丢失的情况。在1994年，L.S. Brakmo等提出了一种新的拥塞控制策略TCP Vegas。由于RTT值与网络运行情况有密切关系，因此，TCP Vegas通过观察TCP连接中RTT值改变感知网络是否发生拥塞，从而控制拥塞窗口大小。 本课题要求进行TCP协议中拥塞控制算法的优化与改进研究。经过本次设计，要求设计者对TCP协议原理与设计以及网络仿真有一个较为全面的了解，熟悉Linu
12、x环境下C+、Tcl/Tk程序设计开发过程和技巧。通过目前网络研究中广泛使用的网络模拟器NS2，在 Redhat Linux 9.0环境中设计仿真实验与已有算法进行比较验证相关结论。开发平台：RedHat Linux 9.0；程序开发语言: C+,Tcl/TK； 针对目前Internet广泛使用的TCP协议存在的性能较低和抖动问题，利用当前网络测量研究的成果，无缝地引入到TCP协议中实现有效的传输控制，适当对TCP协议的慢启动、拥塞避免、快速重传、快速恢复等算法中的部分算法改进优化，实现网络性能。第一章 TCP 拥塞控制机制11 拥塞现象与控制111 拥塞现象的产生当网络中存在过多的数据包时，
13、网络的性能就会下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”（congestion collapse）现象。一般来说，拥塞崩溃发生在网络负载的增加导致网络效率的降低的时候。1986年10月，Internet遭遇了第一次“拥塞崩溃”事故1。在这个期间，由LBL到UC Berkeley的吞吐量从32Kbps跌到了40bps，而这两个地方的空间距离相隔了400英码，其站点则隔了两个IMP的转发距离。Floyd总结出拥塞崩溃主要包括以下几种：传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。 图1.1 网络负载与吞吐量
14、及响应时间的关系对于拥塞现象，我们2可以进一步用图1.1来描述。当网络负载较小时，吞吐量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一点称为Knee。如果负载继续增加，路由器开始丢包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为Cliff。112 控制阶段的划分TCP拥塞控制过程可分为四个阶段3：（1）慢启动阶段：旧的TCP在启动一个连接时会向网络中发送许多数据包，由于一些路由器必须对数据包排队，所以这样就有可能耗尽存储空间，从而导致TCP连接的吞吐量（throughput）急剧下降。避免这种情况发生的算法就
15、是慢启动。当建立新的TCP连接时，拥塞窗口（cwnd）初始化为一个数据包大小（一个数据包缺省为536或512bytes）。源端按cwnd大小发送数据，每收到一个ACK确认，cwnd就增加一个数据包发送量。很显然，cwnd的增长将随RTT呈指数级（exponential）增长：1个、2个、4个、8个。源端向网络中发送的数据量将急剧增加。（2）拥塞避免阶段：当发现超时或收到3个相同ACK确认帧时，网络即发生拥塞（TCP这一假定是基于由传输引起的数据包损坏和丢失的概率很小（小于1%）3）。此时就进入拥塞避免阶段。慢启动阈值（ssthresh）被设置为当前cwnd的一半，如果是超时，cwnd还要被置1
16、。如果此时cwnd ssthresh，TCP就重新进入慢启动过程；如果cwndssthresh，TCP就执行拥塞避免算法，cwnd在每次收到一个ACK时只增加1/cwnd个数据包（这里将数据包大小segsize假定为1），所以在拥塞避免算法中cwnd的增长不是指数的，而是线性的（linear）。（3）快速重传和恢复阶段：当数据包超时时，cwnd要被置为1，重新进入慢启动，这会导致过大地减小发送窗口尺寸，降低TCP连接的吞吐量。所以快速重传和恢复就是在源端收到3个或3个以上重复ACK时，就断定数据包已经丢失，重传数据包，同时将ssthresh置为当前cwnd的一半，而不必等到RTO超时。图1.2
17、和图1.3反映了拥塞控制窗口随时间在4个阶段的变化情况。图1.2 慢启动和拥塞避免（不含快速重传和恢复）图1.3 快速重传与恢复由以上分析可以看出：TCP使用的是一种和式增加积式减少（Additive Increase Multiplicative Decrease,AIMD）的基于窗口的端到端拥塞控制机制。TCP源端“发送速率”由拥塞窗口控制。如果有一个数据包丢失，发送窗口则要减半；否则就简单地增加一个数据包的发送量。大量的实践证明这种拥塞控制机制对Internet上大批量文件传输等尽量做好（best-effort）型服务具有较好的适应性。12 国外相关工作121 控制机制的发展：Tahoe
18、到Reno1988年Van Jacobson在文献1指出了TCP在控制网络拥塞方面的不足，并提出了“慢启动”（slow start）算法、“拥塞避免”（congestion avoidance）算法。1990年出现的TCP Reno版本增加了“快速重传”（fast retransmit）算法、“快速恢复”（fast recovery）算法，避免了网络拥塞不够严重时采用“慢启动”算法而造成过大地减小发送窗口尺寸的现象，这样TCP的拥塞控制就由这4个核心部分组成，这就是TCP Reno版本。事实上，在TCP Reno之前还有TCP Tahoe，两者主要区别在于后者只有拥塞控制的前三部分，没有快速恢
19、复（fast retransmit），所以可以认为TCP Reno是TCP Tahoe的改进版4。但TCP Reno算法仍有不足。首先，源端在检测到拥塞后，要重传自数据包丢失到检测到丢失时发送的全部数据包（即Go-back-n算法），而这中间有些数据包是正确传到接收端，不必重传的。另外，在大多数TCP实现中，RTO（Retransmit TimeOut）计数器的值被认为是RTT（Round Trip Time）的均值和方差的估计值的函数。而准确估计RTO和RTT值并不是一件容易的事。RTT最简洁的估计方法是应用旧RTT值和新RTT采样值的求加权和。如下式5： （1），其中为加权因子且。当接近1
20、时。估计的RTT值在最近采样的短时间内几乎不发生变化（例如一个经历长时延的数据包的RTT）。如果接近0，RTT对时延变化的反应就非常灵敏。理论上，RTT的测量比较简单。它只是数据包从发出到确认ACK返回源端的时间。但由于TCP使用的是用一个ACK确认所有已收到数据的“累积”确认方式，所以RTT的估计在实际中往往很复杂。122 新改进：New-Reno、 SACK和Vegas针对以上缺点，近年来又提出了一些改进算法，其中New-Reno和SACK都是改进版。SACK算法是在Reno基础上进行扩展，对数据包进行有选择地确认和重传。这样，源端就能准确地知道哪些数据包正确地传到接收端，从而避免不必要地
21、重传，减少时延，提高网络吞吐量。New-Reno没有选用SACK方法，而是尽力避免了Reno在快速恢复阶段的许多重传超时，利用一个ACK确认部分发送窗口，立即重传余下的数据包。显然,New-Reno只需修改源端代码。综合来看，即使源端不通过等待超时来恢复一个窗口数据中丢失的包，Reno和New-Reno在一个RTT内也至多只能重传一个丢弃的包。当然，Tahoe并不局限于此。然而这也说明缺乏SACK算法时,源端只能选择两种丢失数据的恢复策略：每一个RTT时间内至多重传一个丢弃的包，或者重传所有包，其中也包括可能已经正确发送的包。Reno和New-Reno使用第一种策略，而Tahoe使用第二种。S
22、ACK使用“管道”（pipe）变量表示在发送路径上损失的数据包的数量。用tcp remtthresh判断拥塞是否发生。由于RTT值与网络运行情况有密切关系，所以近几年又出现了利用RTT控制拥塞的Vegas67算法。Vegas就是通过观察以前的TCP连接中RTT值改变情况来控制拥塞窗口cwnd，如果发现RTT变大，Vegas就认为网络发生拥塞，并开始减小cwnd。另一方面，如果RTT变小，Vegas就解除拥塞，再次增加cwnd。这样，cwnd在理想情况下就会稳定在一个合适的值上。这样做的最大好处在于拥塞机制的触发只与RTT的改变有关。而与包的具体传输时延无关。在拥塞避免阶段，cwnd值由以下公式
23、决定： （2）其中，rtt是观察到的回路响应时间，base_rtt是所观察到所有rtt的最小值。和是两个常数。式（2）表明如果所有数据包的RTT稳定不变，拥塞窗口cwnd将不变。有研究通过仿真分析了Vegas实际的运行效果，由于它没有采用包丢失来判断网络可用带宽，而改以RTT的改变来判断，所以能较好地预测网络带宽使用情况，并且对小缓存（smallbuffer）的适应性较强，其公平性、效率都较好。但Vegas算法离在Internet上普遍采用还有距离。这倒不是算法本身问题，而是由于使用Vegas和未使用Vegas算法在竞争带宽方面不公平所致。13 慢启动算法评估131 面临的困难和问题拥塞控制算
24、法的困难8体现在以下几方面:（1） 算法的分布性.拥塞控制算法的实现分布在多个网络节点中,必须使用不完整的信息完成控制,并使各节点协调工作,还必须考虑某些节点工作不正常的情况.（2） 网络环境的复杂性.Internet 中各处的网络性能有很大的差异,算法必须具有很好的适应性.另外,由于Internet 对报文的正确传输不提供保证,算法必须处理报文丢失、乱序到达等情况.（3） 算法的性能要求.拥塞控制算法对性能有很高的要求,包括算法的公平性、效率、稳定性和收敛性等.某些性能目标之间存在矛盾,在算法设计时需要进行权衡.（4） 算法的开销.拥塞控制算法必须尽量减少附加的网络流量,特别是在拥塞发生时.
25、在使用反馈式的控制机制时,这个要求增加了算法设计的困难.算法还必须尽量降低在网络节点（特别是网关）上的计算复杂性.目前的策略是将大部分计算放在端节点完成,在网关上只进行少量的操作,这符合 Internet 的基本设计思想.人们可以把连接按由建立到终止所经历时间的长短分为长生存期和短生存期连接。有研究表明，当前互联网上数据传输大多数为短生存期连接（如Web页面点击），长生存期连接（如ftp下载）占少数。但是长生存期的连接却传送了大部分的数据量，而短生存期连接的特点是其传输过程往往在慢启动阶段终止。在互联网应用中，短生存期连接不但对带宽而且对延迟都比较敏感，这是由互联网用户的要求所决定的。于是可以
26、说，慢启动机制的性能决定了短生存期连接的传输时间和效率。而对于长生存期连接，慢启动机制只作用于连接建立阶段和分组传输超时而引起的重传阶段。当网络发生拥塞状况时，慢启动机制才对长生存期连接的性能有一定的影响，因为当前互联网的应用已经不再是Telent、FTP、Gopher等为主要服务，而是以Web服务、视频点播、实时信息发送等新兴服务为主要类型，其中尤其以Web浏览服务为首要的服务。而这些服务主要属于短生存期的连接。因此，尽管慢启动阶段在整个TCP拥塞控制阶段所占比重比较小，所经历的时间很短，但是改善和提高慢启动的性能仍具有重要意义。132 算法缺陷分析为了有效提高短生存期连接的传送效率以及改善
27、长生存期连接的启动过程和丢包重启过程的传输效率，研究者提出了系列改进方法。其中，M. Allman等设计一个更大的初始窗口，减少慢启动经历的时间且大大提高了短生存期连接的慢启动开始阶段的效率9；J. Hoe采用基于接收端方法的估测门限值ssthresh替代初始设定门限阈值（ssthinit），以确保拥塞窗口增长至一合适的值10； TCP Vegas采用了一定程度限制慢启动窗口的指数增长，即每两个往返时间间隔（RTT）把拥塞窗口增大一倍6。 以上方法从不同的方面对TCP慢启动进行了优化，但均存在局限性， J. Hoe的方法很难在所有互联网中接收端配置该算法，源端也无法利用测量的带宽信息；TCP
28、Vegas协议虽然限制了窗口的指数增长，但仍无法避免一个窗口中多个分组丢弃，并且在一定程度上降低了网络的传输性能。133 基于网络测量的方向网络拥塞控制中一个关键问题是网络中已存在和待加入的用户数目是动态变化的，于是网络带宽资源的使用和需求就具有相当大的不确定性，从而导致网络带宽的供需矛盾，如果能采取一定的措施实时地和动态地对网络的可用资源得出估计和推测，那么网络管理就可以依靠该数据来保证资源的合理分配，结果将利于网络整体性能的提高，避免拥塞的发生和缓解拥塞的程度。 TCP Vegas通过计算拥塞窗口与实际测量的的比值，计算出实际传送带宽，与期望的传送带宽比较，来调整发送端的传送带宽，并通过两
29、个门限参数，使传送带宽收敛于网络可用带宽，测量表达式，为拥塞窗口的大小，为分组往返时间，通过计算上一个分组传送的速率，作为计算当前大小和慢启动门限值的依据。很显然，TCP Vegas的测量方法比较粗糙，在某种意义上来说它只是用来判断源端发送速率改变的趋势。只有深入研究网络测量的相关技术，才能为拥塞控制提供更好的发展方向。第二章 网络测量方法与研究21 网络测量方法211 测量方法对比网络测量方法11主要分为两种：被动测量和主动测量。被动测量和主动测量的区别在于，前者是被动地在网络上接收流经的数据包，而不会对网络造成任何的负载；后者则是主动地向对方发出测试数据包，根据数据包在网络上的传输情况来判断网络的性能。被动测量提供了单独连接或者节点的性能描述，而主动测量则是针对位于一条路径上的几个连接和节点的性能。被动测量组件包括了报文sniffer工具、边缘路由器所生成的流级别的流量统计表，以及另外一台用于查询路由信息的空闲的顶级路由器。主动测量组件则包括了由那些被置于主路由器中心的测量机器组成的网络。这些机器交换测试流量，并收集全天的丢包率、延迟和连通性统计。然后将这些测量数据存入一个高性能数据仓库。这些数据可以被用于流量工程、性能调试、网络操作和以性能为目的所进行的测试。212 主动测量方法主动测量数据分析技术是由AMP（Active Measureme
