面向时间触发流的时延感知差分多径转发机制

谭兵，蔡岳平，姚宗辰

（重庆大学微电子与通信工程学院，重庆 400044）

1 引言

时间敏感网络[1]（Time Sensitive Networking，TSN）的诞生源于实时以太网概念的提出。在这之前，以EtherCAT、Profinet等为代表的一些实时通信技术已经逐步应用于各个领域。虽然这些技术都基于传统以太网，但是又具有一些专有机制，使得相互之间并不能兼容运行，也就制约了实时以太网的进一步发展。在这种背景下，IEEE802.1工作组提出了时间敏感网络的概念，意图通过标准化使其在各个领域都能够同构运行，提供实时的数据传输[2]。IEEE 802.1时间敏感网络是一种扩展传统以太网的技术，具有时间同步、有界低延时、低抖动、兼容性强等特点，能够实现流的低延时高可靠传输。TSN广泛应用于智能电网、工业自动化、车辆的驾驶系统、航空电子等领域，可提供超高可靠低延时通信（Ultra Reliable Low Latency Communications，URLLC）。

在这些应用中，时间触发（Time Triggered，TT）流扮演着重要的角色，它是一类优先级较高的流量，具有周期性、时延确定性、时延有界性的特点。这类流量常用于传输关键数据，如工业网络中的控制流就是典型的时间触发流[3]。

然而，当前TSN中TT流的传输还存在着未解决的问题，如在传统的转发方案中，具有相同最短路径的流将会在同一条路径传输。单条路径上的传输流量过多，导致调度时保护带宽过多，从而导致端到端平均时延过长。采用负载均衡多路径转发可以有效的减少保护带宽，但是由于流量的差异性，会导致最短路径上保护带宽过多。同时，最为关键的是，没有考虑分析处理时延和发送时延来减少总时延。

2 TT流路径选择的研究现状与分析

TSN流量的路径优化问题在TSN网络中较为常见，本文关注的重点是TT流路径选择问题。传统的TSN路径选择方法使用快速生成树协议（Rapid Spanning Tree Protocol，RSTP）或最短路径桥接（Shortest Path Bridging，SPB）来确定路径[4]。在确定路径之后，TSN再针对路径和节点计算出门控制列表（Gate Control List，GCL）[5]。端口特定的GCL列表以及精确的时钟同步协议（IEEE 802.1AS）使得基于以太网的网络能够满足关键任务应用的严格时延约束[6]。许多研究人员研究了各种路径选择问题，实现在硬截止日期和最坏情况延迟的背景下确定以太网的时间表和路径[7,8]，提高TSN应用到网络物理系统中的控制性能和稳定性。

文献[9]提出在路径选择时考虑最大链路负载率，通过遗传算法求出流的最佳转发路径集，再对流量进行调度。文中是根据最小化最大链路负载率来完成选路，公式（1)表示为最大链路负载率，其中ri,j表示流量i在链路j上传输，F为流量集合，E为链路集合。rsli,j为单个流量负载的时隙长度，cti,j为流量周期。这种解决方案存在的问题是，在路径选择时仅考虑了最大链路负载率，忽视了跳数及流量负载带来的时延影响。

与文献[9]相比，文献[10]中的负载均衡多径转发机制在最大链路负载率相同时，流量优先考虑跳数较少的路径进行传输。文献[10]的作者为联合路由调度问题提出了基于整数线性规划（Integer Linear Programming，ILP）的路由调度解决方案，利用路径选择与调度的同步计算，实现每个流的时延优化。但是，其路径优化选择参数指标过于单一。文中方案与文献[9]相比，其不同在于最大负载率相同时，优先选择跳数最少的路径。

Hop-Load[11]转发方案在考虑路径负载均衡[10]的基础上，引入了跳数对路径选择的影响。公式（2）展示了文中提出的路径优化选择过程，其数学表达式含义同公式（1）。其中，Umax为最大链路负载率。这种解决方案存在的问题是，未考虑不同大小的TT流在各路径上的处理时延与发送时延的差异性。同时，由于文献[11]和文献[10]均是基于ILP的调度过程，且其复杂度较高，上述解决方案在计算路径以及调度时刻列表时也是特别耗时的。

上述最新方案中仅仅是简单地考虑跳数与负载均衡对时延的影响，并没有考虑不同大小的流量在不同路径上所带来的时延影响。相比文献[9]和文献[11]，本文提出的时延感知差分多径转发机制，不仅考虑了路径负载均衡，而且考虑了不同负载对流量端到端时延的影响。差分多径转发机制以基于发送时延与处理时延的多径转发指标DMFI（Differential Multipath Forwarding Index，DMFI）为基础，将多径转发问题转化为0-1整数线性规划问题，并通过差分多径转发算法求解出流的转发路径集，实现流低时延传输。

3 时延感知的差分多径转发机制

