用于跟踪具有同步终端站的“时间敏感型联网<TSN>”-网络的多循环流量的计算机实施的方法、计算机实施的工具和控制系统与流程

本发明涉及根据权利要求1的前序的用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络中的多循环流量(multicyclic traffic)的计算机实施的方法、根据权利要求5的前序的用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络中的多循环流量的计算机实施的工具、以及根据权利要求6的前序的用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络的多循环流量的控制系统。

背景技术：

1、作为一种即将出现的技术的“时间敏感型联网<tsn>”被设计用于使基于实时以太网的网络在数据交换方面以具有定义时延的精确方式具有确定性，但是没有任何专有的解决方案，并且指的是与iso/osi模型的第2层相关的一组ieee 802标准并添加了定义以保证以太网网络中的确定性和吞吐量。

2、工业自动化中尤其需要确定性以太网来实现快速、具有确定性和稳健的通信。在作为即将出现的技术的“时间敏感型联网<tsn>”之前，专有解决方案可用于这个目的，诸如“profinet irt”、“sercos iii”和“varan”。

3、实际上，比如工业4.0和工业物联网的工业趋势导致不断增长的融合网络中的网络流量的增加，这需要灵活性和可扩展性来支持小型设备以及大型数据服务器系统，同时确保对于时间关键型通信的有界时延。这些要求将会被为确定性通信和非确定性通信的同时使用提供标准化机制的“时间敏感型联网<tsn>”来涵盖。

4、在“时间敏感型联网<tsn>”通信规划中，有必要获得对于不同类型的流的延迟和干扰的最差情况估计。最终需要这些估计来决定流是否可以被接受，这只有在这样做会保留它们的类别类型的保证属性的情况下才进行。因此，例如，类别“低”的流(顺便说一下，它允许多循环流量)只有在它们尤其满足以下条件的情况下才能被接受：即它们将不会因为交换机中的缓冲区溢出而被丢失，并且对于已经规划的类别“低”的其它流，它们也将不会引起这个情况。

5、新的通信tsn-标准处理具有不同重要性的几类消息，它们在下文中被称为“优先级”并且必须通过以循环方式运行的工业通信网络来发送它们。为了这个目的，当流类别允许多循环流量时，即流的帧不需要在传输它们的循环中到达时，这是特别重要的。

6、在这种情况下，确定不同流的两个帧是否相遇不仅取决于它们通过网络的路径和它们被发送的阶段，而且还取决于帧到达其目的地花费多少个阶段，以及帧可能在不同时间点所处的地方。

7、流类别(这个流将与哪里特别相关)的一个示例是通常与较低优先级相关联的一类周期性流，相应地由类别“低”来表示。这个类别的流(被称为低优先级流)具有零拥塞损失约束，即没有帧可能被丢失，但是它们不被约束在传输它们的循环中到达，并且它们不能抢占(参见下面进一步的[抢占的定义])其它帧的发送。

8、在下面呈现一些关于tsn-通信的基本信息。

