日期:2014-05-16 浏览次数:20904 次
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