Linux流量控制分析及其算法改进

摘要：Linux在其内核中嵌入了的流量控制机制，但其在流量控制的队列调度算法方面仍然有所欠缺。本文在分析了Linux系统流量控制的内核实现基础上，提出了一种新的队列调度算法－基于流的MAWRED算法，并给出了其具体实现。

关键词：流量控制；队列调度； Linux；加权公平队列；随机早期检测；多平均队列加权随机早期检测

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)21-30547-03

1 序言

Linxu内核从Kernel 2.1.105开始支持QoS(服务质量)，其核心机理是在网络拥塞情况下，如何对不同数据进行调度和处理，即流量控制（TC）。如若要在Linux上实现QoS，必须要确保在编译内核时选中 Kernel/User netlink socket，因为只有这样 TC才能通过 netlink 与内核通讯。并要在编译时把队列规定和分类器都编进内核。应该说在目前通用的操作系统中，Linux对流量控制的实现是做的最好的，但因为Linux系统本身的开源特性，它的队列调度策略却从v2.2起基本没有大的改进。因而本文将在对Linux的流量控制机理进行分析的基础上，对其队列调度策略进行进一步的完善。本文中的基于流的MAWRED流量控制算法为本文创新点。

2 Linux流量控制原理

在linux中，对和网络相关的源代码都放在/Net目录和/include/Net目录下。首先我们了解一下Linux网络协议栈在没有TC模块时发送数据包的大致流程。当数据包进入系统核心时输入多路复用器将判断数据包的目的地址是否是本节点。如果是，这些数据包被送入网络传输层以等待进一步的处理，如果不是这些数据包会被送入转发区，同时本地节点的更高层应用程序产生的数据包也送入转发区内，系统查找路由表并确定这些数据包的下一跳地址。然后，这些数据包被排队送入输出队列中，

当数据包进入输出队列后，每个数据包的发送都会调用dev_queue_xmit函数（net/core/dev.c），在此判断是否需要向AF_PACKET协议支持体传递数据包内容，最后直接调用网卡驱动注册的发送函数把数据包发送给网卡。因而，如果要支持QoS功能，只要在dev_queue_xmit函数调用网卡驱动发送数据包之前，先调用流量控制的相关代码即可。有关代码如下：

int dev_queue_xmit(struct sk_buff *skb)

{……………….

struct net_device *dev = skb->dev;

struct Qdisc*q;

……………….

q = dev->qdisc;

if (q->enqueue) {

int ret = q->enqueue(skb, q);

qdisc_run(dev);

return;

}

if (dev->flags&IFF_UP) {

………….

if (netdev_nit)

dev_queue_xmit_nit(skb,dev);

if (dev->hard_start_xmit(skb, dev) == 0) {

return 0;

}

}

………………

}

从上面的代码中可以看出，当q->enqueue为假的时候，就不采用TC处理，而是直接发送这个数据包。如果为真，则对这个数据包进行QoS处理。

在了解过Linux的QoS入点后，我们再对Linux QoS的功能实现代码进行分析。Linux进行流量控制的基本思路如图1所示。

由图中可以看出，linux的流量控制包含三个基本模块：filter（过滤器）、Class（类别）和Queing discipline（排队策略）。当数据包进入内核的网络发送模块，由过滤器对数据包进行标记，送入不同的类别中，相应每个类别都有一个对应的队列策略负责数据包的最终输出调度。从Linux的流量控制整体架构中，可以看出队列策略是其核心所在。

队列策略的数据结构Qdisc在include/net/pkt_sched.h中定义：，

struct Qdisc

{

struct Qdisc_head h;

int (*enqueue)(struct sk_buff *skb, struct Qdisc *dev);

struct sk_buff * (*dequeue)(struct Qdisc *dev);

unsigned flags;

struct Qdisc_ops *ops; /*Qdisc操作函数集合*/

struct Qdisc *next;

u32 handle;

atomic_t refcnt;

struct sk_buff_head q;

struct device*dev;

.....

char data[0];

};

