一种应用于TSN网络的冗余流调度方法

摘要

本发明公开了一种应用于TSN网络的冗余流调度方法，包括：确定TSN网络拓扑；确定待调度流的集合；初始化调度表参数；对已有路由集合进行排序；按顺序调度路由集合中每条端到端路由。本发明在调度冗余流时：将超周期被划分为若干个时间片，每个时间片的长度刚好能够容纳一个最小数据帧，调度以时间片为最细粒度进行，以提高调度计算效率；优先调度长路由，当短路由与长路由发生交叠时，允许在一定时间范围内延迟短路由的时间段来复用长路由已经分配好的时间片，以提高时间资源利用率。

权利要求

1.一种应用于TSN网络的冗余流调度方法，其特征在于，包括以下步骤：S1、构造TSN网络拓扑G＝(V,E)，其中，G表示有向图，V表示顶点集，E表示边集；

S2、确定待调度流的集合F；

S3、初始化调度表参数；

S4、对已有路由集合P进行排序；

S5、按顺序调度路由集合P中每条端到端路由；所述调度包括以下步骤：a、在发送端口所对应的调度表上分配一个时间段，该时间段用于发送流；

b、令全局时间偏移量 表示流fk的第l条路由 在有向边(vi,vj)占据的第一个时间段的上界，其均相对于0偏移，单位ns；全局时间偏移量是调度的决策变量；

c、令局部时间偏移量 表示全局时间偏移量 在有向边(vi,vj)的相对时间偏移量，其偏移范围为[0,H)，单位ns， 转换到 的计算公式为：其中，H表示超周期长度；调度时必须遵循异流互斥约束、同流异序互斥约束、存储转发约束和端到端延迟约束；

所述异流互斥约束为：为流分配时间片时，必须保证属于不同的流的时间段在超周期中不能够发生重叠，不同的流在超周期中出现的次数不同，必须保证为其分配的时间段都不能够与其他的流发生交叠；

所述同流异序互斥约束为：流在同一个发送端口占据的时间段不允许随意与自身副本发生重叠，只有在流副本之间的全局时间偏移量之差不超过超周期长度H的情况下才允许重叠发生；

所述存储转发约束为：令(vx,vy)和(vy,vz)表示两条邻接的有向边，则 与 必须满足以下不等式：

其中， 表示流fk的第l条路由 在有向边(vx,vy)占据的第一个时间段的上界；

表示流fk的第l条路由 在有向边(vy,vz)占据的第一个时间段的上界； 表示流fk在有向边(vx,vy)的传输时延；

所述端到端延迟约束为：经过调度后，流抵达终点的时间必须小于其端到端延迟上界，令(vm,vn)表示 的最后一条有向边，流的端到端延迟必须满足以下不等式：其中， 表示流fk的第l条路由 在有向边(vm,vn)占据的第一个时间段的上界；

表示流fk在有向边(vm,vn)的传输时延； 表示流fk在有向边(vm,vn)的传播时延；

表示流fk在有向边(vm,vn)的处理时延， 表示流fk的传输周期， 表示正整数集合， 表示流fk的端到端延迟上界；

d、全局时间偏移量 的取值遵循尽早分配‑尽量复用的策略，其初始值计算公式为：ES RS

其中，ok∈V 表示流fk的源点，即流的发起者，V 表示交换设备组成的集合，有向边表示有向边(vi,vj)的上一跳；若有向边(vi,vj)是路由的起始边，则其中， 表示流fk的第l条路由 在有向边 占据的第一个时间段的上界；

表示流fk在有向边 的传输时延； 表示流fk在有向边 的传播时延； 表示流fk在有向边 的处理时延；

尽早分配‑尽量复用策略为：

判断调度表中是否存在其他属于同一条流的全局时间偏移量，且该偏移量与当前值之差不超过H；

如果存在，则选择距离当前值最近的全局时间偏移量，复用其时间段，不执行任何时间段分配操作；

否则，判断 的初始值是否能够满足异流互斥约束、同流异序互斥约束和端到端延迟约束；如果全部满足，则在当前位置分配时间段，更新调度表；如果不全部满足，分为以下几种情况：

(1)不满足端到端延迟约束，则表示调度失败，结束本次调度；

