拥塞控制与RED

拥塞控制与随机早期检测RED拥塞控制1、引言Internet中拥塞控制的大部分工作是由TCP完成的，目前标准TCP协议的实现都包含了一些避免和控制网络拥塞的算法。当今Internet的可靠性和稳定性与TCP拥塞控制机制密不可分，而TCP的成功也要归功于其稳固的拥塞控制机制。随着应用要求的日益丰富和技术的不断发展，要想完全依赖实现在终端系统上的策略和算法很难满足服务质量（QoS）这样复杂的要求，为了解决相应的问题，相关网络技术逐渐转向网络的中间节点即路由器上，通过增强它们的功能来实现端到端无法达到的技术，从而达到有效的拥塞控制，保持网络的良好性能。2、产生拥塞的原因网络中的链路容量（带宽）、交换节点中的缓存和处理机等，都是网络资源，在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能变坏，这种情况就叫拥塞。当通信量增加太快时，路由器没有办法及时进行处理，开始丢弃分组，并会导致情况恶化。通信线路的带宽不够可能导致拥塞。路由器中数据的到达率远远大于链路的服务率，从而导致长队列，缓冲区用完，进而丢失分组。3、拥塞控制拥塞会导致恶性循环。如果路由器没有空闲的缓冲区，它必须丢掉新到来的分组。当扔掉一个分组时，发送该分组的路由器可能会因为超时而重传此分组，甚至可能要多次重传。流量控制和拥塞控制流量控制：流量控制机制用来保证发送端不以比接收者能承受的速率更高的速度传输数据，一般涉及到接收者通过向发送者发送反馈。拥塞控制：拥塞控制确保通信子网能够有效为主机传递分组。横坐标是提供的负载，代表网络提供分组的数目。纵坐标是吞吐量，代表单位时间内从网络输出的分组的数目。在理想下拥塞控制的网络中，在吞吐量饱和前，网络吞吐量等于提供的负载，但当提供的负载超过某一限度的时候，用于网络资源受限，吞吐量不在增长而保持在水平线，吞吐量达到饱和。此时有一部分分组损失掉了。此时网络的吞吐量仍然维持在所能达到的最大值。图1但是，在实际网络中，随着网络负载的增大，网络增长的速率逐渐减小，在网络吞吐量还未达到饱和时，已经有一部分分组被丢弃了，当网络的吞吐量明显小于理想的吞吐量时，网络就进入了轻度拥塞状态。当负载达到某一数值时，网络的吞吐量反而随着负载的增大而下降，网络进入拥塞状态，当负载继续增大，达到某一数值时网络的吞吐量就下降到零，网络已无法工作，即常说的死锁。拥塞控制一般分为四种方式：慢启动，拥塞避免，快重传，快恢复。慢启动和拥塞避免发送发维持一个拥塞窗口（cwnd），取决于网络的拥塞程度，并且动态的变化，发送方让自己的发送窗口等于拥塞窗口。发送方控制用色窗口的原则是：只要网络没有出现拥塞，拥塞窗口就增大一些，以便把更多的分组发送出去。但只要出现网络拥塞，拥塞窗口就减小一点，一间小注入到网络中的分组数。慢启动算法的思路：发送端与接收端的主机建立TCP连接时，拥塞窗口被初始化为1个报文段（即另一端通告的报文段大小）。每收到一个ACK，拥塞窗口就增加一个报文段（cwnd)以字节为单位，但是慢启动以报文段大小为单位进行增加）,发送方取拥塞窗口与接收窗口中的最小值作为发送上限。发送方开始时发送一个报文段，然后等待ACK。当收到该ACK时，拥塞窗口从1增加为2，即可以发送两个报文段。当收到这两个报文段的ACK时，拥塞窗口就增加为4，再以此类推。这是一种指数增加的关系。增长过大引起网络拥塞，还需要设置一个门限值ssthresh状态变量。当cwndssthresh时，使用上述的慢启动算法。当cwndssthresh时，停止使用慢启动，改用拥塞避免。当cwnd=ssthresh时，二者皆可以使用。拥塞避免算法的思路是让cwnd缓慢增大，及每经过一个RTT（往返时间）就把发送方的拥塞窗口加1，而不是加倍。这样cwnd。按线性缓慢增长。无论是在慢启动还是在拥塞避免阶段，只要发送方判断网络出现拥塞，就把ssthresh的值设置为出现拥塞时发送窗口的一半，cwnd重新设置为1，执行慢启动。这样做的目的是迅速减少往网络里注入分组数，使得发生拥塞的路由器有足够的时间把队列中积压的分组处理完毕。图二慢启动和拥塞避免快重传和快恢复：如果发送方设置的超时计时器时限已到但还没有收到确认，那么很可能是网络出现了拥塞，只是报文在网络中的某处被丢失。此时，TCP马上把拥塞窗口减小到1，并开始执行慢启动算法，同时把门限值减半，见图二。主动队列管理主动队列管理机制是种通过有意识地控制路由器的队列长度来预防拥塞的技术，路由器可以监测队列的长度，在队列有一定程度增长而不是等到拥塞真正出现了而导致队列满时才通过丢弃分组来发送通知。尾部丢弃策略：路由器的队列通常是按照“先进先出”FIFO的规则处理到来的分组，由于队列长度总是有限的，因此当队列已满时，以后在到达的分组都将被丢弃。AQM是一族基于FIFO调度策略的队列管理机制，使得路由器能够控制在什么时候丢多少包，以支持端到端的拥塞控制。AQM有以下优势：（1）减少了路由器中丢弃的包的数量：Internet中数据包的突发本质是不可避免的，AQM通过保持较小的平均队列长度（averagequeuesize），能提供更大的容量吸收突发数据包，从而大大减少了丢包数。（2）对交互式服务提供了更低的延迟：AQM通过保持较小的平均队列长度，队列管理能够减少包的排队延迟（queueingdelay），而排队延迟是造成端到端延迟（endtoenddelay）的主要原因。（3）避免了“死锁”现象：AQM能够通过确保到来的包几乎总是有可用的队列空间，从而阻止“死锁”行为的发生。（RandomEarlyDetection）拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞（在队列长度达到一定值时就按照一定的概率将新到来的分组丢弃），使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。RED路由器采用平均队列长度，而不是当前的队列长度来计算分组丢弃的概率。实现RED的要点如下：平均队列长度的计算方法：计算概率p:count是一个变量，代表新到达的分组有多少个已经进入队列，Ptemp是过渡的分组丢弃概率：按照上文中的算法可以算出丢弃的概率很小，但路由器的队列已经没有空间来容纳新到达的分组，那么这时RED的操作和“尾部丢弃”的方式一样，RED只是在可能的条件下尽量的使“尾部丢弃”不要发生，同时也能使得路由器更好的管理队列长队。