SSA:一种面向CQF模型的TSN资源调度算法

doi:10.12068/j.issn.1005-3026.2020.06.005

东北大学学报:自然科学版 ›› 2020, Vol. 41 ›› Issue (6): 784-791.DOI: 10.12068/j.issn.1005-3026.2020.06.005

SSA:一种面向CQF模型的TSN资源调度算法

姜旭艳，严锦立，全巍，孙志刚

(国防科技大学计算机学院，湖南长沙410073)

收稿日期:2019-09-29 修回日期:2019-09-29 出版日期:2020-06-15 发布日期:2020-06-12
通讯作者: 姜旭艳
作者简介:姜旭艳(1998-)，女，湖南永州人，国防科技大学博士研究生; 孙志刚(1973-)，男，江苏连云港人，国防科技大学研究员.
基金资助:
国家重点研发计划项目(2018YFB1800402)；国家自然科学基金资助项目(61802417，61702538)；国防科技大学校内科研项目(ZK17-03-53，ZK18-03-40).

SSA:CQF-oriented Scheduling Algorithm in Time-Sensitive Networking

JIANG Xu-yan， YAN Jin-li， QUAN Wei， SUN Zhi-gang

College of Computer， National University of Defense Technology， Changsha 410073， China.

Received:2019-09-29 Revised:2019-09-29 Online:2020-06-15 Published:2020-06-12
Contact: JIANG Xu-yan
About author:-
Supported by:
-

摘要/Abstract

摘要： 时间敏感网络(time sensitive networking，TSN)的目标是在工业控制和5G领域为时间敏感流提供低延迟、低抖动的确定性传输服务.资源调度是保证TSN服务质量的关键技术之一.为此，TSN标准中提出循环队列转发模型(cyclic queuing and forwarding，CQF)，但是缺乏相应的资源调度算法对多流进行合理的资源分配以避免传输冲突.由于时间敏感流量具有周期性、特征预知的特点，主要从时间维度研究如何将CQF模型中的队列资源合理分配给多条数据流.将该问题抽象为多约束条件下的资源规划最大化问题，提出基于起始时隙分配的轻量级资源调度算法(start-slot assignment based scheduling algorithm，SSA).SSA通过对端系统上发送时隙进行调节，在满足约束条件的前提下最大化对队列资源的使用，避免了端到端逐跳的时隙分配.实验结果表明，与不控制时隙的直接调度方式相比，该算法能够将成功调度的流数目平均提高41.84%.

关键词: 时间敏感网络, 确定性传输, 循环队列转发模型, 网络资源调度, 最大化问题

Abstract: Time-sensitive networking (TSN) is designed for providing determined transmission service with low latency and jitter in industrial control network and 5G.Resource scheduling， the core of TSN， is very crucial to guarantee the quality of service (QoS). Recently， TSN puts forward cyclic queuing and forwarding model (CQF). However， the corresponding scheduling algorithm is demanded for allocating resource rationally to avoid transmission collision.Since the TSN flow is periodic and predetermined， how to allocate resource for multiple TSN flows rationally from time dimension was researched. Resource allocation into multi-constrained maximization problem was abstracted. Then， a start-slot assignment based scheduling algorithm (SSA) was proposed. By adjusting the send slot at end system， SSA maximizes the queue resource utilization with meeting related constraints， which avoids complex time slot allocation hop by hop. Compared with the case without adjusting sending slot， experimental results demonstrate that SSA improves the number of flows scheduled successfully by 41.84% on average.

Key words: time-sensitive networking(TSN), deterministic transmission, cyclic queuing and forwarding model(CQF), network resource scheduling, maximization problem

中图分类号:

TP393.1

姜旭艳，严锦立，全巍，孙志刚. SSA:一种面向CQF模型的TSN资源调度算法[J]. 东北大学学报:自然科学版, 2020, 41(6): 784-791.

JIANG Xu-yan， YAN Jin-li， QUAN Wei， SUN Zhi-gang. SSA:CQF-oriented Scheduling Algorithm in Time-Sensitive Networking[J]. Journal of Northeastern University Natural Science, 2020, 41(6): 784-791.

参考文献

