APP下载

光纤通道调度算法研究*

2017-12-19丁永强谭小虎褚文奎

火力与指挥控制 2017年11期
关键词:令牌实时性权值

丁永强,王 勇,谭小虎,褚文奎,方 挺

(1.空军工程大学第一航空学院,河南 信阳 464000;2.空军工程大学航空航天工程学院,西安 710038)

光纤通道调度算法研究*

丁永强1,王 勇2,谭小虎2,褚文奎2,方 挺2

(1.空军工程大学第一航空学院,河南 信阳 464000;2.空军工程大学航空航天工程学院,西安 710038)

针对光纤通道协议中没有规定数据调度算法的问题,在满足系统实时性的情况下,经过对FC-AE-ASM协议的深入分析,提出一种基于令牌桶的优先级和加权轮转相结合的调度算法,同时给出了权值分配和轮转周期的确定方法。在以消息的延迟率作为算法性能的评价指标的基础上,经过仿真,对调度算法的性能进行了验证,结果显示出该算法可以很好地满足航空电子系统实时性要求。

光纤通道,权值分配,轮转周期,延时率

0 引言

光纤通道(Fiber Channel,FC)作为航空电子系统统一网络的理想协议[1],它具有高可靠性、高带宽以及高实时性的特点,可以满足航电系统对延迟率、误码率的要求。作为研究将光纤通道应用于航空电子环境的分委员会,制定了光纤通道航空电子环境(Fiber Channel Avionics Environment,FC-AE)[2]的草案。主要作用就是支持以FC作为标准的航空电子专用系统[3]。作为光纤通道协议簇中的FC-AEASM支持航空电子系统中传感器、处理器和显示器间的低延迟、安全和确定的通信[4],但是该协议却没有给出网络中消息的调度算法,在满足航空电子环境中对实时性、延时性和大的网络吞吐能力的要求下,如何合理地安排节点上数据的发送和接收是一个很值得思考的问题[5]。

结合国内的研究情况来看,主要集中在网络传输的可靠性、拓扑结构、终端协议芯片等方面。文献[6-8]以网络任务模型为基础,建立了可靠性模型,同时针对光纤通道3种拓扑结构,推导出可靠性的表达式;文献[9]基于航电系统提出一种新型串行网络结构,同时进行建模和仿真分析;文献[10]针对FC协议,设计实现了终端协议芯片,测试结果表明满足协议要求;针对网络中消息的发送控制算法,文献[11]提出了基于实时排队论的调度算法,虽然它借助延时率可以反映系统实时性,但对于重负载以及抢占情况过多的情况下,开销大的同时也不一定满足系统实时性要求。

基于以上分析,提出了加权轮询调度算法(WRR)加优先级队列调度算法(PQ)相结合的调度算法,既很好地调度高优先级的紧急任务,又可以防止低优先级任务被饿死的现象发生,最后经过对调度算法实时性仿真,验证了该算法可以很好地满足现在的航空电子系统对实时性的需求。

1 FC-AE-ASM网络建模

FC-AE-ASM协议规定了支持FC网络协议的上层数据特征,但没有给出网络中消息的调度方式,在这首先定义网络模型结构和FC-AE-ASM的数据特征。

1.1 网络结构

交换式网络结构以其强大的互连功能和提供更多的冗余带宽,成为新一代航空电子系统的主要拓扑结构,所以在本文中主要讨论交换式网络中的FC-AE-ASM消息调度。网络是由FC交换机和通信终端组成,采用默认方式登录,节点间消息传递使用三类服务,同时交换机采用动态静态相结合的路由策略。发送消息终端随机发送单播、多播或广播消息,在网络中允许多个节点同时发送只含有一个数据帧的消息,接收终端只需根据数据表示符来确定数据是否是自己所需要以及该条数据的含义即可,不用区分发消息的终端是什么。网络结构模型如图1所示。

1.2 数据模型

