IP拥塞控制讲座.ppt

1、网络的拥塞控制,TCP拥塞控制,IP拥塞控制,1.概述,2.被动式队列管理,3.主动式队列管理,4.随机早期检测算法,5.IP拥塞控制算法研究热点,6.拥塞控制算法的研究难点,1.概述,TCP端到端的拥塞控制机制是确保Internet鲁棒性的重要因素。 在发生拥塞时，TCP源端会降低发送数据的速度，从而使得大量的TCP连接能够共享一条拥塞的链路。 该机制的有效性依赖于一个基本的假设：所有（或者几乎所有）的流都采用了拥塞控制机制。,1.1 Internet上的数据流,从有无有效拥塞控制机制的角度可以分为三类：,（1）TCP流；,（2）非适应流 。没有采用拥塞控制机制因而不能对拥塞做出反应 ；,（

2、3）适应流但非TCP友好流。例如，用户修改TCP ，改变窗口算法。,（1）能有效地检测早期拥塞。路由器能实时监控队列的长度。 （2）维持较小的队列长度，降低排队延迟，提高吞吐量，还能保持较大的队列空间来吸收突发数据包。 （3）选择哪个流发出拥塞通知。 （4）各流分配带宽的公平性。 （5）实现区分服务。,1.2 IP 拥塞控制任务,2. 被动式队列管理,2.1 队列管理与队列调度,2.2 队列管理的“去尾”算法,2.3 “去尾”算法的缺点,2.4 其它被动队列管理算法,2.1 队列管理与队列调度,路由器是基于包交换的设备，必须在端口上维护一个或多个队列，否则路由器无法处理多个数据包同时向同一端口

3、转发以及端口QoS等问题。 路由器有两类队列算法： 队列管理算法主要是在必要时通过丢包来管理队列长度； 队列调度算法决定下一个要发送哪个包，主要用来管理各流之间带宽的分配.,2.2 队列管理的“去尾”算法,管理路由器队列长度的传统技术是对每个队列设置一个最大值（以包为单位），然后接收包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进入队列，直到队长下降。,队列管理的“去尾”算法,“去尾”的 FIFO（调度策略） 是目前 Internet 使用最广泛的对数据包排队和丢弃方式。这种方式将拥塞控制的所有责任都推给源端，TCP独自承担检测和响应拥塞的全部责任。,2.3 “去尾”算法的缺点,（1）

4、死锁问题：在某些情况下，“去尾”算法会让某个流或者少数几个流独占队列空间，阻止其他流的包进入队列。,“去尾”算法的缺点,（2）满队列问题：“去尾”算法只有在队列满时才发出拥塞信号，因此会使队列在相当长时间内处于充满（或几乎充满）的状态。而队列管理最重要的目标之一就是降低稳定状态下队列的长度。,“去尾”算法的缺点,（3）全局同步问题：到达路由器的包往往是突发的，如果队列是满的或几乎是满的，会导致在短时间内多个连接连续地丢包，而TCP流在源端就急剧地减小发送窗口，包到达速率迅速下降，网络拥塞得以解除；但当源端探知网络不再拥塞后又增加发送速度，最终又造成网络拥塞。这种现象常常会周而复始地进行下去，使

5、网络处于链路利用率很低的状态，降低了整体吞吐量。,2.4 其它被动队列管理算法,另外两种管理机制是“随机丢弃”和“从前丢弃”机制。当队列满时，前者从队列中随机找出一个包丢弃以让新来的包进入队列；后者从队列头部丢包，以便让新包进入队列。 这两种方法都解决了“死锁”问题，但没有解决“满队列”问题。 由于这几种方法都是在队列满了被迫丢包，因此称为被动式队列管理。,3. 主动式队列管理,3.1 主动式队列管理思想,3.2 主动式队列管理的优点,3.3 现有的主动式队列管理算法,3.4 基于控制理论的AQM算法,解决路由器“满队列”的方法便是在队列充满之前丢包，这样端节点便能在队列溢出前对拥塞做出反应。

6、这种方法称为“主动式队列管理”（Active Queue Management AQM ）。,3.1 主动式队列管理思想,AQM 是一族基于 FIFO 调度策略的队列管理机制，使得路由器能够控制在什么时候丢多少包，以支持TCP拥塞控制。,主动式队列管理思想,Internet中数据包具有突发性，AQM通过保持较小的平均队列长度，能提供更大的容量吸收突发数据包，从而大大减少了丢包数。,3.2 主动式队列管理的优点,1. 减少了路由器中丢弃的包的数量,AQM通过保持较小的平均队列长度，能够减少包的排队延迟，而排队延迟是造成端到端延迟的主要原因。,主动式队列管理的优点,2. 对交互式服务提供了更低的延

7、迟,AQM能够通过确保到来的包几乎总是有可用的队列空间，从而阻止“死锁”行为的发生。,主动式队列管理的优点,3. 避免了“死锁”现象,RED、SRED、FRED、ARED； BLUE； FQ、WFQ等。,3.3 现有的主动式队列管理算法,3.4 基于控制理论的AQM算法,传统的PI、PID控制器被比较早地应用到拥塞控制中，它的参数调节已经有了比较成熟的方法，针对控制器存在的参数缺乏自适应性、缺少延迟补偿环节等缺点，研究人员又提出了一系列的PI及PID的改进算法。,1. 经典控制,模糊控制常与PID控制、滑模控制相结合应用到AQM中，可以很好的解决TCP/IP网络中存在的网络模型不确定性、网络参

