Internet路由器主动式队列管理机制综述(3)

2019-11-05 00:34:11

字体：大中小

来源：转载

供稿：网友

　　7 Adaptive RED
　　
　　
　　我们知道，Internet是基于统计复用的，一条链路上有很多活动连接在竞争有限的带宽资源。在拥塞严重的网络中，AQM必须将拥塞信息通知到足够的源端，以充分降低负荷避免队列溢出丢包。另一方面，AQM也要防止拥塞信息传给了过多的源端，从而造成瓶颈链路利用率的下降。因此，进行拥塞通知时应充分考虑到瓶颈链路上流的数量。而RED并没有考虑到这一点。为此ARED提出了一种自动配置机制，根据流量的变化来配置适当的参数。
　　
　　RED中，拥塞指示的发送速度是由参数maXP来体现的。假如maxp太大，那么丢包比例主要就是由于早期拥塞检测中产生的丢包造成的；假如maxp太小，丢包主要就是由于队列溢出造成的。RED的一个弱点是平均队长对拥塞程度和参数设置很敏感。假如拥塞不太严重或者maxp很大，则平均队长接近min_th；假如拥塞很严重或者maxp很小，则平均队长接近或大于max_th。结果造成平均排队时延对流量负荷和参数设置很敏感。
　　
　　TCP流获得带宽的上限可以通过下式估计：（1）
　　　

　　其中MSS：最大段尺寸（Maximum Segment Size） C ：常数 p ：丢包率
　　
　　假如有N个流竞争带宽，我们可以得到：
　　　

　　（2）
　　
　　也即：
　　

　　（3）
　　
　　从上式可以看出，假如所有的流都采用了TCP的拥塞控制机制，那么丢包率的上限是和连接数的平方成正比。因此，激进的方法或者较大的maxp值适合于流较多的情况；保守的方法或者较小的maxp值适合于流较少的情况。
　　
　　ARED的基本思想就是通过检查平均队长的变化来感知RED是应更激进还是更保守。假如平均队长是在min_th四周振荡，那么拥塞控制就太激进了；假如在max_th四周振荡，那么拥塞控制就太保守了。基于所观察到的平均队长，ARED动态地maxp调整的值。其算法如图所示。
　　
　　Every avg_Q Update：
　　If（min_thmax_th && status!=Above）
　　　 status=Above
　　　 maxp= maxp *β
　　各参变量含义：
　　status　：平均队长状态
　　Between ：min_th和max_th之间
　　Below　：小于min_th
　　Above　：大于max_th
　　α　　　：maxp减少量
　　β　　　：maxp增加量
　　
　　
　　
　　ARED算法很简单，就是根据平均队长是否在min_th和max_th之间，对maxp采用积式增加和减少（Multiplicative Increase Multiplicative Decrease，MIMD）从而尽量保持平均队长在min_th和max_th之间。
　　
　　ARED是对RED改动很小的一种算法，它保留了RED的基本结构，只需调节参数maxp从而保持平均队长在min_th和max_th之间，消除了RED的队列延时问题和参数敏感性问题。
　　
　　7．1 New ARED
　　
　　为了提高ARED的鲁棒性，Sally Floyd等提出了一种新的ARED算法，我们姑且称为New ARED。其基本思想和ARED一样，都是采用自适应的maxp以保持平均队长在min_th和max_th之间。不一样之处在于，New ARED保持平均队长在min_th和max_th的一半之内；不是每来一个包都改变，而是有一定时间间隔；maxp不采用积式增加和减少，而是和式增加和减少（Additive Increase Multiplicative Decrease，AIMD）；maxp限制在[0.01，0.5]。具体算法如下：
　　
　　Every interval seconds：
　　　If（avg_Q>target && maxp<=0.5）
　　maxp = maxp +α
　　else if（avg_Q=0.01）
　　　　 maxp = maxp *β
　　各参变量含义：
　　interval：时间间隔
　　target　：avg_Q的目标范围
　　[min_th+0.4*(max_th-min_th),
　　min_th+0.6*(max_th-min_th)]
　　
　　
　　
　　New ARED的鲁棒性主要来自于maxp不是很频繁的变化。但假如拥塞程度急剧变化，则maxp需要过一段时间才能适应。为了保证ARED在这段时间里性能不会过度下降，因此将maxp限制在[0.01,0.5]之间。这样，即使这段时间内平均队长不足目标范围内，平均延时和吞吐量也不会下降太多。
　　
　　7.2 ARED的缺陷
　　
　　ARED虽然解决了RED的参数敏感性问题，但其自身也带来了参数设置问题。α、β设置太大，maxp振荡过于频繁，不利于网络性能稳定；α、β设置太小，maxp就要经过多次调整荡才能达到期望值。New ARED中参数interval的选择也有类似问题。另外maxp的初值也会影响调整的过程和结果。
　　8其它几种AQM机制
　　
　　
　　8.1 带有惩罚盒的RED（RED with penalty box）
　　
　　这种算法是对RED不能有效保护适应流的一种改进。在RED的算法基础之上增加了分类策略和调度策略。其基本思想是对流进行鉴别分类，鉴别出TCP-friendly和非TCP-friendly流。调度策略可以采用带有权重的轮转法（Weighted Round- Robin）、带有权重的公平排队（Weighted Fair- Queuing）或基于分类的排队（Class-based Queueing CBQ）等。
　　
　　被鉴别为非TCP-friendly的流被分配到低优先级的调度区。若某一流在收到拥塞通知后，作出了降低发送速度的反应，那么它应该被重新分类（reclassfied）到高优先级调度区。
　　
　　8.2 GREEN
　　
　　GREEN的基本思想是根据拥塞程度来调整发送拥塞通知的速度，是一种反馈控制机制。GREEN主要是根据数据包到达路由器的速度来判定拥塞程度。假如包到达的速度超过了链路的容量，那么在某一时间间隔内，拥塞通知速度增加一次；反之，假如包到达的速度小于了链路的容量，那么在某一时间间隔内，那么拥塞通知速度减小一次。
　　
　　8.3 CHOKe（CHOose and Keep for responsive flows CHOose and Keep for unresponsive flows）
　　
　　CHOKe的主要目的也是保护适应流，惩罚非适应流。其基本思想是，当一个包到达拥塞的路由器时，CHOKe从FIFO队列中随机地挑出一个包进行比较。假如它们属于同一个流，则这两个包都被丢弃；否则，被挑出地包依然留下，而刚到达的包则依某种概率被丢弃，此概率的计算和RED中一样。
　　
　　CHOKe算法是基于以下原因：由于非适应流的特点，FIFO队列可能会更多地包含非适应流地包，也就意味着这种流的包更有可能被选中进行比较。从而对非适应流进行了惩罚。CHOKe基本上继续了RED的优点，只是少量增加了一些额外开销。

上一篇：关于路由器cpu利用率过高的解决

下一篇：移动IP的多层次位置管理及路由优化