(2)满足端到端延迟约束，但是不满足异流互斥约束或同流异序互斥约束，则 的值累加一个时间片的长度L，则重新执行步骤d，直到调度成功，否则表示调度失败，结束本次调度。

2.根据权利要求1所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述构造TSN网络拓扑，具体包括以下步骤：ES

S101、令顶点vi∈V表示网络中的网络设备，网络设备分为终端设备和交换设备，令VRS ES RS

表示终端设备组成的集合，V 表示交换设备组成的集合，V＝V ∪V ，令有向边(vi,vj)∈E表示网络设备vi连接网络设备vj的发送端口；

S102、对于每个有向边(vi,vj)∈E，确认有向边的属性。

3.根据权利要求2所述一种应用于TSN网络的冗余流调度方法，其特征在于，步骤S102所述有向边的属性由一个三元组描述，记为 其中，表示有向边(i,j)的带宽，即有向边(vi,vj)所代表的网络设备vi上相应发送端口的数据率； 表示有向边(vi,vj)的传播时延，即数据包从网络设备vi传播到网络设备vj所花费的时间，其取值取决于链路传输介质， 表示有向边(vi,vj)的处理时延，即网络设备vj处理网络设备vi发送过来的包所花费的时间， 表示正整数集合。

4.根据权利要求1所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述步骤S2具体为：

S201、对于每个流fk∈F，确定每个流的属性；所述每个流的属性由一个五元组描述，记k ES

为fk＝{ok,D ,ck,sk,τk}，其中，ok∈V 表示流fk的源点，即流的发起者； 表示流fk的终点的集合，即流的接收者的集合， 表示流fk的传输周期，单位为ns； 表示流fk的大小，即流在每个周期所承载的数据量，单位为B； 表示流fk的端到端延迟上界，单位为ns，调度时必须保证流在任意源点/终点对之间的延迟不超过设定的阈值，否则认为调度失败；

每个流的源点和终点都处在同一个组播组内，不同的流之间使用不同的组播组隔离，故需要为每个流配置一个组播地址，每个交换设备也必须维护组播地址表；

S202、确定所有流的端到端路由集合P令 表示流fk的第m个终点，则任意 表示第l条连通源点ok和终点 的路径，其中， 是边集E的子集，记为 ok和 称为流fk的一个源点/终点对；

流的任意源点/终点对之间存在多条路径，这些冗余路径是完全独立的，或者复用部分链路；同一个源点/终点对的冗余路不允许完全重叠；冗余路由产生的方式是：人为手动指定、K最短路径算法、以及其他已有冗余路由计算方法；

S203、所有交换设备发送端口设置重复数据帧消除点。

5.根据权利要求4所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述步骤S3具体为：

S301、计算超周期长度H

所述超周期是一段连续的时间，单位为ns，超周期的计算公式为：H＝lcm(C)

其中，C＝{ci,j|(vi,vj)∈E}表示所有流的传输周期的集合，lcm(C)则表示求其最小公倍数，任意发送端口(vi,vj)都维持着一个调度表，其表示的时间范围为[0,H)，调度表记录任意流fk在发送端口(vi,vj)上的发送时间点和发送持续时间，发送时间点是超周期中的相对偏移量，故该偏移量的范围为[0,H)，发送持续时间是一段连续的时间，只有在该时间段内流才允许被发送，其长度必须不大于超周期长度；任意流fk在发送端口(vi,vj)的传输时延是一段连续的时间，其计算公式为：S302、计算时间片长度L

所述时间片是调度的基本单元，单位为ns，时间片能够刚好容纳一个最小数据帧的长度，其值等于一个二层网络最小传输单元再加上物理层额外开销，考虑到不同的发送端口具有不同的数据率，时间片大小的计算公式为：L＝U/max(B)

其中，U表示二层网络最小传输单元加上物理层额外开销所需的数据量，单位为B；B＝{bi,j|(vi,vj)∈E}表示所有链路带宽的集合，max(B)则表示从中取最大值。

6.根据权利要求5所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述调度表的参考IEEE 802.1Qbv标准中的门控机制，具体实现为：(1)只有最高优先级的队列用于缓存流；