在Qdisc中有一个指针型变量ops指向Qdisc_ops结构，在Qdisc_ops中定义了队列策略的各类动作。

最新版的Linux内核（v2.6.17）中实现了14种队列调度策略：atm、cbq、csz、dsmark、fifo、gred、hfsc、htb、netem、prio、red、sfq、tbf和teql。在net\sched目录下针对每种调度策略都有一个单独的C语言实现文件。每一个策略实现文件的结构大体相同，都是对Qdisc_ops结构中描述的队列操作函数在该策略情景下的具体实现。因而，如果要进一步改进Linux的流量调度策略，只要在net\sched目录下实现该策略的C语言实现文件，并在文件中提供Qdisc_ops中定义的接口函数即可。

3 加权公平队列(WFQ)

WFQ是一个简单、动态的排队机制，它通过给重要的通信较高的优先级，以使它得到相对的更多的带宽，保证重要通信的服务。同时也兼顾低优先级流的公平，保证低优先级流的带宽占总带宽一定的比例，不至于发生“饥俄”的情况。其示意图如图2。

WFQ 能够自动识别IP 优先权。具体地说,WFQ 能够检测到被IP 转发器标记了优先权的级别较高的数据包，并且通过为这些通信提供更快的响应时间,使这些数据包更快地传输。因此，随着优先权级别递增，WFQ 在拥塞期间给这个会话分配了更多的带宽。WFQ 为每一个数据流分配一个权重。这个权重确定了排队等候的数据包的发送顺序。在这个方案中，权重小的通信可以先得到服务。

WFQ对报文按流进行分类（相同源IP地址，目的IP地址，源端口号，目的端口号，协议号，TOS的报文属于同一个流），每一个流被分配到一个队列，该过程称为散列，采用HASH算法来自动完成，并尽量将不同的流分入不同的队列。WFQ的队列数目N可以配置。在出队的时候，WFQ按流的优先级来分配每个流应占有出口的带宽。优先级的数值越小，所得的带宽越少。 优先级的数值越大，所得的带宽越多。比如优先权字段的值为7的通信所得到的权重要小于优先权字段的值为3 的通信。这样就保证了相同优先级业务之间的公平，体现了不同优先级业务之间的权值。为了决定为每一个队列分配的带宽,可以用单个数据流的字节总数来除所有数据流的总字节数。例如：如果对应于每一种优先权等级都有一个数据流，则每一个数据流将会得到的带宽是它的优先权级别+ 1 比上这个链接的总带宽。

例如：接口中当前有8个流，它们的优先级分别为0、1、2、3、4、5、6、7。则带宽的总配额将是所有（流的优先级+1） 之和，即：1+2+3+4+5+6+7+8=36

每个流所占带宽比例为：（自己的优先级数+1）/（所有 (流的优先级+1)之和）。即，每个流可得的带宽比例分别为：1/36、2/36、3/36、4/36、5/36、6/36、7/36、8/36。

但是,如果对应于优先权级别1共有18个数据流,对应于其他的优先权级别各有一个数据流,则总数是:1+2(18)+3+4+5+6+7+8=70。优先权级别为0 的通信将会得到总带宽的1/70 ,而每一个优先权级别为1 的数据流将会得到总带宽的2/70。

又如：当前共4个流，3个流的优先级为4，1个流的优先级为5，则带宽的总配额将是：(4+1)*3+(5+1)=21 。那么，3个优先级为4的流获得的带宽比例均为5/21，优先级为5的流获得的带宽比例为6/21。

由此可见，WFQ在保证公平的基础上对不同优先级的业务体现权值，而权值依赖于IP报文头中所携带的IP优先级。 当添加或者结束数据流的时候，实际所分配的带宽会连续发生变化。因此，通过分配每一个通信所获得的带宽，WFQ 可以适应于不断变化的网络环境。