9、tsn-通信是以流的形式组织的，其中在流内，沿着所选取的具有一定的周期性的路由(route)来发送固定大小的帧。流的这个周期性是在调度循环中测量的。出于实际原因，这个周期性(在下面它被定义或称为流的减少率“rr(reductionrate)”具有2的幂，“rr＝2n”，其中

10、这意味着在具有“rr＝2”的流内，每隔一个调度循环发送一个帧。对于除了“rr＝1”之外的所有情况，这需要选取将在哪些调度循环中发送流，这被称为流的阶段(phase)“p”。因此，例如，具有减少率r的流，阶段“p”可以在“0,…,r-1”的范围内选取，并且其中p0:＝p＝0,…,pr-1:＝p＝r-1。

11、通常，在“时间敏感型联网<tsn>”-网络中存在多个具有不同属性的流的优先级类别。因此，它被认为是一种设置，在其中网络中的每一个节点为每个流优先级类别维护队列，并且每一个队列在内部以“先进先出<fifo>”方式操作，但是如果存在多于一个非空队列，则处理与最高优先级相关联的队列。如果队列中没有留下足够的存储空间来存储传入的帧，则这个帧会被丢弃，并且对应的消息会丢失。作为这个fifo/优先级概念的结果，“时间敏感型联网<tsn>”-网络中的不发送或接收消息的节点不需要访问同步时间或复杂的流量整形器。

12、通常，除了上述低优先级流之外，还存在高优先级流，其帧也被周期性地发送，但是除了零损失约束之外，它还具有最大时延约束，即，它们必须在它们的发送循环内或者在甚至更短的时间窗口中到达它们的目的地。这些流也可以抢占(参见下面进一步的[抢占的定义])其它流，特别地上述低优先级流。

13、此外，还存在较低优先级流的流量，其本质上可以是随机的，例如不能保证到达的“非实时<nrt>”-流量，即帧可能被丢失。基于类别的流约束总是通过接受过程来保证，这通常是递增的，即tsn-通信网络可以拒绝发送流以维护所有必要的保证。

14、因为“时间敏感型联网<tsn>”是新的标准，所以在操作中几乎还没有既定的实践。然而，在调查文献以确定通常如何处理低优先级流中，大多数策略涉及在各个节点处的流量整形器(参见例如非专利文献：在http://www.cs.unisalzburg.at/～scraciunas/pdf/techreports/craciunas etr17.pdf中craciunas，oliver等人的“对于时间敏感网络的调度机制的概述”)。

15、根据这个文献，所有节点都需要时间信息和同步，而本发明指的是“时间敏感型联网<tsn>”-网络，在其中只有发送或接收消息的节点是同步的，这些节点是tsn-网络的终端站。

16、替代地，要求满足严格的约束以提供所需要的保证是可能的。

17、例如，如果要求所有低优先级帧在发送它们的循环内到达它们的目的地，则可以应用与对于高优先级流相类似的策略。

18、然而，这严重限制了网络的容量，即通过仅发送理论上可能的流量数据数量的一小部分，并且它甚至可以使网络中的一些较长的路由在所有场景中都不可行。因此，因为低容量帧不能抢占(参见下面进一步的[抢占的定义])其它帧的发送，所以最差情况分析需要至少计及“非实时<nrt>”-流量。因此，这应被视为一种短期的变通办法，而不是永久的解决方案。

19、此外，存在几个预先公布的专利申请wo2019/083508a1、wo2019/083509a1、wo2019/083510a1，其通过使用基于循环的干扰模型来处理由考虑关于“时间敏感型联网<tsn>”的高优先级流而引起的优化问题，即阶段分配和发送顺序。

技术实现思路

1、本发明的一个目的是提出一种用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络的多循环流量的计算机实施的方法、计算机实施的工具和控制系统，通过它们来建立和更新“时间敏感型联网<tsn>”内的流帧的可能位置。

2、通过解决这个目的，对应的解决方案为其需求使得一些问题更加复杂得多的不同的流类别供应了缺失的部分。这是朝着解决在“时间敏感型联网<tsn>”-网络内的低优先级和混合流场景中的类似问题的第一步。

3、通过权利要求1的表征部分中的特征来解决关于在权利要求1的前序中定义的计算机实施的方法的这个目的。

4、进一步通过权利要求5的表征部分中的特征来解决关于在权利要求5的前序中定义的计算机实施的工具的该目的。

5、此外，通过权利要求6的表征部分中的特征来解决关于权利要求6的前序中定义的控制系统的该目的。

6、根据权利要求1、5或6的本发明的主要思想是通过将软件方法呈现为一种用来表示信息“什么(例如流帧)在哪个时间可能在什么地方”的紧凑方式以及基于算法的框架或算法框架(参见权利要求3)来在“时间敏感型联网<tsn>”-网络中捕获多循环流量的可能位置，以迭代地且递归地计算相关值(诸如流延迟的边界)，并且因此保证根据定时约束不发送流量，例如流量可能不会由于溢出队列而被丢失，该“时间敏感型联网<tsn>”-网络对于低优先级流或其它类别的多循环流的延迟估计和流接受是必要的，所述低优先级流或其它类别的多循环流每个具有减少率“rr”和固定路径。

7、因为这样做，该方法或框架不依赖于时间同步的中间节点或其它流量整形器来跟踪“时间敏感型联网<tsn>”-网络的多循环流量。因此，无整形器的方法或框架在硬件和软件要求方面更加灵活。

8、因为有可能对框架的算法进行参数化，所以有可能在不同用例所需要的运行时间和解决方案质量之间找到正确的平衡。基于循环的阶段间隔模型与不同的延迟计算模型兼容，并且因此在不同的上下文中可用。

9、此外，因为边界计算是一个迭代过程，所以该方法或框架可以被用在仅一个流被添加到“时间敏感型联网<tsn>”-网络的设置中，也可以被用在多个流被添加到“时间敏感型联网<tsn>”-网络的情况中。

10、下面给出了解决要处理的问题(本发明的目的)并在上文总结的思想的单个方面：

11、1.该方法或框架基于在“时间敏感型联网<tsn>”-网络内建立和更新参与所考虑的通信过程的多循环流的帧的可能位置。这是对于多循环流的接受过程中的一个必要步骤，除非可以通过替代方式来保证约束(参见第3点)。

12、关于这个方法或框架，应该注意为什么多循环流量难以决定帧可以在给定时间所处的地方。对于其帧具有一个循环的一小部分的时延约束的流，能够相互影响的唯一流是处于同一阶段“p”中的那些。因此，在循环的基础上进行队列填充水平和延迟的分析就足够了。需要所分析的延迟来估计在最差的情况下到达“时间敏感型联网<tsn>”-网络的节点花费多久。另一方面，对于多循环流(相应地帧)，如果一个帧使另一个帧延迟了，则任何变化或附加流可以导致连锁反应，然后这会出现在新的阶段“p”中。并且，它继而可以使新流延迟等等。

13、2.根据对于低优先级流的帧的图片1，在“时间敏感型联网<tsn>”-网络内的对应路径上的每一个节点具有以帧被发送的阶段开始的循环间隔，在该循环间隔期间，帧可以出现在输出端口处，例如，对于在阶段“p0:＝p＝0”中发送的帧，路径上的阶段间隔可以看起来像这样：

14、3.基于算法的框架是基于下面这些假设的迭代和递归过程：

15、-对于没有流干扰的“时间敏感型联网<tsn>”-网络，已知桥或边和节点中的最小和最大处理时间(参见图论中使用的术语；因此，图的数据结构是非分层的，其中点被称为节点，链接被称为边并且连接图的桥是图边，桥的移除会断开该图)。

16、-给定的延迟计算模型是有必要的，该给定的延迟计算模型计算由与其它流的干扰引起的上界。这个延迟可以包含恒定份额(其可以是逐节点的和/或全局的)、以及取决于哪些流可以出现在同一节点处的一部分。这可能是对于具有或不具有“抢占”的高优先级帧[在计算中:抢占是暂时中断正在执行的任务，打算在稍后的时间恢复它的行为；以太网；“时间敏感型联网<tsn>”：这项新技术解决了过长的网络消息不适合在一个循环中的问题。简单地解释，它做以下事情:在保护带结束之前停止(抢占)太长消息的传输。]、其它低优先级帧(参见第1点，对于这些帧，如图片1中描绘的已经计算了阶段间隔)、以及具有甚至更低优先级的另外的帧。

17、-由所有流路径引起的基础无向图是非循环的，即，或者“时间敏感型联网<tsn>”-网络自身是非循环的，其中允许沿两个方向延伸的边，或者至少对于流的所有无向固定路径的并集(union)是非循环图。

18、如果使用这样的延迟计算模型，可以以直接的方式计算对于阶段间隔的下界。这里的挑战是上限的确定。因为延迟和阶段间隔相互影响，这意味着阶段间隔的变化可以改变最差情况延迟，并且反之亦然，所以提出了一种迭代递归算法来解决这个问题，该算法可以与不同的延迟计算模型一起使用。

19、在图片2中，举例说明了在给定干扰延迟的情况下如何计算不同交换机处的下限、以及上限。

20、如此，帧“f”通过一个网络节点(交换机1(switch1))在发送节点(sendnode)和交换机2(switch2)之间行进。如果在给定阶段中不存在其它流量，则最早到达时间由电缆延迟和桥延迟的最小值来确定。不失一般性，没有示出处于发送的其它延迟或其它转发延迟。

21、arrivaltime_earliest(@switch1)＝framestarttime+cd1

22、arrivaltime_earliest(@switch2)＝framestarttime+cd1+bdmin{+}cd2

23、在其它流量同时出现在交换机1中，并且与帧“f”共享同一输出端口的情况下，附加的干扰延迟可以由其它帧产生。使可以计算的最差情况干扰延迟是“interfd”，则帧“f”的最晚到达时间为：

24、arrivaltime_latest(@switch2)＝framestarttime+cd1+(bdmax+int erfd){+}cd2

25、“f”的最后一位到达交换机2的时间等于第一位到达它的时间加上帧持续时间“fd”。因此，假定“时间敏感型联网<tsn>”-网络的速度总体上是相同的。从到达时间计算循环间隔是简单明了的。

26、4.阶段间隔的紧凑表示：

27、如果认为“时间敏感型联网<tsn>”-网络对于每一个流和每一个节点来说是随着时间推移的，则对于节点处的流的结果将是一组阶段间隔，其随着时间而增长，因为被发送的每一个帧占用一系列循环，在所述循环期间它可以出现在某个节点处，其中对于每一个流的阶段间隔以周期性的方式出现。

28、因此，需要回答的第一个问题是如何以紧凑的方式表示这些阶段间隔。

29、如果以两个流中没有两个帧可以在同一队列中(即在“时间敏感型联网<tsn>”-网络的同一节点处)的这样的方式使用拒绝策略，则所有tsn-流量在(i)max{rr(s)，其中“s”是tsn-流量接受的一组流“s”，其中s:＝s1,s2,…,sn，其中以及(ii)max{rr(s)，其中s是请求tsn-流量接受的至少一个新流"s"}＝:rrmax之后重复。虽然有可能使该测量适于存在所考虑的rrmax个循环的时间块并记录对于每一个流和节点的一组阶段间隔的情况，但是提出了一种使用更简化且稍微更悲观的测量的算法。

30、对于该组流“s”中的每一个已接受流“sx”，其中x＝(1,2,…,n)，只考虑至多rr(sx)的减少率大小的阶段间隔长度。这意味着，从最差情况的角度来看，在任何rr(sx)个连续循环期间可以发生什么。这可以通过适应对rr(sx)取模的阶段间隔边界来进行。

31、对于每一个新流“s”，只考虑至多rr(s)的减少率大小的阶段间隔长度。这意味着，从最差情况的角度来看，在任何rr(s)个连续循环期间可以发生什么。这可以通过适应对rr(s)取模的阶段间隔边限来进行。

32、以下示例说明了这两种测量之间的差异：

33、使“sx”是在节点“v”处具有减少率“rr(sx)＝4”(以及因此4，8，…)的流，它可以在阶段“p0:＝p＝0”中到达。假定在节点“v”处添加了具有减少率“rr(s)＝8”(以及因此8，16，…)的新流“s”，这可能将流“sx”的帧推送到下一个循环中。现在，如果流“s”在节点“v”处也具有阶段“p0:＝p＝0”，则对于在节点“v”处的流“s”，考虑阶段间隔[0，1]，[4，4]，[8，9]，[12，12]，…将足够了。

34、但是相比之下，所有阶段间隔边界都被投影到[0,rr(s)–1]，并且取在定义对于流“s”的时段的该组rr(s)个循环中的任何一个中可能发生的最差情况来确定对于节点“v”的节点间隔，即，对于流“s”，它是人们感兴趣的阶段间隔集合[0，3]，[4，7]，[8，11]，…，之中的最差循环中的阶段间隔。

35、更一般地，对于流“s”来说，它是人们感兴趣的阶段间隔集合[0+i*rr(s),rr(s)–1+i*rr(s)]之中最差循环中的阶段间隔，其中这同样适合于已接受流“sx”。

36、因此，在这种情况下，假定流“s”在节点“v”处具有阶段间隔[0，1]，以及因此阶段间隔[4，5]，[8，9]，[12，13]。

37、从积极的一方面来看，这意味着对于每一个节点和流，最多需要考虑两个阶段间隔。

38、对于帧，在“时间敏感型联网<tsn>”-网络的节点处存在一个阶段间隔，由于取模计算，该阶段间隔可以被分成两个，即对于流“s”可能存在间隔[0,y]和[z,rr(s)-1]，其中y,z＝(1,2,3,…)，但是没有必要考虑几个帧。

39、为了确保同一流中没有两个帧在同一循环中在“时间敏感型联网<tsn>”-网络的节点处相遇，在进行取模计算之前，需要对流“s”的阶段间隔[a，b]检查拒绝条件“b–a<rr(s)”。如果在某一点处这没有满足，则当前考虑的流被拒绝，但是它将有可能增加减少率“rr”并再次尝试。对于已接受流“sx”，同一拒绝条件是有效的。

40、5.递归算法框架：

41、上述阶段间隔计算可以被包括在用于检查是否可以接受新的低优先级流的递归算法框架中：

42、总体思想是通过遍历与流“s，s”的帧相关的所有循环，迭代地计算阶段间隔和最差情况延迟，它们被用于阶段间隔计算。对于每一个这样的循环，在“时间敏感型联网<tsn>”-网络的所有相关节点处对其进行检查，其中帧可能在当前循环中。这已经通过对于先前循环的计算来确定。对于这些节点，在也考虑先前循环和其它流的情况下，更新延迟。如果这引起另一流的节点阶段间隔的增加，则针对那个流递归地调用同一算法。

43、如先前提及的，阶段间隔计算取决于具有某种基础的延迟计算模型。为了计算阶段间隔，具有简单的延迟模型就足够了，该延迟模型仅使用基于循环的信息来进行计算。

44、根据权利要求3，呈现了用伪代码的“纯递归算法框架”。

45、因此，如下描述递归阶段间隔和/或延迟计算和接受算法：

46、其用伪代码为：

47、假设：

48、·具有节点间隔和计算的延迟的该组流“s”。

49、·新流“s”。

50、·发送流“s”的阶段“p0”。

51、输出：如果新流“s”的接受不允许保证流并集"s"∪"s"的所有必要约束，则新流“s”将在阶段“p0”中被拒绝，因为违反了拒绝条件。否则，输出对于流并集"s"∪"s"的新间隔。

52、主要算法：

53、init("s","s")

54、recompute("s","p0","s")

55、函数定义：

56、init(s,s)

57、利用对于该组流“s”的原始节点间隔，计算新流“s”沿着新流“s”的路径在每一个节点“v”处的最早和最晚到达时间

58、recompute("s","p","s")//外部重新计算框架//

59、f("s","p","s")

60、在新流“s”的最晚到达时间不在具有阶段“p”的循环中时。

61、f("s","p","s")

62、将表格更新到流“s”的减少率rr("s")

63、f("s","p","s")

64、成功＝假

65、当不成功时

66、重新计算＝假

67、对于沿着新流“s”的路径的每一个节点“v”，其中新流“s”可以从开始到结束都处于阶段“p”中！

68、(a)如果在阶段“p”中在节点“v”处已经存在对于新流“s”的账号，则继续到下一个节点"v"

69、(b)如果在节点“v”处新流“s”违反了拒绝条件，则→拒绝

70、如果在阶段“p”中新流“s”的添加导致在节点“v”处缓冲区溢出，则→拒绝

71、对于该组流"s"中的其延迟受到在阶段“p”中在节点“v”处添加新流"s"的影响的每一个流"s’"，

72、根据针对新流"s"的新延迟来更新该流"s’"的间隔。

73、如果这改变了任何节点间隔

74、(c)recompute("s’","p"mod rr("s’"),"s""s’")//即，更新延迟//

75、如果该组流"s"中的任何流"s’"增加了任何间隔则重新计算＝真

76、如果重新计算

77、(d)使新流"s"的延迟适于小于阶段"p"的阶段"p’"中在节点"v"处的变化即,"p’"<"p"

78、如果沿着新流"s"的路径到达最后节点，则→成功＝真→停止。

79、6.根据权利要求4，有利的是，递归间隔和/或延迟计算和接受算法包括有限的递归深度，该递归深度由函数f("s","p","s")出于性能原因而完成之前被自身调用的次数来定义，并且相应地拒绝将需要更深递归的新流“s”。

80、应该注意，在这个框架内的拒绝仅拒绝那些将违反“时间敏感型联网<tsn>”-网络的约束的流，所述约束对于算法的正确性是必要的。在完整的帧接受过程中，由于其它约束违反，进一步的流可能被拒绝。

81、7.插图和注释：

82、图片3描绘了具有减少率“rr(sx)＝4”的已接受流“sx”的阶段间隔的示图，列对应于流“sx”的路径上的节点“v”，并且行对应于循环。

83、图示了对于一个流的结果的视觉表示，以使算法的步骤更清楚。结果被表示在表格中，其中每一行表示一个循环，并且因此表示根据第5点用伪代码描述的“纯递归算法框架”的外部while循环的一次迭代，但是其它行(下面)的调整可能是必要的。所述列对应于流“sx”的路径的顶点，按照它们在“时间敏感型联网<tsn>”-网络中被访问的顺序排序。在每一行中，它从左到右通过节点列(表示通过“时间敏感型联网<tsn>”-网络的路径的开始(start)到结束(end))进行迭代。在根据第5点用伪代码描述的“纯递归算法框架”的(d)中的更新对应于更新当前行下面的列，对另一个流调用“recompute(…)”对应于更新不同的表格。

84、考虑具有减少率“rr(sx)＝4”的已接受流sx的情况，其路径在阶段“p0:＝p＝0”的情况下访问9个节点。黑色x标记表示(在阶段“p0:＝p＝0”中发送的)流sx的一个帧的可能位置。橙色标记示出将在阶段“p4:＝p＝4”中发送的流sx的下一帧。

85、图片3中的蓝色标记示出如何将阶段间隔投影到rr(s)。

86、在循环4中，这对于流“sx”来说等同于循环0。它再次被投影到循环0(->蓝色标记)，以用于干扰计算。由于拒绝条件(一个流的两个帧不会在节点处相遇)，这些标记不会与已经在循环0上的黑色x重叠。

87、因此，图片3中的橙色框可以被用来确定阶段间隔和/或决定在哪里可发生与其它流的干扰。

88、从循环表格来创建橙色框是在根据第5点关于“recompute(…)”用伪代码描述的“纯递归算法框架”的部分(d)中发生的事物，可能为每一个节点创建两个间隔，而不是一个间隔。

89、如前面提及的，使用了一种被视为用来记录对于流“sx”的间隔的rr(sx)阶段的版本，并因此考虑对于任何rr(sx)个阶段的最差情况干扰。

90、这样，如果存在一个具有减少率“rr(s)＝8”的新流“s”，该减少率在阶段“p0:＝p＝0”中影响已接受流“sx”，并且其次在阶段“p4:＝p＝4”中影响已接受流“sx”，则将只考虑两个场景中较差的。

91、如前面提及的，考虑干扰的替代方式是考虑在“rrmax-1”和“0”之间所有阶段中的可能干扰，从而假定“时间敏感型联网<tsn>”-网络的rrmax是预先已知的。然后，只需要将“rrmax”之后发生的事物向下投影到更小的阶段。如果使用变体来跟踪“rrmax”-阶段中的间隔，则将需要这个表格的一个具有“rrmax”的更大版本。在这种情况下，将需要更仔细地考虑如何更新延迟。仅考虑一次已接受流“sx”的路径将是不够的。替代地，将需要考虑已接受流“sx”的帧的所有可能状态，直到阶段“rrmax”为止，即需要考虑在对于已接受流“sx”的rrmax/rr(sx)个不同帧中开始的帧，并且更新所有这些帧。该算法可以适于这个设置，但是技术细节将会变化。

92、根据在图片4中呈现并示出的另一示例，解释了递归计算和自适应如何工作。

93、使我们具有下面的场景：存在一组已接受流“s”，其中s＝s1,s2，并且已接受流“s2”的减少率“rr(s2)＝2”，并且它打算添加应该在阶段“p0:＝p＝0”中发送的具有减少率“rr(s)＝4”的新流“s”。因此，调用根据第5点用伪代码描述的“纯递归算法框架”的函数recompute(s,0,s)。现在，根据图片4，当实际上考虑节点“v2”处的情况时，f("s","0","s")中的表格可能看起来像根据第5点用伪代码描述的“纯递归算法框架”的外部while循环的第二次迭代中的表格。注意：根据减少率“rr(s)＝4”，最后的表格将具有4行。

94、假定在阶段“p1:＝p＝1”中，根据红色标记，在节点“v2”处添加新流“s”，这增加了已接受流“s2”的延迟，使得其间隔在节点“v2”处或之后已接受流“s2”的路径上的某处增加。因为“时间敏感型联网<tsn>”-网络是非循环的，所以这不能在节点“v0”或节点“v1”处。因此，调用根据第5点用伪代码描述的“纯递归算法框架”的函数recompute(s2,ss2＝s1,1mod rr(s2))。仅在包括对recompute(s1,-,p’)的调用的完全完成那个之后，并且如果必要的话，才继续对于新流“s”的计算。首先，通过在先前阶段处更新对于节点“v2”的新流“s”。因为对于已接受流“s2”的阶段间隔增加了，它现在是[0，1]而不是[1，1]，所以它可影响阶段“p0:＝p＝0”中的新流“s”。

95、这也可影响在接下来的循环中必须考虑哪些节点(图片4的表格中的阶段“p>1”)，但是它不改变在先前循环中对于新流“s”而考虑的节点(图片4的表格中的阶段“p<＝1”)。

96、对于阶段“p2:＝p＝2”，必须指出另外一件事。假定节点“v2”是已接受流“s2”的阶段间隔被改变的节点。这意味着，对于阶段“p2:＝p＝2”，已接受流“s2”也将存在。然而，必须记住，这已经计及了在更新期间，在阶段“p0:＝p＝0”中由新流“s”对节点“v2”处的已接受流“s2”造成的延迟。因此，跟踪在实施期间已经考虑了哪些影响是重要的。这在根据第5点用伪代码描述的“纯递归算法框架”的部分(a)、(b)中进行。在已接受流“s2”的阶段间隔增加到[0，1]但在阶段“p0:＝p＝0”中不存在新流“s”的相对场景中，现在将必须进行更新。

97、8.实施方式注意事项

98、该算法可以适于用来通过限制递归深度(参见权利要求4)来限制计算时间的实际设置。这意味着通过向根据第5点用伪代码描述的“纯递归算法框架”的函数f(…)添加“递归_深度(recursion_depth)”变元来用日志记录递归树有多深，每调用一次函数f(…)，“递归_深度”变元就加1，并且如果递归树变得太深，即“递归_深度”参数太高，则自动拒绝。

99、在从函数recompute(s,…)调用函数recompute(s2,…)的先前示例中，递归深度为2将意味着(如果有必要的话)拒绝在那个第二次调用内调用函数recompute(s1,…)。然而，直接从函数recompute(s,…)调用函数recompute(s1,…)将是好的。

100、作为特例，考虑递归深度被限制为1的场景。在这种情况下，根本不允许递归调用。这意味着，根据第5点用伪代码描述的“纯递归算法框架”的部分(d)将永远不会被执行，并且如果任何干扰流将在某个节点处增加其阶段间隔，则递归停止。应该注意的是，当前处理的流可能仍然采取几个循环来到达其目的地，因此这与要求所有低优先级流在一个循环内到达是不相同的。

101、此外，本发明的附加有利发展源于本发明根据单个图片的优选实施例的以下描述。

102、该图片示出了用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络的多循环流量的计算机实施的工具cit的原理图，该计算机实施的工具cit优选地是计算机程序产品cpp。计算机实施的工具cit(相应地计算机程序产品cpp)被设计为例如app，其可上传到众所周知的计算机中。这样的计算机可以被包括在用于跟踪“时间敏感型联网<tsn>”-网络的多循环流量的控制系统中。

103、根据图片中的描绘，计算机实施的工具cit(相应地计算机程序产品cpp)包括：非暂时性处理器可读存储介质stm(例如随机存取存储器<ram>)，其具有程序模块pgm的处理器可读程序指令，该程序模块pgm实施存储在该非暂时性处理器可读存储介质stm中的用于跟踪具有同步终端站的“时间敏感型联网<tsn>”-网络的多循环流量的软件方法swa；以及与存储介质stm连接的处理器prc，其执行用来跟踪“时间敏感型联网<tsn>”-网络中的多循环流量的程序模块pgm的处理器可读程序指令。

104、为了跟踪这个多循环流量，软件方法swa包括延迟计算模型dcm和递归算法框架frwalg，并且被设计成使得：

105、1)tsn-流量是以涉及多个优先级类别的流的形式、特别地涉及与零损失和/或时延约束相关的高优先级类别和/或低优先级类别的流的形式来组织，并且包括tsn-流量接受的一组流“s”，其中s:＝s1,s2,…,sn，其中以及请求tsn-流量接受的至少一个新流“s”，其中对于具有减少率“r”的每一个流“s1,s2,…,sn”、“s”，沿着经由tsn-节点“v”选取的路由发送固定大小的帧，所述路由包括其间的终端站和tsn-桥并且具有作为在调度循环中测量的减少率“rr”的一定周期性且具有在范围“0,…,r-1”内的阶段“p”，其中p0:＝p＝0,…,pr-1:＝p＝r-1，

106、2)每一个节点维护每个流优先级类别的队列，并且每一个队列在内部基于fifo方式操作缓冲区，

107、3)延迟计算模型dcm，其基于由tsn-流量的流的所有路径引起的基础无向图是非循环的，该延迟计算模型dcm被用来：

