基于FPGA的以太网队列调度器设计与实现

高旭超,李海华

(上海交通大学 电子信息与电气工程学院,上海 200240)

0 引 言

以太网通信因为具有带宽高、成本低、安全可靠等优点,近些年来被广泛的应用在汽车、工业控制等领域[1,2]。与传统的以太网应用不同,这些应用场景对以太网数据传输性能提出了新的要求[3]。例如,车载自动驾驶系对数据的实时性要求非常高[4],系统中关键控制数据的丢失和延迟会造成潜在的安全隐患。区分服务(DiffServ)模型针对实时业务定义了加速转发的逐跳行为,为时延敏感的实时业务供低时延、低时延抖动、低丢包率、保证带宽的“三低一保证”服务质量[5]。为了在以太网通信中实现区分服务模型对实时业务的支持,队列调度是其中的关键[6]。

在目前常用的调度策略中,DRR(deficit round robin)调度器因为其良好的公平性和可扩展性,被广泛地应用在网络的核心交换节点上[7]。但是与此同时,DRR调度无法保证队列中分组的时延性能[8],所以无法满足实时业务对服务质量的要求。

针对上述问题,本文对DRR调度器进行了改进,设计了IDRR(insertable DRR)调度器。IDRR对链路中的实时业务和非实时业务采取不同的调度策略。调度非实时业务时,调度器采用DRR调度进行出队调度；对于实时业务,以实时业务的排队时间为参考标准,当队列中分组的排队时间超过一定值时,实时业务可以进行插队并提前得到服务。实时业务和非实时业务同时请求调度时,插队调度和DRR调度交替进行。

目前有许多针对DRR调度器的研究和改进,大部分都是通过网络仿真器来研究其性能[7,9,10]。本文在现场可编程门阵列(FPGA)实现了以太网交换机中的IDRR调度器的硬件电路设计并通过Ixia以太网测试平台对该调度模块进行了测试。测试结果表明,与DRR调度器相比,IDRR调度器可以在不增加复杂度的前提下,有效地降低实时业务的时延和时延抖动,满足区分服务模型的要求。

1 区分服务与队列调度

1.1 区分服务模型对数据的分类

逐跳行为(per-hop behavior,PHB)是区分服务模型对特定业务流转发和调度的行为描述。网络交换设备实现区分服务的机制就是根据PHB的定义将各个业务流分类聚集,再根据PHB对业务流的行为描述和优先级进行调度和转发。

其中,加速转发(expedited forwarding,EF)针对网络传输过程中的实时业务,EF业务应该作为优先级最高的业务被调度[11]；确保转发(assured forwarding,AF)的逐跳行为要求网络为不超过带宽限制的AF业务提供转发质量保证,这种业务模型着眼于保证业务带宽,不涉及时延和时延抖动；尽力转发(best effort,BE)是网络中的缺省服务,网络不对BE业务流的服务质量做任何保证。当链路出现阻塞时,网络只为BE业务保留少量带宽,以防止其“饥饿”[12]。

1.2 以太网二层协议对优先级的定义

以太网二层交换机主要通过IEEE 802.3Q中定义的VLAN标签对流量进行优先级区分。802.3Q中定义的以太网VLAN帧格式如图1所示[5]。

图1 IEEE 802.1Q 帧格式

VLAN帧的TPID(tag protocol identifier)字段固定为0x8100,TCI(tag control information)中的PCP(priority codepoint)字段为3 bit的优先级。根据802.3Q协议,4队列调度模块的PCP解码定义和服务质量如表1所示。网络控制流量是网络中优先级最高的流量类型,网络需要为其提供“三低一保证”的服务质量；音视频流量和关键应用流量为需要网络提供尽力转发的服务质量；最后,网络通信系统不为尽力转发的业务提供服务质量保证。

表1 PCP字段解码定义与服务质量

1.3 队列调度

