htb_yyz.c

/*
（一）空闲资源流控算法
算法概述：单位时间内产生的空闲资源一定，每发送一个字节都要消耗相应大小的空闲资源，当空闲资源不足时停止发送数据包，设定的流速越大，
发送一个字节所消耗的空闲资源就越小，通过设置发送一个字节所消耗的空闲资源来进行流速控制。

基本概念:

1. 空闲资源：发送一个数据包都必须消耗空闲资源，如果某个对象的空闲资源为0，将无法发送数据包，只要空闲资源足够多就可以发送数据包。
(TC用户空间规则定每秒产生的空闲资源是TIME_UNITS_PER_SEC       1000000，而TC内核根据空闲时间来计算空闲资源。)

2.空闲时间：假设对象最近一次发送数据包的时刻是T1，系统当前的时刻是T2，则空闲时间tk = T1 – T2。

2. 流速rate：每秒允许发送的的字节个数。
3. 空闲资源积累量：以空闲时间为参数根据一定的算法得到的值（比如可以将空闲时间乘上一个正数），但是要保证空闲时间越大，对应的空闲资源的积累量必定要越大。
4. 空闲资源剩余量：最近一次发送数据包以后，空闲资源的剩余量。
5. 当前可用空闲资源：以空闲资源的剩余量和空闲资源的积累量为参数根据一定的算法得到的值（比如可以 = 1/6空闲资源的剩余量 + (1 – 1/6)空闲资源的积累），
但是要保证当前可用空闲资源都是空闲资源剩余量和空闲资源积累量的递增函数。

为了更好的理解空闲资源流控算法，需要引入流速概念的第二种描述，也就是，使用空闲资源来描述流速的概念。
 

6.流速kc(用空闲资源描述)：假设每秒产生的空闲资源是TIME_UNITS_PER_SEC，流速rate(每秒允许发送的数据量是rate个字节)，则发送一个字节的流量需要消耗的
空闲资源是kc = TIME_UNITS_PER_SEC/rate
这里的kc就是新引入的流速描述方法。流速rate越大，kc就越小。

如果要发送size字节的数据包需要消耗size*(TIME_UNITS_PER_SEC/rate)的空闲资源。

只要空闲资源足够多，就可以发送数据包，每发送一个数据包，空闲资源减去相应的消耗量。

只要空闲时间一直累积，空闲资源将会变得很大，这时就失去了调控流速的意义，所以引入最大空闲资源，以使空闲资源不会太大。

调控流速的过程：
假设只要空闲资源非零，就试图发送一个长度是L的数据包，流速是kc。
1.      初始时刻空闲资源和空闲时间都为0，显然不允许发送数据包。
2.      休眠一段时间，空闲时间大于0，计算空闲资源累积量，并计算当前可用空闲资源tu。
3.      计算L长度的数据包需要消耗kc*L的空闲资源，如果tu > a*L，发送数据包，否则再休眠一段时间。
4.      发送数据包后减少空闲资源：tu = tu – a*L，如果tu > 0，重复3的过程，直到再次休眠。
5.      最理想的状态是：总是成立ts = a*L。

基本上时可以达到调控的目的，但是结果是不准确的，相同的算法，相同的参数，在不同的网络环境（主要是硬件的配置不同）中流控的结果肯定不同。
但是可以根据具体的网络环境，来选择适当的参数来提高算法的准确度。
可以调整的参数有两类：1. 算法参数，2. 配置参数。
可调整算法参数有：1. 空闲时间和空闲资源的换算参数 2. 每秒可产生的空闲资源TIME_UNITS_PER_SEC。

可以调整的配置参数很多，可以参看《linux高级路由与流量控制》。比如，实际要的流速是real_rate，当配置流速是rate1时，实际的流速比要求的大，此时就可以减小配置流速，还可以通过调整其它的配置参数来调整精确度。


本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。

E-mail: wwwlkk@126.com

来源: http://blog.csdn.net/wwwlkk



空闲资源流控算法---linux内核的具体实现

具体的实现是把数据包长度和空闲资源的消耗量的对应关系放在一个256大的数组内，
数组的大小固定且不大，而数据包的大小是不固定的且可能比较大，那么数据包和数组如何建立对应关系呢？看linux的的实现代码。
int tc_calc_rtable(struct tc_ratespec *r, __u32 *rtab,

                 int cell_log, unsigned mtu,

                 enum link_layer linklayer)

{

       int i;

       unsigned sz;

       unsigned bps = r->rate;获得配置流速(字节单位)

       unsigned mpu = r->mpu;最小数据包长度
 

       if (mtu == 0)

              mtu = 2047;如果最大数据包长度未设定，使用默认值
 

       if (cell_log < 0) {

              cell_log = 0;//指数偏移参数，保证最大数据包映射到数组的第255个元素
              while ((mtu >> cell_log) > 255)

                     cell_log++;

       }

 

       for (i=0; i<256; i++) {

              sz = tc_adjust_size((i + 1) << cell_log, mpu, linklayer);//获得数组元素对应的数据包长度(数量级的概念)

              rtab[i] = tc_calc_xmittime(bps, sz);//填写空闲资源消耗量
       }

 

       r->cell_align=-1; // Due to the sz calc

       r->cell_log=cell_log;//填写指数偏移参数
       return cell_log;//返回指数偏移参数
}

流速控制结构如图0所示;




图0 流速控制结构
rtab数组的每个元素存储相应长度的数据包应消耗的剩余资源，将数据包的长度进行指数偏移，得到对应的数组索引号，也就如果得到的值大于rtab的大小，则对应的消耗量，将会很大(惩罚)。
现在整个限速控制流程可以总结：
1.      启动CBQ流控对象，并根据优先级顺序选择一个子类。
2.      判断选择的子类是否为空，不为空，则试图发送子类中的一个数据包。
3.      根据rtab数组计算数据包的空闲资源消耗量。
4.      如果子类的可用空闲资源大于需要消耗的空闲资源，发送数据包，否则不发送，并选择下一个子类。
5.      发送数据包完毕，刷新子类的空闲资源，如果大于0，执行2，否则选择下一个子类。
 

可以进行流速控制的流控对象有CBQ， TBF(令牌桶)，HTB(分层令牌桶)，HFSC，其中前3个都是使用这个流控算法。


*/