在航电网络中所有消息的格式和长度都是固定的,即采用标准的数据帧,每条数据根据其唯一的32位数据ID来识别帧的内容,标准帧格式如图2所示。每条数据相应代表一条数据流,网络中的消息大部分为周期消息,即使是非周期消息也可以确定它发送的最大时间间隔,对于任意数据流Si,给出如下定义:第i个数据流的长度用Ci表示;数据产生的周期表示为Pi,Pmin为周期最小值;数据允许的最大延时为Di,一般取Pi=Di;每条链路的传输速率用v表示(假设每条链路的传输速率相同);第i个数据流对链路的占用要求表示为Ui,Ui=(Ci/v)/Pi,网络总的链路占用率为每条链路的占用率之和,表示为。

1.3 实时调度轮转约束条件

强实时条件下,当算法为消息i分配的权值wi满足下面两个条件时就可以实现强实时的调度。

1.3.1 轮询权值的约束条件

其中TRL表示信道轮转周期,取值小于Pmin并且为正整数;M为强实时的信道个数。

1.3.2 时限的约束条件:

在任意时间间隔t内,消息i发送的最小时间量:

处于消息集合中的每条消息在其允许的最小延迟时间内有足够的时间被发送,即就是满足:

2 消息调度算法

航空电子系统中的数据以周期性任务模型来传输。消息的类型一般分为紧急消息、周期性消息和数据块消息。在每个终端节点中设置3个不同优先级队列,消息按照优先级和允许最大延迟时间从小到大进行排队为M1,M2,…,Mn。它们构成一个等待传输队列集合 M={M1,M2,…,Mn}。一般情况下,消息产生时间表示为Tscr,消息到达时间表示为Tdst,消息的队列调度就是由4条入线进入的消息同时竞争一条出线,要保证消息最大允许延迟也就是Tdst和Tscr差值小于消息周期Pi。在选择调度算法的时候,通常有加权循环调度算法(WRR)、优先级队列调度算法(PQ)以及加权公平调度算法(WFQ)。在本文中提出PQ+WRR算法相结合的调度形式,充分结合两种算法的优势,同时采用令牌桶算法来控制紧急消息过多使得优先级较低的消息得不到调度情况。

2.1 PQ调度算法

优先级调度算法的基本原理就是到达的数据包由头部服务类型字段来确定分类,之后根据相应类别进入4个优先级队列,调度器首先调度高优先级的队列,直到队列为空时,才可以调度低优先级队列。该算法的优点就是可以保证实时性较强任务的低延时和低抖动。缺点就是在高优先级任务较多的情况下,低优先级队列长时间得不到调度,从而产生饿死的现象。队列调度原理如图3所示。

2.2 WRR调度算法

加权轮询调度算法基本原理就是业务根据不同需求分配到不同队列,之后按照占用带宽的比例为相应队列分配一个权值W,这样对于紧急性高,实时性强的任务所分配的权值就大,调度器按照权值来调度消息。它克服了PQ算法存在饿死的现象,缺点就是在消息长度变化情况下的支持性不够好。算法原理如图4所示。

2.3 令牌桶算法

令牌桶算法[12]是网络流量速率限制中常使用的一种算法,用来控制发送到网络上数据数目,同时允许发送突发数据。容量固定的令牌桶可以以恒定速率产生令牌,若令牌没有消耗或者消耗速率小于其产生的速率,那么令牌就不断增多,直至将桶填满,达到最大令牌数。令牌桶的控制机制为桶内是否存在令牌是决定发送数据的依据,每一个令牌代表一个字节,当桶内存在令牌时,允许发送数据,相反则不允许发送数据。如果令牌桶中有足够多的令牌,同时突发门限被合理配置,这样流量就可以以峰值速率进行发送。算法原理如图5所示。

本质上来说,令牌桶算法是一种测量引擎,可以用来控制突发流量,同时用发送流量的多少指定流量速率,令牌桶算法有单速率双色、单速率三色和双速率三色3种技术,其中单速率三色是对单速率双色的逻辑描述。