(2)最高优先级队列的传输门保持为开启状态时，开启的时长等价于流的发送持续时间，其他队列的传输门保持关闭状态。

7.根据权利要求6所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述步骤S4具体为：

S401、计算路由集合P中所有路由的跳数；

S402、把路由集合P中的所有路由放入优先级队列Q，优先级为：跳数多>条数少。

8.根据权利要求7所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述步骤S5具体为：

S501、取出优先级队列Q的队首元素 即当前跳数最多的路由；

S502、按照距离源点sk从近到远的顺序，调度 中的每一条有向边，并更新其调度表；

S503、如果优先级队列Q不为空，则返回步骤S501，否则结束调度。

9.根据权利要求8所述一种应用于TSN网络的冗余流调度方法，其特征在于，所述时间段分配为：在调度表中把范围为 的连续的时间分配给流使用，即在该时间范围内保持发送端口(vi,vj)的最高优先级队列的传输门为开启状态，其中， 表示时间段副本序号，取值范围为 考虑到时间段在超周期尾部可能发生溢出，假设 所表示的时间段在超周期末尾发生溢出，α′表示在超周期末尾发生溢出的时间段，则将刻时间段截断成两部分，分别为： 和

基中，H mod L表示位于超周期末尾长度不足L的碎片的长度，为保证流的完整性不会在此处遭到破坏，该碎片不参与时间段分配，该碎片所对应的时间段内始终保持开启最高优先级队列传输门的状态，其他队列的传输门保持关闭状态。

说明书

一种应用于TSN网络的冗余流调度方法

技术领域

[0001] 本发明涉及TSN网络调度的研究领域，特别涉及一种应用于TSN网络的冗余流调度方法。

背景技术

[0002] 流(Stream)是TSN(Time Sensitive Networking)标准中的核心抽象。TSN标准对流的定义是一种从单源点到多终点的单向数据流，它的每周期最大数据发送长度和周期长
度是固定的。每个TSN流都是用独一无二的流ID索引，它是一个64位的非负整数，其中高48
位是源点的MAC地址，低16位是一个独一无二的无符号整数。流能够承载一个或多个TSN数
据帧。

[0003] 时间是TSN网络的核心概念。传统以太网网络设备没有时间的概念，可靠地交付数据比在特定时间内交付更重要，因此对延迟或同步精度没有限制。但是，即使平均跳跃延迟
非常低，网络抖动也可能使得个别延迟非常的高。网络拥塞是通过在传输层限制和重传丢
弃的数据包来处理的，但是没有办法防止链路层的拥塞。TSN标准是一系列技术标准的集
合，其中关于多网络设备时间同步和定时的技术规范由IEEE 802.1AS标准定义。

[0004] 一些实时以太网实现采用优先级和VLAN标记来分离实时流量和尽力而为的流量。TSN标准对实时流量类做了进一步区分，分为适用于软实时应用的音视频桥接(Audio‑
Video‑Bridging，AVB)类型和适用于硬实时应用的控制数据流量(Control Data Traffic，
CDT)类型。前者在IEEE 802.1Qav标准中定义，后者在IEEE 802.1Qbv标准中定义，本发明只
关注后者的调度。CDT流量采用时分多址的概念，通过全局预配置的传输调度为每个流建立
特定时间段的虚拟通信信道，将CDT业务与非CDT业务分离。确定性调度可以实现流在终端
之间的无竞争传输，从而实现确定性的端到端延迟，即零抖动。CDT流量与非CDT流量分离是
通过IEEE 802.1Qbv标准中定义的门控机制实现的。如图1所示，TSN网络工作在全双工模
式，每个TSN交换机的物理端口逻辑上可以分为接收端口和发送端口。每个TSN交换机的物
理端口逻辑又分为最多8个发送队列，分别对应8个由低到高的优先级。所有发送队列都配
置了传输门，并交给门控列表控制。门控列表决定每个队列的传输门所开启的时间和保持
开启状态的时长，它需要预先配置。在任意时刻，只有传输门是打开状态且优先级最高的发
送队列中的数据帧允许被发送。