本文提出的方案增加了对处理与发送时延的感知能力，提出了一种时延感知的差分多径转发机制。首先，通过时延分析得出DMFI指标，用以优化各路径选择。然后，将路径选择问题转化为0-1整数线性规划问题，采用差分多径转发算法求出流的转发路径集。该方法可以有效地减少收敛时间和端到端时延。

3.1 时延感知分析

通过时延感知分析，确定差分多径转发指标DMFI，用以优化路径选择。在时延分析上，本文将从帧的传输过程的分析。根据图1中TSN交换机内部结构图，可以将TSN中的时延组成解析出来。数据帧在经过TSN交换机时，需经历(a)转发处理、(b)排队等待、(c)发送数据帧三个部分。

（1）处理时延：图1中的(a)过程，从交换机接收消息到将消息放入TT队列的时间，交换机的处理时延由Ft表示。

（2）排队时延：图1中的(b)过程，从将数据帧放入交换机传出端口的队列中开始到发送帧之前的时间。排队时延取决于端口上的调度时刻，在GCL合成时确定。交换机端口负载越大，流量数越多，调度时间Qt也会越大。

（3）发送时延：图1中的(c)过程，在端口发送。单个节点发送时延由Lt表示，并取决于消息的大小和发送速率。

（4）流量端到端时延：流量的端到端时延，包含三个部分：处理时延、排队时延、发送时延（此处不考虑传播时延，传播时延与链路的物理特性有关，与负载大小无关，此处不加讨论）。处理时延与交换机的处理能力相关；排队时延取决于路径端口上的调度时刻，在GCL合成时确定，与端口的负载相关。交换机端口负载越大，流量数越多，排队时间Qt也会越大。发送时延与链路带宽以及数据大小相关，流量端到端时延用Delay表示，则其计算方式如（3）式所示。

由公式（3）与上述分析可知，TT流端到端时延与流量负载、路径跳数、经过的节点数（等于跳数）相关。因此，本文依据上述分析以增加路径选择时的时延感知能力，得出了公式（4），并定义为多径转发指标MFI（Multipath Forwarding Index）。公式（4）的第二项为对总处理时延与总发送时延的感知处理，并作归一化处理。Vlink链路为发送速率（带宽），Vprocess为交换机节点处理速度，loadi,j为流量i在链路j上的负载，与公式（1）、（2）不同的是，此处ri,j为流量i选择在路径j上传输，hopj表示路径j的跳数。

图1 TSN交换机内部结构图

3.2 差分多径转发机制

不同流量负载之间对发送时延与处理时延的影响存在差异性，即负载越大对处理时延与转发时延的影响越大。因此，为了进一步加强对时延的感知，本方案加强了负载较大的流量时延影响能力。本文在公式（4）的基础上引入差分因子α，来区分不同负载对时延的影响程度，并化简得到公式（5）。最后将公式（5）定义为差分多径转发指标（DMFI），作为路径选择的依据。其中，

在数学模型的建立上，本文将路径选择问题转化为0-1整数线性规划问题，接着提出了一种基于贪心算法的差分多径转发算法，实现对最优路径集的求解，从而达到更低的端到端时延。其中，0-1整数型线性规划数学描述如公式（6）、（7）、（8）所示，s公式（6）中的ri,j用以表示流量i是否选择路径j；公式（7）表示每个流量只能选择一条路径；公式（8）为优化目标。

针对此问题，本文使用差分多径转发算法进行求解。由公式（3）、（5）可知，负载越大的流量对时延的影响也将越大。因此，本文通过设置阈值（平均负载的大小）来判断差分因子设置的大小。

算法描述：在对各路流量的路径集选择需遵从两个原则。

（1）各流在选择路径时必须满足Delay小于截止期限。

（2）贪心准则：由式（3）、（5）可知，负载越大的流量越适合最短路径，因此将流量按负载从大到小的顺序排列，路径根据跳数从小到大排列，优先给负载最大的流量安排路径；选出流量i的路径时，使前i个流量中DMFI最小，若流量i的负载大于流量的平均负载，则，否则，用以加强差分感知。以此类推，每添加一个流量均计算出DMFI最小的路径选择，直到所有流量选择完。

按照上述两种原则，采用贪心的思想，通过计算（5）式的值，每次选取最小的DMFI值得路径，直到将所有流量挑选完路径，输出各流量的转发路径。

算法 1 差分多径转发算法

Input: TopMatixs: Network topology；

Traf fi ci: Characters, number of fl ows M；

Output: The path selection set of fl ows PATH。

1）Pathi = KSP (traf fi ci, TopMatixs); //采用删除法求得；

流量i前K条最短路径；

2）Combine paths with inclusion relationships ;

3）Compute and rank the load, number setting M;

4）Compute the average of the flow load AverageLoad;

5）FOR (i =1, i ++, i < M);

6）FOR (j = 1, j ++,j < N);

7）Compute the delay of fl ow i in path j,

Tt = Ft + Lt ;

8）IF (Tt > deadline (i)) THEN;

