TCP拥塞控制

计算机网络TCP拥塞控制算法及仿真小组成员：PART01PART02PART03基本概念TCP拥塞控制的几个阶段经典的TCP控制算法PART04仿真思路基本概念在某段时间，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏——产生拥塞出现资源拥塞的条件：对资源需求的总和可用资源若网络中有许多资源同时产生拥塞，网络的性能就要明显变坏，整个网络的吞吐量将随输入负荷的增大而下降。01基本概念拥塞控制是很难设计的，因为它是一个动态的（而不是静态的）问题。当前网络正朝着高速化的方向发展，这很容易出现缓存不够大而造成分组的丢失。但分组的丢失是网络发生拥塞的征兆而不是原因。在许多情况下，甚至正是拥塞控制本身成为引起网络性能恶化甚至发生死锁的原因。这点应特别引起重视。02基本概念•拥塞窗口(cwnd):拥塞控制的关键参数，控制源端在拥塞情况下一次最多能发送多少数据包。•接收窗口(rwnd):接收端对源端发送窗口大小所做的限制，在建立连接时山接收方通过ACK确认带给源端•慢启动阀值(ssthresh):拥塞控制中用来限制发送窗口大小的门限值，它是慢启动阶段与拥塞避免阶段的分界点，初始值设为65535bytes或awnd的大小。03基本概念•回路响应时间(RTT):一个数据包从源端发送到接收端直至源端收到接收端R寸该数据包确认信息所经历的时间间隔。•超时重传计数器(RTO):描述数据包从发送到失效的时间间隔，是源端用来判断数据报是否丢失和网络拥塞的重要参数，通常设为2RTT或SRTT04TCP拥塞控制的几个阶段1234拥塞避免阶段快速重传阶段快速恢复阶段慢启动阶段慢启动阶段01当连接刚建立或超时时，进入慢启动阶段。当新建TCP连接时，拥塞窗口(cwnd)被初始化为一个数据包大小(缺省为512或536bytes)。实际发送窗口win取拥塞窗口与接收方提供的通告窗口的较小值，即win=min(cwnd,awnd)，每收到一个ACK确认，就增加一个数据包发送量，这样慢启动阶段cwnd随RTT呈指数级增长(1个、2个、4个、8个…)发送方接收方发送M1确认M1发送M2~M3确认M2~M3发送M4~M7确认M4~M7cwnd=1cwnd=2cwnd=4发送M8~M15cwnd=8…tt发送方每收到一个对新报文段的确认（重传的不算在内）就使cwnd加1。轮次1轮次2轮次3传输轮次03使用慢开始算法后，每经过一个传输轮次，拥塞窗口cwnd就加倍。一个传输轮次所经历的时间其实就是往返时间RTT。“传输轮次”更加强调：把拥塞窗口cwnd所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。例如，拥塞窗口cwnd=4，这时的往返时间RTT就是发送方连续发送4个报文段，并收到这4个报文段的确认，总共经历的时间。慢启动阶段04优点：慢启动采用逐渐增大cwnd的方法，可以防止TCP在启动一个连接时向网络发送过多的数据包而造成不必要的数据丢失和网络拥塞，并且它还能够避免采用单纯的AIMD算法造成的吞吐量增加过慢的问题为了防止cwnd的无限制增长引起网络拥塞，引入一个状态变量：慢启动阈值ssthresh当cwndssthresh时，使用上述的慢启动算法，cwnd随RTT呈指数增长。当cwndssthresh时，使用下面的拥塞避免算法，减缓cwnd的增长速度。拥塞避免阶段05当TCP源端发现超时或收到3个相同的ACK确认帧时，即认为网络将发生拥塞，此时进入拥塞避免阶段。在拥塞避免阶段，慢启动域值ssthresh将被设置为当前cwnd的一半，当发生超时时，cwnd被置为初始值1。此时，如果cwndssthresh，TCP重新进入慢启动过程；如果cwnd=ssthresh，则执行拥塞避免算法，即cwnd在每次收到一个ACK确认时只增加1/cwnd个数据包。拥塞避免阶段cwnd随RTT呈线性增长。tt2216“乘法减小”24681012141618200048122024网络拥塞指数规律增长慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”快速重传阶段07当网络发生拥塞时，如果源端等待超时之后再进行拥塞控制，那么从出现拥塞到实施控制有一定的时延。除了超时之外，源端还可以使用重复ACK作为拥塞信号。源端在接收到重复ACK时并不能确定是由于分组丢失还是分组乱序产生的，通常假定如果是分组乱序，在目的端处理之前源端只可能收到一个或两个重复的ACK;如果源端连续接收到三个或更多的重复ACK，表明网络中某处已经发生了拥塞，这时，源端不等到重传定时器超时就重发这个可能丢失的分组，这就是快速重传算法。发送方接收方发送M1确认M1t确认M2发送M2发送M3发送M4？发送M5发送M6重复确认M2重复确认M2重复确认M2t发送M7收到三个连续的对M2的重复确认立即重传M3丢失快速重传阶段07在快速重传阶段，当源端收到3个或3个以上重复的ACK时，就判定数据包丢失，同时ssthresh设置为当前cwnd的一半，并重传丢失的包，进入快速恢复阶段。快速恢复阶段08当快速重传算法重传了可能丢失的分组之后，如果TCP重新进入慢启动阶段，将会使拥塞窗口减为1，重新开始探测网络带宽，从而严重影响网络吞吐量，因此快速恢复算法在快速重传之后转去执行拥塞避免算法，避免了过大地减小发送窗口而导致的网络性能下降。快速恢复阶段08在快速恢复阶段，每收到重复的ACK，则cwnd加1；收到非重复ACK时，置cwnd＝ssthresh，转入拥塞避免阶段；如果发生超时重传，则置ssthresh为当前cwnd的一半，cwnd＝1，重新进入慢启动阶段。tt242468101214161820220048121620传输轮次拥塞窗口cwnd收到3个重复的确认执行快重传算法慢开始“乘法减小”拥塞避免“加法增大”TCPReno版本TCPTahoe版本(已废弃不用）ssthresh的初始值拥塞避免“加法增大”新的ssthresh值慢开始快恢复从连续收到三个重复的确认转入拥塞避免经典的TCP拥塞控制算法1234TCPRenoTCPNewRenoTCPVegasTCPTahoeTCPTahoe算法01Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼进可用信道容量，然后慢慢接近均衡。Tahoe包括3个基本的拥塞控制算法：“慢启动”、“拥塞避免”和“快速重传”。TCPTahoe算法02Tahoe算法存在着不足之处：在收到3个重复ACK或在超时的情况下，Tahoe置cwnd为1，然后进入慢启动阶段。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。TCPReno算法01针对Tahoe算法的不足，提出了改进算法Reno。改进主要有两方面：一是对于收到连续3个重复的ACK确认，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传和快速恢复机制。Reno算法以其简单、有效和鲁棒性成为TCP源算法的主流，被广泛的采用。但它不能有效的处理多个分组从同一数据窗口丢失的情况。TCPNewReno01TCPNewReno修改了TCPReno的快速恢复算法，处理一个窗口中的多个报文段同时丢失时出现的“部分确认”(PartialACKs，它在快速恢复阶段到达并且确认新数据，但它只确认进入快速重传之前发送的一部分数据)。在这种情况下，TCPReno会退出快速恢复状态，等待重传定时器溢出或者重复的确认ACK到达，但是TCPNewReno并不退出快速恢复状态，而是(1)重传紧接着那个部分ACK之后的报文段，拥塞窗口等于其减去部分的ACK；(2)对于得到确认的新数据，设置cwnd等于其加上SMSS：(3)对于第一个或每一个PartialACK，重传定时器复位Vegas算法011994年，Brakmo提出了TCPVegas算法，TCPVegas是一种截然不同的拥塞控制算法，它采用一种更巧妙的带宽估计策略，根据期望的流量速率与实际速率的差估计网络瓶颈处的可用带宽。TCPVegas对TCPReno主要做了三个方面的改进，分别是快速重传机制、拥塞避免阶段和慢启动阶段，这三个方面改进的具体情况如下：Vegas算法02对快速重传机制的改进TCPVegas主要在两个方面对快速重传进行了改进，使得探测丢包现象变得更及时，且能进一步减少超时情况的发生。第一个改进措施是，当TCPVegas收到重复的确认包时，计算从发送该数据包时刻到当前时刻的时问间隔，比较是否大于RTO，如果是，Vegas就重传该数掘包而不用等到第2、3个重复确认包的到达，如下图所示。而且在TCPVegas中使用了比TCPReno更为精确的计时器，可以测得更加准确的RTT以及其他的一些时间数据，对RTT的估计将更加准确，同样也能得到更加精确的超时时间。Vegas算法04第二个改进措施是当检测到超时并重传数据包后，收到第1个或第2个非重复确认包时，检查从重传该数据包到收到非重复确认包的时间间隔，时间间隔若大于超时时间，就认为发生了丢包，并重传该数据包。这样能够不用等到重复的确认包到达，就准确的传送在重传前发生丢包的那些数据，这在发生多个丢包的时候尤为重要，否则发送端会一直等待直到超时，其过程如下图所示:ttVegas算法05拥塞避免机制的改进Reno是把丢包情况作为拥塞发生的信号，而Vegas则是通过计算期望值的吞吐量与实际吞吐量之间的差来估计网络瓶颈处的可用带宽。由于Vegas不需要等到丢包才认为发生了拥塞，所以能更有效的利用带宽。其基本思想是期望的吞吐量与实际的吞吐量相差超过一定值时，就认为网络拥塞程度严重，应该减小发送窗口；另一方面，当两者之间的差距小于一定值时，则认为连接没有完全有效的利用带宽，应该要增大发送窗口。Vegas算法06TCPVegas在拥塞避免阶段的具体算法为：1、计算期望的吞吐量与实际吞吐量之间的差值其中代表传输延时，也是当缓存中数据包为空时的RTT值(BaseRTT),cwnd代表源端在每个往返时间(RTT)中允许发送窗口的大小，期望的吞吐量为cwnd/T，设r代表实际网络中的RTT，实际的吞吐量为cwnd/rcwndcwndrVegas算法072、由(1)式得到路由器缓存中的数据包个数为（1）3、塞窗口的调整策略：()1,(1)(),()1,cwndkcwndkcwndkcwndk()cwndcwnddrVegas算法08TCPVegas线性增大或减小窗口是基于d(k)的大小，d(k)代表数据包在路由器中的数量，当d(k)小于时，说明网络资源还没有充分利用，需要进一步的增大发送窗口，当d(k)大于时，则减小发送窗口，防止发生拥塞。如果在,之间，则窗口不变。可用下面的公式来说明:()1,(1)(),()1,cwndkcwndkcwndkcwndk()dk()dk()dkVegas算法05慢启动阶段的改进TCPReno在慢启动阶段的每个RTT内窗口都会增大一倍，TCPVegas修改为每隔一个RTT才将窗口增大一倍，在这之间，窗口固定不变。这样是为了保证能够正确的比较吞吐量的差值，Vegas还在慢启动中加入了拥塞检测。在初始的慢启动阶段，TCPVegas通过计算期望的吞吐量估计出可用的网络带宽，当实际的吞吐量变得比期望的吞吐量小于一定门限值y时，窗口将会减小1／8，并且从慢启动阶段进入拥塞避免阶段。为慢启动加入拥塞检测是十分重要的，当网络带宽变大时，其作用尤为明显，改进的慢启动算法对改善丢包情况和超时现象十分有效。09仿真思路05在omnet++中抽象出如下仿真模型01计算机网络谢谢Thanks