[0005] 冗余流技术在流的源点和终点之间建立多条传输路径，能够显著提高流的端到端可靠性。然而，在冗余流存在的网络中，携带大量重复数据包的冗余流会使网络不堪重负，
导致低吞吐量和链路瓶颈的出现。IEEE 802.1CB标准中定义的重复数据帧消除技术可以用
来缓解这种现象。所述重复数据帧消除为：当有多个相同数据帧从不同的端口进入同一个
交换机，并从相同的端口发送时，只有一个数据帧会被发送了，其余重复的数据帧会被丢
弃，从而防止的链路传输多个相同的数据帧。另一方面，流工作在组播模式，该特性使得流
的冗余路由往往呈现复杂的网状拓扑，其中不可避免地存在环路。把冗余路由成约束成有
向无环图可以避免环路问题，代价是提高了计算路由的难度。数据帧消除技术可以防止数
据帧在环路中旋转，因此可以允许冗余路由存在环路，降低计算路由的难度。路由的计算不
在本发明讨论范围内，但是计算存在冗余路由的流调度方案时需要考虑重复数据帧消除的
情况。

[0006] 即使引入重复数据帧消除技术，在冗余路由存在的环境下执行确定性调度仍然存在独特的长短路问题(Long‑Short Paths Problem)。如图2所示，两个相同的流以相反的方
向从源点出发，最终合流到与终点邻接的汇聚节点。假设流经过每一跳所花费的时间相同。
在正常情况下，如果汇聚节点发送端口处不对两个副本执行同步，长路径上的副本到达汇
聚节点的时间必然晚于短路径上的相同副本。汇聚节点丢弃具有相同序列号的帧，即丢弃
从长路径接收到的重复帧。长路径上的副本只有在短路径发生故障的情况下才会被发送。
考虑到长路径和短路径上的重复数据到达时间不同，汇聚节点的发送端口必须对每一个副
本都建立虚拟通信信道，即预留时间资源。由于重复数据帧消除机制的存在，这两个虚拟通
信信道总有一个处于空闲状态，造成多一倍的带宽资源浪费。

[0007] 整数规划方法被广泛用于求解最优的流调度方案。然而，流调度问题是NP难的，这类方法的扩展性不佳，难以向大的实例扩展。禁忌搜索、贪婪随机自适应搜索算法等元启发
式在流调度问题中也有所应用，通过牺牲解质量来取得较好的计算效率。以上传统的流调
度方案服务于端到端路由仅存在单路径的场景，在兼容冗余流时往往效率十分低下。这类
方法在求解冗余流调度问题时，必须将一条冗余流拆分成多条端到端单路径子流，针对子
流集合进行求解，进而引发长短路问题。

发明内容

[0008] 为了解决上述问题，本发明能够提供一种应用于TSN网络的冗余流调度方法。

[0009] 本发明至少通过如下技术方案之一实现。

[0010] 一种应用于TSN网络的冗余流调度方法，包括以下步骤：

[0011] S1、构造TSN网络拓扑G＝(V，E)，其中，G表示有向图，V表示顶点集，E表示边集；

[0012] S2、确定待调度流的集合F；

[0013] S3、初始化调度表参数；

[0014] S4、对已有路由集合P进行排序；

[0015] S5、按顺序调度路由集合P中每条端到端路由。

[0016] 优选的，所述构造TSN网络拓扑，具体包括以下步骤：

[0017] S101、令顶点vi∈V表示网络中的网络设备，网络设备分为终端设备和交换设备，ES RS ES RS
令V 表示终端设备组成的集合，V 表示交换设备组成的集合，V＝V ∪V ，

[0018] 令有向边(vi，vj)∈E表示网络设备vi连接网络设备vj的发送端口；

[0019] S102、对于每个有向边(vi，vj)∈E，确认有向边的属性。

[0020] 优选的，步骤S102所述有向边的属性由一个三元组描述，记为其中， 表示有向边(i，j)的带宽，即有向边(vi，vj)所代表的
网络设备vi上相应发送端口的数据率； 表示有向边(vi，vj)的传播时延，即数据
包从网络设备vi传播到网络设备vj所花费的时间，其取值取决于链路传输介质，
表示有向边(vi，vj)的处理时延，即网络设备vj处理网络设备
vi发送过来的包所花费的时间， 表示正整数集合。