在本文使用单速率三色标记方式,IETF RFC2697将单速率三色算法用CIR、CBS和EBS进行评估。CIR表示令牌产生的速度,也叫做最大发送速度;CBS表示令牌桶深度,也就是可接受突发数据包的最大容量;EBS表示额定突发容量。单速率方式下采用两个令牌桶。这样CBS中没有使用的令牌都被放入另一个桶内,在突发流量超过CIR时使用,所以第2个桶的大小是第2个桶的容量和第1个桶中未使用的令牌之和。

3 基于令牌桶的PQ+WRR算法

本文提出的调度算法由PQ+WRR分组调度器和令牌桶流量调节器构成,本文采用令牌桶算法这种流量调节器来控制实时性紧急任务占用过多的网络带宽,同时结合优先级调度算法为高优先级的紧急任务提供低延时、低抖动的性能,以及为网络中其他业务提供最佳服务。当分组数据到达区分服务位置时,若该数据分组被标记成紧急任务,那么它就要令牌桶所过滤,此时令牌桶中有令牌,那么就会通过PQ调度,立刻转发,相反就会经过WRR算法进行调度。当非紧急任务到达时,首先会通过WRR算法进行调度,之后再经过优先级调度算法发送出去。在上述算法中,紧急任务总是最先得到服务,但是由于令牌桶对其的控制,使得紧急任务不可能长时间占据整个带宽,保证了低优先级任务可以的到调度,这样就克服了两种算法的缺点,提高网络的总体性能。算法调度原理如下页图6所示。

算法具体实现:为方便软件实现,相应两个队列调度数据包的个数就是其权值,为了充分利用带宽,在高优先级队列为空时,立即调度低优先级队列,具体实现流程如图7所示。

3.1 调度算法参数设计

在调度算法中,轮转周期的选择对系统性能有着关键的影响。权值的分配方式直接关系系统分配的信道资源数目,也决定了消息队列分配的权值大小。

3.1.1 权值分配

在单信道WRR算法中为保证消息传输的实时性,消息i的权值通常取

3.1.2 轮转周期TRL的选择

本文定义轮转函数为:

当轮转函数取值最小时,相应的轮转周期就是当前分配方式下的最优值,这时分配权值和初始权值的差值最小,有效利用率最高。

4 仿真结果

仿真过程中,首先根据FC-AE-ASM协议建立节点、状态和网络模型,每个节点的数据特征如表1所示,网络中的消息以数据包的形式传输,链路速率为1 Gbit/s。节点中的消息按照提出的调度算法进行排队,针对不同的权值分配方式,在每个消息传送成功后,记录其延迟时间和延迟率。

表1 仿真数据

4.1 不同权值分配方式下F函数与TRL的关系

仿真数据如表1所示。根据实时调度的轮转约束条件以及轮转函数的定义,可得其关系如下:

由图8可知当采用分配方式1时,在TRL=6 μs时轮转函数min(F)=0.75取得最小值,表明此时分配权值和初始权值差值最小,有效利用率最高。同理在分配方式2条件下,在TRL=10 μs时轮转函数min(F)=0.2取得最小值,有效利用率最高。

经过上面的结果,本文取TRL=10 μs,对两种权值的分配方式下消息的延迟时间和延时率进行仿真,结果如图9~图11所示:

由仿真结果看出,在权值分配方式1的情况下,消息的延迟时间随着仿真时间的进行在不断波动,而在权值分配方式2的情况下,每条消息的延迟时间都保持不变,说明在权值分配方式2的情况下调度效果更好。从延迟率来看,两种分配方式下所有消息的延迟率都没有超过1,可以满足系统对实时性的要求,但是相对来说消息的时间延迟率一方面代表系统的实时性,另一方面也代表消息传输对系统的容忍程度,相应的值越小,内外各种因素影响系统的可能性就越低,这样来说,分配方式1更适合在现代航空系统中应用。相比于文献[5]中的调度方式,本文的算法较好地改变了调度性能。

5 结论

在对FC-AE-ASM协议深入研究的基础上,针对数据的发送控制,提出了基于令牌桶的PQ+WRR算法,同时给出了权值分配和轮转周期的确定方法。最后经过仿真验证了这种算法可以很好地满足系统对实时性的要求。对于目前国内在光纤通道中对于调度算法的研究方面具有很好的借鉴作用。