9）Delete path j in fl ow i ;

10）END IF;

11）END FOR;

12）END FOR;

13）FOR (i = 1, i ++, i < M);

14）Select the corresponding α according to the load, and then calculate the DMFI value;

15）Update the set of PATH (i, j) ;

16）END FOR;

17）Output the PATH 。

4 仿真实验与结果分析

4.1 实验设置

本文在MATLAB上对上述差分多径转发机制进行了实现，并与最短路径转发方案、负载均衡转发方案、Hop Load转发方案[11]进行对比。实验的总交换结点数为5个，每个节点可连接5台主机，可视为工业系统的终端设备或者控制器。考虑路径选择的多样性，实验网络选择如图2[13]所示，具有较强冗余性的网络，图中链路带宽设置为100 Mbit/s，节点处理速度为2 ns/bit，如表2所示。

本实验以TSN在工业网络中的应用为例，采用工业网络中的TT流的属性特点。工业网络中TT流主要包含为控制流，而不同终端应用产生的控制流大小以及周期又存在着差别，为了充分模拟现实中的工业网络的环境，设置了四种类型[12]控制流来组成TT流，其具体的流量特征如表1所示。

图2 网络实验拓扑

4.2 性能评价指标

为了客观反映不同方案的实际效果及不同参数对差分多径转发机制的影响，本文定义了性能指标。

（1）TT流量端到端平均时延

即将各流量到达目的地的时间求和，再除以总流量数可得流量端到端平均时延，这是反映出TSN的低时延性的重要指标。

（2）可调度性

可调度性[12]是指在网络中能够调度成功的流量个数与需要调度的流量个数之比，即用来评估路径选择对后续流量调度的影响。

表2 实验参数的设置

（3）最大链路负载率

最大链路负载率Umax是衡量多径转发算法能否可能保障网络链路负载均衡的重要指标，是指单位时间内通过的数据量与可以链路通过的数据量之比。

4.3 仿真结分析

仿真结果分为3种指标，每种指标对应比对4种方案。4种方案分别是最短路径转发方案、负载均衡转发方案、HopLoad转发方案、差分多径转发方案。本文将针对不同的方案在不同的指标下，将逐个进行分析。

如图3所示，为TT流端到端平均时延的对比。如实验结果所示，Hop Load转发方案平均时延是比负载均衡方案的低8.43%左右。差分多径转发方案的TT流端到端平均时延比负载均衡转发方案与Hop Load方案要低，通过计算本文提出的方案比负载均衡方案减少了22.55%，比Hop Load方案减少了17.32%。

图3 TT流端到端平均时延比较

表1 流量参数的设置

因此可知，差分多径转发方案所需平均时延最短。差分多径转发方案相比最短路径转发方案，可以同时有多两条路径端口参与转发，队列长度大大减小。从另一角度看，多路径转发可理解为并行转发，而最短单路径则为需等待更多时间的串行发送。而相比于差分多径转发方案，负载均衡转发方案没考虑跳数对时延的影响导致时延较高，HopLoad转发方案则是没考虑到不同流量负载在不同路径上对时延的影响，导致时延过高。

如图4所示，是不同转发方案的可调度性比较。从图4中可以看出，最短路径转发方案的可调度性最低。这是由于随着流量数的增加，会导致过度使用链路从而违反流量调度中的时隙不冲突约束和最大端到端时延约束，导致调度失败。而差分多径转发与负载均衡转发方案则是通过在不同路径上发送TT流，以解决单条链路的瓶颈问题。在图4中，显示差分多径转发、负载均衡转发的可调度性与Hop Load转发方案差别不是很大，具有相似的可调度性。

图4 TT流可调度性比较

如图5所示，是最大链路负载率，其是用以评判链路是否负载均衡的标准之一。从图中可以看出，使用负载均衡的方案其最大链路负载率是优于差分多径转发方案。其中，主要原因是其以最大链路负载率为指标进行路径选择的，而在差分多径转发方案则更多的考虑了时延因素。其实际表现为传输时延较短的路径转发的流量会较多点，进而导致多路径有差分转发最大链路负载率提高。因此，本文提出的方案是在牺牲部分负载均衡能力的前提下，为TT流提供更低平均端到端时延。

图5 最大链路负载率

5 结束语

为了实现TT流在TSN中的低时延传输，本文对TT流在TSN中的传输过程进行了分析，确定了影响流量端到端传输时延的因素。基于发送时延与处理时延的多径转发指标DMFI成为TT流路径选择的依据。将多径转发问题转化为0-1整数线性规划问题，并通过差分多径转发算法求解出流的转发路径集进行路径选择。仿真结果显示：与负载均衡多径转发和Hop Load转发机制相比，提出的方案使时间触发流端到端平均时延分别降低了22.55%和17.32%。未来研究工作包括解决贪心算法局部最优问题的启发式算法研究、时间触发流的最坏有界时延分析等。