QoS原理与使用以及其中WRR策略的设计与实现

STAR-NET星网锐痛QoS原理与使用以及其中WRR策略的设

计与实现文档编号：00-6201-100当前版本：

创建日期：2011-6-13

编写作者：ganjingweiQoS原理与使用以及其中WRR策略的设计与实现摘要Linux系统由于它的开放源代码、内核小、效率高、免费性等特点，使得它在嵌入式领域极具优势。另外，Linux适应于多种CPU和多种硬件平台，是一个跨平台的系统，具有非常强的移植性，可以在几乎任何嵌入式硬件上经过一些裁剪很容易地工作起来。总之，Linux在嵌入式领域占有重要的地位。Linux对于网络功能方面也具有强大的支持。它的其中一个最重要的特点就是“零拷贝”。所谓“零拷贝”就是数据包在内核中的层次传递过程，完全由指针完成，中间没有任何由于函数的调用而产生的数据复制。这样既提升了处理速度，又节省了空间。使得Linux也是嵌入式网络产品的第一选择。QoS，从字面意思看，就是服务质量。它是Linux内核中对于数据包的一种调度方式，根据数据包的不同服务，提供不同的带宽质量。它解决了Linux内核对于数据包的传统处理方式无法适应当今多样的网络业务需求的问题。加权循环调度策略（WRR）是QoS的概念下，对于数据包的调度的一种算法。它为每种数据包分配不同的权重，按照权重提供不同比例的带宽。本文重点是、阐述QoS的实现原理，并在其基础上实现我们的加权循环调度策略。关键词：Linux，网络，QoS,TC,嵌入式DesignandImplementationofWeightRoundRobinAbstractLinuxreleaseitssourceopeningforfree.Anditworksefficientlywithareducedkernel.Soitlivesahighadvantageinthefieldofembeddedsystem.Inaddition,LinuxcanworkonmanykindsofCPUandhardwareplatform.Itisacross-platformsystem,hasaverystrongportability,andcanworkonallmosteveryembeddedhardwarewithsomepartsimplycut.Inshort,Linuxplaysanimportantroleinthefieldofembeddedsystem.LinuxofferastrongsupportonInternetnetworkfunction.Oneofit'smostimportantadvantagesiscalled“zero-copy”.Theso-called“zero-copy”isthatpacketsarepassedthroughthekernellayersallbypointers.Nodataiscopiedwhenfunctioniscalled.Inthisway,itnotonlyenhancetheprocessingspeed,butalsosavesmemory.SoLniuxisthefirstchoiseofnetworkembeddedsystem.QoS,viewedfromtheliteralmeaning,isqualityofservice.ItisamethodofschedulingwithinpackagesinLinuxkernel.Itoffersdifferentqualityofbandwidthfordifferentserviceofpackages.ItsolvedtheproblemthatthetraditionalmethodofLinuxkernelcannotmeetthedemandofvariousnetworkservice.WeightRoundRobin(WRR)isanalgorithmofschedulingwithinpackagesundertheconceptofQoS.Itallocateseverykindsofpackagesdifferentweight,andoffersthemdifferentbandwidthinlightoftheweight.ThisdocumentillustratetheImplementationofQoS,andimplementourWRRbasedonit.Keywords:Linux,Network,QoS,TC,EmbeddedSystem目录TOC\o"1-5"\h\z\o"CurrentDocument"第1章绪论 11.1传统的网络数据包发送机制 1\o"CurrentDocument"1.2QoS需求的提出 1\o"CurrentDocument"1.3研究WRR的目的 11.4关于本文 2\o"CurrentDocument"第2章QoS工作原理 2\o"CurrentDocument"ISO层次结构 2\o"CurrentDocument"Linux内核数据包流程和Netfilter框架 3\o"CurrentDocument"QoS工作定位 5\o"CurrentDocument"QoS框架及其实体 14\o"CurrentDocument"2.5本章小结 23\o"CurrentDocument"第3章TC命令 24\o"CurrentDocument"TC命令格式 24\o"CurrentDocument"一个简单的例子 prio 24\o"CurrentDocument"一个稍微复杂的例子 htb+prio 26\o"CurrentDocument"wrr的测试例子 273.5本章小结 28第4章WRR(WeightRoundRobin)基本概念 28\o"CurrentDocument"WRR基本算法 28WRR的优点与缺陷 29WRR算法总体设计 29\o"CurrentDocument"4.4本章小结 30\o"CurrentDocument"第5章WRR的设计与实现 315.1总体架构以及一些结构体 31\o"CurrentDocument"入队enqueue函数设计 32\o"CurrentDocument"出队dequeue函数设计 33\o"CurrentDocument"5.4其他功能函数设计 345.5本章小结 36\o"CurrentDocument"总结 36\o"CurrentDocument"致谢 37\o"CurrentDocument"参考文献 37第1章绪论1.1传统的网络数据包发送机制传统的IP网络无区别地对待所有的报文，路由器处理报文采用的策略是先入先出FIFO（FirstInFirstOut），它依照报文到达时间的先后顺序分配转发所需要的资源。所有报文共享网络和路由器的带宽等资源，至于得到资源的多少完全取决于报文到达的时机。这种服务策略称作Best-Effort（尽力而为），它尽最大的努力将报文送到目的地，但对分组投递的延迟、延迟抖动、丢包率和可靠性等需求不提供任何承诺和保证。传统的Best-Effort服务策略只适用于对带宽、延迟性能不敏感的WWW、文件传输、E-Mail等业务。1.2QoS需求的提出随着计算机网络的高速发展，越来越多的网络接入因特网。Internet无论从规模、覆盖范围和用户数量上都拓展得非常快。越来越多的用户使用Internet作为数据传输的平台，开展各种应用。同样地，服务提供商也希望通过新业务的开展来增加收益。网络发展日新月异随着IP网络上新应用的不断出现对IP网络的服务质量也提出了新的要求例如VoIP（VoiceoverIP）,IP语音等实时业务就对报文的传输延迟提出了较高要求。如果报文传送延时太长将是用户所不能接受的相对而言E-Mail和FTP业务对时间延迟并不敏感为了支持具有不同服务需求的语音视频以及数据等业务要求网络能够区分出不同的通信进而为之提供相应的服务传统IP网络的尽力服务不可能识别和区分出网络中的各种通信类别而具备通信类别的区分能力。正是为不同的通信提供不同服务的前提所以说传统网络的尽力服务模式已不能满足应用的需要QoS（QualityofService）服务质量技术的出现便致力于解决这个问题，同时也解决网络中拥塞的问题1.3研究WRR的目的当网络拥塞时，我们很容易想到带宽应该分配给实时性要求高的业务（例如VoIP、视频点播等）。然而如果一味地偏袒这些业务，会使得实时性不是那么高的业务（例如E-Mail）完全得不到发送，从而在另一个角度也降低了服务质量。加权循环调度策略（WRR）是为了解决这一矛盾，既能够给一些业务较高的带宽保证拥塞时尽力支持它们的通畅，又能够不“饿死”其他数据。1.4关于本文本文第1章阐述了QoS提出的背景，也就是传统数据包在网络中发送的机制，并分析它的缺陷。之后根据这个缺陷，提出如何弥补这个缺陷，并进而提出QoS。而本文的最终主题WRR则是QoS概念中的一种解决方案。本文第2章详细描述了QoS的工作原理。包括QoS的作用地点，QoS框架设计等等。并结合ISO层次结构和Linux内核协议栈和Netfilter框架，对整个Linux网络处理功能进行概要阐述。第3章阐述如何使用QoS方面的应用层机制——TC命令。并通过两个例子来帮助读者理解和学习使用它。第4章和第5章则完整地讲述WRR算法的原理及其实现。第2章QoS工作原理2.1ISO层次结构图1-1展示了一个完整的iso网络层次结构。每一层完成各自的功能，层与层之间是相互透明的。把网络的需求分配到各个层次有许多优点，这里不再一一列举。以下是每一层的概要性描述［1］：物理层----定义了为建立、维护和拆除物理链路所需的机械的、电气的、功能的和规程的特性，其作用是使原始的数据比特流能在物理媒体上传输。具体涉及接插件的规格、“0”、“1”信号的电平表示、收发双方的协调等内容。数据链路层----比特流被组织成数据链路协议数据单元(通常称为帧)，并以其为单位进行传输，帧中包含地址、控制、数据及校验码等信息。数据链路层的主要作用是通过校验、确认和反馈重发等手段，将不可靠的物理链路改造成对网络层来说无差错的数据链路。数据链路层还要协调收发双方的数据传输速率，即进行流量控制，以防止接收方因来不及处理发送方来的高速数据而导致缓冲器溢出及线路阻塞。网络层----数据以网络协议数据单元(分组)为单位进行传输。网络层关心的是通信子网的运行控制，主要解决如何使数据分组跨越通信子网从源传送到目的地的问题，这就需要在通信子网中进行路由选择。另外，为避免通信子网中出现过多的分组而造成网络阻塞，需要对流入的分组数量进行控制。当分组要跨越多个通信子网才能到达目的地时，还要解决网际互连的问题。运输层----是第一个端--端，也即主机--主机的层次。运输层提供的端到端的透明数据运输服务，使高层用户不必关心通信子网的存在，由此用统一的运输原语书写的高层软件便可运行于任何通信子网上。运输层还要处理端到端的差错控制和流量控制问题。会话层----是进程--进程的层次，其主要功能是组织和同步不同的主机上各种进程间的通信(也称为对话)。会话层负责在两个会话层实体之间进行对话连接的建立和拆除。在半双工情况下，会话层提供一种数据权标来控制某一方何时有权发送数据。会话层还提供在数据流中插入同步点的机制，使得数据传输因网络故障而中断后，可以不必从头开始而仅重传最近一个同步点以后的数据。表示层----为上层用户提供共同的数据或信息的语法表示变换。为了让采用不同编码方法的计算机在通信中能相互理解数据的内容，可以采用抽象的标准方法来定义数据结构，并采用标准的编码表示形式。表示层管理这些抽象的数据结构，并将计算机内部的表示形式转换成网络通信中采用的标准表示形式。数据压缩和加密也是表示层可提供的表示变换功能。应用层----是开放系统互连环境的最高层。不同的应用层为特定类型的网络应用提供访问OSI环境的手段。网络环境下不同主机间的文件传送访问和管理(FTAM)、传送标准电子邮件的文电处理系统(MHS)、使不同类型的终端和主机通过网络交互访问的虚拟终端(VT)协议等都属于应用层的范畴。2.2Linux内核数据包流程和Netfilter框架Netfilter是Linux内核中关于网络数据包处理的一个框架，它实现不同数据包在内核中要经过不同的处理，不同的处理程序这个需求。它就像许多层的筛子，层层过滤。它在网络数据包的处理流程中设置了一个又一个的函数HOOK（钩子），这些钩子对应每一层“筛子”。当某一个筛子过滤出了一些满足条件的数据包以后，“钩子”会调用对应这些数据包要流向的处理流程的函数，进入下一步的处理。在内核中，我们叫这种“钩子”为HOOK点。在代码中，这些HOOK点被定义为一个一个的宏，然后通过一个函数指针数组，在每个过滤的地方，通过调用不同的函数在实现对数据包的不同处理。进入不同函数的数据包，还会遇到下一个HOOK点，等等。表2-1列出了IPv4的主要5个HOOK点。Nef_receive_skb是网卡中世纪接收到数据包的函数。这个函数之后有一个过程——解析接收到的数据包，分析它的协议类型，如果是PF_INTERNET，也就是IPv4类型的数据包，将会被提交给ip_rcv这个函数处理。之后就进入了Netfilter处理过程。PRE_ROUTING是第一个HOOK点，这个HOOK点主要做的是，分析数据包是发送给本地当前这个主机的，还是要经过这个主机而进行转发的。如果是发送给本地的，则分流进入本地处理过程进入LOCAL_IN这个HOOK点进行操作，否则进入数据包的进一步处理。之后的FORWARD和POST_ROUTING是转发数据包的处理过程，这两个HOOK点主要是对数据包进行NAT（地址转换）过程。这里涉及到了IPv4的各种协议，这里不再深究。还要提一下的是，在POST_ROUTING中也处理本地产生的数据包，也就是LOCAL_OUT这个HOOK点出来的数据包。表2-1可用的IPv4hookHook调用的时机NF_IP_PRE_ROUTING在完整性校验之后，选路确定之前NF_IP_LOCAL_IN在选路确定之后，且数据包的目的是本地主机NF_IP_FORWARD目的地是其它主机地数据包NF_IP_LOCAL_OUT来自本机进程的数据包在其离开本地主机的过程中NF_IP_POST_ROUTING在数据包离开本地主机“上线”之前图2-1简要列出了IPv4的Netfilter过程。图2-1IPv4的Netfilter框架基本流程在POST_ROUTING这个HOOK点的处理完成以后内核已经选定一个网卡设备来发送这个数据包，内核会调用dev_queue_xmit，来使用选中的网卡设备来发送这个数据包。dev_queue_xmit这个函数的主要流程是，检查设备是否有安装 QoS，如果有，则调用dev->qdisc->enqueue来让数据包计入这个网卡设备的发送队列。到这里，就进入了。。$对数据包输出的处理和调度程序。2.3QoS工作定位2.3.1流入口数据包控制对于入口数据包的控制是通过HOOK函数来实现的。关于HOOK点，上一节中已经进行了一定程度的介绍。每个HOOK点有若十个挂钩处理函数：typedefunsignedintnf_hookfn(unsignedinthooknum,structsk_buff**skb,conststructnet_device*in,conststructnet_device*out,int(*okfn)(structsk_buff*))对于入口数据部分的控制，LINUX中挂载的HOOK点如下：/*afteript_filter*/staticstructnf_hook_opsing_ops={.hook =ing_hook,.owner =THIS_MODULE,.pf =PF_INET,.hooknum =NF_IP_PRE_ROUTING,.priority =NF_IP_PRI_FILTER+1,｝；ingresspolicing用的是NF_IP_PRE_ROUTING这个HOOK点，其挂钩处理函数用的是net/sched/sch_ingress.cing_hook()。函数处理流程如图2-2所示。图2-2所示接收数据包的过程中，通过软中断调用net_rx_action()将硬件层得到的数据传输到IP层。ip_rcv()这个函数在net/ipv4/ip_input.c中，它丢弃校验和不正确的ip包。nf_hook_slow()在net/core/netfilter.c中。nf_iterate()在net/core/netfilter.c中。ing_hook()在net/sched/sch_ingress.c中。之后是QoS的处理过程：如果设置了qdisc_ingress，则调用ingress_dequeue()。此处可以对流量进行限制，相关代码在 net/sched/sch_ingress.c中。ip_rcv_finish()函数在net/ipv4/ip_input.c中。ip_route_input()函数完成路由的功能，在net/ipv4/route.c中实现。net/ipv4/route.c中的ip_route_input_slow()是转发的数据包的下一步处理函数，而同样在net/ipv4/route.c中的ip_route_input_mc()与之相反，处理的是发给本地的数据包。图2-2Netfilter与ingress流量控制这里要提一下的是sch_ingress.c中的enqueue()有限流制作用，然而dequeue()却是空函数。这是Linux对输入流量控制的缺失，这一部分的功能是不完善的。这也正是作者为什么只做了输出流量控制的WRR，而忽略输入流控。2.3.2流出数据包的控制首先我们了解一下Linux网络协议栈在没有TC模块时发送数据包的大致流程。从图2-3可以看出，没有TC的情况下，每个数据包的发送都会调用dev_queue_xmit，然后判断是否需要向AF_PACKET协议支持体传递数据包内容，最后直接调用网卡驱动注册的发送函数把数据包发送出去。发送数据包的机制就是本文开始讲到的FIFO机制。一旦出现拥塞，协议栈只是尽自己最大的努力去调用网卡发送函数。所以这种传统的处理方法存在着很大的弊端。上层协议7f发送链路层：(dev_queue_Xmit^AF_PACKET支持 .. 调用屈卡丢谜函数网卡驱动发送函数：rk-r驱动交给硬件发送1图2-3Linux网络协议栈在没有TC模块时发送数据包的大致流程为了支持QoS，Linux的设计者在发送数据包的代码中加入了TC模块。从而可以对数据包进行分类，管理，检测拥塞和处理拥塞。为了避免和以前的代码冲突，并且让用户可以选择是否使用TC。内核开发者在图2-3中的两个红色圆圈之间添加了TC模块。为了实现QOS的支持LINUX内核中添加如下的代码：以下是net/core/dev.c中的dev_queue_xmit函数(其中略了部分代码)：intdev_queue_xmit(structsk_buff*skb){q=dev->qdisc;if(q->enqueue){/*如果这个设备启动了TC,那么把数据包压入队列*/intret=q->enqueue(skb,q);/*启动这个设备发送*/qdisc_run(dev);return;}if(dev->flags&IFF_UP){if(netdev_nit)dev_queue_xmit_nit(skb,dev);/*对AF_PACKET协议的支持*/if(dev->hard_start_xmit(skb,dev)==0){/*调用网卡驱动发送函数发送数据包*/return0;}}}从上面的代码中可以看出，当q->enqueue为假的时候，就不采用TC处理，而是直接发送这个数据包。如果为真，则对这个数据包进行QoS处理。处理流程如图2-4所示。图2-4流出的数据包的控制过程QoS：如果有排队方式，那么skb先进入排队q->enqueue(skb,q)，然后运行qdisc_run()。qdisc_run()函数在include/net/pkt_sched.h中，代码如下(有省略)：while(!netif_queue_stopped(dev)&&qdisc_restart(dev)<0);qdisc_restart(dev);qdisc_restart()函数在net/sched/sch_generic.c中，其中调用q->dequeue(q)把数据包从队列中取出。图2-4中q->enqueue是对数据包入队，而q->dequeue是选择队列中的一个数据包然后取出。进行数据包的发送。当然入队、出队根据不同的策略有不同的动作具体后面讨论。2.3.3在Linux内核中给一个设备安装一个新的流量控制对象structQdisc_ops说明Qdisc_ops是策略对象，内核中提供了很多中的策略对象比如说TBF、CBQ、HTB、SFQ、DSMARK等的策略对象，这么多的策略对象内核是怎么组织起来的呢？当然内核是通过Qdisc_ops这个结构进行组织的，每个策略都有一个策略对象，并且内核把他们组织成一个链表，根据需要直接从链表中查找相应的策略对象进行安装就可以。Qdisc_ops数据结构如下⑵：structQdisc_ops{structQdisc_ops*next;structQdisc_class_ops*cl_ops;charid[IFNAMSIZ];intpriv_size;int(*enqueue)(structsk_buff*,structQdisc*);structsk_buff*(*dequeue)(structQdisc*);int(*requeue)(structsk_buff*,structQdisc*);unsignedint(*drop)(structQdisc*);int(*init)(structQdisc*,structrtattr*arg);void(*reset)(structQdisc*);

