主从结构交换式以太网中实时消息调度研究

J4 ›› 2014, Vol. 36 ›› Issue (12): 2312-2320.

主从结构交换式以太网中实时消息调度研究

檀明

(合肥学院计算机科学与技术系，安徽合肥 230601)

收稿日期:2014-08-05 修回日期:2014-10-16 出版日期:2014-12-25 发布日期:2014-12-25
基金资助:
安徽省教育厅产学研重点资助项目(KJ2014A210）；合肥学院重点研究资助项目（14KY01ZD）；合肥学院重点建设学科（2014xk08）;合肥学院学科带头人培养对象（2014dtr08）

Research on scheduling of realtime
messages over master-slave switched Ethernet

TAN Ming

(Department of Computer Science and Technology,Hefei Union University,Hefei 230601,China)

Received:2014-08-05 Revised:2014-10-16 Online:2014-12-25 Published:2014-12-25

摘要/Abstract

摘要：

为使交换式以太网能满足实时通信的要求，针对FTTSE网络调度模型，提出了一种同时适用于周期性和非周期性实时消息的链路可调度性判定方法。在证明了消息链路调度优化问题MLSOP为NPcomplete的同时，针对周期性实时消息的链路调度优化给出了启发式算法LSHA。最后,对于周期性和非周期性实时消息分别设计了基于EDF的调度算法。仿真实验表明,在提高网络链路带宽利用率和减小消息平均延时方面,该算法均较FTTSE有明显的优势。

关键词: 主从交换式以太网, EDF调度, 周期性实时消息

Abstract:

To make switched Ethernet meet the requirements of real-time communication, a novel link schedulability analysis method for both periodic and aperiodic realtime messages is proposed based on FTT-SE (Flexible Time Triggered Switched Ethernet) paradigm. In addition, it is proved that finding the optimal schedule for a given set of periodic messages on transmission links in order to minimize the maximum finishing time of reception links is NP-complete, and a heuristics algorithm named LSHA is proposed to solve this problem. Particularly, we design different EDF-based scheduling algorithms for periodic and aperiodic real-time messages respectively, which make it possible for the scheduler to take full advantage of multiple transmission paths, thus enhance the realtime communication over a COTSbased switched Ethernet. Simulation results show that the proposed Real-Time scheduling algorithm outperforms FTTSE in terms of enhancing network bandwidth utilization and reducing average message delay.

Key words: master-slave switched Ethernet；EDF-based scheduling；periodic real-time message

檀明. 主从结构交换式以太网中实时消息调度研究[J]. J4, 2014, 36(12): 2312-2320.

TAN Ming. Research on scheduling of realtime
messages over master-slave switched Ethernet [J]. J4, 2014, 36(12): 2312-2320.

参考文献［10］

［1］	Behnam M, Iqbal Z,Silva P,et al.Engineering and analyzing multiswitch networks with single point of control［C］∥Proc of the 1st International Workshop on WorstCase Traversal Time,2011:1118.
［2］	Lim H T, Weckemann K, Herrscher D. Performance study of an incar switched Ethernet network without prioritization［M］∥Proc of the 3rd International Conference on Communication Technologies for Vehicles, 2011:165175.
［3］	Kim MK,Shan Liang, Yu Wang. EDFbased realtime message scheduling of periodic messages on a masterslavebased synchronized switched Ethernet［J］. International Journal of Control and Automation,2009,2(4):2534.
［4］	Yang Shiping,Sang Nan,Xiong Guangze.Safety critical realtime networks based on Ethernet technology ［J］. Journal of Software, 2005, 16(1):121134.(in Chinese)
［5］	Ashjaei M. Extending the FTTSE protocol for multimaster/multislave networks［M］.Gemany:LAP Lambert Academic Publishing, 2012.
［6］	Chen Shiyuan.Research of time delay and scheduling algorithm of network control system based on Switch Ethernet［D］. Kunming:Yunnan University, 2013.(in Chinese)
［7］	Loeser J,Haertig H.Lowlatency hard realtime communication over switched Ethernet［C］∥Proc of the 16th Euromicro Conference on RealTime Systems,2004:1322.
［8］	Hoang H,Jonsson M,Kallerdahl A, et al.Switched realtime Ethernet with earliest deadline first schedulingprotocols and traffic handling［J］. Parallel and Distributed Computing Practices,2002,5(1):105115.
［9］	Kopetz H,Ademaj A,Grillinger P,et al.The timetriggered Ethernet (TTE) design［C］∥Proc of the 8th IEEE International Symposium on ObjectOriented RealTime Distributed Computing, 2005:2233.
［10］	Tan Ming,Wei Zhen,Han Jianghong. Research on deadline partitioning schemes for realtime message transmission over switched Ethernet［J］. Application Research of Computers,2012,29(12):17141718.(in Chinese)
［11］	Marau R,Almeida L,Pedreiras P.Enhancing realtime communication over cots Ethernet switches［C］∥Proc of WFCS’06, 2006:295302.
［12］	Marau R, Pedreiras P, Almeida L. Asynchronous traffic signaling over masterslave switched Ethernet protocols［C］∥Proc of the 6th International Workshop on Real Time Networks (RTN’07), 2007:1.
［13］	Cuong D M, Kim M K, Lee H C. Supporting hard realtime communication of periodic messages over switched Ethernet［C］∥Proc of the 1st International Forum on Strategic Technology, 2006:419422.
［14］	Kim M K,Lee H C.Periodic message scheduling on a switched Ethernet for hard realtime communication［C］∥Proc of High Performance Computing and Communications, 2006:457466.
［15］	Michael R G, David S J. Computers and intractability:A guide to the theory of NPcompleteness［M］. San Francisco:WH Freeman & Co,1979.
	附中文参考文献：
［4］	杨仕平, 桑楠, 熊光泽. 基于 Ethernet 技术的安全关键实时网络［J］. 软件学报, 2005, 16(1):121134.
［6］	陈施垣. 基于 Switch Ethernet 网络控制系统时延与调度算法的研究［D］. 昆明：云南大学, 2013.
［10］	檀明, 魏臻, 韩江洪. 交换以太网中实时消息截止期划分算法研究［J］. 计算机应用研究, 2012, 29(12):17141718.