108、-考虑在没有tsn-流量的流干扰的情况下，归因于沿着经由tsn-节点和tsn-桥的路由的最小和最大处理时间的延迟，以及

109、-计算由tsn-流量的流干扰引起的延迟的上界，

110、4)对于每一个流“s1,s2,…,sn”、“s”和每一个节点“v”，随着时间的推移考虑tsn-流量，从而产生对于每一个流“s1,s2,…,sn”、“s”和每一个节点“v”的一组阶段间隔“[a,b]”，其中

111、5)通过以下步骤来执行递归算法框架frwalg：

112、5.1)使用对于阶段间隔的紧凑表示的拒绝策略，这样是因为所有tsn-流量在作为流“s”、“s”的最大减少率“rr(s1,s2,…,sn；s)”的最大减少率“rrmax”之后，对于每一个流“s1,s2,…,sn”、“s”重复，同时投影所有阶段间隔边界“0,…rr(s1,s2,…,sn；s)–1”，

113、5.1.1)采取发生在任何减少率“rr(s1,s2,…,sn；s)”连续循环中的最差情况场景，

114、5.1.2)考虑阶段间隔集合“[0+i*rr(s1,s2,…,sn；s),rr(s1,s2,…,sn；s)–1+i*rr(s1,s2,…,sn；s)]”之中的最差循环中的阶段间隔，其中