[1]Nasrallah A，Thyagaturu A，Alharbi Z，et al.Ultra-low latency (ULL) networks:The IEEE TSN and IETF Det Netstandards and related 5G ULL research［J］.IEEE Communications Surveys & Tutorials， 2018，21(1):88-145.
[2]Nayak N G，Dürr F，Rothermel K.Incremental flow scheduling and routing in time-sensitive software-defined networks［J］.IEEE Transactions on Industrial Informatics， 2017，14(5):2066-2075.
[3]Chowdhury S R.Packet scheduling algorithms for a software-defined manufacturing environment［D］.Stuttgart:University of Stuttgart，2015.
[4]Wilfried S，Silviu C，Ramon S O.Traffic planning for time-sensitive communication［J］.IEEE Communications Standards Magazine， 2018，2(2):42-47.
[5]Steiner W.Synthesis of static communication schedules for mixed-criticality systems［C］//14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops.Newport Beach，2011:11-18.
[6]Craciunas S S，Oliver R S，Chmelík M，et al.Scheduling real-time communication in IEEE 802.1 Qbv time sensitive networks［C］//Proceedings of the 24th International Conference on Real-Time Networks and Systems.Brest:ACM，2016:183-192.
[7]Dürr F，Nayak N G.No-wait packet scheduling for IEEE time-sensitive networks (TSN)［C］//Proceedings of the 24th International Conference on Real-Time Networks and Systems.Brest:ACM，2016:203-212.
[8]Steiner W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks［C］//2010 31st IEEE Real-Time Systems Symposium.San Diego，2010:375-384.
[9]Pozo F，Rodriguez-Navas G，Hansson H，et al.SMT-based synthesis of TTEthernet schedules:A performance study［C］//10th IEEE International Symposium on Industrial Embedded Systems (SIES).Siegen，2015:1-4.
[10]Pozo F，Steiner W，Rodriguez-Navas G，et al.A decomposition approach for SMT-based schedule synthesis for time-triggered networks［C］//IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA).Luxembourg，2015:1-8.
[11]Tamas-Selicean D，Pop P，Steiner W.Synthesis of communication schedules for TTEthernet-based mixed-criticality systems［C］//Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis.Tampere:ACM，2012:473-482.
[12]Oliver R S，Craciunas S S，Steiner W.IEEE 802.1 Qbv gate control list synthesis using array theory encoding［C］//IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS).Porto，2018:13-24.
[15]关守平，房少纯.一种新型的区间-粒子群优化算法［J］.东北大学学报(自然科学版)，2012，33(10):1381-1384.(Guan Shou-ping，Fang Shao-chun.A new interval particle swarm optimization algorithm［J］.Journal of Northeastern University(Natural Science)，2012，33(10):1381-1384.)

SSA:一种面向CQF模型的TSN资源调度算法

SSA:CQF-oriented Scheduling Algorithm in Time-Sensitive Networking

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	姚巍，赵海，朱剑，陈香伊. 基于traceroute的多特征子网发现与分析[J]. 东北大学学报:自然科学版, 2020, 41(8): 1075-1082.
[2]	何璇，王卢阳，赵海，刘晓. 地震数据关系网络的空间尺度[J]. 东北大学学报:自然科学版, 2018, 39(10): 1385-1389.
[3]	沙毅，范倩雯，张立立，朱丽春. 自校正模糊PID控制的FAST节点位移控制方法[J]. 东北大学学报:自然科学版, 2018, 39(4): 487-491.
[4]	徐久强，赵楠，何璇，赵海. 基于时空影响域地震加权网络的研究[J]. 东北大学学报:自然科学版, 2017, 38(6): 804-808.
[5]	沙毅，陈曦，张立立，朱丽春. 基于ELM神经网络的FAST节点位移预测研究[J]. 东北大学学报:自然科学版, 2017, 38(5): 630-633.
[6]	徐久强，宋佳，何璇，赵海. 基于OFC的仿真地震序列网络化特征对比分析[J]. 东北大学学报:自然科学版, 2017, 38(2): 205-209.
[7]	沙毅，郭自强，朱丽春，张志伟. 一种基于地理位置预测的高性能路由算法[J]. 东北大学学报:自然科学版, 2015, 36(9): 1242-1245.
[8]	沙毅，吕飞，方晶晶，朱丽春. 一种链路稳定性预测的分层路由协议[J]. 东北大学学报:自然科学版, 2015, 36(3): 354-358.