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的优点，只是少量增加了一些额外开销。
【责编:admin】
--------------------next---------------------
阅读(241) | 评论(0) | 转发(0) |