115、5.1.3)进行取模计算“阶段间隔边界“0,…rr(s1,s2,…,sn；s)–1”mod“rr(s1,s2,…,sn；s)””，

116、5.2)对于阶段间隔“[a,b]”和每一个流“s1,s2,…,sn”、“s”，检查拒绝策略的拒绝条件“b–a<rr(s1,s2,…,sn；s)”，以便确保同一流“s1,s2,…,sn”、“s”中没有两个帧在同一循环处于同一队列中，

117、5.3)迭代地计算阶段间隔“[a,b]”，特别地适应该组流“s”的阶段间隔“[a,b]”，并通过遍历与通过节点“v”的tsn-流量的每一个流“s1,s2,…,sn”、“s”相关的所有循环来计算最差情况延迟和至少一个新流“s”的阶段间隔，以通过对于先前循环的先前计算来确定帧在节点“v”处的位置，并且通过考虑先前循环和流“s”、“s”的每一个其它流来更新所计算的对于这些节点“v”的延迟，

118、5.4)如果步骤5.3)的迭代计算和更新导致每一个其它流的节点间隔增加，则对于该每一个流“s1,s2,…,sn”，“s”，递归地进行步骤5.3)的迭代计算和更新，并且优选地除了步骤5.1)至5.4)之外，