[0021] 优选的，所述步骤S2具体为：

[0022] S201、对于每个流fk∈F，确定每个流的属性；所述每个流的属性由一个五元组描k ES
述，记为fk＝{ok，D ，ck，sk，τk}，其中，ok∈N 表示流fk的源点，即流的发起者； 表
示流fk的终点的集合，即流的接收者的集合， 表示流fk的传输周
期，单位为ns； 表示流fk的大小，即流在每个周期所承载的数据量，单位为B；
表示流fk的端到端延迟上界，单位为ns，调度时必须保证流在任意源点/终点对之
间的延迟不超过该阈值，否则认为调度失败；

[0023] 每个流的源点和终点都处在同一个组播组内，不同的流之间使用不同的组播组隔离，故需要为每个流配置一个组播地址，每个交换设备也必须维护组播地址表；

[0024] S202、确定所有流的端到端路由集合P

[0025] 令 表示流fk的第m个终点，则任意 表示第l条连通源点ok和终点的路径，其中， 是边集E的子集，记为 ok和
称为流fk的一个源点/终点对；

[0026] 流的任意源点/终点对之间存在多条路径，这些冗余路径是完全独立的，或者复用部分链路；同一个源点/终点对的冗余路不允许完全重叠；冗余路由产生的方式是：人为手
动指定、K最短路径算法、以及其他已有冗余路由计算方法。

[0027] S203、所有交换设备发送端口设置重复数据帧消除点。

[0028] 优选的，所述步骤S3具体为：

[0029] S301、计算超周期长度H

[0030] 所述超周期是一段连续的时间，单位为ns，超周期的计算公式为：

[0031] H＝lcm(C)

[0032] 其中，C＝{ci，j|(vi，vj)∈E}表示所有流的传输周期的集合，lcm(C)则表示求其最小公倍数，任意发送端口(vi，vj)都维持着一个调度表，其表示的时间范围为[0，H)，调度表
记录任意流fk在发送端口(vi，vj)上的发送时间点和发送持续时间，发送时间点是超周期中
的相对偏移量，故该偏移量的范围为[0，H)，发送持续时间是一段连续的时间，只有在该时
间段内流才允许被发送，其长度必须不大于超周期长度；任意流fk在发送端口(vi，vj)的传
输时延是一段连续的时间，其计算公式为：

[0033]

[0034] S302、计算时间片长度L

[0035] 所述时间片是调度的基本单元，单位为ns，时间片能够刚好容纳一个最小数据帧的长度，其值等于一个二层网络最小传输单元再加上物理层额外开销，考虑到不同的发送
端口具有不同的数据率，时间片大小的计算公式为：

[0036] L＝U/max(B)

[0037] 其中，U表示二层网络最小传输单元加上物理层额外开销所需的数据量，单位为B；B＝{bi，j|(vi，vj)∈E}表示所有链路带宽的集合，max(B)则表示从中取最大值。

[0038] 优选的，所述调度表的参考IEEE 802.1Qbv标准中的门控机制，具体实现为：

[0039] (1)只有最高优先级的队列用于缓存流；

[0040] (2)最高优先级队列的传输门保持为开启状态时，开启的时长等价于流的发送持续时间，其他队列的传输门保持关闭状态。

[0041] 优选的，所述步骤S4具体为：

[0042] S401、计算路由集合P中所有路由的跳数；

[0043] S402、把路由集合P中的所有路由放入优先级队列Q，优先级为：跳数多＞条数少。

[0044] 优选的，所述步骤S5具体为：

[0045] S501、取出优先级队列Q的队首元素 即当前跳数最多的路由；

[0046] S502、按照距离源点sk从近到远的顺序，调度 中的每一条有向边，并更新其调度表；

[0047] S503、如果优先级队列Q不为空，则返回步骤S501，否则结束调度。

[0048] 优选的，步骤S502所述调度包括以下步骤：

[0049] a、在发送端口所对应的调度表上分配一个时间段，该时间段用于发送流；

[0050] b、令全局时间偏移量 表示流fk的第l条路由 在有向边(vi，vj)占据的第一个时间段的上界，其均相对于0偏移，单位ns；全局时间偏移量是调度的决策变量；

