logo资料库

队列管理算法RED源码全解全析.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.22M 资料格式：pdf 举报 版权申诉
第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
资料共21页，剩余部分请下载后查看
    主动队列管理算法 主动队列管理算法 主动队列管理算法 源码全解全析 源码全解全析 源码全解全析 version version version （（（ REDREDRED 0.11 0.11 0.11 ））） author author author ：：： souroot souroot souroot --------------------------------------------- --------------------------------------------- --------------------------------------------- 有问题或者有基于 有问题或者有基于 有问题或者有基于 NSNSNS 的项目合作都可联系我 的项目合作都可联系我 的项目合作都可联系我 QQ:406774647 QQ:406774647 QQ:406774647 欢迎加入网络流量控制 欢迎加入网络流量控制 欢迎加入网络流量控制 &&& 队列管理 队列管理 队列管理 QQQQQQ 群：群：群： 群号：群号：群号： 74012467 74012467 74012467
    序 我研究生阶段研究定的方向是网络拥塞管理，而我研究 RED 算法也有挺长时间了，很久以前就有解析 NS 中的队列 管理算法 RED 的源代码（red.cc&red.h）的想法，借寒假有 时间，匆匆写了一下。有些东西自己也没完全弄懂，但是对 于困惑于如何修改 RED 算法的同学来说，应该有很大的参 考价值。 本文档首先分析了 RED 算法涉及参数的含义，然后给出 了主要函数的作用，最后对主要函数的源代码进行了分析。 希望本文档对你有用。 souroot 2010-2-5
    关于版本 0.11 的说明： 添加了 RED 算法的参数的默认设置（见附录 1）
    主动队列管理算法 RED 源码全解全析 目录 一、一、一、 二、二、二、 三、三、三、 参数解析 参数解析 参数解析 函数功能 函数功能 函数功能 函数解析 函数解析 函数解析 .............................................................................................................................1 .............................................................................................................................2 .............................................................................................................................3 3.1 initialize_params()................................................................................................................ 3 3.2 reset().....................................................................................................................................5 3.3 updateMaxPFeng（）.......................................................................................................... 6 3.4 updateMaxP（）.................................................................................................................. 7 3.5 estimator（）........................................................................................................................8 3.6 deque()...................................................................................................................................9 3.7 calculate_p_new()................................................................................................................. 9 3.8 modify_p（）..................................................................................................................... 10 3.9 drop_early（）................................................................................................................... 11 3.10 pickPacketToDrop()..........................................................................................................12 3.11 enque( )..............................................................................................................................12 ns-default.tcl 中 RED 参数的设置.................................................................................................. 16 附录 111 16
    主动队列管理算法 RED 源码全解全析 参数解析 参数解析 参数解析 一、一、一、 说明：所谓默认设置，即 ns-default.tcl 文件中的设置。 在 red.h 中， 在结构体 edp 中，定义了让用户自己赋值的参数，默认由 ns-2.xx/tcl/lib/ns-default.tcl 文件赋 值。 int mean_pktsize; 平均每个包的大小，默认为 500KB; int idle_pktsize; 在队列空闲时每个包的大小，默认为 100KB； int bytes; 如果为 true 则队列的大小以字节数来计算，若为 false 则队列大小以包的个数 来计算； int wait; int setbit; int gentle; /* true for waiting between dropped packets */默认为 true，不知是何用意？ 如果为真则采用显式拥塞通知（ECN）的方式（拥塞通知有两种方式：采 用提前丢包或者在包上设置拥塞位为真来实现），默认为 false； 如果 gentle 参数为真则当平均对列长度超过 maxthresh 后丢包概率是线性 缓慢增长的，而非直接变为 1，默认为 true； double th_min; 平均队列长度的最小阀值； double th_min_pkts; 总是以数据包个数来计算数据流量； double th_max; 平均队列长度的最大阀值； double th_max_pkts; 总是以数据包个数来计算数据流量； double max_p_inv; 最大丢包概率的倒数： 1/max_p； double mark_p; 当 p < mark_p 时，标记被选择的包；当 p > mark_p 时，丢弃被选择的包； mark_p 的默认值为 0.1； int use_mark_p; 如果采用 ECN 的方式，那么当队列长度没有满时设置 use_mark_p 参数为 double q_w; int adaptive; int cautious; true 并且设置 mark_p 参数的值为 2.0，默认设置①为 true； 给当前抽样瞬时队列的队列权重； 若参数 adaptive 的值为 1 则使用 ARED 算法， 为 0 则为 RED 算法，默 认为 0； 当瞬时队列长度小于平均队列长度很多时作为不要丢包或者标记包的标 示符。 由用户配置，在 ns-default.tcl 文件中给的值为 0； 在 ARED 中的丢包概率 max_p 加法增加参数，即α，默认为 0.01； 在 ARED 中的丢包概率 max_p 乘法减小参数，即β，默认为 0.9； /* adaptive RED: interval for adaptations */ ========================以下参数为 ARED 特有=========================== double alpha; double beta; double interval; double targetdelay; double top; double bottom; 在 ARED 中 max_p 所允许的下限，默认设置是动态配置（在 0~0.01 之间 ） int feng_adaptive; 使用 Feng 等人版本的 ARED，默认是不采用的（注：ARED 有两个版本）； 每秒钟包的个数，它是在 reset()函数中定义的，是指一条链路上所能容纳 double ptc; 的数据包的最大个数； 连接延时； double delay; 在 ARED 中希望达到的转发延时，默认为 0.005s，即 5ms； 在 ARED 中 max_p 所允许的上限，默认的设置为 0.5； 1
    主动队列管理算法 RED 源码全解全析 /* v_prob = v_a * v_ave + v_b */ 以下参数的值有 RED 算法源码直接提供（在结构体 edv 中） TracedDouble v_ave; 平均队列长度； TracedDouble v_prob1; 在被"count"之前的丢包概率； double v_prob; 丢包概率 double v_a; double v_b; double v_c; double v_d; int count; int count_bytes; 自从上次丢弃事件发生后接收的字节数。 int old; TracedDouble cur_max_p; 当前的丢包概率 double lastset; 在 gentle 模式中使用； 在 gentle 模式中使用； 自从上次丢包后过来包的数量？ ARED 中上一次参数动态调整的时间 /* 0 when average queue first exceeds thresh */ ==========================其它的参数================================ int qib_; int drop_tail_; int drop_front_; 丢最前面的数据包，默认为 false； int drop_rand_; 随机丢弃，默认为 false； 为真则数据以字节数来计算，为假则数据以包的个数来计算 丢尾，默认为 ture ①所谓默认设置，即 ns-default.tcl 文件中的设置； 二、二、二、 函数功能 函数功能 函数功能 绿色字体为已经解析的代码； 灰色字体是已经弃用的代码，不做解析； 蓝色字体的代码量含义显而易见，因此不做解析； 红色字体为与 tcl 文件的交互代码，不做解析； ===================================================================== 1 2 3 4 int command(int argc, const char*const* argv); void enque(Packet* pkt); 负责对接收到的数据包进行处理； virtual Packet *pickPacketForECN(Packet* pkt); virtual Packet *pickPacketToDrop(); 选择 一 个 数 据 包 来 丢 弃 ， 常 用 的 有 droptail ， drophead，dorpradom，为 enque 所调用； Packet* deque( ); 返回下一个将要被转发的队列中的包； void initialize_params(); 初始化那些动态配置的参数：qw，th_min_pkts，th_max_pkts， 以及 bottom。为 reset（）函数所调用； void initParams(); 初始化那些静态配置的参数，一般为 0，为 REDQueue 类的构造函数 所调用； void reset(); 用于在连接前初始化参数，为谁所调用还不知道。 void run_estimator(int nqueued, int m); /* Obsolete */ 8 9 10 double estimator(); 计算平均队列长度，为 enque( )函数所调用； 11 void updateMaxP(double new_ave, double now); 动态调整 maxp 的值，以让平均队列长 5 6 7 2
    主动队列管理算法 RED 源码全解全析 度达到目标范围内，为 estimator（）函数所调用； 12 void updateMaxPFeng(double new_ave); 功能 updateMaxP( )一样，也同样为 estimator（） 函数所调用； 13 int drop_early( ); 根据丢包概率来决定这个包是被丢弃还是被转发，为 enque( )函数所调 用； 14 double modify_p( ); 计算丢包概率 max_p，这个计算的 max_p 和上一次丢包到现在为止 所转发的数据包有关，为 drop_early( )所调用； 15 double calculate_p_new( ); 计算丢包概率 p（并非最终的丢包概率），为 drop_early( )(或 者说 modefy_p()函数的调用)和 calculate_p（）函数所调用； 16 double calculate_p( ); 计算丢包概率 p，没有函数调用它，作用和 calculate_p_new( )是一 样的，至于为什么要设置两个功能一样的函数，源代码上的注释说是为了向前兼容。 17 virtual void reportDrop(Packet *pkt) {} 18 void print_summarystats(); 为 command 函数所调用； 19 int bcount_() { return q_->byteLength(); }; 返回以字节计算的队列长度（没见那个函数 //pushback ？没有实现的虚拟函数？ 调 用 它）； 20 void trace(TracedVar*); 循环的记录一些参数值的变化（需要在 tcl 文件中写相应的代码 来输出相应的参数变化情况），包括平均队列长度 ave，丢包概率以及瞬时队列长度 curq。 为 REDQueue 的构造函数所调用； 21 void print_edp(); 从屏幕上输出 edp 结构体中的参数的值，作为调试用的，为构造函数 所调用； 22 void print_edv(); 和 print_dep()的作用一样，从屏幕上输出 edp 结构体中的参数的值， 作为调试用的，为构造函数所调用； 函数解析 函数解析 函数解析 三、三、三、 3.1 initialize_params() /* * Note: if the link bandwidth changes in the course of the * simulation, the bandwidth-dependent RED parameters do not change. * This should be fixed, but it would require some extra parameters, * and didn't seem worth the trouble... */ void REDQueue::initialize_params() { /* * If q_weight=0, set it to a reasonable value of 1-exp(-1/C) * This corresponds to choosing q_weight to be of that value for * which the packet time constant -1/ln(1-q_weight) per default RTT * of 100ms is an order of magnitude more than the link capacity, C. 1 2 3 4 5 6 7 3
    主动队列管理算法 RED 源码全解全析 * * If q_weight=-1, then the queue weight is set to be a function of * the bandwidth and the link propagation delay. In particular, * the default RTT is assumed to be three times the link delay and * transmission delay, if this gives a default RTT greater than 100 ms. * * If q_weight=-2, set it to a reasonable value of 1-exp(-10/C). */ if (edp_.q_w == 0.0) { edp_.q_w = 1.0 - exp(-1.0/edp_.ptc); } else if (edp_.q_w == -1.0) { double rtt = 3.0*(edp_.delay+1.0/edp_.ptc); //printf("delay: %5.4f rtt: %5.4f\n", edp_.delay, rtt); if (rtt < 0.1) rtt = 0.1; edp_.q_w = 1.0 - exp(-1.0/(10*rtt*edp_.ptc)); } else if (edp_.q_w == -2.0) { edp_.q_w = 1.0 - exp(-10.0/edp_.ptc); } // printf("ptc: %7.5f bandwidth: %5.3f pktsize: %d\n", edp_.ptc, link_->bandwidth(), edp_.mean_pktsize); // printf("th_min_pkts: %7.5f th_max_pkts: %7.5f\n", edp_.th_min_pkts, edp_.th_max); if (edp_.th_min_pkts == 0) { edp_.th_min_pkts = 5.0; // set th_min_pkts to half of targetqueue, if this is greater // double targetqueue = edp_.targetdelay * edp_.ptc; if (edp_.th_min_pkts < targetqueue / 2.0 ) than 5 packets. edp_.th_min_pkts = targetqueue / 2.0 ; } if (edp_.th_max_pkts == 0) edp_.th_max_pkts = 3.0 * edp_.th_min_pkts; //printf("th_min_pkts: %7.5f th_max_pkts: %7.5f\n", edp_.th_min_pkts, edp_.th_max); //printf("q_w: %7.5f\n", edp_.q_w); if (edp_.bottom == 0) { edp_.bottom = 0.01; // Set bottom to at most 1/W, for W the delay-bandwidth // product in packets for a connection with this bandwidth, // 1000-byte packets, and 100 ms RTTs. // So W = 0.1 * link_->bandwidth() / 8000 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 4
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料