8、数时变性以及非TCP适应流所引起的网络抖动，但模糊系统本质上是一种非线性系统，稳定性分析存在一定的问题，而且模糊规则的制定上还有待研究.,2. 模糊控制,鲁棒控制已经被应用到网络拥塞控制中，它主要考虑了对网络进行建模过程中系数的不确定性，大大提高了系统的鲁棒性，同时也很好地解决了系统的延迟问题。,3. 鲁棒控制,预测控制用于网络拥塞控制的研究在国内外均处于起步阶段。它是一种在线滚动时域优化控制方法，对未来有限时域内的状态进行预测，获得优化控量，可对延迟及时补偿，提高自适应能力。 但预测模型的精确性、优化问题的求解速度是有待解决的问题。,4. 预测控制,4. 随机早期检测算法,4.1 RED 的

9、设计目标,4.2 RED算法,4.3 RED 的优点和存在的问题,RED拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列导致溢出丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。 RED 是基于 FIFO 队列调度策略的，只是依概率丢弃正进入路由器的数据包。,RED 算法（Random Early Detection）,（1）最小化包丢失率和排队延迟； （2）避免全局同步现象； （3）尽量避免“去尾”的发生； （4）即使在缺乏TCP拥塞控制机制有效配合的情况下也能控制平均队列长度，从而避免拥塞。,4.1

10、RED 的设计目标,RED算法主要分为两个部分： （1）计算平均队列长度，以此作为对 拥塞程度的估计； （2）计算丢弃包的概率。,4.2 RED 算法,（1）计算平均队列长度,RED 算法,RED在计算平均队长 avgQ 时，采用了类似低通滤波器带权值的方法：,其中，w为权值，q为瞬时队列长度。这样短暂拥塞导致的瞬时队列长度暂时的增长将不会使得平均队长有明显的变化，从而“过滤”掉短期的队长变化，尽量反映长期的拥塞变化。,（1）计算平均队列长度,公式中，权值w决定了路由器对输入流量变化的反应程度。如果w较大，RED对短暂的拥塞反映大；如果w太小，avgQ就会对实际队列长度的变化反应慢，路由器就不

11、能有效检测到早期的拥塞。,（2）计算丢弃包的概率,RED 算法,RED有两个和队列长度相关的阈值：minth和maxth。当有包到达路由器时，RED计算出平均队长avgQ。平均队长和丢包概率的关系如图所示。,（2）计算丢弃包的概率,若 则没有包需 要丢弃； 当 时， 计算出丢弃概率；,当 时，所有的包都被丢弃，即,计算最终丢弃概率P的方法如下：,最终丢弃概率P不仅和 avgQ 有关，而且还与从上一次丢包开始到现在进入队列的包的数量 count 有关。,随着count 的增加，下一个包被丢弃的可能性也在缓慢增加。这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包。,4.3 RED 的优点和存

12、在的问题,（1）RED在平均队长超过了最小阈值后就丢包，从而有效地控制了平均队长，限制了平均时延的大小。 （2）在发生拥塞时，RED标记某个流的数据包的概率基本上和该流在路由器中得的带宽成比例。这是因为发送速度更快的流，其供随机标记的包也更多。从而消除了对突发流的偏见,RED的优点,（3）RED 标记包的概率依赖于拥塞水平，并且均匀地间隔丢包，避免了由于连续丢包导致的全局同步现象。,RED的优点,RED 存在的问题,（1）参数设置问题 RED工作性能的优劣很大程度上是由其预先设置的参数w、minth 和 maxth 决定的。一组RED 参数也许是给定业务吞吐量的最优化参数，但对于连续丢包、延迟

13、等就未必是最优参数了。另外，RED 参数的微小的变化会给总体性能带来很大的影响。,RED 存在的问题,（2）有时出现延迟抖动 由于权重w 很小，因此平均队长的变化很小。当负荷很重时，平均队长总是在 maxth 附近缓慢地振动，丢包率接近或等于1，产生全局同步现象。也由于此原因，尽管 RED 减小了平均时延，但却增加了延迟抖动。,RED 存在的问题,（3）公平性问题 RED标记包的概率是和该流使用的带宽成比例的，这会带来不公平的带宽使用。例如两个TCP流竞争带宽，一个使用小窗口，另一个使用大窗口，发生拥塞时，RED就会使得小窗口的源端陷入多重超时。另外，由于UDP之类的流没有拥塞控制机制，其在和TCP-friendly流竞争时会获得更多的带宽。,（1）对于 RED 各种改进算法的研究； （2）基于路由器的实现资源公平分配算法 （3）显示拥塞标识（ECN），需要路由器 的配合； （4）多媒体流的拥塞控制； （5）为支持 QoS 的区分服务； （6）完善网络模型，应用自动控制理论和 技术对网络实施优化控制。,5.IP拥塞控制算法研究热点,（1）网络本身的复杂性。拥塞控制算法的实现分布在多个网络节点上，通常探测的网络信息是局部的情况，缺乏全局透明性，需要算法仍能使其协调工作。 （2）网络环境的复杂性。网络各处的拓扑结构可能不同，网络