为了对网络中不同的业务流实现区分服务,首先要对进入交换节点的各个分组进行分类和排队,然后使用调度器对各个队列进行调度。目前在交换机中常用的队列调度策略为WRR，DRR，WFQ等。WFQ调度器具有很好的公平性,但是因为其具有O(N2)的复杂度,导致这种调度器很难部署在网络的核心交换节点；WRR调度器的复杂度为O(1),所以很容易在大型交换机和路由器中实现[9]。WRR调度根据每个队列的权值(weight)来区分各个队列,权值代表该队列在每次循环中可以得到服务数量的上限,权值越高队列的占用链路带宽也就越高。当各个队列中的分组长度相等时,WRR调度器可以提供很好的公平性,保障低优先级的业务可以得到一定的带宽。但是当队列中分组长度不相等时,较长的分组会得到更多的服务,从而造成队列实际占用的带宽与该队列的权值不一致。

DRR调度改善了WRR调度中变长分组带来的公平性问题,该调度策略给每个队列分配的是每次服务过程中此队列可以被服务的赤字(deficit),如果队列的赤字大于队列中需要被调度的分组的长度,这个分组就可以得到服务；否则调度器就调度下一个非空队列,而当前队列的赤字将保留到下次循环使用。DRR调度器和WRR一样具有O(1)复杂度,但是在某些情况下,高优先级队列中的分组可能需要等待低优先级的队列中的分组完成调度之后才能得到服务,所以调度器无法保证高优先级队列的时延性能[8]。

为了在不增加复杂度的前提下改善DRR调度中实时业务的时延性能。本文首先研究了以太网通信中支持区分服务的DRR调度器,设计并实现了相应的硬件电路,然后在此基础上设计并实现了IDRR调度器。

2 调度模块的设计与实现

队列调度模块结构框图如图2所示,主要包括分类器,储存队列、调度器和时间发生模块四部分。当新的以太网分组到达时,如果分类器检测到分组为VLAN TAG类型,则根据其PCP字段中定义的优先级将分组入队,若为非VLAN TAG类型的分组,则将其归为BE业务。与此同时,分类器会给所有属于EF业务的分组打上时间戳。队列管理模块维护管理EF,AF1,AF2,BE四个队列,队列的优先级依次降低,其中EF队列储存时延敏感的实时业务分组,两个AF队列储存要求带宽保证的非实时业务,BE队列储存只需尽力而为的非关键数据分组。队列管理模块除了保存分组数据之外,也会为每个分组保存其数据长度,针对EF业务,队列管理模块还会为其保存时间戳中的信息。时间发生模块为分类器和调度器提供统一的系统时间。在后续调度时,调度器根据时钟模块给出的系统时间和EF分组中的时间戳计算出EF业务分组在队列中的等待时间。

图2 队列调度模块结构框图

IDRR调度器由DRR调度器改进而来[13],调度器为每个队列维护一个赤字计数器DC(deficit counter),并使用图3所示的ActiveList来追踪当前的非空队列。当队列i状态由空变为非空时,将i加入ActiveList尾部。调度器每次调度出现在ActiveList头部的队列。队列i完成一次出队调度后,将队列i从AcitiveList中出队,如果此时队列非空,则将队列i重新加入ActiveList尾部。

图3 DRR调度中ActiveList操作

IDRR调度器状态机如图4所示,为了防止恶意EF流量长时间占用出口带宽,导致低优先级队列饿死,在调度器中设置标志位INSERT_ENABLE,以确保在EF队列和非EF队列同时出现调度请求时,调度器可以交替进行插队调度和DRR调度。调度器复位后进入IDLE状态,此时调度器检查EF队列中分组的等待时间,如等待时间大于设定的阈值Thr且INSERT_ENABLE为1,状态机进入INSERT_EF状态进行插队调度,并且在插队调度完成后将INSERT_ENABLE置0。调度器进入CHK状态后开始根据DRR调度策略对ActiveList中头部的队列i进行出队调度。如果队列i积累的赤字大于带调度的分组长度,则进入DEQUE状态进行出队调度,否则将直接进入AL_SHIFT状态,将i从ActiveList头部出队。在AL_SHIFT状态中,调度器检查队列i的状态,若队列i非空,则将队列i重新加入ActiveList尾部,使其继续等待调度。

