没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
2020 年 11 月 Journal on Communications November 2020
第 41 卷第 11 期 通 信 学 报 Vol.41
No.11
面向大规模时间敏感网络的分组调度机制
邱雪松
1
,黄徐川
1
,李文萃
2
,李温静
3
,郭少勇
1
(1. 北京邮电大学网络与交换技术国家重点实验室,北京 100876;2. 国网河南省电力公司信息通信公司,河南 郑州 450052;
3. 国网信息通信产业集团有限公司,北京 102211)
摘 要:针对大规模时间敏感网络中时间触发流量的确定性时延问题,提出了一种分组调度机制。所提机制通过
拓扑修剪策略和基于谱聚类的流分组策略,避免了由于网络拓扑规模和流量规模剧增对调度响应速度的影响,提
升了调度计算效率。仿真实验结果表明,所提机制在大规模调度的场景下,可以在较短时间内进行模型的求解,
并且保证一定的调度成功率。
关键词:时间敏感网络;时间触发流量;拓扑修剪;谱聚类
中图分类号:TP393
文献标识码:A
doi: 10.11959/j.issn.1000−436x.2020203
Group-scheduling mechanism for large-scale
time-sensitive network
QIU Xuesong
1
, HUANG Xuchuan
1
, LI Wencui
2
, LI Wenjing
3
, GUO Shaoyong
1
1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2. Information & Telecommunication Company of State Grid Henan Electric Power Company, Zhengzhou 450052, China
3. State Grid Information and Telecommunication Group Company Limited, Beijing 102211, China
Abstract: In order to achieve the deterministic delay of time-triggered traffic in a large-scale time-sensitive network, a
kind of group-scheduling mechanism was proposed. By designing a topology pruning strategy and a flow grouping strat-
egy based on spectral clustering, the impact of the rapid increase in network topology scale and traffic scale on the speed
of scheduling response was avoided, and the scheduling calculation efficiency was improved. The results of experiment
show that the mechanism can solve the model in a relatively short time for large-scale scheduling problem and achieve a
relatively high scheduling success rate.
Key words: time-sensitive network, time-triggered traffic, topology pruning, spectral clustering
1 引言
随着信息技术的飞速发展,在工厂自动化控
制、自动驾驶和电力自动化等领域,对数据流传输
的时延要求超出了传统以太网的可控范围
[1]
。为解
决传统以太网中实时数据的可靠传输问题,IEEE 802
工作组提出了时间敏感网络(TSN, time-sensitive
network)的概念。TSN 支持时间触发流量(TT,
time-triggered traffic)的传输,该类流量具有周期性
传输的特点,并具有确定性的低时延要求。针对 TT
的调度问题出现了大量的研究
[2-10]
。
文献[2]使用可满足性模理论(SMT, satisfia-
bility modulo theory)和优化模理论(OMT, opti-
mization modulo theory)来实现有效调度。文献[3]
基于整数线性规划(ILP, integer linear programming)
计算式生成门控制列表,通过计算全局调度将资源
最佳地分配给时间触发流量。文献[4]提出了一种混
合遗传算法,用于生成时间触发流量的静态调度
收稿日期:2020−06−18;修回日期:2020−09−04
基金项目:国家电网有限公司总部科技基金资助项目(No.5700-202024176A-0-0-00)
Foundation Item: State Grid Corporation of China Science and Technology Project (No.5700-202024176A-0-0-00)
第 11 期 邱雪松等:面向大规模时间敏感网络的分组调度机制 ·125·
表,优化了时隙的分配数量并提高了传输效率。文
献[5]提出了一种基于遗传算法的启发式调度算法,
使用路由和调度的联合约束来生成静态的全局调
度,从而使可调度性、传输效率和资源利用率得到
显著提高。文献[6-7]基于 ILP 提出了针对路由和调
度联合问题的解决方案。文献[6]使用 2 个性能指标
(即端到端时延和调度能力)来评估不同流量模式
和网络拓扑的实验结果。文献[7]利用 ILP 解算器对
参数变化很大的问题实例进行了求解,根据求解时
长对算法的性能进行了评估。文献[8]基于 SMT 提
出了一种联合路由和调度的迭代算法,但是算法性
能对流量之间传输路径的冲突程度敏感,导致成功
率较低。文献[9-10]提出了时间敏感软件定义网络
(TSSDN, time-sensitive software-defined network)的
概念和用于计算调度的 ILP 式,TSSDN 利用逻辑集
中的控制平面来计算全局的调度方案。
上述研究通过不同方法给出了时间触发流量
可行的调度机制,但是在大规模调度场景下的求解
时间难以满足调度需求。为此,本文针对大规模时
间敏感网络中时间触发流量的调度问题进行了研
究,具体包括以下三部分。
1) 建立了分组调度模型,在每一组流量的调度
中,通过时间和空间上将待调度流量分离的时分多
址(TDMA, time division multiple access)思想消除
了排队时延,保证了时延的确定性。
2) 针对网络拓扑规模庞大的问题,设计了一种
拓扑修剪策略。通过减少不必要的约束条件简化调
度模型,减少了调度的求解耗时。
3) 针对流量规模庞大的问题,设计了一种基于
谱聚类的流分组策略。通过分组调度的方式减少调
度求解时间,同时保证较高的成功率。
2 数学模型
2.1 时延分析
时间触发流从源主机到目的主机沿着指定路
径进行周期性传输,其端到端时延包括传播时延、
发送时延、处理时延,当网络中发生拥塞时,还包
括排队时延。时延分析如图 1 所示。
图 1 中,t
i
表示节点 v
i
的发送时刻,d
trans
、d
prop
和 d
proc
分别表示发送时延、传播时延和处理时延。
当发生排队时,排队时延为 d
queu
,D 表示某个节点
和下一节点之间的端到端时延,如式(1)所示。
trans prop proc queu
D
dddd=+++ (1)
图 1 时延分析
当不发生排队时,D 只包含发送时延、传播时延
和处理时延。传播时延由信道长度和介质中信号的传
播速率决定,可以认为具有确定性。交换机内部的处
理时延与其存储转发的能力有关,可以认为具有确定
性。发送时延由帧大小和发送速率决定,也具有确定
性。当网络中发生拥塞时,在交换机内部排队时间无
法确定,导致产生的排队时延具有不确定性。
由于端到端时延的不确定性主要来源于可能
包含的排队时延,因此在设计时间触发流的调度模
型时,需要避免排队情况的出现,从而保证其传输
的确定性。
2.2 调度模型
当多个数据分组试图在交换机的同一个输出
端口进行传输时,会发生排队的情况,若在时间触
发流传输时为其分配特定的链路资源仅供其传输,
就可以消除排队的情况从而保证端到端时延的确
定性。在时间上,可以在一个基本周期内为不同的
时间触发流分配不同的时隙;在空间上,可以为不
同的时间触发流分配不冲突的链路资源。通过这种
在时间和空间上将不同时间触发流分离的时分多
址思想,可以实现每个时间触发流到达交换机时,
始终有一个空状态的队列为其开放,从而避免了排
队情况的出现。
如图 2 所示,一个基本周期被分为多个时隙,
每个时隙从 0~t
max
编号,被分给特定的时间触发流
进行传输,且时隙的长度足够宽,足以使最大传输
单元(MTU, maximum transmission unit)的数据分
组穿过最长的网络路径。
图 2 基本周期的时隙分片
剩余7页未读,继续阅读
资源评论
weixin_38681286
- 粉丝: 1
- 资源: 898
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- shopex升级补丁只针对 485.78660版本升级至485.80603版本 其它版本的请勿使用!
- 基于Django和HTML的新疆地区水稻产量影响因素可视化分析系统(含数据集)
- windows conan2应用构建模板
- 3_base.apk.1
- 基于STM32F103C8T6的4g模块(air724ug)
- 基于Java技术的ASC学业支持中心并行项目开发设计源码
- 基于Java和微信支付的wxmall开源卖票商城设计源码
- 基于Java和前端技术的东软环保公众监督系统设计源码
- 基于Python、HTML、CSS的crawlerdemo软件工程实训爬虫设计源码
- 基于多智能体深度强化学习的边缘协同任务卸载方法设计源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功