4 MAWRED算法

MAWRED（Multiple Average Weigthed Random Early Detction）多平均队列加权随机早期检测算法是RED算法的一种变体。RED算法采用滑动窗口指数加权计算平均队长Qavg，将平均队长与最小丢弃阈值Tmin和最大丢弃阈值Tmax比较。当Qavg

MAWRED对RED的改进体现在平均队列长度的计算上。RED将所有数据放在一个队列中计算Qavg，而MAWRED将流量进行分类，分别计算不同类别数据包的平均队长。在计算各类别数据包的平均队长时，高丢弃优先级的平均队长用它的队长和较低丢弃优先级的队长之和计算。即在计算较低丢弃优先级数据包的平均队长时，仅用较低丢弃优先级数据包的总队长计算；在计算较高丢弃优先级数据包的平均队长时，用较低丢弃优先级数据包和较高丢弃优先级数据包的总队长之和计算。MAWRED算法描述如下：

假设有数据包类别N1、N2、……Ns，其丢弃优先级L1

当有数据包到来，

if 数据包类别为n

计算类别n的平均队列长度Qavgn=avg( Qn＋Qn－1＋……＋Q1 )

if Tminn=

计算类别n的丢弃概率Pn

以概率Pn丢弃到达的数据包

if Qavgn>=Tmaxn

丢弃所有达到的数据包

5 基于流的MAWRED流量控制算法

5.1 基于流的MAWRED流量控制算法思路

RED 技术对于那些对拥塞控制敏感的流(如TCP流) 有用，在TCP 流与非TCP 流混合情况下并不理想，为了提供更有效的公平保障，满足流量服务区分的需要，可将MAWRED和WFQ配合使用，这样就可以实现基于流的MAWRED。这是因为，在进行分类的时候，不同的流有自己的队列，对于流量小的流，由于其队列长度总是比较小，所以丢弃的概率将比较小。而流量大的流将会有较大的队列长度，从而丢弃较多的报文，保护了流量较小的流的利益。 即使WRED和其他的队列机制配合使用，对于流量小的流，由于其报文的个数较少，所以从统计概率来说，被丢弃的概率也会较小，也可以保护流量较小的流的利益。

基于流的MAWRED示意如图3所示：

在这种模式下，先利用WFQ可基于源和目的网络地址或者MAC地址、协议类型、源和目的端口以及帧中继数据链接标识符和服务类型等数据包报头参数动态地把通信划分成不同的数据流能力，将网络按流分类。而后利用MAWRED算法保证带宽在各个会话之间公平分享,保证数据量少的通信能够以一种及时的方式进行传输。这样以来，对于经过WFQ散列的每类队列，当出现网络拥塞时，将对每类队列采取WRED 的报文丢弃策略，在具体实现中还可由用户设定队列长度的上限和下限。当队列长度低于下限时，不丢弃报文；当队列长度在上限和下限之间时，WRED 开始随机丢弃报文(队列长度越长，丢弃的概率越高)；当队列长度高于上限时，丢弃所有报文。

5.2 基于流的MAWRED流量控制算法实现

我们在具体编程时考虑数据包的收发都是在系统运行时动态进行的，因此采用堆排序技术都数据包进行处理。堆排序是堆数据结构为队列向量向量的排序提供的一种有效技术。其基本思想是首先把队列构成堆，然后将堆顶元素(队列向量的最小值)与队列向量的最后一个元素交换，同时令堆的大小减少一个。下面给出我们的基于流的MAWRED算法的实现。

1)算法实现的主要步骤

每个数据包都会按照各自的带宽速率进入输出缓冲区，每个分组都有一个调度结束时刻，将这个时刻定义为每个分组的F(i), i代表第i个分组。具体算法如下：

使用分类器给分组分类，分类依据为数据包头的上文各项参数，并建立初始堆。