[1]GASKA T D.COTS fibre channel network technology insertion into avionicssystems [C]//IEEE 1998 National Aerospace and Electronics Conference,1998:120-127.

[2]ANSI.Rev.2.4.Fibre channel avionics environment(FC-AE)[S].USA:American National Standard for Information Systems,2004.

[3]INCTIS.T11/02-041v1.Fibre Channel-Avionics environment[S].Washington:InternationalCommittee forInformation Technology Standards,2002.

[4]INCITS.T11/08-013v1-FC-AE-ASM/AM1[S].Washington:International Committee for Information Technology Standards,2008.

[5]丁凡,宋丽茹,熊华钢.FC-AE-ASM网络数据发送控制算法研究[J].电子与信息学报,2009,31(6):1509-1512.

[6]翟正军,陈康,焦航.FC-AE-ASM网络的模糊可靠性研究[J].计算机应用研究,2013,30(8):2467-2469.

[7]徐亚军,张晓林,熊华钢.FC互连的可靠性建模[J].北京航空航天大学学报,2005,31(5):539-543.

[8]易川,翟正军,羊昌燕.基于蒙特卡罗法的FC-AE-ASM网络可靠性研究[J]. 计算机工程与应用,2014,50(3):59-62.

[9]刘达,王勇,褚文奎,等.航空电子系统中串行光纤通道网络建模与仿真[J].应用激光,2015,35(6):724-728.

[10]刘达,王勇,李炳乾,等.基于FPGA的FC终端协议处理芯片的设计与实现[J].火力与指挥控制,2017,42(7):124-128.

[11]付中培,吴勇,张建东,等.FC-AE-ASM网络调度算法研究[J].现代电子技术,2011,34(6):108-111.

[12]蒋维成.令牌桶算法比较研究[J].电脑知识与技术,2010,6(4):861-862.

[13]MAODE M,HAMIDZADEH B,HAMDI M.Providing deterministic quality-of-service guarantees on WDM optical network [J].IEEE Journal on Selected Areas in Communications,2000,18(10):2072-2083.

[14]林强,熊华钢,张其善.光纤通道交换机在强实时约束条件下的分组调度[J].计算机学报.2006,29(4):570-575.

[15]周立,王昊天,何锋,等.航空电子多信道实时分组调度方法[J].航空学报,2010,31(10):2034-2039.

Research on Fiber Channel Scheduling Algorithm

DING Yong-qiang1,WAGN Yong2,TAN Xiao-hu2,CHU Wen-kui2,FANG Ting2
(1.College of The First Aeronautic,Air Force Engineering University,Xinyang 464000,China;2.College of Aeronautics and Astronautics Engineering,Air Force Engineering University,Xi’an 710038,China)

This paper primarily aim at the problem that it don’t have data scheduling algorithm in FC.Through analysis deeply,an algorithm which combine PQ with WRR basing on Token Bucket algorithm is presented,at the same time,include ensured the way of weight distribution and turnaround time.Delay rate is as to the performance of algorithm.Simulation turn out that the scheduling algorithm can meet real-time in avionics system.

FC,weight distribution,turnaround time,delay rate

TP914

A

10.3969/j.issn.1002-0640.2017.11.17

1002-0640(2017)11-0077-05

2016-10-05

2016-11-07

航空科学基金资助项目(20165515001)

丁永强(1981-),男,河南信阳人,博士,讲师。研究方向:机载总线技术。

猜你喜欢

令牌实时性权值
一种融合时间权值和用户行为序列的电影推荐模型
称金块
基于5G MR实现Massive MIMO权值智能寻优的技术方案研究
一种基于互连测试的综合优化算法∗
航空电子AFDX与AVB传输实时性抗干扰对比
计算机控制系统实时性的提高策略
可编程控制器的实时处理器的研究
财务风险跟踪评价方法初探
《道教法印令牌探奥》出版发行