Linux内核中流量控制(7)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn

5.7 RED(Random Early Detection queue)

RED算法由Sally Floyd和Van Jacobson提出, 论文为"Random Early Detection Gateways  for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking.

基本算法:
对新数据包计算平均队列长度:
平均长度avg=(1-W) * avg + W*当前队列长度
 W是参数, 取值为1/(2^Wlog), Wlog可配置, W越小, 平滑能力越强.
 算法中两个阈值: th_min和th_max, 这两个参数可配置
当avg > th_max时,  该新包被丢弃;
当avg < th_min时,  该新包允许通过;
当th_min <= avg <= th_max时, 计算概率:
 Pb = max_P * (avg - th_min)/(th_max-th_min)
然后按此概率丢包, max_P为一小数, 通常为0.01, 0.02等, 一般在算法中通过右移操作来实现:
 max_P = (qth_max-qth_min)>>Plog
Plog为可配置参数

5.7.1 RED操作结构定义

// RED算法参数
struct red_parms
{
 /* Parameters */
// 最小队列长度
 u32  qth_min; /* Min avg length threshold: A scaled */
// 最大队列长度
 u32  qth_max; /* Max avg length threshold: A scaled */
// 最大休眠时间
 u32  Scell_max;
// 保存随机掩码
 u32  Rmask;  /* Cached random mask, see red_rmask */
//
 u8  Scell_log;
// Wlog, Plog参数含义如上所示
 u8  Wlog;  /* log(W)  */
 u8  Plog;  /* random number bits */
// 256个元素
 u8  Stab[RED_STAB_SIZE];
 /* Variables */
// 以下的参数是在处理过程中会改变的参数
// 从上次随机数产生时的处理的数据包数
 int  qcount;  /* Number of packets since last random
        number generation */
// 缓存的随机数
 u32  qR;  /* Cached random number */
// 平均队列长度
 unsigned long qavg;  /* Average queue length: A scaled */
// 当前休眠起始时间
 psched_time_t qidlestart; /* Start of current idle period */
};

// RED私有数据
struct red_sched_data
{
// 最大队列长度, 这是硬限制
 u32   limit;  /* HARD maximal queue length */
// 标志
 unsigned char  flags;
// RED算法参数
 struct red_parms parms;
// RED统计值
 struct red_stats stats;
 struct Qdisc  *qdisc;
};

// RED流控操作结构
static struct Qdisc_ops red_qdisc_ops = {
 .id  = "red",
 .priv_size = sizeof(struct red_sched_data),
 .cl_ops  = &red_class_ops,
 .enqueue = red_enqueue,
 .dequeue = red_dequeue,
 .requeue = red_requeue,
 .drop  = red_drop,
 .init  = red_init,
 .reset  = red_reset,
 .destroy = red_destroy,
 .change  = red_change,
 .dump  = red_dump,
 .dump_stats = red_dump_stats,
 .owner  = THIS_MODULE,
};

// RED类别操作结构
static struct Qdisc_class_ops red_class_ops = {
 .graft  = red_graft,
 .leaf  = red_leaf,
 .get  = red_get,
 .put  = red_put,
 .change  = red_change_class,
 .delete  = red_delete,
 .walk  = red_walk,
 .tcf_chain = red_find_tcf,
 .dump  = red_dump_class,
};
 
5.7.2 RED一些基本操作函数

在include/net/red.h中定义

// 返回Plog对应RED掩码, 和网络掩码不同,RED掩码值是从低位开始算的
// 掩码值位2^Plog-1, , Plog超过31后就和31相同
static inline u32 red_rmask(u8 Plog)
{
 return Plog < 32 ? ((1 << Plog) - 1) : ~0UL;
}

// 设置RED参数, 平均长度阈值的最大最小值等
static inline void red_set_parms(struct red_parms *p,
     u32 qth_min, u32 qth_max, u8 Wlog, u8 Plog,
     u8 Scell_log, u8 *stab)
{
 /* Reset average queue length, the value is strictly bound
  * to the parameters below, reseting hurts a bit but leaving
  * it might result in an unreasonable qavg for a while. --TGR
  */
 p->qavg  = 0;
// 队列元素统计
 p->qcount = -1;
// 内部平均长度阈值的最大最小值为设置值的2^Wlog倍
 p->qth_min = qth_min << Wlog;
 p->qth_max = qth_max << Wlog;
 p->Wlog  = Wlog;
 p->Plog  = Plog;
// 随机掩码
 p->Rmask = red_rmask(Plog);
 p->Scell_log = Scell_log;
// 最大休眠时间
 p->Scell_max = (255 << Scell_log);
// stab
 memcpy(p->Stab, stab, sizeof(p->Stab));
}

// 算法是否在休眠状态, 也就是看qidlestart是否为0, qidlestart非0表示正在休眠
static inline int red_is_idling(struct red_parms *p)
{
 return !PSCHED_IS_PASTPERFECT(p->qidlestart);
}

// RED休眠, 将p->qidlestart设置为当前时间
static inline void red_start_of_idle_period(struct red_parms *p)
{
 PSCHED_GET_TIME(p->qidlestart);
}
// RED停止休眠, 将p->qidlestart设置清零
static inline void red_end_of_idle_period(struct red_parms *p)
{
 PSCHED_SET_PASTPERFECT(p->qidlestart);
}

// RED算法重新启动
static inline void red_restart(struct red_parms *p)
{
// RED数值清零,
 red_end_of_idle_period(p);
 p->qavg = 0;
 p->qcount = -1;
}

// 从休眠恢复后重新计算队列平均值
static inline