Ｌｉｎｕｘ流量控制分析及其算法改进.docVIP

Ｌｉｎｕｘ流量控制分析及其算法改进 　　摘要：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-flagsIFF_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 *op