[0051] c、令局部时间偏移量 表示全局时间偏移量 在有向边(vi，vj)的相对时间偏移量，其偏移范围为[0，H)，单位ns， 转换到 的计算公式为：

[0052]

[0053] 调度时必须遵循异流互斥约束、同流异序互斥约束、存储转发约束和端到端延迟约束；

[0054] 所述异流互斥约束为：为流分配时间片时，必须保证属于不同的流的时间段在超周期中不能够发生重叠，不同的流在超周期中出现的次数不同，必须保证为其分配的时间
段都不能够与其他的流发生交叠；

[0055] 所述同流异序互斥约束为：流在同一个发送端口占据的时间段不允许随意与自身副本发生重叠。只有在流副本之间的全局时间偏移量之差不超过超周期长度H的情况下才
允许重叠发生；

[0056] 所述存储转发约束为：令(vx，vy)和(vy，vz)表示两条邻接的有向边，则 与必须满足以下不等式：

[0057]

[0058] 其中， 表示流fk的第l条路由 在有向边(vx，vy)占据的第一个时间段的上界； 表示流fk的第l条路由 在有向边(vy，vz)占据的第一个时间段的上界； 表
示流fk在有向边(vx，vy)的传输时延；

[0059] 所述端到端延迟约束为：经过调度后，流抵达终点的时间必须小于其端到端延迟上界，令(vm，vn)表示 的最后一条有向边，流的端到端延迟必须满足以下不等式：

[0060]

[0061] 其中， 表示流fk的第l条路由p产在有向边(vm，vn)占据的第一个时间段的上界； 表示流fk在有向边(vm，vn)的传输时延； 表示流fk在有向边(vm，vn)的传播时
延； 表示流fk在有向边(vm，vn)的处理时延；

[0062] d、全局时间偏移量 的取值遵循尽早分配‑尽量复用的策略，其初始值计算公式为：

[0063]

[0064] 其中，有向边 表示有向边(vi，vj)的上一跳。若有向边(vi，vj)是路由的起始边，则

[0065] 其中， 表示流fk的第l条路由 在有向边 占据的第一个时间段的上界； 表示流fk在有向边 的传输时延； 表示流fk在有向边 的传播
时延； 表示流fk在有向边 的处理时延；

[0066] 所述尽早分配‑尽量复用策略为：

[0067] 判断调度表中是否存在其他属于同一条流的全局时间偏移量，且该偏移量与当前值之差不超过H；

[0068] 如果存在，则选择距离当前值最近的全局时间偏移量，复用其时间段，不执行任何时间段分配操作；

[0069] 否则，判断 的初始值是否能够满足异流互斥约束、同流异序互斥约束和端到端延迟约束；如果全部满足，则在当前位置分配时间段，更新调度表；如果不全部满足，分为
以下几种情况：

[0070] (1)不满足端到端延迟约束，则表示调度失败，结束本次调度；

[0071] (2)满足端到端延迟约束，但是不满足异流互斥约束或同流异序互斥约束，则的值累加一个时间片的长度L，则重新执行步骤d，直到调度成功，否则表示调度失败，结束
本次调度。

[0072] 优选的，所述时间段分配为：在调度表中把范围为的连续的时间分配给流使用，即在该时间范围内保持发送端口(vi，vj)的最
高优先级队列的传输门为开启状态，其中， 表示时间段副本序号，取值范围为
考虑到时间段在超周期尾部可能发生溢出，假设
所表示的时间段在超周期末尾发生溢出，α′表
示在超周期末尾发生溢出的时间段，则将该时间段截断成两部分，分别为：
和
其中，HmodL表示位于超周期末尾长度不足L的碎片的长度，为保证流的完整性不会在此处
遭到破坏，该碎片不参与时间段分配，该碎片所对应的时间段内始终保持开启最高优先级
队列传输门的状态，其他队列的传输门保持关闭状态。

[0073] 本发明与现有技术相比，具有如下优点和有益效果：

[0074] 本发明提出一种TSN网络流调度方法，能够优化冗余路由引起的长短路问题。为了提高计算效率，超周期被划分为若干个时间片，每个时间片的长度刚好能够容纳一个最小
数据帧，调度以时间片为最细粒度进行。为优化长短路问题，优先调度长路由，当短路由与
长路由发生交叠时，可以延迟短路由的时间段来复用长路由已经分配好的时间片。

