《cbq流速控制实现分析.doc》由会员分享，可在线阅读，更多相关《cbq流速控制实现分析.doc（6页珍藏版）》请在金锄头文库上搜索。
1、本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。 E-mail: 来源: http:/ cbq流速整形实现机制3（一）空闲资源流控算法算法概述：单位时间内产生的空闲资源一定，每发送一个字节都要消耗相应大小的空闲资源，当空闲资源不足时停止发送数据包，设定的流速越大，发送一个字节所消耗的空闲资源就越小，通过设置发送一个字节所消耗的空闲资源来进行流速控制。基本概念:1. 空闲资源：发送一个数据包都必须消耗空闲资源，如果某个对象的空闲资源为0，将无法发送数据包，只要空闲资源足够多就可以发送数据包。(TC用户空间规则定每秒产
2、生的空闲资源是TIME_UNITS_PER_SEC1000000，而TC内核根据空闲时间来计算空闲资源。)2.空闲时间：假设对象最近一次发送数据包的时刻是T1，系统当前的时刻是T2，则空闲时间tk = T1 T2。2. 流速rate：每秒允许发送的的字节个数。3. 空闲资源积累量：以空闲时间为参数根据一定的算法得到的值（比如可以将空闲时间乘上一个正数），但是要保证空闲时间越大，对应的空闲资源的积累量必定要越大。4. 空闲资源剩余量：最近一次发送数据包以后，空闲资源的剩余量。5. 当前可用空闲资源：以空闲资源的剩余量和空闲资源的积累量为参数根据一定的算法得到的值（比如可以 = 1/6空闲资源的剩
3、余量 + (1 1/6)空闲资源的积累），但是要保证当前可用空闲资源都是空闲资源剩余量和空闲资源积累量的递增函数。为了更好的理解空闲资源流控算法，需要引入流速概念的第二种描述，也就是，使用空闲资源来描述流速的概念。6.流速kc(用空闲资源描述)：假设每秒产生的空闲资源是TIME_UNITS_PER_SEC，流速rate(每秒允许发送的数据量是rate个字节)，则发送一个字节的流量需要消耗的空闲资源是kc = TIME_UNITS_PER_SEC/rate这里的kc就是新引入的流速描述方法。流速rate越大，kc就越小。如果要发送size字节的数据包需要消耗size*(TIME_UNITS_PE
4、R_SEC/rate)的空闲资源。只要空闲资源足够多，就可以发送数据包，每发送一个数据包，空闲资源减去相应的消耗量。只要空闲时间一直累积，空闲资源将会变得很大，这时就失去了调控流速的意义，所以引入最大空闲资源，以使空闲资源不会太大。调控流速的过程：假设只要空闲资源非零，就试图发送一个长度是L的数据包，流速是kc。1. 初始时刻空闲资源和空闲时间都为0，显然不允许发送数据包。2. 休眠一段时间，空闲时间大于0，计算空闲资源累积量，并计算当前可用空闲资源tu。3. 计算L长度的数据包需要消耗kc*L的空闲资源，如果tu a*L，发送数据包，否则再休眠一段时间。4. 发送数据包后减少空闲资源：tu
5、= tu a*L，如果tu 0，重复3的过程，直到再次休眠。5. 最理想的状态是：总是成立ts = a*L。基本上时可以达到调控的目的，但是结果是不准确的，相同的算法，相同的参数，在不同的网络环境（主要是硬件的配置不同）中流控的结果肯定不同。但是可以根据具体的网络环境，来选择适当的参数来提高算法的准确度。可以调整的参数有两类：1. 算法参数，2. 配置参数。可调整算法参数有：1. 空闲时间和空闲资源的换算参数 2. 每秒可产生的空闲资源TIME_UNITS_PER_SEC。可以调整的配置参数很多，可以参看linux高级路由与流量控制。比如，实际要的流速是real_rate，当配置流速是rate
6、1时，实际的流速比要求的大，此时就可以减小配置流速，还可以通过调整其它的配置参数来调整精确度。下面分析一下linux内核的具体实现：(令牌桶和CBQ流控都是使用这个流控算法，不同点在于算法参数不同)具体的实现是把数据包长度和空闲资源的消耗量的对应关系放在一个256大的数组内，数组的大小固定且不大，而数据包的大小是不固定的且可能比较大，那么数据包和数组如何建立对应关系呢？看linux的的实现代码。int tc_calc_rtable(struct tc_ratespec *r, _u32 *rtab, int cell_log, unsigned mtu, enum link_layer lin
7、klayer)int i;unsigned sz;unsigned bps = r-rate;获得配置流速(字节单位)unsigned mpu = r-mpu;最小数据包长度if (mtu = 0)mtu = 2047;如果最大数据包长度未设定，使用默认值if (cell_log cell_log) 255)cell_log+;for (i=0; i256; i+) sz = tc_adjust_size(i + 1) cell_align=-1; / Due to the sz calcr-cell_log=cell_log;/填写指数偏移参数return cell_log;/返回指数偏移参
8、数流速控制结构如图0所示;图0 流速控制结构rtab数组的每个元素存储相应长度的数据包应消耗的剩余资源，将数据包的长度进行指数偏移，得到对应的数组索引号，也就如果得到的值大于rtab的大小，则对应的消耗量，将会很大(惩罚)。现在整个限速控制流程可以总结：1. 启动CBQ流控对象，并根据优先级顺序选择一个子类。2. 判断选择的子类是否为空，不为空，则试图发送子类中的一个数据包。3. 根据rtab数组计算数据包的空闲资源消耗量。4. 如果子类的可用空闲资源大于需要消耗的空闲资源，发送数据包，否则不发送，并选择下一个子类。5. 发送数据包完毕，刷新子类的空闲资源，如果大于0，执行2，否则选择下一个子
9、类。可以进行流速控制的流控对象有CBQ， TBF(令牌桶)，HTB(分层令牌桶)，HFSC，其中前3个都是使用这个流控算法。(二) cbq流速整形实现机制cbq类型的流控对象是用于流速整形，而流速整形的实现是基于cbq子类，cbq子类的流速控制是基于空闲资源流控算法，前面已经介绍了空闲资源流控算法，在这里就不详细介绍了。cbq子类：一个流速整形器，使用结构struct cbq_class来实现，其关键的属性有：1.流速大小 2.最大空闲资源 3.最小空闲资源 4.平均数据包大小 5.优先级 6.权重。每个cbq对象必然有一个根cbq子类，也可以通过tc class add命令来建立更多的cbq
10、子类，并可以建立一定的逻辑结构。（tc class add | del | change | get 命令就是用于操作cbq子类）每个cbq子类都有自己的classid，根子类的classid等于cbq对象句柄。每个cbq子类都有一个过滤器链，和一个流控对象。cbq子类就是用来控制其内部流控对象的流速。流速的控制是基于空闲资源流控算法。运行一个cbq子类就是运行cbq子类中的流控对象。子类的流控对象每发送一个数据包，子类的空闲资源就相应的减少，当空闲资源不足时，停止运行这个子类。图 1，图2展示了cbq子类和cbq子类间，cbq子类和对象间的逻辑关系：(其中cbq_sched_data是cbq
11、对象的私有数据)图1 cbq子类逻辑关系图2 流控对象逻辑关系cbq子类建立起亲属关系的逻辑结构有以下2方面作用：1. 当子类的空闲资源不够时，可以借用父类的空闲资源。2. 入队时，最先遍历根类的过滤器链选择一个子类，然后会继续调用这个子类的过滤器链选择一个子类，直到最终确定一个子类，并将数据包加入最终确定的子类的流控对象中。注意：cbq子类的查找并不是根据亲属逻辑来进行，而是使用cbq子类查找哈希表，每个cbq子类必须在查找哈希中注册。cbq子类查找哈希表结构如图3所示：图3 cbq子类查找哈希表函数struct cbq_class *cbq_class_lookup(struct cbq_
12、sched_data *q, u32 classid)用来遍历cbq查找哈希表，返回id号是classid的cbq子类地址。cbq入队过程可以总结如下：1. 获得根cbq子类，如果过滤器为空，加入根cbq子类的流控对象，最后返回；否则执行2。2. 遍历过滤器链，试图选择一个子类，如果没有匹配成功，加入根cbq子类的流控对象，并返回；如果匹配成功，选择一个cbq子类，转入3.3. 遍历前边选择的cbq子类的过滤器链，试图选择一个子类，如果没有匹配成功，加入本子类的流控对象，并返回；如果匹配成功，选择一个cbq子类，重新执行3.注意：每个cbq子类在建立时都自带一个流控对象(pfifo类型)，称作
13、默认流控对象。默认流控对象是没有对象句柄的，我们是没法引用这个对象，替换后的对象必定有一个对象句柄(默认的句柄或者指定的)，是可以被引用的对象(比如修改，删除，添加子对象等等)。只有默认对象才可以直接使用tc qdisc add替换，其它对象必须先删除或者使用tc qdisc replace来替换。（这是由于默认子对象没有在根对象中注册，tc qdisc add添加的位置必定是默认对象或者非默认对象，如果该对象没有在根对象注册，说明是默认对象，可以使用add被替换，否则不能使用add替换）。cbq对象的出队过程使用到一个新的结构优先级活动队列数组，队列数组结构如图4所示：数组的每个元素都指向一
14、个cbq子类队列。第一个cbq子类队列的优先级最高，最多可以设置8个优先级。图3 优先级活动队列数组cbq对象的出队函数会根据优先级顺序轮询优先级活动队列中的所有cbq子类，运行一个cbq子类就是运行cbq子类中的流控对象。每个cbq子类必须加入优先级活动队列，才可以发送数据包。如果cbq子类的优先级是4，将会加入第4个活动队列。cbq对象是通过以下成员来使每个队列都轮流取得发包的机会。(在cbq对象的私有数据结构中)intnclassesTC_CBQ_MAXPRIO+1;/相应活动队列的子类个数unsignedquantaTC_CBQ_MAXPRIO+1;/相应活动队列权重unsignedactivemask;/活动队列掩码struct cbq_class*activeTC_CBQ_MAXPRIO+1;/活动队列数组优先级活动队列数组的大小是8，相应位置的元素和activemask相应位对应，0表示链中有子类。例如：activemask = 11111101 则只有active2中有cbq子类，其他元素都指向NULL。active0的优先级最高。cbq对象运行的过程：1. 根据队列掩码active