voidintintstructmodule(*destroy)(structQdisc*);voidintintstructmodule(*destroy)(structQdisc*);(*change)(structQdisc*,structrtattr*arg);(*dump)(structQdisc*,structsk_buff*);*owner;};例如对于sch_tbf.c,这个文件实现的是令牌桶算法，最后生成一个structQdisc_ops的结构变量tbf_qdisc_ops，在模块初始化的时候，注册tbf_qdisc_ops，调用register_qdisc（&tbf_qdisc_ops），注册的过程其实就是加入一个链表的过程，sch_api.c提供这个注册的函数。以下是sch_tbf.c文件的一部分代码（其余的sch*.c的第二部分的文件与之类似）：structQdisc_opstbf_qdisc_ops=NULL,NULL,"tbf",sizeof(structtbf_sched_data),tbf_enqueue,tbf_dequeue,tbf_requeue,tbf_drop,tbf_init,tbf_reset,tbf_destroy,tbf_change,tbf_dump,};#ifdefMODULEintinit_module(void)returnregister_qdisc(&tbf_qdisc_ops);voidcleanup_module(void)unregister_qdisc(&tbf_qdisc_ops);

#endifLinux内核中安装策略对象过程在网卡注册的时候，都会调用register_netdevice，给设备安装一个Qdisc和Qdisc_ops。为了实现QOS的支持，structnet_dev中我们要做如下添加：structnet_device{structQdiscstructQdiscstructQdiscstructQdiscstructQdiscstructlisthead*qdisc;*qdisc_sleeping;*qdisc_ingress;qdisc_list;}在网卡注册的时候，都会调用register_netdevice，给设备安装一个Qdisc和Qdisc_register_netdevice(structnet_device*dev){dev_init_scheduler(dev);}voiddev_init_scheduler(structnet_device*dev){/*安装设备的qdisc为noop_qdisc*/dev->qdisc=&noop_qdisc;dev->qdisc_sleeping=&noop_qdisc;dev_watchdog_init(dev);}此时，网卡设备刚注册，还没有UP，采用的是noop_qdisc。structQdiscnoop_qdisc={noop_enqueue,noop_dequeue,TCQ_F_BUILTIN,&noop_qdisc_ops,}；noop_qdisc采用的数据包处理方法是noop_qdisc_ops。structQdisc_opsnoop_qdisc_ops={NULL,NULL,"noop",0,noop_enqueue,noop_dequeue,noop_requeue,};staticintnoop_enqueue(structsk_buff*skb,structQdisc*qdisc){kfree_skb(skb);returnNET_XMIT_CN;}网卡刚开始注册的时候就安装了Qdisc和相应的策略，不过这个策略是空的即没策略。他们并没有对数据包进行任何的分类或者排队，而是直接释放掉skb。所以此时网卡设备还不能发送任何数据包。必须ifconfigup起来之后才能发送数据包。当网卡启动的时候会调用如下的函数：intdev_open(structnet_device*dev){dev_activate(dev);}voiddev_activate(structnet_device*dev){if(dev->qdisc_sleeping==&noop_qdisc){/*安装缺省的qdisc*/qdisc=qdisc_create_dflt(dev,&pfifo_fast_ops);}/*.安装特定的qdisc*/if((dev->qdisc=dev->qdisc_sleeping)!=&noqueue_qdisc){}内核中缺省的策略是pfifo_fast_ops,也就是绝对优先级的队列，其内部就4个队列。设备启动之后，此时当前设备缺省的Qdisc->ops是pfifo_fast_ops。如果需要采用不同的ops，那么就需要为设备安装其他的Qdisc。本质上是替换掉dev->Qdisc指针。见sched/sch_api.c中的dev_graft_qdisc函数：staticstructQdisc*dev_graft_qdisc(structnet_device*dev,structQdisc*qdisc){oqdisc=dev->qdisc_sleeping;/*首先删除掉旧的qdisc*/if(oqdisc&&atomic_read(&oqdisc->refcnt)<=1)qdisc_reset(oqdisc);/*安装新的qdisc*/if(qdisc==NULL)qdisc=&noop_qdisc;dev->qdisc_sleeping=qdisc;dev->qdisc=&noop_qdisc;/*启动新安装的qdisc*/if(dev->flags&IFF_UP)dev_activate(dev);}从dev_graft_qdisc可以看出，如果需要使用新的Qdisc，那么首先需要删除旧的，然后安装新的，使dev->qdisc_sleeping为新的qdisc，然后调用dev_activate函数来启动新的qdisc。结合dev_activate函数中的语句：if（（dev->qdisc=dev->qdisc_sleeping）!=&noqueue_qdisc）可以看出，此时的dev->qdisc所指的就是新的qdisc（注意，上面语句中左边是一个赋值语句）。在网卡down掉的时候，通过调用dev_close->dev_deactivate重新使设备的qdisc为noop_qdisc，停止发送数据包。2.4QoS框架及其实体2.4.1QoS框架Linux内核中的QoS代码主要包括以下概念［3］：•队列规则•类（对应一种队列规则）•分离器每个网络设备都有一个与它关联的队列规则，以控制进入队列的数据包如何被操作。一个非常简单的队列规则可以只包含一个单一的队列，所有的数据包将存放在其中，并按照进队的顺序排序，设备尽自己的努力取出它们并发送。图2-5展示了一个没有外部可见的内部结构队列规则。Queuingdiscipline图2-5一个不分类的队列规则更复杂的队列规则可能会用分离器来区分不同类别的数据包并按照特定的方式处理每个类，例如：给一个类高于其他类的优先级。图2-6展示了一个队列规则的例子。注意，多个分离器可以映射到同一个类。图2-6一个含有多种类别的队列规则队列规则和类是紧密联系的：类和类的含义是队列规则的基本属性。相反地，分离器可以与队列规则和类任意组合，只要队列规则和类对应就行。但是灵活性还在——类一般不管如何保存它们这个类别的数据包，而是通过队列规则来做到这一点。可以通过设置可用的队列规则来任意选择这个队列规则，它很可能已经有类，反过来又包含队列规则，等等。图2-7展示了这样一个递归的例子：首先，这里有一个含有两个延迟优先级的队列规则。被分离器挑选的数据包进入高优先级的类，其他包进入低优先级的类。只要高优先级队列中有数据包，就先发送高优先级的包（例如：sch_prio队列就是这样工作的）。为了防止低优先级的流量完全得不到发送，我们使用一个令牌桶过滤器（TBF），使得速率最高1Mbps。最后，低优先级队列的数据包通过先进先出队列规则来排队。注意，有更好的方法来做到我们这里做到的结果，例如：使用基于类的队列（CBQ）。图2-7结合了优先级算法、令牌桶算法和先进先出算法的队列规则数据包像这样进入队列：当一个队列规则的入队函数被调用，它运行一个又一个分离器直到其中一个表示匹配。然后它按照相应的类给这个包排序，一般是通过请求这个类“拥有”的队列规则的入队函数。不匹配任何分离器的数据包都被归到默认类中。通常情况下每个类“拥有”一个队列，但是原则上也可能若干个类共用同一个队列，或者甚至一个队列被各自的队列规则的所有类使用。但是要注意，数据包不包含关于这个包属于哪个类的任何明确信息。如果“内部”队列被共享，当数据包出队的时候改变每个类的信息的队列规则（例如：CBQ）可能因此不能正确地工作，除非他们能重新被分类或者是通过其他方式在进队到出队的过程中跳过分类的结果。通常，当数据包进队列的时候，符合的数据流能够被处理，例如：丢弃超过流速的数据包。2.4.2队列规则每个队列规则提供以下的函数定义来控制它的运作（参见include/net/pkt_sched.h中的structQdisc_ops）:enqueue根据队列规则将数据包入队，如果这个队列规则有对应的类，enqueue函数首先搜索一个类，然后请求匹配的队列规则的enqueue函数执行更长远的入队操作。dequeue取出下一个满足发送条件的数据包。如果队列规则没有数据包发送（例如：因为队列为空或者因为数据包都还没有被调度到可以发送），dequeue返回NULL。requeue在一个数据包用dequeue函数出队以后，再次把它放入队列。这个函数与enqueue函数的区别在于数据包应该恰好在它被dequeue函数删除的位置入队，而且它不能被当做已经通过队列的流量累积统计下来，因为这个统计已经在enqueue函数中执行过了。drop丢弃一个队列中的数据包。init初始化并配置队列规则。change改变一个队列规则的配置。reset让一个队列规则恢复到一开始的状态。所有的队列被清空，计时器停止，等等。同样的，所有与该队列规则的类有关的队列规则的reset函数都被调用。destroy删除一个队列规则。它删除所有类，也许也是所有分离器，取消所有等待事件，并释放该队列规则申请的所有资源（特别是描述队列规则自己的数据结构）。dump返回用于维护的诊断数据。通常情况下，dump函数返回足够重要的配置信息和状态变量。为了调用这些函数，队列规则被一个指向适当的Qdisc结构体的指针引用。一个数据包通过一个接口（net/core/dev.c中的dev_queue_xmit）入队的时候，设备的队列规则（include/linux/netdevice.c中structdevice的qdisc成员）的enqueue函数被调用。然后，dev_queue_xmit函数调用设备的include/net/pkt_sched.h中的qdisc_wakeup函数来尝试发送刚刚入队的数据包。qdisc_wakeup函数立刻呼叫net/sched/sch_generic.c中的qdisc_restart函数，这是轮询队列规则并且发送数据包的主要函数。qdisc_restart函数首先尝试从设备的队列规则中获得一个数据包，如果成功获得，qdisc_restart函数将调用设备的hard_start_xmit函数来实际发送这个数据包。如果因为某些原因发送失败，数据包将通过requeue函数交还给队列规则。当一个队列规则发现一个数据包应当被发送时，qdisc_wakeup函数也可以被这个队列规则调用，例如：计时器提示过期°TBF就是这样的一个队列规^U。qdisc_restart函数也通过qdisc_run_queues函数由在net/core/dev.c中的net_bh调用。net_bh是网络处理栈的下半部处理程序，只要数据包入队进行更长远的操作，它就会被执行。图2-8说明了流程。为了简单起见，队列规则的请求呼叫（例如：请求分类）没有被标出。请注意，队列规则从来不直接调用发送函数，而是必须等待直到他们被轮询。如果一个队列规则被编译到内核，它必须在net/sched/sch_api.c中的pktsched_init函数中注册。另外，它也可以在其他地方用register_qdisc函数进行注册，例如：如果队列规则被编译成模块，在init_module函数中可以注册。图2-8入队和发包时的函数调用当一个队列规则的实例被创建或更改的时候，一个选项的载体（在include/linux/rtnetlink.h中申明的structrtattr*类型）被传递给初始化函数。每个选项都按照它的类型、长度、值来编码（例如：0或者更多的字节）。选项类型和值所使用的数据结构在include/linux/pkt_sched.h中申明。选项载体的解析通过调用rtattr_parse函数来完成，rtattr_parse函数返回一个由指向每个元素的指针组成的数组，用来索引选项类型。选项的长度和内容可以分别在宏RTA_PAYLOAD和RTA_DATA中读取到。选项载体通过rtnetlink机制在用户空间和内核空间传递。解释rtnetlink和底层netlink超出了本文的范畴。每个源文件的定位在第三部分说明了。队列规则的实例被32位数字标记，这32位被分成主次两个数字。通常的标记方法是主标记号：次标记号。对于队列规则，次标记号总是0。请注意，这里的主次号和设备文件使用的设备号没有关系。2.4.3类类可以用两种方式标记：通过类ID，由用户指定；通过内部ID，由队列规则指定。后者在给出的队列规则中必须是独一无二的，并且，可以是一个索引也就是一个指针，等等。请注意，0这个值是特殊的，如果get函数返回0，则表示“没有找到”。类ID是一个U32类型的，而内部ID是一个unsignedlong类型。在内核中，通常找到一个类的方式是通过内部ID。只有get函数和change函数使用类ID。请注意，多个类ID可以映射到同一个内部ID。在这种情况下，类ID传递更多的信息从分类器到队列规则或者类。类ID的结构像队列规则ID一样，有一个对应队列规则实例的主号，和一个标记实例中的类得次号。含有类的队列规则提供了以下函数族来控制类(参见include/net/pkt_sched.h中的structQdisc_class_ops)：graft给一个类附加一个新的队列规则，并返回先前使用的队列规则。leaf返回类的队列规则。get通过类ID查找类，并返回它的内部ID。如果这个类支持一个可用的计数器，get函数应该增加计数器。put在一个之前和get函数一起提到的类被提取的时候调用。如果这个类支持一个可用的计数器，put函数应该减少计数器。如果这个计数器达到零，put函数将删除这个类。change改变类的属性。change函数也用于创建新类，适用于那些含有一个始终不变的号的，在队列规则初始化时被创建的类的队列规则。delete处理删除类的请求。它检查这个类是否在使用中，在这种情况下停用并删除它。walk遍历队列规则的所有类并为每个类调用一个回调函数。这用于获得队列规则的每个类的特征数据。tcf_chain返回一个指向与类关联的分离器的链表节点的指针。这用于操作分离器链表。bind_tcf给一个类绑定一个分离器的实例。bind_tcf函数通常和get函数等同，除了当队列规则需要能够明确拒绝类的删除操作的时候。(例如：sch_cbq拒绝删除那些被分离器提及的类。)unbind_tcf从类中删除分离器的实例。unbind_tcf函数通常等同于put函数。dump_class返回特征数据，就像dump函数对队列规则做的一样。类在队列规则的入队函数中被选择，通常是通 过调用include/net/pkt_cls.h中的tc_classify函数，这个函数返回一个包含类ID(classid)也可能包含内部ID(class)的结构体structtcf_result(在include/net/pkt_cls.h中申明)，参见第7部分。tc_classify函数的返回值不是1(TC_POLICE_UNSPEC)就是分离器返回的策略决定(策略是队列规则的另一个概念，这里略去，有兴趣者可以上网寻找其他资料)。tc_classify函数的返回值在include/linux/pkt_cls.h中申明。还有一个为本地流量分类的捷径：如果skb->priority包含了当前队列规则的类的ID，这个类直接被使用，不再尝试其他分类。当本地生成一个数据包时，skb->priority(include/linux/skbuff.h中的structsk_buff)被设置为sk->priority(include/net/sock.h中的structsock)。sk->priority可以被设置为SO_PRIORITY套接字选项(net/core/sock.c中的sock_setsockopt)。这种分类可以被用于实现像Arequipa提供的那种功能。请注意，2.2.3以上的内核限制与SO_PRIORITY设置的那个值在范围0〜7内，因此这个分类的捷径失效了。然而，所有的队列规则都支持它。也要注意，skb->priority可以包含其他优先值，例如：从IPv4头中TOS字段获得的优先级。所有这些值都低于最小有效类号65536。选择完类以后，各自内部队列规则的入队函数被调用。队列规则在与类关联的数据结构中存储方式可以在队列规则的实现中多样变化。传递给change函数的选项载体和传递给队列规则初始化函数的载体是同一个结构体。相应的声明也在include/linux/pkt_sched.h中。2.4.4分离器分离器被队列规则用于分配传入的数据包给其中一个类。这个过程发生在队列规则的入队操作期间。分离器被保存在分离器链表中，链表被每个队列规则或者每个类维持着，依赖于队列规则的设计。分离器链表按照优先级排列，递增的顺序。此外，分离器的入口用他们申请的协议来当钥匙。那些协议号在skb->protocol被使用，在include/linux/if_ether.h被定义。在同一个分离器链表上的相同协议的分离器必须具有不同的优先级。分离器也可以有一个内部结构：它可以控制内部元素，之后被32位句柄引用。这些句柄和类ID很类似，但是他们没有被拆分为主次号。0句柄总是指向这个分离器自己。像类一样，分离器也有内部ID，可以通过get函数获得。分离器的内部结构可以是随意的。图2-9展示了一个含有一个内部元素链表的分离器。