119、5.5)在进行取模计算之前，检查拒绝策略的拒绝条件“b–a<rr(s1,s2,…,sn；s)”。

120、递归算法框架frwalg优选地是递归间隔和/或延迟计算和接受算法，其通过以下内容用伪代码来实现：

121、假设：

122、·具有节点间隔和计算的延迟的该组流“s”。

123、·新流“s”。

124、·发送流“s”的阶段“p0”。

125、输出：如果新流“s”的接受不允许保证流并集"s"∪"s"的所有必要约束，则新流“s”将在阶段“p0”中被拒绝，因为违反了拒绝条件。否则，输出对于流并集"s"∪"s"的新间隔。

126、主要算法：

127、init("s","s")

128、recompute("s","p0","s")

129、函数定义：

130、init(s,s)

131、利用对于该组流“s”的原始节点间隔，计算新流“s”沿着新流“s”的路径在每一个节点“v”处的最早和最晚到达时间

132、recompute("s","p","s")//外部重新计算框架//

133、f("s","p","s")

134、在新流“s”的最晚到达时间不在具有阶段“p”的循环中时，

135、f("s","p","s")，

136、将表格更新到流“s”的减少率rr("s")

137、f("s","p","s")

138、成功＝假

139、当不成功时

140、重新计算＝假

