SFB(Stochastic Fair Blue)是一个FIFO类型的队列算法，基于类似于BLUE算法的记账机制，来标识非响应性质的流，并且限制其速率（这类流不处理ECN或者丢包事件）。SFB的记账系统由L*N个桶（bin）组成,其中L表示级别，N表示每个级别的桶的数量。Linux内核中使用8个级别，每个级别16个桶用于记账。

 37 #define SFB_BUCKET_SHIFT 438 #define SFB_NUMBUCKETS  (1 << SFB_BUCKET_SHIFT) /* N bins per Level */39 #define SFB_BUCKET_MASK (SFB_NUMBUCKETS - 1)40 #define SFB_LEVELS  (32 / SFB_BUCKET_SHIFT) /* L */

另外，SFB维护着L数量的独立哈希函数，对应于记账系统中的L个级别，每个哈希函数将数据流映射到其对应级别的某个桶中，这些桶用于记录匹配流的队列占用情况。SFB的每个桶维持着一个类似于BLUE算法的marking/dropping probability （Pm）值，每次桶被占用的使用更新此值。例如，在某个报文到达队列后，根据L个级别的相应哈希函数，将其哈希到每个级别的N个桶中的一个。如果摸个映射到某个桶的报文数量超过一定的阈值，此桶的Pm值将增加；如果桶中的报文数据降为零，减小Pm值。

如下为使用伪代码描述的以上介绍的SFB记账系统算法。