图4 IDRR调度器状态转移图

3 硬件方案与测试环境

本文使用的FPGA开发板为Xilinx公司的VC707,选用裕太车通的YT8010国产芯片作为PHY芯片,使用MII接口与PHY芯片通信。所有交换机模块和调度模块均在Xilinx的vivado集成开发环境下使用Verilog语言开发。

基于FPGA的以太网交换机系统如图5所示。外接的以太网PHY芯片通过MII接口向交换机的端口传送以太网分组,接收端口的MAC对收到的以太网分组进行储存和校验,并将数据分组转换为32位的并行数据。交换机确定该分组的目的端口之后,通过端口间的高速交换总线将该数据分组发送到目的端口中的调度模块进行排队调度。最后由目的端口的MAC将调度后的分组转换为4位MII接口数据发送给外部的PHY芯片。

图5 以太网交换机架构

本文使用的网络测试工具为Ixia公司的以太网测试仪。如图6(a)所示,通过软件控制Ixia测试仪向交换机发送网络流量,在接收端对网络流量进行采集,将接收到的以太网流量与发端的流量进行对比,即可统计出通信链路的性能。本文使用的网络测试拓扑结构如图6(b)所示,图中BE,AF2,AF1和EF流的带宽分别为6,5,4,2 Mbps,交换机出口带宽为10 Mbps。4个以太网业务流的分组长度均是符合均匀分布的随机值。

图6 Ixia测试环境

4 测试结果与分析

图7展示了在上述网络环境下,实时业务经DRR和IDRR调度器调度后的时延性能。图7(a)为实时业务经过两种调度后的时延抖动性能。测试结果表明,经IDRR调度后,EF分组的时延抖动为0.36 ms,比DRR调度降低了51.3 %,这意味着IDRR调度可以更加平滑地调度EF队列中的分组。如图7(b)所示,相比于DRR调度器,经IDRR调度后,EF业务流的端到端最大传输时延为7.2 ms,相比DRR调度减少了3.1 ms,表明IDRR调度可以为实时业务提更好的端到端的时延保障。

图7 DRR和IDRR调度中实时业务的时延性能

DRR和IDRR两种调度器的交换机在Ixia以太网测试平台中测试60 min后实时业务流的丢包率分别为0.27 %和0.28 %。可以看到在经过两种调度后,实时业务都具有极低的丢包率(0.01 %可近似认为实时随机波动)。这说明IDRR调度器在改善实时业务流时延性能的同时,也保证了该业务的带宽占用。以上测试结果表明IDRR调度为实时业务提供更好的服务质量。这是因为IDRR调度器可以将EF队列中的分组的调度时延LEF控制在以下范围Thr≤LEF≤Thr+F/r。而DRR调度中EF分组经历的调度时延为0≤LEF≤(3F-2Φi)。其中，F为网络中的最大帧长,Фi为队列i的预约带宽因子,r为链路带宽。

因此,相比于DRR调度器,IDRR调度器一方面可以控制EF业务的最大调度延迟,另一方面,可以将EF业务的调度延时控制在一个比较小的区间里,从而改善了实时业务在整个通信链路里的最大延迟和时延抖动。

5 结 论

在DRR调度器基础的基础上改进并设计了IDRR调度器。非实时业务使用DRR调度进行调度,而实时业务则根据分组在队列中的等待时间来决定是否进行插队调度。当存在多种业务流时竞争链路带宽时,两种调度方式交替进行。测试结果表明：相比于DRR调度,改进后的调度器在保持了低复杂度的同时,很好地提高了网络中关键业务的实时性,可以方便地部署在车载和工业以太网中。