附图说明

[0075] 图1是TSN交换机工作原理的示意图；

[0076] 图2是长短路问题说明的示意图；

[0077] 图3是本发明所述一种应用于TSN网络的冗余流调度方法的方法流程图；

[0078] 图4是实施例调度过程的示意图；

[0079] 图5是实施例调度结果的甘特图。

[0080] 具体实施方法

[0081] 下面结合实施例及各个附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

[0082] 如图3、图4所示的一种应用于TSN网络的冗余流调度方法，包括以下步骤：

[0083] 第一步、确定TSN网络拓扑G＝(V，E)。

[0084] S101、对于每个网络设备vi∈V，确认其归属于终端设备集合VES，或者是交换设备RS
集合V 。

[0085] 确认终端设备v1、v2和v6属于终端设备集合VES；确认终端设备v3、v4和v5属于交换设ES
备集合V 。

[0086] S102、对于每个有向边(vi，vj)∈E，确认其属性。

[0087] 确认有向边(v1，v3)、(v2，v4)、(v3，v4)、(v3，v5)、(v4，v5)、(v5，v6)均可表示为三元组{100Mbps，0ns，0ns}。所有链路带宽均为100Mbps，传播时延和处理时延均忽略不计。

[0088] 第二步、确定待调度流的集合F。

[0089] S201、对于每个流fk∈F，确定其属性。

[0090] 确认流f1的源点是v1，终点是v3，传输周期是1s，大小是25Mb，端到端延迟上界是10ms，记为f1＝(v1，{v3}，1s，25Mb，10ms)；确认流f2的源点是v2，终点是v3，传输周期是1s，大
小是25Mb，端到端延迟上界是10ms，记为f2＝(v2，{v3}，1s，25Mb，10ms)；确认流f3的源点是
v6，终点是v1和v2，传输周期是1s，大小是25Mb，端到端延迟上界是10ms，记为f3＝(v6，{v1，
v2}，1s，25Mb，10ms)。

[0091] S202、确定所有流的端到端路由集合P。

[0092] 产生冗余路由的方式有：人为手动指定，K最短路径算法，以及其他已有冗余路由计算方法等。本实施例中所有流的路由均采用人为手动指定方式。

[0093] 流f1的源点是v1，终点是v3，其冗余路由有：

[0094]

[0095]

[0096] 流f2的源点是v2，终点是v3，其冗余路由有：

[0097]

[0098]

[0099] 流f3的源点是v6，终点是v1和v2，其冗余路由有：

[0100]

[0101]

[0102]

[0103]

[0104] 最终，路由集合

[0105] S203、设置重复数据帧消除点。

[0106] 为所有交换设备发送端口设置数据帧消除点，具体的位置在内部中继模块之后，在发送队列之前。

[0107] 第三步、初始化调度表参数。

[0108] S301、计算超周期长度H。

[0109] 超周期的计算公式为：

[0110] H＝lcm(C)

[0111] 其中，C＝{ci，j|(vi，vj)∈E}表示所有流的传输周期的集合，lcm(C)则表示求其最小公倍数。

[0112] 本实施例中，所有流的传输周期均为1s，故H＝1s。进而，所有发送端口上的调度表所表示时间范围为[0，1s)。

[0113] S302、计算时间片长度L。

[0114] 时间片大小的计算公式为：

[0115] L＝U/max(B)

[0116] 其中，U表示二层网络最小传输单元加上物理层额外开销所需的数据量，单位为B；B＝{bi，j|(vi，vj)∈E}表示所有链路带宽的集合，max(B)则表示从中取最大值。

[0117] 本实施例中，U＝125B，所有链路的带宽均为100Mbps，故L＝10μs。

[0118] 第四步、对已有路由集合P进行排序。

[0119] S401、计算路由集合P中所有路由的跳数。

[0120] S402、把路由集合P中的所有路由放入优先级队列Q，优先级为：跳数多＞条数少。

[0121] 排序后的得到的优先级队列

[0122] 第五步、按顺序调路由集合P中的每条端到端路由。