B[l][n]: L x N array of bins (L levels, N bins per level)
enque()Calculate hash function values h0, h1, ..., hL-1;Update bins at each levelfor i = 0 to L - 1if (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()elseMark/drop with probability pmin;

对于某个非响应的流，其会很快将SFB记账系统中L个级别的每个级别对应的哈希桶的Pm值拉高为1。对于响应式的流，其有可能与非响应流共同使用某几个级别中的桶，但是，只要非响应流的数量不是远远大于桶的数量，响应式流就有很大可能哈希到至少一个没有被非响应式占用的桶，以上算法可见，流的最小Pm值为每个级别中其对应的哈希桶的Pm值中的最小值，所有，响应式流将保持一个正常的Pm值。报文的（ECN）标记依据最小Pm值实现，如果Pmin为1，SFB认为此流为一个非响应式流，将对其进行限速（penalty_rate）。

如下图所示，一个非响应式流将它映射到的所有哈希桶的Pm（marking probablilities）值都增加到了1，而图中的TCP流（响应式流）在级别0与非响应式流哈希到了同一个桶中，但是在其它级别中二者完全在不同的桶中，所以，TCP流的最小Pmin没有受到影响，其值为0.2。另一方面，由于非响应式流的最小Pm为1，其被标识为非响应流，并且进行限速处理。

基于以上SFB的介绍， 响应式流也有可能也非响应式流共用所有相同的哈希桶，导致其被误判定为非响应流。对于一个L级别，每个级别B个桶的SFB，如果非响应式流的数量为M，那么，响应式流被误判的可能p由以下公式给出：

$p = \left [ 1 - \left ( 1-\frac{1}{B} \right )^{M} \right ]^{L}$

对于Linux内核的8级别、每级别16个桶的情况，带入以上公式可得：

$p = \left [ 1 - \left ( 1-\frac{1}{16} \right )^{M} \right ]^{8}$

举例来说，对于数量为10（M=10）的非响应式流的系统，响应式流被误判的可能性为0.2%。为解决此问题，SFB每隔一段时间执行重哈希操作，将误判限制在一定的时间内。

以下为tc命令中sfb的帮助信息和配置命令。

$ tc qdisc add sfb help
What is "help"?
Usage: ... sfb [ rehash SECS ] [ db SECS ][ limit PACKETS ] [ max PACKETS ] [ target PACKETS ][ increment FLOAT ] [ decrement FLOAT ][ penalty_rate PPS ] [ penalty_burst PACKETS ]
$ 
$ sudo tc qdisc add dev ens38 handle 1: root sfb rehash 600000 db 60000 limit 1000 max 25 target 20 increment 0.00050 decrement 0.00005 penalty_rate 10 penalty_burst 20
$ 
$ tc qdisc show dev ens38
qdisc sfb 1: root refcnt 2 limit 1000 max 25 target 20increment 0.00050 decrement 0.00005 penalty rate 10 burst 20 (600000ms 60000ms)
$ 

以上配置的实际上都是SFB的默认参数，参见以下的sfb_default_ops结构的成员赋值。limit参数为零的话，将在初始化过程中重新赋值为网络设备的发送队列长度（例如：1000）。

static const struct tc_sfb_qopt sfb_default_ops = {.rehash_interval = 600 * MSEC_PER_SEC,.warmup_time = 60 * MSEC_PER_SEC,.limit = 0,.max = 25,.bin_size = 20,.increment = (SFB_MAX_PROB + 500) / 1000, /* 0.1 % */.decrement = (SFB_MAX_PROB + 3000) / 6000,.penalty_rate = 10,.penalty_burst = 20,
};  

以下命令用于显示sfb的相关运行信息：

$ tc -s qdisc show dev ens38 
qdisc sfb 1: root refcnt 2 limit 1000 max 25 target 20increment 0.00050 decrement 0.00005 penalty rate 10 burst 20 (600ms 60ms)Sent 1032 bytes 12 pkt (dropped 0, overlimits 0 requeues 0) backlog 0b 0p requeues 0 earlydrop 0 penaltydrop 0 bucketdrop 0 queuedrop 0 childdrop 0 marked 0maxqlen 0 maxprob 0.00000 avgprob 0.00000 

SFB入队列

如下SFB入队列函数sfb_enqueue，当队列长度超过或者等于限制值limit时，丢弃报文。

static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free)
{struct sfb_sched_data *q = qdisc_priv(sch);struct Qdisc *child = q->qdisc;struct tcf_proto *fl;u32 p_min = ~0;u32 minqlen = ~0;u32 r, sfbhash;u32 slot = q->slot;int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;if (unlikely(sch->q.qlen >= q->limit)) {qdisc_qstats_overlimit(sch);q->stats.queuedrop++;goto drop;}

如果重新进行哈希操作的时间间隔大于零，判断是否时间已到，成立的话进行扰数的更新和slot的切换，参见函数sfb_swap_slot，并且更新重哈希时间戳。否则，如果到了双缓存的预热时间，开启双缓存double_buffering预热，变量warmup_time定义了在重哈希之前的多长时间为预热时间。

    if (q->rehash_interval > 0) {unsigned long limit = q->rehash_time + q->rehash_interval;if (unlikely(time_after(jiffies, limit))) {sfb_swap_slot(q);q->rehash_time = jiffies;} else if (unlikely(!q->double_buffering && q->warmup_time > 0 &&time_after(jiffies, limit - q->warmup_time))) {q->double_buffering = true;}}

SFB可使用tc配置的外部classifier分类器，也可使用内部的哈希计算值（默认情况），两种情况都要增加扰数（perturbation-每个slot有不同的扰数）。

    fl = rcu_dereference_bh(q->filter_list);if (fl) {u32 salt;/* If using external classifiers, get result and record it. */if (!sfb_classify(skb, fl, &ret, &salt))goto other_drop;sfbhash = jhash_1word(salt, q->bins[slot].perturbation);} else {sfbhash = skb_get_hash_perturb(skb, q->bins[slot].perturbation);}if (!sfbhash)sfbhash = 1;sfb_skb_cb(skb)->hashes[slot] = sfbhash;

得到的哈希值为32bit，内核的SFB实现使用8个级别（SFB_LEVELS），每个级别16个桶（SFB_BUCKET_SHIFT=4），这样每4位的哈希值可覆盖一个级别内所有的桶。如果哈希桶的队列长度为零，降低Pm值。反之，如果队列长度大于设定的桶大小（bin_size，这里为20），增加Pm的值。

另外，在循环过程中，记录下最小的队列长度，以及Pm的最小值（p_min）。

    for (i = 0; i < SFB_LEVELS; i++) {u32 hash = sfbhash & SFB_BUCKET_MASK;struct sfb_bucket *b = &q->bins[slot].bins[i][hash];sfbhash >>= SFB_BUCKET_SHIFT;if (b->qlen == 0)decrement_prob(b, q);else if (b->qlen >= q->bin_size)increment_prob(b, q);if (minqlen > b->qlen)minqlen = b->qlen;if (p_min > b->p_mark)p_min = b->p_mark;}

如果最小队列长度（minqlen）已经大于设定的最大值，将报文丢弃。

    slot ^= 1;sfb_skb_cb(skb)->hashes[slot] = 0;if (unlikely(minqlen >= q->max)) {qdisc_qstats_overlimit(sch);q->stats.bucketdrop++;goto drop;}

以上的slot与1的异或操作，已经反转了slot的值。在Pmin的值大于等于SFB_MAX_PROB的情况下，如果启用了double_buffering预热功能，依据报文的哈希结果，对预备slot的哈希桶进行类似的操作。最后，调整到enqueue执行，将报文添加到队列中。

    if (unlikely(p_min >= SFB_MAX_PROB)) {/* Inelastic flow */if (q->double_buffering) {sfbhash = skb_get_hash_perturb(skb, q->bins[slot].perturbation);if (!sfbhash)sfbhash = 1;sfb_skb_cb(skb)->hashes[slot] = sfbhash;for (i = 0; i < SFB_LEVELS; i++) {u32 hash = sfbhash & SFB_BUCKET_MASK;struct sfb_bucket *b = &q->bins[slot].bins[i][hash];sfbhash >>= SFB_BUCKET_SHIFT;if (b->qlen == 0)decrement_prob(b, q);else if (b->qlen >= q->bin_size)increment_prob(b, q);}}if (sfb_rate_limit(skb, q)) {qdisc_qstats_overlimit(sch);q->stats.penaltydrop++;goto drop;}goto enqueue;}

如果以上条件不成立，进行随机报文丢弃（RED/ECN）处理。即Pmin的值小于SFB_MAX_PROB，取一个随机值，如果此随机值（r）小于Pmin，并且报文支持ECN，设置marked标记，否则，丢弃报文。但是，在此之前，先判断一下Pmin是否过大，如果大于SFB_MAX_PROB的一半，并且随机值r的一半小于Pmin超出（SFB_MAX_PROB / 2）的值，直接丢弃报文，不进行ECN标记判断。

    r = prandom_u32() & SFB_MAX_PROB;if (unlikely(r < p_min)) {if (unlikely(p_min > SFB_MAX_PROB / 2)) {/* If we're marking that many packets, then either* this flow is unresponsive, or we're badly congested.* In either case, we want to start dropping packets.*/if (r < (p_min - SFB_MAX_PROB / 2) * 2) {q->stats.earlydrop++;goto drop;}}if (INET_ECN_set_ce(skb)) {q->stats.marked++;} else {q->stats.earlydrop++;goto drop;}}

以下为qdisc的入队列函数，成功入队列之后，使用函数increment_qlen增加SFB哈希桶中相应的队列长度。

enqueue:ret = qdisc_enqueue(skb, child, to_free);if (likely(ret == NET_XMIT_SUCCESS)) {qdisc_qstats_backlog_inc(sch, skb);sch->q.qlen++;increment_qlen(skb, q);} else if (net_xmit_drop_count(ret)) {q->stats.childdrop++;qdisc_qstats_drop(sch);}

SFB出队列

SFB的出队列处理相对来说比较简单，调用SFB的函数decrement_qlen减少哈希桶中对于bin的队列长度。

static struct sk_buff *sfb_dequeue(struct Qdisc *sch)
{struct sfb_sched_data *q = qdisc_priv(sch);struct Qdisc *child = q->qdisc;struct sk_buff *skb;skb = child->dequeue(q->qdisc);if (skb) {qdisc_bstats_update(sch, skb);qdisc_qstats_backlog_dec(sch, skb);sch->q.qlen--;decrement_qlen(skb, q);}return skb;
}

SFB虚拟队列长度

在成功执行qdisc_enqueue之后，调用increment_qlen增加队列长度。这里分别对两个slot：0和1，分别执行增加操作。对于队列长度的递减decrement_qlen函数，原理相同，分别递减slot0和1中相应的哈希桶队列长度。

static void increment_qlen(const struct sk_buff *skb, struct sfb_sched_data *q)
{u32 sfbhash;sfbhash = sfb_hash(skb, 0);if (sfbhash)increment_one_qlen(sfbhash, 0, q);sfbhash = sfb_hash(skb, 1);if (sfbhash)increment_one_qlen(sfbhash, 1, q);
}

遍历指定slot中，每个级别（SFB_LEVELS）中哈希对应的桶，如果其队列长度小于0xFFFF，将其递增。队列的递减函数decrement_one_qlen，原理与此相同。

static void increment_one_qlen(u32 sfbhash, u32 slot, struct sfb_sched_data *q)
{int i;struct sfb_bucket *b = &q->bins[slot].bins[0][0];for (i = 0; i < SFB_LEVELS; i++) {u32 hash = sfbhash & SFB_BUCKET_MASK;sfbhash >>= SFB_BUCKET_SHIFT;if (b[hash].qlen < 0xFFFF)b[hash].qlen++;b += SFB_NUMBUCKETS; /* next level */}
}

标记概率Pm计算

当队列长度等于零时，减低Pm的值，如下函数decrement_prob。递减的步长decrement可通过TC命令设置，默认为：(SFB_MAX_PROB + 3000) / 6000。

static void decrement_prob(struct sfb_bucket *b, struct sfb_sched_data *q)
{b->p_mark = prob_minus(b->p_mark, q->decrement);
}

当队列长度大于等于bin_size时（以上TC命令设置为20，其也是默认值），增加Pm值。递增的步长increment可通过TC命令设置，默认为：(SFB_MAX_PROB + 500) / 1000。

static void increment_prob(struct sfb_bucket *b, struct sfb_sched_data *q)
{b->p_mark = prob_plus(b->p_mark, q->increment);
}

Pm值使用Q0.16格式表示，即没有整数部分，小数部分由16bit表示。默认情况下，increment的值等于：（65535 + 500）/1000 = 66.035，除以SFB_MAX_PROB的话，相当于0.001007。decrement的默认值为：（65535 + 3000）/6000 = 11.4225，除以SFB_MAX_PROB的话，相当于0.000174。

#define SFB_MAX_PROB 0xFFFFstatic const struct tc_sfb_qopt sfb_default_ops = {.rehash_interval = 600 * MSEC_PER_SEC,.warmup_time = 60 * MSEC_PER_SEC,.limit = 0,.max = 25,.bin_size = 20,.increment = (SFB_MAX_PROB + 500) / 1000, /* 0.1 % */.decrement = (SFB_MAX_PROB + 3000) / 6000,

以下为Pm的增减函数prob_plus和prob_minus，其取值范围为：[0, 65535]。

static u32 prob_plus(u32 p1, u32 p2)
{u32 res = p1 + p2;return min_t(u32, res, SFB_MAX_PROB);
}static u32 prob_minus(u32 p1, u32 p2)
{return p1 > p2 ? p1 - p2 : 0;
}

SFB哈希扰数

如下函数sfb_swap_slot，在切换slot时，更新之前使用的slot的扰数值（perturbation），关闭双缓存预热开关。

static void sfb_init_perturbation(u32 slot, struct sfb_sched_data *q)
{q->bins[slot].perturbation = prandom_u32();
}static void sfb_swap_slot(struct sfb_sched_data *q)
{sfb_init_perturbation(q->slot, q);q->slot ^= 1;q->double_buffering = false;
}

非响应性流限速

如果penalty_rate或者penalty_burst设置为零，丢弃非响应性流的报文。初始化时tokens_avail设置为与penalty_burst相同的值，token_time为初始化时的时间戳。所以，开始时一直递减可用的token值（tokens_avail），并且不丢报文，不限速。当前tokens_avail递减到小于1时，检查经过了多长时间（不大于10秒钟），根据此时间长度更新可用的令牌值，其值不能大于penalty_burst给出的上限值。tokens_avail小于1时，进行限速。

static bool sfb_rate_limit(struct sk_buff *skb, struct sfb_sched_data *q)
{if (q->penalty_rate == 0 || q->penalty_burst == 0)return true;if (q->tokens_avail < 1) {unsigned long age = min(10UL * HZ, jiffies - q->token_time);q->tokens_avail = (age * q->penalty_rate) / HZ;if (q->tokens_avail > q->penalty_burst)q->tokens_avail = q->penalty_burst;q->token_time = jiffies;if (q->tokens_avail < 1)return true;}q->tokens_avail--;return false;

内核版本 5.0