多令牌桶流量控制排队算法的设计与实现

任春云 沙启鑫 尚传进 刘玉海

（1、中国海洋大学信息科学与工程学院，山东 青岛 266100 2、阿尔卡特-朗讯青岛研发中心，山东 青岛 266100）

1 引言

随着网络应用的日益广泛和一些新的网络技术的出现,网络流量控制和带宽管理成了一个亟待解决的问题[1][2]。Linux的TC模块提供了强大的流量控制功能[3][4]，其中TBF就是一种很精确的流量控制方式，它对网络和处理器的影响都很小[5]。但是tbf与其他流量控制算法一样，要对连续网段内的每个IP分配固定带宽，必须使用多条规则，否则就会共享带宽。

2 tbf算法的工作原理

令牌桶过滤器(TBF)[4]是一个简单的队列规则：它只允许以不超过事先设定的速率到来的数据包通过，但可能允许短暂突发流量朝过设定值。它很精确,对于网络和处理器的影响都很小。图1揭示了令牌桶的基本原理

图1 tbf原理示意图

令牌桶的控制机制是基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在足够的令牌，则允许发送流量；而如果令牌桶中不存在足够的令牌，则不允许发送流量,直到等到有足够令牌。在linux中令牌桶过滤器是上述机制的一个扩展（一个双重令牌桶）两个个令牌桶背靠靠背设置，一个用来保证平均速率，另一个用来设置峰值速率。

3 etbf的工作原理

为了实现在局域网中对每台机器平分带宽，我们可以在一个class下建立多个速率相同的tbf队列，但是这明显存在两个问题：a.每一个class下建多个队列，随着队列数的增加系统系能会急剧下降，b.过多的队列导致书写的困难。为了解决这个问题，我们根据tbf的令牌桶原理发展了etbf，一个etbf队列规则就可以为一个IP网段分配相同的带宽。在etbf中我们根据IP地址的数目来确定令牌桶的个数，每个令牌桶对应一个令牌桶队列来存储数据报。当一个数据报到达时，根据源地址或者目的地址将此数据报放入对应的令牌桶队列的末尾，如果没有相匹配的则放入到默认序列中。下面将从etbf数据结构、数据报的出对入队等方面介绍。

3.1 etbf的数据结构

我们把内核中tbf_sched_data数据结构扩展为 etbf_sched_data，etbf_sched_data 相对于tbf_sched_data增加五个变量

saddr，eaddr分别表示要控制的网段的开始和结束IP地址，flattr表示开始结束地址是源IP还是目的IP，subQueueList是一个链表，它的大小为subQueueListSize（等于eaddr减去saddr），链表中的每一个元素都是一令牌桶队列结构

其中tokens，ptokens表示对应序列中的普通令牌桶和峰值令牌桶，subQueue用来存储数据报。当一个数据报到达时根据IP分配到相应队列结构体中subQueue成员末尾。

3.2 入队处理

etbf_enqueue()函数进行入队处理。首先，提取数据报中IP地址，若此IP地址在（saddreaddr）范围内，根据IP将此数据报分配到sub－QueueList链表中相应的令牌桶对列中，如下所示：skb_queue_tail(&q->subQueueList[subQidx].subQueue,skb);如果不在，那么则将此数据报放入默认队列中，默认队列处理过程与tbf的处理过程相同

3.3 重入队处理

etbf_requeue()函数将先前移除的报文放回到队列中，处理的过程同入队处理，所不同的是入队是将数据报放在队尾，而重入对是放到对头，如下所示：skb_queue_head(&q->sub－QueueList[subQidx].subQueue,skb);

3.4 出队处理

出队函数etbf_dequeue(),是完成流量整形的关键所在。具体步骤如下：

①决定出队序列，并执行出队列操作以获取数据报skb,并检测skb的有效性。

若skb有效则执行下一步，否则继续执行这一步，直到找到有数据报的令牌桶序列。如果所有队列已经被遍历，那么执行默认队列出队处理。

②若skb有效，则根据当前队列的prokens和tokens及已用时间计算令牌的数量，若是有足够令牌返回，否则再重入对。

3.5 etbf shell脚本书写

etbf书写格式如下：

4 实验结果

我们选择实验环境如下一共十台机器，一台作为ftp服务器，一台运行etbf流量控制程序（eth0上传，eth1下载），其他八台作为ftp客户端下载（192.168.3.3-192.168.3.11）。

Linux为红旗6.0，内核为2.6.24.4。运行于网关状态下。

控制下行流量脚本如下

其中一个ip的控制效果图2，其他ip的效果图类似:

图2 etbf下行效果控制图

由图可见，开始时没有实施带宽管理策略，ftp下载占用了大量的带宽，且带宽波动较大。在实施带宽管理策略后，ftp服务占用的带宽迅速降低，最终每一个IP占用的带宽分别维持在351.6KB/s，(策略所实施的带宽分别为3000kbps)，且几乎没有波动。然后在撤销了带宽管理策略后，又恢复至原来状态。实验结果表明本文的etbf算法可以有效地限制每一个ip的带宽，并且不存在带宽共享问题,效果较好。

[2]陈蓓,蔡淮.基于Linux系统的IP服务质量(QoS)管理[J].计算机应用,2003,23,17~19.

[3]Bert Hubert.Linux Advanced Routing&Traffic Control HOWTO [DB/OL].http://lartc.org/ HOWTO/ cvs/ 2. 4routing/output/2.4routing.html,2002205201.

[4]Klaus Wehrle[等]2006 Linux网络体系结构:Linux内核中网络协议的设计与实现清华大学出版社,2006