[0123] S501、取出优先级队列Q的队首元素 即当前跳数最多的路由。

[0124] 本实施例中，第一轮迭代取出

[0125] S502、按照距离源点sk从近到远的顺序，调度 中的每一条有向边，并更新其调度表，具体包括以下步骤：

[0126] S1、从 取出有向边(v1，v3)，初始化全局时间偏移量 进而，计算得到其局部时间偏移量 有向边(v1，v3)上的调度表为空，无可复用时间段，故继续采
用尽早分配‑尽量复用策略分配时间段。 同时满足异流互斥约束、同流异序互斥
约束和端到端延迟约束，故直接在此处分配时间段。流f1在发送端口(v1，v3)的传输时延
由于超周期H＝1s，流f1的时间段在超周期中只出
现一次，故所分配时间片范围为[0，0.25s)。

[0127] S2、从 取出有向边(v3，v4)，初始化全局时间偏移量进而，计算得到其局部时间偏
移量 有向边(v3，v4)上的调度表为空，无可复用时间段，
故继续采用尽早分配‑尽量复用策略分配时间段。 同时满足异流互斥约束、
同流异序互斥约束和端到端延迟约束，故直接在此处分配时间段。流f1在发送端口(v3，v4)
的传输时延 由于超周期H＝1s，流f1的时间段在超
周期中只出现一次，故所分配时间片范围为[0.25s，0.5s)。

[0128] S3、从 取出有向边(v4，v5)，初始化全局时间偏移量进而，计算得到其局部时
间偏移量 有向边(v4，v5)上的调度表为空，无可复用时
间段，故继续采用尽早分配‑尽量复用策略分配时间段。 司时满足异流互斥
约束、同流异序互斥约束和端到端延迟约束，故直接在此处分配时间段。流f1在发送端口
(v3，v4)的传输时延 由于超周期H＝1s，流f1的时间
段在超周期中只出现一次，故所分配时间片范围为[0.5s，0.75s)。

[0129] S4、从 取出有向边(v5，v6)，初始化全局时间偏移量进而，计算得到其局部时
间偏移量 有向边(v5，v6)上的调度表为空，无可复用时
间段，故继续采用尽早分配‑尽量复用策略分配时间段。 司时满足异流互斥
约束、同流异序互斥约束和端到端延迟约束，故直接在此处分配时间段。流f1在发送端口
(v3，v4)的传输时延 由于超周期H＝1s，流f1的时间
段在超周期中只出现一次，故所分配时间片范围为[0.75s，1s)。

[0130] S503，如果优先级队列Q不为空，则返回步骤S501，否则结束调度。

[0131] 以 为例再次阐述完整的一轮迭代过程。同理可类推其余轮次。最终完整的调度结果如图5中所示，横轴表示时间，纵轴表示有向边，具体
包括以下步骤：

[0132] 1、从 取出有向边(v1，v3)，初始化全局时间偏移量 进而，计算得到其局部时间偏移量 有向边(v1，v3)上的调度表不为空，存在已分配时间段[0，
0.25s)。 分配的时间段的局部时间偏移量等于 故 可直接复用 分配的时间段
[0，0.25s)。

[0133] 2、从 取出有向边(v3，v5)，初始化全局时间偏移量进而，计算得到其局部时间偏移量
有向边(v3，v5)上的调度表为空，无可复用时间段，故继
续采用尽早分配‑尽量复用策略分配时间段。 同时满足异流互斥约束、同流
异序互斥约束和端到端延迟约束，故直接在此处分配时间段。流f1在发送端口(v3，v5)的传
输时延 由于超周期H＝1s，流f1的时间段在超周期
中只出现一次，故所分配时间片范围为[0.25s，0.5s)。

[0134] 3、从 取出有向边(v5，v6)，初始化全局时间偏移量进而，计算得到其局部时间偏移量
有向边(v1，v3)上的调度表不为空，存在已分配时间段
[0，0.75s)。 分配的时间段的局部时间偏移量与 之差为0.25s，不大于超周期长度H
＝1s，故 可直接复用 分配的时间段[0，0.75s)。

[0135] 上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，
均应为等效的置换方式，都包含在本发明的保护范围之内。