图2-10展示了分离器和分离器的元素被检查的顺序。一个顺序处理的链表当然在分离器许多可能的内部结构中是唯一的。~~Nomatch~~Match分离器通过以下函数族来控制（参见include/net/pkt_cls.h中的structtcf_proto_ops）：classify完成分类并返回TC_POLICE_...这些值中的一个（这些值也属于策略概念范畴，本文不作介绍）。如果结果不是TC_POLICE_UNSPEC，它也返回找到的类ID或者也可选择返回structtcf_result中被res指向的内部类ID。如果内部类ID是缺省的，res->class的值必须为0。init初始化分离器。destroy删除一个分离器。队列规则sch_cbq和sch_atm在删除类的时候也使用destroy函数来删除过时的分离器。如果分离器或者任何它的元素与类一起注册，将会通过调用unbind_tcf函数来撤销注册。get按照句柄查找一个分离器元素并返回其内部分离器ID。put当一个之前被get函数引用的分离器元素不在使用时被调用。change配置一个新的分离器或改变一个已经存在的分离器的属性。配置参数传递的机制和队列规则、类的传递机制是一样的。change函数通过调用bind_tcf函数来注册添加一个新的分离器或者是分离器元素给一个类。delete删除一个分离器的元素。为了删除整个分离器，destroy函数必须被使用。这一点在net/sched/cls_api:tc_ctl_tfilter中被区分，并且对用户透明。如果这个分离器元素已经和类一起注册，则调用unbind_tcf函数来撤销注册。walk遍历一个分离器的所有元素，并对每一个元素调用一个回调函数。这用于获得特征数据。dump返回一个分离器或他的元素的特征数据。请注意，RSVP分离器的代码在cls_rsvp.h中。cls_rsvp.c和cls_rsvp6.c只包含了文件包含的正确设置，并设置一些参数（主要是RSVP_DST_LEN），这些参数控制cls_rsvp.h中产生的分离器类型。分离器在分离器的实例可以分类的数据包的范围中变换：当使用cls_fw和cls_route分离器的时候，每个队列规则一个实例可以把所有类的数据包分类。这些分离器从数据包描述符中得到类ID，类ID在存放到其他协议栈中的实体中之前存放在数据包描述符中，例如：cls_fw使用防火墙编码中的标记功能。我们叫这些分离器为通用分离器。如图2-11。二d'ss-p油.Enunoclassify二d'ss-p油.EnunoclassifyPacketcontent另一个类型的分离器（cls_rsvpandcls_u32）对于每个类需要一个或多个分离器实例或分离器的内部元素。我们叫他们特定分离器。这种分离器（或者是它的元素）的多个实例存放在同一个分离器列表上（例如：对于同一个类），他们靠一个分离器内部ID来区分，就像类使用的内部ID一样。然而，不像类那样，分离器没有“分离器ID”。取而代之的是，根据他们对应注册的队列规则或类，以及他们在这些分离器中的优先级可以识别他们。因为特定分离器中对每个类至少一个实例或元素，特定分离器很自然地储存了类的内部ID，并把他们当做分类的结果。这就支持了队列规则对类信息的快速检索。图2-12展示了这个情况，指向类结构体的指针的位置就是像内部ID一样使用的地方。不幸的是，通用分离器没有办法提供这个信息。因此，通用分离器设置tcf_result结构体中的class成员为0，并把查找操作交给队列规则。

