先进先出(FIFO)调度算法按照数据帧的到达顺序依次进行处理,难以对不同优先级、不同安全性及实时性要求的数据包进行分类处理,在实现紧急数据流的优先发送方面有待改善[1]。严格优先级队列(SP)调度算法对所有的数据流根据优先级分类,对同一优先级的数据流采用FIFO,该方法的不足在于高优先级队列数据流流量较大时,会抢占端系统发送通道,造成低优先级队列延迟时间过长[2]。文献[3]介绍了短帧优先算法,该调度策略考虑到机载电气系统数据传输过程中,短帧数据流量较大且实时性要求较高,优先发送短帧以减小其发送延迟,但是当短帧数据流相对较大时会造成长帧数据链路长时间等待的问题以及数据流的处理带宽不合理性。文献[4]介绍的带权重轮询(WRR)算法,是以数据帧帧长划分优先级,通过带权重轮询的方式轮询调度各优先级队列的数据流,使得不同队列得到合理的传输带宽,但是效率较低,且短帧会因为等待长帧发送而延迟。
本文以配电控制系统与AFDX网络数据交互为例,提出一种在短帧优先基础上结合带权重轮询的组合调度(CS)策略,结合短帧优先调度算法的优点,通过带权重轮询长帧数据,以牺牲一般任务数据流的带宽来保证较重要任务数据的及时传输,提高机载网络AFDX端系统带宽利用率,降低短帧虚链路(VL)的最大延迟上界,尤其适用于短帧数据流较多的数据传输网络。
1 AFDX网络与配电系统数据交互 AFDX网络用于互连机载设备、子系统及各模块,实现系统之间信息传递和数据交互[5-6]。
图 1给出了AFDX网络与配电系统数据交互示意图,其中配电系统时间触发(TTP)总线信号与AFDX网络通过数据转换接口进行消息传输。供电系统处理机(PSP)完成系统控制任务,从发电机控制器(GCU)、负载管理中心(ELMC)和汇流条控制器(BPCU)处接收状态数据并结合从航空电子系统接收到的控制指令,对配电系统进行综合管理[7]。在系统信息交互中,负载电源请求信号、汇流条转换接触器控制信号和转换继电器控制指令等为重要短帧数据;发电机状态、蓄电池状态和负载供电状态等为较重要任务数据;汇流条转换接触器状态、转换继电器状态和数据备份等为一般任务数据。重要指令一般多为重要短帧且要求实时性高、延迟小[8],因此本文提出短帧优先的权重轮询组合调度算法,降低端系统发送延迟上界,进一步提高端系统发送效率。
图 1 AFDX网络与配电系统数据交互 Fig. 1 Data interaction between AFDX network and power distribution system |
图选项 |
2 短帧优先与带权重轮询组合调度 组合调度策略结构如图 2所示,根据系统网络各单元之间信息交互,将网络数据流根据帧长的长短分为:短帧数据流和长帧数据流,其中短帧数据流被赋予最高优先级,优先进行短帧数据包的调度和处理,同时将长帧数据流设置为低优先级,按照其数据类型分为较重要任务和一般任务,并对其分配不同比例的传输带宽,保证不同类型的数据流有不同的权重分别满足其对实时性的要求[9]。调度短帧队列时,优先发送以保证短帧数据的及时传输,长帧队列的权重比则给予了较重要任务、一般任务数据包传输所需要的带宽,实现较重要任务数据及时传输[10-11]。
图 2 组合调度策略结构 Fig. 2 Structure of combinatorial scheduling strategy |
图选项 |
图 2中的组合调度策略结构参数说明如下:BAGi为虚链路的参数,表示带宽分配间隔,ms;lmaxi为虚链路的最大帧长[3-4], b;Q1为优先级最高队列,聚集短帧数据流且帧长小于100 B的虚链路;Q2为优先级次高队列,数据类型为较重要任务且帧长大于100 B的虚链路;Q3为优先级最低队列,数据类型为一般任务且帧长大于100 B的虚链路;L为优先级最高队列Q1中聚集的最大数据流, B;?2为优先级次高队列Q2的权重,表示一轮轮询调度中Q2队列被处理发送的分组数[4];?3为优先级最低队列Q3的权重,表示一轮轮询调度中Q3队列被处理发送的分组数[4];C为物理链路的带宽, b/s。
k2、k3为Q2、Q3队列在一轮轮询调度中已被处理发送的分组数。设在某时刻,虚链路到达组合调度服务器,到达的虚链路按照最大帧长分别进入相应的优先级队列(见图 2),初始化k2=k3=0,设置C的值。其步骤如下:
1)?首先判断Q1队列是否有数据帧到达,若是则发送Q1队首的一个分组数据,继续步骤1),否则跳转到步骤2)。
2)?判断k2是否大于等于?2,若是则跳转到步骤3),否则发送Q2队首的一个分组,k2=k2+1,继续步骤2)。
3)?判断k3是否大于等于?3,若是则k2=k3=0且跳转到步骤1),否则发送Q3队首的一个分组,k3=k3+1,继续步骤3)。
2.1 不同优先级队列的服务曲线 对于组合调度器,服务曲线满足β(t)=Ct,t为时间,s。以各个优先级队列聚集的虚链路最大帧长lmaxi相等为前提,则调度器执行一轮最大执行时间为
则对于各个优先级队列,其服务时间为
(1) |
得到优先级队列Qi的服务速率Ci保证为
(2) |
考虑最差情况下的队列Qi被延时处理的情形,需等待其他队列数据被轮回调度后,再在下一轮调度中被处理,所以其最大延时时间Ti为
(3) |
可推算出组合调度器分配给队列Qi的服务曲线βi(t)为
(4) |
队列Qi由多个虚链路组成时,则Qi队列中的第j条虚链路的服务曲线βij(t)为
(5) |
式中:n为各优先级队列聚集的虚链路个数。
2.2 虚链路的延迟时间 如图 3所示,对于不同优先级队列Qi,所有虚链路的到达曲线可表示为[3]
(6) |
图 3 最大延迟上界Di Fig. 3 Maximum delay upper bound Di |
图选项 |
由图 3可知,为确保端系统数据传输的实时性和稳定性,带宽、权重比等参数的设定需满足:
(7) |
解算出组合调度算法下队列Qi的最大延迟上界Di为
(8) |
队列Qi由多个虚链路组成时,Qi队列中的第j条虚链路的最大延迟上界Dij为
(9) |
由式(9)可知,虚链路的最大延迟上界与物理链路带宽、虚链路的最大帧长和轮询权重比等因素有关。
3 组合调度与其他调度算法比较 以某短帧较多的机载主干网AFDX网络环境为例[12](配置参数情况如表 1所示, X表示有短帧数据时就一直发送短帧数据),比较研究组合调度与其他调度算法下虚链路的最大延迟上界。
表 1 虚链路配置表 Table 1 VL configuration table
数据类型 | 链路数 | BAGi/ms | lmax/B | 分组数 |
短帧 | 12 | 1 | 100 | X |
较重要任务 | 4 | 1 | 800 | 5 |
一般任务 | 3 | 1 | 800 | 2 |
表选项
3.1 短帧优先调度策略 使用短帧优先调度算法时,按照帧长分为3个队列,队列1的链路VL1~VLi最大帧长不超过300 B,队列2的链路VLi+1~VLj最大帧长范围为300~600 B,队列3的链路VLj+1~VLn最大帧长大于600 B。优先发送短帧数据以达到减小其发送延迟的目的,虚链路的最大延迟上界为[3]
(10) |
式中:lmaxE1为队列2和队列3中虚链路的最大帧长;lmaxE2为队列1和队列3中虚链路的最大帧长; lmaxE3为队列1和队列2中虚链路的最大帧长; BAGE2为队列2虚链路的带宽分配间隔; BAGE3为队列3虚链路的带宽分配间隔。
3.2 带权重轮询调度策略 使用带权重轮询调度算法时,根据数据对实时性的要求,分别赋予短帧队列、中等帧队列和长帧队列不同的比重,虚链路的最大延迟上界为[4]
(11) |
分别计算以上两种调度策略和本文提出的短帧优先与带权重轮询组合调度算法下,表 1配置环境的虚链路最大延迟上界,见表 2,可见:
表 2 组合调度与FIFO调度最大延迟上界比较 Table 2 Comparison of maximum delay upper bound between combinatorial scheduling and FIFO scheduling
数据类型 | 链路数 | 最大延迟上界/μs | ||
组合调度 | 短帧优先 | 权重轮询 | ||
短帧 | 12 | 89 | 89 | 472 |
较重要任务 | 4 | 702 | 836 | 702 |
一般任务 | 3 | 971 | 836 | 971 |
总和 | 6 789 | 6 920 | 11 385 |
表选项
1)?与短帧优先调度算法相比,组合调度算法可改善当短帧数据流相对较大时造成的长帧数据链路长时间等待的问题,以牺牲一般任务的处理带宽,以保证较重要任务的完整带宽,减小其发送时延。
2)?与带权重轮询调度算法相比,组合调度算法有效降低短帧虚链路的最大延迟上界,对于短帧数据流占主要部分的机载网络而言,该方法比较适用,可有效提高网络传输效率。
4 仿真分析 建立AFDX网络仿真模型,根据表 1的参数配置,仿真研究该端系统模型在不同调度算法下,虚链路的延迟时间和端系统的数据传输效率[13-14]。
4.1 端系统建模 利用OPNET网络工具构建不同调度算法下的AFDX端系统仿真模型,如图 4所示。P1~P12、P13~P16、P17~P19分别为12个短帧、4个较重要任务和3个一般任务虚链路的源模块,Schedule则为调度算法处理模块。在Schedule模块中分别引用新型组合调度策略、短帧优先调度以及带权重轮询调度的处理器模型,结合理论计算结果,仿真验证组合调度算法的优越性和适用性[15-16]。
init—初始化进程模块;idle—闲置进程模块;default—系统默认自循环等待发送;CS_tx—Q1队列发送进程;WRR_tx—Q2和Q3队列轮询发送进程;Pk_ace—发送完成中断模块。 图 4 AFDX端系统仿真模型 Fig. 4 Simulation model of AFDX terminal system |
图选项 |
4.2 发送效率比较 利用所建模型比较分析3种调度策略下,各虚链路延迟时间,仿真结果如图 5所示。
图 5 各调度算法下虚链路的延迟时间 Fig. 5 VL delay time with different scheduling strategies |
图选项 |
由图 5(a)可见,组合调度算法提高了较重要任务虚链路的传输效率,延迟时间减少了16.0%,然而对于一般任务虚链路延迟时间增加了15.9%,延迟时间控制在ms级以内。
由图 5(b)可见,组合调度算法减少了短帧链路的延迟时间,并且各虚链路的延迟时间都小于最大延迟上界,其延迟时间总和减少了40.0%,提高了AFDX端系统的发送效率。
4.3 权重比对延迟时间的影响 针对本文提出的组合调度算法,适当调整较重要任务和一般任务队列的权重,研究分析该队列聚集的虚链路延迟时间的变化,以及对所有虚链路延迟时间总和的影响,如图 6所示。
图 6 不同权重比的各队列延迟 Fig. 6 Queue delay time at different weight radios |
图选项 |
若提高较重要任务队列的权重,可进一步缩短较重要任务虚链路的延迟时间,但一般任务虚链路的延迟时间增加。当一般任务对发送时间有要求时,应适当提高一般任务的权重,缩短一般任务队列的延迟时间。
5 结论 本文使用网络微积分理论,分析和研究了飞机AFDX网络端系统的数据流发送延时,给出一个可行的基于短帧优先的带权重轮询的组合调度策略。
1)?与短帧优先调度策略相比,该策略提高了较重要任务虚拟链路的传输效率,有效保证了较重要任务的及时传输。当一般任务对发送时间有要求时,应适当提高一般任务的权重,缩短一般任务队列的延迟时间。
2)?与带权重轮询调度策略相比,组合策略有效降低了短帧虚拟链路的最大延迟上界和延迟时间、系统所有链路的延迟时间总和,提高了端系统带宽利用率。
本文给出的组合调度策略以较多重要短帧并具有不同优先级数据的机载网络为适用研究对象,如何让该策略兼容更加复杂的数据流还需进一步研究。
参考文献
[1] | BOYER M, FRABOUL C.Tightening end to end delay upper bound for AFDX network calculus with rate latency FIFO servers using network calculus[C]//IEEE International Workshop on Factory Communication Systems.Piscataway, NJ:IEEE Press, 2008:11-20. |
[2] | 张勇涛, 黄臻, 熊华钢. 保证速率的AFDX交换机实时调度算法[J].北京航空航天大学学报, 2010, 36(12): 1412–1416.ZHANG Y T, HUANG Z, XIONG H G. Real time scheduling algorithm based on rate guaranteed in AFDX switch[J].Journal of Beijing University of Aeronautics and Astronautics, 2010, 36(12): 1412–1416.(in Chinese) |
[3] | 吴桓, 葛红娟, 倪建丽, 等. 基于短帧优先调度的AFDX端系统发送策略[J].航空计算技术, 2012, 42(6): 125–128.WU H, GE H J, NI J L, et al. AFDX end system transmission strategy based on shortest frame first scheduling[J].Aeronautical Computing Technique, 2012, 42(6): 125–128.(in Chinese) |
[4] | XU Y Y, GE H J, WU H, et al. Research of virtual combinatorial scheduling strategy in AFDX end system[J].Journal of Information & Computational Science, 2015, 12(1): 255–262. |
[5] | HUSSEIN C, JEAN L S, CHRISTIAN F.Methods for bounding end-to-end delays on an AFDX network[C]//Proceedings of the 18th Euromicro Conference on Real-Time Systems (ECRTS'06).Piscataway, NJ:IEEE Press, 2006:193-202. |
[6] | 周天然, 张勇涛, 何锋, 等. 基于AFDX的航空电子系统可调度性分析[J].北京航空航天大学报, 2012, 38(1): 75–79.ZHOU T R, ZHANG Y T, HE F, et al. Schedulability analysis for AFDX-based avionics systems[J].Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(1): 75–79.(in Chinese) |
[7] | 陈思, 葛红娟, 杨宗翰, 等. 基于TTP协议的飞机配电系统通信仿真研究[J].航空计算技术, 2014, 44(6): 95–99.CHEN S, GE H J, YANG Z H, et al. Research on simulation of communication in aircraft power distribution system based on TTP protocol[J].Aeronautical Computing Technique, 2014, 44(6): 95–99.(in Chinese) |
[8] | 杨绪强, 支高飞. 新一代航空总线协议AFDX[J].科技传播, 2010(17): 194.YANG X Q, ZHI G F. A new generation of avionics bus protocol AFDX[J].Public Communication of Science & Technology, 2010(17): 194.(in Chinese) |
[9] | 刘成, 王彤, 李铮, 等. 时间触发AFDX网络的设计和实时性分析[J].北京航空航天大学报, 2013, 39(6): 728–733.LIU C, WANG T, LI Z, et al. Design and delay analysis of time-triggered AFDX network[J].Journal of Beijing University of Aeronautics and Astronautics, 2013, 39(6): 728–733.(in Chinese) |
[10] | 赵红敏, 王建新, 黄家玮. FRA:基于帧长和发送速率的信道竞争算法[J].计算机工程, 2010, 36(17): 123–125.ZHAO H M, WANG J X, HUANG J W. FRA:Channel contending algorithm based on frame size and transmission rate[J].Computer Engineering, 2010, 36(17): 123–125.(in Chinese) |
[11] | 王绮卉.AFDX核心交换技术的研究与实现[D].西安:西安石油大学, 2010.WANG Q H.The study and application about switching technique of AFDX[D].Xi'an:Xi'an Shiyou University, 2010(in Chinese).http://cdmd.cnki.com.cn/article/cdmd-10705-2010133947.htm |
[12] | 王建宇, 王世奎. AFDX交换机管子功能测试方法的研究与设计[J].测控技术, 2012, 31(7): 82–84.WANG J Y, WANG S K. Research and design of test method of AFDX switch policing function[J].Measurement & Control Technology, 2012, 31(7): 82–84.(in Chinese) |
[13] | 安东, 曾星星, 丁丽娜. AFDX网络系统建模与仿真实现[J].测控技术, 2012, 31(2): 76–80.AN D, ZENG X X, DING L N. The modeling and the simulation implementation of AFDX network system[J].Measurement & Control Technology, 2012, 31(2): 76–80.(in Chinese) |
[14] | 赵永库, 李贞, 唐来胜. AFDX网络协议研究[J].自动化测试技术, 2012, 20(1): 8–10.ZHAO Y K, LI Z, TANG L S. Research on network protocol of AFDX[J].Computer Measurement & Control, 2012, 20(1): 8–10.(in Chinese) |
[15] | 陈昕, 周拥军, 万剑雄. AFDX端系统关键技术的研究与实现[J].计算机工程, 2009, 35(5): 1–3.CHEN X, ZHOU Y J, WAN J X. Research and implementation of key techniques in AFDX end system[J].Computer Engineering, 2009, 35(5): 1–3.(in Chinese) |
[16] | Condor Engineering, Inc..AFDX PROTOCOL TUTORIAL[EB/OL].2005[2015-10-14].Santa Barbara, CA:Condor Engineering, Inc..http://www.cems.uwe.ac.uk/~a2-lenz/n-gunton/afdx_detailed.pdf. |