在调度模块中，每次都选取每个队列的第一个分组的调度时刻，采用最小堆排序的方法对其进行选择，选取最小F (i)的分组进行调度。

重构堆。若所调度的分组所在的队列仍不为空，则向堆中插入该队列的下一个分组，直到队列为空。每次队列从空变成为非空时，都需要向堆中插入该队列的第一个分组。

2)主要函数

基于以上算法思路，给出我们的算法实现函数：

（下转第554页）

（上接第549页）

fmawred_enqueue ：把包插入该Qdisc所维护的队列中，如果该Qdisc有类，则先将包分类，然后再调用该类的Qdisc的enqueue函数进行下一步的入队操作。

fmawred_dequeue：从队列中取出一个可以发出的包。

fmawred_requeue：把包重新放回原来的位置，这通常是在调用dequeue之后，包发往相应的设备时返回错误，需要把包重新放回队列中。

fmawred_drop：从队列中丢弃一个包。

fmawred_initQidc：初始化队列。

initHeap：初始化堆栈。

fmawred_reset：将Qdisc置为其初始状态，即清除所有的队列、停止所有定时器。

fmawred_destroy：删除一个Qdisc，除了描述它本身的数据结构以外，该Qdisc所有的类、过滤器均被清除。

changeMaxp：修改最大丢弃概率。

changMaxT：修改最大丢弃阈值。

changeMinT：修改最小丢弃阈值。

enHeap：数据包入堆。

deHeap：数据包出堆。

heapCounte：堆栈计数。

fmawred_dump：返回用于诊断该Qdisc的数据。

基于流的MAWRED流量控制算法可以对最大丢弃阈值、最小丢弃阈值和最大丢弃概率Maxp进行逐流的调节，避免了RED机制下类似尾丢弃的现象。通过程序还证明了基于流的MAWRED流量控制算法的调度机制能够相对公平的调度各个队列的分组。而且在我们的实际编程中，每次都选取每个队列的第一个分组的F(i)进行比较，选出最小的进行调度。由于每次只需选出最小的，并不需要排序，考虑到时间复杂度，采用最小堆的结构，用一个有64个元素(对应64个类)的数组表示。它具有较低的时间复杂度O(N10g2N)，并且由于堆排序的一个重要优点是它直接在队列向量数据上构造堆，所使用的附加空间仅仅是几个简单的临时变量，因而效率很高。

6 总结

在传统的IP网络中，网络设备对所有报文都无区别的等同对待，采用先入先出的调度策略进行处理，“尽最大的努力”将报文送到目的地，但对报文传送的可靠性和传送延迟不能提供任何保证。Linux在其内核中集成进流量管理与控制的功能模块，提供很好的解决这一问题的结构，但Linux在流量管理的队列调度方面还不完善。本文提出这一新的队列调度算法很好的解决了队列调度的灵活性和高效性的两难问题，不仅能够完善Linux这方面的不足，也可应用与其它系统和网络设备中。

参考文献：

[1] 刘建峰,潘军.linux防火墙内核中Netfilter和Iptables的分析[J].微计算机信息,2006(03).

[2] 彭丹,沈苏彬.基于区分服务的服务定制系统的实现[J].南京邮电大学学报:自然科学版,2006(01).

[3] 刘晏兵. 孙世新.基于堆排序的PQ+CBWFQ路由器排队调度算法[J].计算机工程,2006(01).

[4] 丁晓波,桑楠.linux 2.6内核的内核对象机制分析[J].计算机应用,2005(01).

[5] 杨继峰.IP QoS主要体系结构及路由实现[J].河南科技,2006(3).

[6] 杨永斌.队列调度算法在网络中的应用研究[J].计算机科学,2005(7).

[7] 黄启萍,唐亮贵.流量控制与IP服务质量[J].计算机工程,2006(11).

[8] 刘辉,夏汉铸.支持区分服务的自适应队列调度算法[J].计算机应用,2005,25(4).

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”