4 BLUE
与RED使用平均队长来管理拥塞不同，BLUE使用丢包事件和链路空闲事件来管理拥塞拥塞。 BLUE维持了一个概率Pm用以标记包。如果由于队列溢出导致持续的丢包，BLUE就增加Pm，因而增加了向源端发送拥塞通知的速度。相反，如果由于链路空闲导致队列空，BLUE就减小Pm。这样BLUE就能有效地控制发送拥塞通知信息地速度。其具体算法如下所示：
Upon link idle event:
if ((now-last_update)>freeze_time)
Pm = Pm-d2;
Last_update = now;
Upon packet loss event:
if ((now-last_updatte)>freeze_time)
Pm = Pm+d1;
last_update = now;
BLUE地主要参数有d1、d2和freeze_time。其中，d1决定了当队列溢出时Pm增加的量，d2决定了当链路空闲时Pm减少的量。freeze_time决定了连续改变Pm的最小时间间隔，使得Pm改变之后在再次变化之前能有效发挥作用。一般来说，d1要比d2大很多，这主要是因为当拥塞管理太保守（conservative）或太激进（aggressive）时，都会导致链路使用率很低；而丢包只发生在拥塞管理太保守时。这样，通过赋予丢包事件更大的比重，BLUE能够对流量大量迅速地增加很快地作出反应。
BLUE最大地贡献在于，使用相对较小地缓冲区就能够完成拥塞控制。这样，BLUE减少了端到端延迟，提高了TCP流的吞吐量。另外，较小的缓冲区需求也使得器有更多的自由空间来执行其他的路由器功能，比如更大的路由表，从而提高了路由器的性能。而要达到类似的效果，RED则需要大很多的缓冲区。
BLUE基于丢包事件和链路空闲事件的拥塞管理，能够较好地估计拥塞程度，从而作出适当的反应。因此其标记包地比率相对较稳定，这又使得队长也相对稳定，减少了延迟抖动。而RED基于平均队长地拥塞管理，由于不能正确及时地估计拥塞严重性，特别是在负荷很重，变化很快的情况下，常常导致队长波动很大。增加了丢包数和延迟抖动，甚至产生全局同步现象，降低链路使用率。
4.1 随机公平BLUE（Stochastic Fair BLUE，SFB）
现在，越来越多的应用不采用TCP的拥塞控制机制，这些流会对适应流带来很大地影响，甚至在竞争带宽时使它们陷入"饥饿"。因此必须对适应流进行保护。
SFB的基本思想就是采用记帐的方法鉴别非适应流并对它们进行速度限制。SFB持有一些用于记帐的"柜子"（accounting bins）。这些柜子以L层，每层N个的形式组织起来。另外，SFB拥有L个独立的Hash函数，每个函数和一层柜子相关联。每个Hash函数将一个流映射到该层的一个柜子。每个柜子有一个标记包的概率Pm，此概率是基于队列占用的。如果映射到某个柜子的包的数量超过了一定的阈值，则该柜子的Pm便会增加；如果该柜子中包的数量降为0，Pm便会下降。SFB取该包所映射到的L个柜子的标记包概率的最小值Pmin，如果该值为1，就认为该包所属的流是非适应流，从而对其限速。否则以Pmin的概率来标记包。SFB算法如下所示：
B[l][n]: L N array of bins
For each packet arrival:
Calculate hash function values h0,h1,…,hL-1;
Update bins at each level
For i =0 to L-1
If(B[i][hi].QLen> bin_size)
B[i][hi].Pm += delta;
Drop packet;
Else if (B[i][hi].Qlen ==0)
B[i][hi].Pm - = delta;
Pmin = min(B[0][h0].Pm.…B[L][hL].Pm);
If(Pmin==1)
Ratelimit();
Else
Mark/drop with probability Pmin;
SFB鉴别非适应流地原理在于，此类流会迅速地使其所映射到的L个柜子的标记概率增加到1。即使适应流会和非适应流共享一、两个柜子，但除非非适应流的个数比柜子的个数多很多，适应流总会被Hash函数映射到至少有一个
图5：SFB示意图
柜子没有被非适应流"污染"过，该柜有一个正常的概率Pm。因此，适应流最终得到的标记包的概率Pmin往往总是小于1。从而鉴别出适应流和非适应流（如图2所示）。
SFB能够在非适应流不是很多时，将其精确地鉴别出来，而不会影响适应流地性能。但当非适应流的数量增加时，被非适应流"污染"的柜子也就大大增加，从而增加了适应流被鉴别为非适应流的可能性。
解决这个问题地方法是采用移动Hash函数（moving hash functions）。其基本思想是周期性地或随机地重新设置柜子并更改Hash函数。因为无论使用什么Hash函数，非适应流总是能被鉴别出，而被鉴别为非适应流地适应流就有可能被重新映射到至少一个没被"污染"地柜子。这种方法有些类似于CDMA系统中的信道跳转（channel hopping）。但用这种方法，在更改Hash函数和重置柜子期间，非适应流会有如被"假释"一样消耗更多地带宽。解决此问题地一个方法是使用两套柜子。当一套柜子正在进行队列管理时，第二套使用另一组Hash函数地柜子就作"准备活动"（w up）。当某个流被鉴别为非适应流时，更改第二套柜中相应柜子标记包的概率，然后使用第二套柜子进行鉴别。从而大大减少了适应流被错误鉴别地可能性。
4.2 BLUE和SFB的不足
（1） 由于发生丢包事件后BLUE会相对大地增加丢包地概率，从而会产生连续丢包，导致TCP陷入超时，严重时会降低链路利用率。
（2） 参数freese_time的设置问题。如果freese _time太小，会导致Pm的变化过于频繁，使得拥塞管理很激进（aggressive）；如果freese_time太大，Pm的变化很缓慢，从而使得拥塞概率很保守，不能适应流量的变化。freese_time的设置问题和RED中权重w_Q的问题有些类似。
（3） SFB虽然较好地解决了区分适应流和非适应流地问题，但过于复杂，会大大增加路由器的额外开销。
5 Stabilized RED（SRED）
SRED的主要目的是保持FIFO队列的占用稳定而与活跃流（active flows）数量无关；另外一个目的是鉴别行为恶意的流（misbehaving flows）。
SRED的基本思想就是进行比较。当有一个包到达buffer时，就和buffer中随机选出的一个包进行比较，若这两个包属于同一个流，则称为"击中"（hit）。这种方法虽简单，但要和已经离开buffer的包进行比较是不可能的，为了使系统有更长的记忆，SRED设计了一种数据结构，称为"僵尸"列表（Zombie List）。这个列表可以被认为是一种流Cache，其中记录了最近流经该buffer的M个流及其一些额外信息："count"和"时间戳"。
起初列表为空，当有一个包到达时，只要列表非空，则该包的流标识（源、目的地址等）加入列表，其僵尸的count设为0，时间戳为该包的到达时间。
一旦僵尸列表满了，则作如下工作：当一个包到达后，它和僵尸列表中随机选出的僵尸进行比较：
击中： 则此僵尸的count加1，时间戳改为现在包的到达时间。
没击中： 以概率P，用刚到包的流标识覆盖选出来的僵尸，count重置为0,时间戳改为刚到包的到达时间。概率P和原来僵尸的时间戳有关，时间戳越老，P就越大。
SRED用一个函数Hit(t)来记录第t个包是否击中，如果击中，则Hit(t)取值为1，否则为0。从恶意流相比较良好流更易引发"击中"这个意义上说，如果一个包引发"击中"，则可认为该包属于恶意流。如果一个包"击中"并且该僵尸的count值很大，就更明显了。
5.1 Simple SRED
首先计算第t个包到达队列时击中的概率：P(t)=(1-α)×p(t-1)+α×Hit(t)（0<α<<1）
其中α是一个常数。P(t)-1可以被认为是在第t个包到达之前很短时间内对活跃流数量的估计。如果要减少比较的开销，可以每隔L个包或者一个预定的时间段再更新P(t)，而不是每来一个包就更新，其计算公式如下：P(new)=(1-Lα)×p(old)+α×Hit （0
丢弃包的概率依赖于队列的占用情况和活跃流的估计值。
其中，B是队列大小，q是当前队列占用大小。首先根据队列占用情况计算出Psred，然后再结合对活跃流的估计，计算出丢包概率Pzap。并且在计算Pzap时，引入了 这一项，之所以这样，是因为：
当丢包率已经很大时，TCP就要用相当多的时间来处理超时重传，因此进一步增大Pzap就没有意义了。
当P(i)很小时，也即击中很少发生，此时用P(i)估计活跃流数量就不是很可靠。
因此当P(i)小于一定值后，Pzap统一取值为Psred；这里的"256"也是任意取的，还需要进一步的研究。
5.2 Full SRED
在Simple SRED中，Hit只是用来估计活跃流数量。由于恶意流会产生更多的击中事件，并且它们也更容易出现在僵尸列表中，因此可以将Hit直接用到计算标记包概率中去。修改后标记包的概率如下：
这样增加了恶意流的丢包率，并且也减小了TCP对RTT较小的流的偏好。
5.3 SRED的优点及其存在的问题
SRED克服了RED队长波动的缺点，在相当大的负荷范围内，SRED都能保持队列的稳定而与活跃流的数量相独立，从而有效地减小了延迟抖动。SRED也给出了鉴别恶意流的方法并且对其进行惩罚。SRED的缺陷：
（1） 对异质的流量，P(i)-1不能很好地估计活跃流地数量。
（2） 参数设置问题： 与RED中的参数设置问题一样，SRED中参数Psred、Pmax的设置也需要依赖不同的网络流量情况而定，包括Pzap中256的选择等仍然是有待研究的问题。
【责编:admin】
--------------------next---------------------
