时间敏感网络中基于ILP的动态流量均衡调度算法.docx

基于 ILP 的动态流量均衡调度算法在时间敏感网络中的应用 时间敏感网络是当前网络通信领域的一个热点话题，以 EtherCAT、Profinet、TTE 等实时通信技术为代表的技术被应用在一些对实时性要求高的场景中，但这些技术都基于以太网，并具有一些专用机制，使得相互之间并不能兼容运行，也就限制了实时性以太网的进一步发展。在这种背景下，IEEE 802 TSN 任务组提出了时间敏感网络的概念，意图构建一个统一的数据链路层协议，通过标准化使其在各个领域都能够同构运行，提供实时的数据传输。 TSN 目前主要开发了时钟同步、流量调度、网络配置系列标准集，网络配置可以将调度信息配置到各节点，各节点在时钟同步的基础上用各种调度方法来实现实时性与确定性。其中流量调度方法中最重要的便是 IEEE 802.1 Qbv 基于门控的时间感知整形器（Time Aware Shaper，TAS），定义了一种基于队列传输选择的门控机制，每个传输队列与一个传输门相关联，传输门的状态一共有两种：open：该队列门打开，若该队列中有待传输的帧，可以进行传输; close：该队列门关闭，该队列无法进行传输。 然而，协议中并没有如何得到 GCLs 的方法。因此，针对网络运行时需要新加入可调度流和交换机某端口故障的情况，以及网络中链路负载可能出现的极端情况，本文在文献[6]的研究基础上，改进了其算法。 在时间敏感网络中，应用数据一般分为两种，一种是系统控制的实时数据，即 TSN 数据流（简称 TSN 流），还有一种是用于辅助服务的尽力而为数据，即 BE 数据流。TSN 流具有固定的周期和大小，必须在其截止时间内到达其目的节点并满足抖动约束。相比之下，BE 数据流不需要时间保证。 为了解决调度问题，引入了两类变量来说明路由和调度问题。二进制决策变量 lo[vi, vj]fa 表示链路[vi, vj]∈E 是否被 fa∈F 占用。实数型决策变量 t[vi, vj], fa 来表示调度结果。如果 fa 通过[vi, vj]（即，lo[vi, vj], fa=1）时，t[vi, vj], fa∈[1, Ta] 是流 fa 在链路[vi, vj]上的发送时刻，否则，t[vi, vj], fa=0。 基于 ILP 的动态流量均衡调度算法可以解决这个问题。ILP 是一种广泛接受的，成熟的方法，可以理论上用于解决所有可以用整数决策变量建模的问题。因此，本文基于 ILP 设计了该调度算法。 该算法的主要思想是将时间敏感网络建模为无权有向图 G=＜V, E＞，其中 V 是网络节点的集合，由终端(End Station，ES)和交换机(Switch，SW)组成，E={[vi, vj], vi, vj∈V, 并且 vi, vj 通过一个链路连接}，是定向网络链路集。然后，对时间敏感网络和 TSN 流建模，并引入两类变量来说明路由和调度问题。使用 ILP 来解决调度问题，并得到一个动态流量均衡的调度算法。 该算法可以解决当前时间敏感网络中的一些问题，如小幅变动网络的情况下需要重新全部调度的时间过长的问题，并且可以应用于各种场景，如工业物联网、车载网络、航空电子网络等。