个配置的改变发生在明确绑定类给他们的时候。2.5本章小结本章从网络的基础知识作为入口点，先介绍了iso七层协议栈。然后结合协议栈，简要描述了Linux用于实现网络功能的Netfilter框架。然后顺着Netfilter，分析网络数据包在内核中的处理流程，最终找到QoS的作用地点。分析完了QoS再内核网络功能中的位置以后，我们大致分析了QoS的实现方法，框架，并对框架中的各个实体，结合代码进行了实践性的讲解。本文的主题一一WRR只是一个简单的调度算法，并没有多少讨论的价值。但是要想实现它，需要了解的是整个QoS的实现及其提供的接口。要熟练运用它并完全理解它的意义，还需要知道网络数据包在内核中的走向。所以笔者这里花费了大量的篇幅说明QoS和Netfilter。第3章TC命令TC命令格式TC命令是QoS的应用层提供的控制QoS内核功能的程序，在shell中以命令行的形式被使用。通过TC命令，用户可以为设备添加或删除自己的队列规则，并对队列规则中的实体，根据应用需求进行操作。以下是TC命令的格式：tcqdisc[addIchangeIreplaceIlink]devDEV[parentqdisc-idIroot][handleqdisc-id]qdisc[qdiscspecificparameters]tcclass[addIchangeIreplace]devDEVparentqdisc-id[classidclass-id]qdisc[qdiscspecificparameters]tcfilter[addIchangeIreplace]devDEV[parentqdisc-idIroot]protocolprotocolpriopriorityfiltertype[filtertypespecificparameters]flowidflow-idtc[-s|-d]qdiscshow[devDEV]tc[-s|-d]classshowdevDEVtcfiltershowdevDEV其中，tcqidsc命令用于给一个设备或一个类挂载一个队列，所有这个设备的数据包，或这个类所分类得到的数据包，都进入这个队列。tcclass命令给一个队列添加类，这个队列必须是可分类的。添加的类必须分配类的属性，这个要根据具体的队列规则而定，htb就是这个类的流速，wrr就是这个类的权重，等等。tcfilter命令给一个队列规则添加一个分离器，分离器设置的是分类的依据，比如，源ip，端口，目的ip，端口，等等。分离器根据分类的依据分理处数据包以后，这些数据包进入flowid后面的类ID所指定的类。一个简单的例子 prio现在我们来看一个简单的tc命令的例子，首先要设置好测试的环境。这里我们选用broadcom96358GW添加了TrafficControl以后的板子。把eth1.2网卡端口配置成wan口，其他端口为br0的lan口。wan口ip为，lan口ip为网关。在wan口外接一台主机，ip设置成6，网关设置为。lan口接观察流量的主机，网关设置为，ip设置为。板子串口同样接到观察流量的主机，host1用Ix观察流量。如图3-1。图3-1测试环境环境搭建好以后，在终端上输入命令如下：为目的端口为10000、20000、30000、40000的数据包分别标记mark值为0x1、0x2、0x3、0x4：iptables-tmangle-APREROUTING-pudp--dport10000-jMARK--set-mark0x1iptables-tmangle-APREROUTING-pudp--dport20000-jMARK--set-mark0x2iptables-tmangle-APREROUTING-pudp--dport30000-jMARK--set-mark0x3iptables-tmangle-APREROUTING-pudp--dport40000-jMARK--set-mark0x4为eth1.2挂载一个HTB根节点：tcqdiscadddeveth1.2roothandle1:0htb为这个根节点分类，提供给每个ip使用：tcclassadddev eth1.2parent 1:0classid 1:1htb rate5000kbittcclassadddev eth1.2parent 1:0classid 1:2htb rate4000kbittcclassadddev eth1.2parent 1:0classid 1:3htb rate3000kbittcclassadddev eth1.2parent 1:0classid 1:4htb rate2000kbit为每个类挂载分离器，过滤每个ip的流量：TOC\o"1-5"\h\ztcfilteradddev eth1.2parent 1:0protocolallprio 1 handle 0x1fwclassid 1:1tcfilteradddev eth1.2parent 1:0protocolallprio 1 handle 0x2fwclassid 1:2tcfilteradddev eth1.2parent 1:0protocolallprio 1 handle 0x3fwclassid 1:3tcfilteradddev eth1.2parent 1:0protocolallprio 1 handle 0x4fwclassid 1:4命令输入完成以后，开始发送流量。hostl上使用Ix对host2的10000、20000、30000、40000端口发送10M的流量。在笔者的试验中，观察到的结果如图3-2所示。3.3一个稍微复杂的例子一一htb+prio上一节我们讲述了一个htb的例子，这一节里，我们在一个htb节点上挂载4个prio分类。其实主要目的是测试prio的功能，但是由于设备网卡带宽是百兆，而QoS只有在阻塞的情况下才会有效果显示出来。然而当速度接近百兆的时候，由于硬件或软件上的原因，流速会很不稳定，不便观察，故而使用htb把总流速限定为10M。由于上一节的操作已经用iptables打好标签了，这里不再重复。只需要输入相应的tc命令，当然删除之前的qdisc是必须的：给网卡挂载一个根队列，使用htb，默认进入类1:1，并把速率限制为10M：tcqdiscadddeveth1.2roothandle1:0htbdefault1tcclassadddeveth1.2parent1:0classid1:1htbrate10000kbit为这个htb节点替换叶子队列，替换为prio,并设置4个带，优先级表为0、1、2、3：tcqdiscadddeveth1.2parent1:1priobands4输出这个prio类的ID：tcclassshowdeveth1.2把流量过滤到这4个带上（根据之前输出的类ID）：tcfilteradddeveth1.2parent8001:0 protocolall prio1 handle 0x1 fw classid8001:1tcfilteradddeveth1.2parent8001:0 protocolall prio1 handle 0x2 fw classid8001:2tcfilteradddeveth1.2parent8001:0 protocolall prio1 handle 0x3 fw classid8001:3tcfilteradddeveth1.2parent8001:0 protocolall prio1 handle 0x4 fw classid8001:4命令输入完成以后，开始发送流量。我们使用hostl上使用Ix对host2的10000、20000、30000、40000端口发送10M的流量。在笔者的实验中，Ix观察到的结果如图3-3所示。3.4wrr的测试例子这一节要进行的是我们的wrr队列规则的测试。Iptables的标签命令统一沿用之前的。下面是tc命令（注意，权重值的比例是1:2:3:4）：tcqdiscadddeveth1.2roothandle1:wrrTOC\o"1-5"\h\ztcclass add deveth1.2parent 1:0 classid 1:1wrrweight 100tcclass add deveth1.2parent 1:0 classid 1:2wrrweight 200tcclass add deveth1.2parent 1:0 classid 1:3wrrweight 300tcclass add deveth1.2parent 1:0 classid 1:4wrrweight 400tcfilter add deveth1.2parent 8001:0protocolall prio 1 handle0x1fwclassid8001:1tcfilter add deveth1.2parent 8001:0protocolall prio 1 handle0x2fwclassid8001:2tcfilter add deveth1.2parent 8001:0protocolall prio 1 handle0x3fwclassid8001:3tcfilter add deveth1.2parent 8001:0protocolall prio 1 handle0x4fwclassid8001:4命令输入完毕以后，开始发送流量。从host1向host主机的4个端口发送800kbit的流量。在笔者的实验中，结果如图3-4所示。Throughput.图3-4wrr测试结果3.5本章小结本章主要讲述QoS方面的应用层接口——tc命令的使用，并通过3个例子来实践它。在实际的应用中，需求会更加复杂，命令也就更复杂。如果读者需要在更广泛的方面使用tc命令，可以上网搜寻其他的介绍及实例。第4章WRR(WeightRoundRobin)基本概念4.1WRR基本算法加权轮询调度简称WRR，对数据包进行分类。可以按照数据包中的源IP地址，目的IP地址，源端口号，目的端口号，协议号，IP优先级，DSCP等进行分类。然后放到不同权值的队列中。假如有4个队列，权值分别为：4、3、2、1。根据自己定义的规则对数据包进行分类，分别放到这4个队列中，然后调度程序就会轮询调度这4个队列，当然调度的时间或者调度数据包的量与队列的权值是成正比的。也就是说调度过程中四个队列调度的流速比例为4：3：2：1[4]。如图4-1所示。Hflti-I段羸2|x：I图4-1WRR调度结果WRR的优点与缺陷WRR是针对PQ和RR调度算法的不足提出的，它支持不同的带宽需求，可以为不同的队列分配不同比例的输出带宽。在WRR算法中，分组首先被分成不同的服务等级（如实时业务，交互信息，文件传输等），然后被分配到与之相应的队列，对每一个队列采用轮询服务，因此在一个轮询周期中每一个队列至少有一个分组被传送，所以避免了绝对的优先级排队策略中低优先级队列可能出现的队列“饥饿”现象。WRR算法还可以通过为那些对延迟和延迟抖动要求高的数据流分配较大的权重，使其占有较多的输出带宽，从而减小延迟和延迟抖动，这样可以为对延迟敏感的应用如IP电话业务提供良好的QoS保证。WRR算法具有以下优点：由于WRR算法可以通过硬件实现，所以它可以用于核心网络；WRR通过为不同的业务流分配不同的输出带宽，实现对每个服务等级输出带宽的粗略控制；WRR在一个轮询周期中每一个队列至少有一个分组被传送，从而避免队列“饥饿”现象；WRR通过为对QoS指标要求高的流分配较大的权值，可以减小此业务流的延迟和延迟抖动；•当有剩余带宽时，各业务流可以按权值分配剩余带宽，从而提高链路利用率。WRR算法最主要的不足在于：只有当分组尺寸一样时，这种算法才能为每个服务等级提供准确的带宽分配比例，如果一个服务等级业务的分组尺寸大于另一个等级，它将会占用比预定值更多的输出带宽。在队列调度算法中，为照顾公平性和效率,WRR是常用的队列调度算法，它也是IETF推荐的QoS调度算法。采用WRR队列调度算法，为了保证业务的时延，对不同的队列设置不同的权值和缓冲，以减小高优先级业务的时延。在笔者设计的WRR算法中，弥补了这一缺陷。数据包从队列中取出的时候，是按照数据包的长度而不是数据包的数目来分配权重流量的。如果这一次轮询的流量不足以取出一个数据包，就把权重累加，等待下一次轮询取出这个数据包。具体的算法将在下一章详细讲述。WRR算法总体设计wrr要实现的功能是为每种流量分配的带宽进行规划，针对的是带宽的比例，而不像htb那样针对的是带宽的大小。而且，WRR是对每种流量的轮流发送，虽然每次轮询每种流量的数据发送的数量不同，但是对于每种流量，被“访问”的频率是一样的。所以这里，我们首先要像RR算法那样，为每种流量分配一个队列，属于这个类的流量，进入这个队列。这是入队的方式。在移除队列的地方，我们需要为WRR设计算法。这是WRR的精髓之处所在。WRR队列规则在入队，分类等方面可以和prio、RR等队列规则完全相同，或者由于应用需求做相应的改动。这些都不重要，蛋WRR关键之处在于，对已经入队的数据包，要进行按照权重取出数据的轮询。上面说了，为了弥补WRR对于数据包大小位置而产生的流量分配不公平这一缺陷，我们的WRR使用每次发送的数据长度来作为权重，而不是数据包数量。然而这样又出现了一个问题，如果每次分配的权重，也就是每次轮询允许数据包发送的长度，比要发送的下一个数据包的长度小，也就是没有足够的权限值来发送下一个数据包，那么改如何来发送这个数据包呢（总不能分片吧）？这个细节的问题，笔者将在下一章详细讲述，有耐心的读者可以在下一章看到WRR的详细设计⑸。综上，我们知道了WRR的入队方式和出队方式，图4-2简要描述了这一过程。skb图skb图4-2WRR基本结构4.4本章小结本章对WRR算法进行了概念性的描述，简要介绍了WRR算法的基本流。主要思想如下：WRR规则的入队部分可以随意，可以由用户指定分类规则，入队规则，也可以用内置的分类方法，主要算法体现在出队部分一一轮询并按权重取出数据包。第5章WRR的设计与实现5.1总体架构以及一些结构体按照图4-2所示，整个WRR模块可以分为入队和出队两大部分，按照上一章叙述的流程，可以分理处以下实体：wrr_clasify用于把数据包分类。wrr_class这是wrr_clasify的分类结果返回的结构体。wrr私有数据中包含两个这个类列表，一个是所有的类的列表，另一个是正在工作也就是有数据包的类的列表。wrr_clasify从有数据包的列表中选出一个并返回。InnerQdisc这是每个分类的内部队列，默认情况是pfofi_fast，但是可以通过wrr_graft来挂载别的队列。enqueue、dequeue、 这是wrr提供给外部（网卡）使用的接口，外部通过Qdisc_ops结构体中的函数指针来调用这些操作函数。而这些函数的内部实现，其实是通过操作对应的类的内部队列的操作函数来完成的。enqueue函数是调用分类以后的类的内部enqueue；dequeue函数是调用轮询到的权重足够发送的队列的dequeue函数。按照这些实体，我们首先需要设计