四种拥塞控制算法PPT.ppt

拥塞控制方法 计算机科学与技术 卢连女 拥塞 拥塞：在某段时间，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏 出现资源拥塞的条件： 对资源需求的总和 可用资源 为什么要控制拥塞： 若网络中有许多资源同时产生拥塞，网络的性能就要明显变坏，整个网络的吞吐量将随输入负荷的增大而下降 拥塞控制算法的引入 TCP有一个端对端通告的接收窗口(rwnd)。窗口值的大小就代表能够发送出去的但还没有收到ACK（确认）的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也越有可能使得网络出现拥塞， 如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。 TCP的拥塞控制算法就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。 几种常见TCP的拥塞控制算法 1.慢开始算法 2.拥塞避免算法 3.快重传算法 4.快恢复算法 我们假设： 1.数据是单方向传送，而另一个方向只传送确认。 2.接收方总是有足够大的缓存空间，因而发送窗口的大小由网络的拥塞程度来决定。 1.慢开始算法 最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。 发送方维持一个叫做拥塞窗口 cwnd (congestion window)的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口。如再考虑到接收方的接收能力，则发送窗口还可能小于拥塞窗口。（取决于接收方缓存空间的大小） 发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减小一些，以减少注入到网络中的分组数。 慢开始算法原理 在主机刚刚开始发送报文段时可先设置拥塞窗口 cwnd = 1。 在每收到一个对新的报文段的确认后，将拥塞窗口加 1。 用这样的方法逐步增大发送端的拥塞窗口 cwnd，可以使分组注入到网络的速率更加合理 这里 是说每收到1个对新的报文段的确认后，将拥塞窗口加1，而第二次会收到2个确认，第三次会收到4个确认，以此类推，可以知道每经过一个传输轮次，拥塞窗口就加倍。 即cwnd的大小呈指数形式增长（与拥塞避免算法相区别） 具体如后图所示 发送方 接收方 发送 M1 确认 M1 发送 M2~M3 确认 M2~M3 发送 M4~M7 确认 M4~M7 cwnd = 1 cwnd = 2 cwnd = 4 发送 M8~M15 cwnd = 8 … t t 轮次 1 轮次 2 轮次 3 发送方每收到一个对新报文段的确认（重传的不算在内）就使 cwnd 加 1。 传输轮次 使用慢开始算法后，每经过一个传输轮次，拥塞窗口 cwnd 就加倍。 一个传输轮次所经历的时间其实就是往返时间 RTT。 “传输轮次”更加强调：把拥塞窗口 cwnd 所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。 例如，拥塞窗口 cwnd = 4，这时的往返时间 RTT 就是发送方连续发送 4 个报文段，并收到这 4 个报文段的确认，总共经历的时间。 2.拥塞避免算法 从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是cwnd不能一直这样无限增长下去，一定需要某个限制。TCP使 用了一个叫慢启动门限(ssthresh)的变量，当cwnd超过该值后，慢启动过程结束，进入拥塞避免阶段。 拥塞避免算法原理： 拥塞避免的主要思想是加法增大，也就是cwnd的值不再指数级往上升，开始加法增加。此时当窗口中所有的报文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。 慢启动门限(ssthresh)的设置 慢开始门限 ssthresh 的用法如下： 当 cwnd ssthresh 时，使用慢开始算法。 当 cwnd ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。 当 cwnd = ssthresh 时，既可使用慢开始