141、对于沿着新流“s”的路径的每一个节点“v”，其中新流“s”可以从开始到结束都处于阶段“p”中！

142、(a)如果在阶段“p”中在节点“v”处已经存在对于新流“s”的账号，则继续到下一个节点"v"

143、(b)如果在节点“v”处新流“s”违反了拒绝条件，则→拒绝

144、如果在阶段“p”中新流“s”的添加导致在节点“v”处缓冲区溢出，则→拒绝

145、对于该组流"s"中的其延迟受到在阶段“p”中在节点“v”处添加新流"s"的影响的每一个流"s’"

146、根据针对新流"s"的新延迟来更新该流"s’"的间隔。

147、如果这改变了任何节点间隔

148、(c)recompute("s’","p"mod rr("s’"),"s""s’")//即，更新延迟//

149、如果该组流"s"中的任何流"s’"增加了任何间隔则重新计算＝真

150、如果重新计算

151、(d)使新流"s"的延迟适于小于阶段"p"的阶段"p’"中在节点"v"处的变化，即"p’"<"p"

152、如果沿着新流"s"的路径到达最后节点，则→成功＝真→停止。

153、此外，递归间隔和/或延迟计算和接受算法包括有限的递归深度，并且相应地拒绝将需要更深递归的新流“s”，该有限的递归深度由函数f("s","p","s")在出于性能原因而完成之前被自身调用的次数来定义。

154、

155、