基于时间触发DIMA架构的网络拓扑优化

王红春, 屈静, 牛文生

(1.西安电子科技大学 计算机科学与技术学院, 陕西 西安 710071;2.西安电子科技大学 通信工程学院, 陕西 西安 710071;3.清华大学天津高端装备研究院, 天津 300300; 4.西安航空计算技术研究所, 陕西 西安 710068)

面对未来信息化的作战战场和空-天-地“系统之系统”信息融合的需求，分布式综合模块化航空电子系统(distributed integrated modular avionics,DIMA)的概念于近年内浮出水面，并在航空和航天领域得到了极大关注和重视[1-2]。对于DIMA 航电系统，涉及到多个子功能区域的分布式集成，更加强调任务关键和安全关键等性能保障机制在系统集成过程中的一致性性能。在DIMA这种实时分布式系统中，采用时间触发(time-triggered,TT)的通信方式可以避免数据帧争用物理链路，保证数据交换的实时性和准确性，提高离线通信任务负载均衡分配的效果[3-4]。而在时间触发以太网(time-triggered ethernet,TTE)场景中，用于安全关键的路由一般都是静态的，它们在拓扑设计阶段就被加载到终端和交换机中，在运行阶段不会因为检测到网络故障而动态重组，以避免帧丢失等错误的发生。由此可见，拓扑结构的优化设计对于TTE网络而言是至关重要的。

在网络可靠性和拓扑设计方面有很多学者开展了研究工作，提出了几个衡量网络可靠性的度量，如：连通性、恢复力及可执行性，并提出了解决拓扑设计问题的几种方法：启发式、元启发式和基于数学规划的精确求解法[5-6]。然而，这些方法不能被TTE直接利用，原因是传统的拓扑设计算法是在拓扑已知的前提条件下，由通信业务选择路径进而完成通信任务，而在基于时间触发以太网的DIMA系统中，是根据已知业务，通过调整节点与交换机的互连关系来进行设计。并且在传统的设计算法中，并没有考虑路径选择和负载均衡对拓扑结构设计产生的影响。

为了进一步改善现有的拓扑设计算法，针对TTE网络拓扑进行优化设计。考虑到TTE网络的拓扑优化是典型的NP问题，很难采用某种固定的解析方法得到最优解，而模拟退火算法在启发式算法中，具有应对复杂系统的非线性不连续解集的能力，且通过其具体的应用可以在全局最优和局部最优之间权衡，这些特点非常适用于本文所关注的课题[7]。因此，研究了Floyd算法和模拟退火算法，优化目标是使该网络可以在给定通信任务情况下，生成一个通信路径短、负载均衡兼顾低成本架构的拓扑网络，从而可以使得整体网络拓扑架构成本更低，整个网络的节点以及链路上的流量分布更加均匀，更好的缓解在精确时间流情况下网络拥塞问题。

1 基于TTE的 DIMA系统模型

在分布式综合模块化航空电子系统中，采用交换机骨干网络将具有处理资源的嵌入式终端系统通过全双工的通信方式将全局同步机制和时间触发的数据流量添加到星型拓扑以太网中，同时保持与SAE AS6802标准的兼容性[8]。对于TTE网络，可以从物理拓扑和流量虚拟拓扑2个方面来描述。物理拓扑显示了物理设备之间的TTE网络互连，虚拟拓扑描述了3种不同类型的通信流之间的TTE网络通信链路，如时间触发通信流、速率约束(rate constraint,RC)通信流和“尽力传”(best effort,BE)通信流[9-11]。从而使得TTE网络在一个物理网络上可支持具有不同的实时性和安全性需求的应用之间的通信。值得注意的是，讨论的拓扑优化问题是在集群层进行的。

图1 DIMA架构下的TTE网络拓扑结构

如图1所示，从初始节点vi到目的节点vj的数据流链路可以表示为eij,即

eij=[vi,vj]

(1)

且节点vi和vj可以是端系统(end system,ES)或交换机(network switch,NS)。并对数据流路径进行如下定义:

Pij=eii1+ei1i2+…+einj

(2)

数据流路径Pij是一个有序的数据流链路序列,连接一个发送端到一个接收端,在图1中,数据流路径P13将终端ES1连接到终端ES3,而P14将终端ES1连接到终端ES4。此外,根据ARINC 664part7规范,将虚拟链路(virtual links,VL)定义为网络拓扑中全部数据流路径Pij的一个并集[12],其数学表达式如(3)式

Vlink=∪Pij

(3)

2 拓扑结构设计问题描述

网络拓扑设计问题,对于TTE网络而言,实际上就是在给定通信业务的情况下,生成一个具体的网络路径,使业务可以准时准确地到达目的地。针对这一问题,本文主要从路径短、负载均衡和低价构成本这几方面来进行考虑,从而设计出优秀的网络拓扑。

首先从网络拓扑开始阐述这一问题,物理拓扑由双向物理通信链路和包括端系统(end system,ES)和交换机(network switch,NS)的网络节点构成,运用图论的相关知识,将图1中的TTE集群建模为无向图G=(V,E),其中,V=VES+VNS表示网络节点集合,V=(v1,v2…vN),下标N为节点数量。E是连接节点的物理链路的集合,M是链路数量。节点vi到节点vj的链路e(e∈E)可以表示eij。图1抽象后所形成的的拓扑结构，如图2所示。

图2 抽象出的拓扑结构

采用连接矩阵X=(xij)N·N定义节点之间的连通关系,其中xij如下:

(4)

式中，xij=1表示节点vi到节点vj之间有链路连接,xij=0则表示无连接。

2.1 负载均衡

由于TTE网络通信本身所具有的时间确定性,并且在TTE网络中节点和链路上的负载均衡可以显著降低离线调度表生成的不可行的概率,同时也能保证整个网络中的各个部分都能有足够的闲时片剩余,以保证RC和BE任务的正常传输,所以负载均衡对于拓扑优化设计非常重要[13]。因而本文使用TTE网络中节点和链路上的负载均衡程度来作为拓扑设计的约束条件。

由于在给定的通信任务下,通过各节点和链路上的通信流可能存在不均匀情况,则需要通过定义如下的指标对整网的负载情况进行衡量:

(5)

(6)

(7)

(8)

式中,Li是消息i的帧长,Gi是消息i的周期,N是一条链路上的消息数,M是拓扑中的链路数,U(i)是在一条链路上传输的所有消息的负载,U(i,j)是网络上所有链路的负载,U/M是流经所有链路的负载均值,D(i,j)是负载的方差。以TTE网络中各节点上负载的方差作为衡量负载均衡的指标,这个值越小,则说明其负载均衡度越好。

2.2 通信路径的选择

尽管每个任务都有其特定的发送端和接收端,但在同一个网络拓扑中传输路径仍然有几个可能的解决方案。因此需要用路径生成算法来找出最优的传输路径[14]。图3描述了具有10个节点(6个终端系统和4个交换机)的TTE网络拓扑的示例。

图3 TTE网络中的拓扑连接

从图3我们可以看到,从ES2发送到ES5的TT流有5个可能的传输路径:

1) ES2→NS1→NS4→ES5

2) ES2→NS1→NS2→NS4→ES5

3) ES2→NS1→NS3→NS4→ES5

4) ES2→NS1→NS2→NS3→NS4→ES5

5) ES2→NS1→NS3→NS2→NS4→ES5

路径1)是需要跳数最少的路径,只有2跳,路径2)和3)是3跳,路径4)和5)使用4跳来完成传输。更多的跳数意味着更多的通信流将会在物理通信链路上传输,从而导致网络上更大的负载。但是,对于整个TTE网络来说,如果每个消息都选择跳数最少的路径作为传输路径,可能会导致少量链路的负载过大,导致整个TTE网络的传输性能下降。

2.3 目标函数的确定

网络体系结构的成本定义为拓扑中所有物理链路的成本Cdt与交换机成本CNS之和,本文暂不考虑设备安装费用、通信信道费用如信道的距离,建立和维护等开销[15]。

(9)

在实际问题中,对于网络拓扑的工程设计方案要评价其优劣,往往需要考虑多方面因素的影响,因此本文以TTE网络中的拓扑架构成本和负载方差作为目标函数,根据实际工程需求引入一个参数m,使得在架构成本和负载均衡之间做出权衡,最终设计方案应使得目标函数尽可能小,即拓扑设计方案的成本更低,负载更均衡。

minf(X)=C(X)+m*D(i,j)

(10)

由于网络拓扑中每个节点的处理能力以及各条链路的带宽必须符合相应的限制要求,在进行拓扑优化时要考虑到各节点和链路的约束条件,因而本文采用罚函数法将有约束最优化问题转化为无约束的带有罚函数的优化问题来进行求解,并对非可行解进行相应处理。

(11)

式中,bk是传输通信流所使用的带宽,bmaxk是拓扑中通信链路的最大带宽。参数P是一个远大于目标函数值的正整数。当满足拓扑中节点和链路的约束条件时,则有bk-bmaxk≤0恒成立,此时的目标函数则有为G(X)=f(X)+P×0,此即为可行解所得的目标函数值。

根据以上几方面,考虑图4中的例子,图4描述了具有8个节点(4个ES节点和4个NS节点)的TTE网络拓扑的示例。3个通信任务分配情况为:消息m1从ES1到ES4,消息m2从ES1到ES3,消息m3从ES2到ES4。

图4 TTE拓扑优化示例

在TTE网络拓扑设计中,常用的方法是初步生成一个过度设计的拓扑,然后利用一些优化算法进行优化设计。这类方法已经被广泛的应用。图4a)为一个初始过度设计的拓扑,假设消息m1和m3是RC帧,m2是TT帧,并且消息的时序属性(帧长决定传输时间,周期和截止时间)使得消息是可调度的即负载均匀分布。假设每个NS是20个单位成本和每条物理链接是10个单位成本,图4a)具有总成本数为180(C(a)=4×20+10×10)。

通过进一步优化得到图4b)所示拓扑,其成本数为110(C(b)=2×20+7×10)。该拓扑负载是不均衡的。即所有消息都必须通过NS1。假设最坏情况时,m3必须等待m1和m2传输完后,才能继续传输,这将导致m3错过其最后期限,发生超时传输。然而,通过进一步优化网络拓扑,可得图4c)中的拓扑,其具有与图4b)拓扑相同的低成本,并且它是可调度的。此时,消息m3通过NS2到达ES4而不是经过拥塞的NS1,因此它能够达到其最终期限。

3 网络拓扑的优化方法

3.1 算法设计思想

网络拓扑优化设计的本质是路径优化的问题,我们所考虑的就是负载和路径最短之间的平衡,从而使得通过整个网络中的通信流处于相对均衡状态[15]。考虑到TTE网络具有的拓扑任意性特点,在对通信任务路径进行选择时,既不能只按照路径最短准则选择通路,又不能只按照负载最低准则选择通路。原因是前者可能会导致部分链路上的负载过大,影响整网的负载均衡;后者则会导致传输路径较长,最终引起整网负载增大的弊端。同时,由于每次计算目标函数时都需要对通信路径进行选择,可见在拓扑优化问题中选择适当路径算法的关键作用。在目标函数的约束条件较为复杂的情况下,考虑到TTE网络拓扑可根据通信业务,通过调整节点与交换机的互连关系进行设计的特点。正是这种拓扑结构的任意性使得拓扑优化问题很难采用某种解析方法去解决,而启发式算法能在有限的计算时间内寻找次优解的特点适用于对此问题的求解[16]。因此,本文将Floyd算法和模拟退火算法相结合,解决拓扑优化问题。首先在采用路径选择算法求出给定通信任务下的最短距离和最短路径的基础上,进一步使用模拟退火算法启发式地对TTE网络拓扑中的交换机和链路进行增删操作,最终确定出路径短、负载均衡兼顾成本低的网络拓扑结构。

3.2 设计转换操作

拓扑优化算法通过从当前拓扑设计方案移动到邻近拓扑设计方案来探索局部搜索空间。邻近拓扑设计方案是在当前拓扑设计方案的基础上通过使用设计转换操作来确定的,使得生成的每个邻近拓扑设计方案都使用目标函数来进行评估。

为了进一步说明算法中的设计转换操作,我们使用2.3节中图4的TTE拓扑案例。图4a)给出了拓扑优化算法的初始拓扑方案。帧f1和f2是m1消息的2个帧,f3和f4分别用于m2和m3消息。4个帧初始的虚拟连路(VL)分配情况如下:

f1: VL1为ES1→NS1→NS3→ES4

f2: VL2为ES1→NS2→NS4→ES4

f3: VL3为ES1→NS1→NS3→ES3

f4: VL4为ES2→NS1→NS3→NS4

我们假设直接设计方案是在图5a)中呈现的拓扑,其中f2在VL2为ES1→NS2→ES4上路由,其他虚拟链路由保持不变。

图5 设计转换示例

第一组设计转换操作涉及NS,即根据网络中的负载情况插入和删除NS。插入操作意味着创建一个新的NS并添加到当前的拓扑方案中以缓解部分节点处过大的网络负载。此时,所有节点以一定的概率与这个新插入节点连接,直到其1/2的端口被占用之后,在与新的NS连接的节点上路由的帧再进行重路由操作。对于删除操作,将根据网络负载情况,选取一个负载较小的NS,删除它及与其直接相连的链路。在NS被删除后,考虑涉及的所有链路。对于每个中断的路径,应用一个有门限约束的回溯跟踪,以便找到另一条连续路径,从源节点开始,尽可能遵循旧路径,创建部分路径。并在路径短的约束下探索其邻近,搜索到目的节点的另一条路径。如果找不到替代路径,则应用后退移动,并将最后一条物理链接从部分路径中移除。探索替代路径,直到找到满足连续性和距离短条件的路径或者直到部分路径变空为止。如果从初始部分路径的一组NS中不存在这样的替代路径,则选择具有可用端口的路径,创建此NS与目标之间的新连接,使路径变得连续。如果产生的解决方案不能使目标函数更优,则它将被拒绝,即这种解决方案不会被接收。

例如,如果从图5a)中呈现的拓扑结构删除NS3,则在删除之后应添加物理链路以确保m1消息的实时传输,例如添加链路NS1→ES4。拓扑结构“修复”后,通过删除组件的帧将重路由。因此,将上述删除操作应用于当前的解决方案,得到图5b)中的拓扑结构和路由:

f1: VL1为ES1→NS1→ES4

f3: VL3为ES1→NS1→ES3

f4: VL4为ES2→NS1→NS4

f2帧被进一步分配给VL2。

第二组设计转换操作是根据负载情况对携带消息帧的VL进行重新路由。此操作使得帧从源节点到目的节点会经过不同的数据流链接和交换机。

将这一操作应用于图5b),我们得到图5c)中的拓扑方案。假设这一操作是先随机选择重路由f1的VL1,由图可知VL1须通过拥塞的NS1(VL1,VL3和VL4通过)。但是,由于无法找到与f2的路由不相交的另一个不拥塞的路径,因此f1不会被重路由。如果移动选择f2,它不经过拥挤路径,也将被忽略。如果f3被重路由,则找到另一个非拥塞路径,即VL3为ES1→NS2→ES3。因此VL3将在此路径上重新路由。

拓扑优化算法中使用的最后一组设计转换是增减链路。与之前的移动类似,可以根据负载分布情况从当前解决方案中插入或删除链路,以便将它连接到临近的2个随机选择的节点,其中最多有一个是ES。之后,应用重路由策略。

例如,若在图5b)中添加一个新的链路,则最可能的位置是在ES2和NS2之间。此外,考虑到拓扑方案被接受并且删除链路操作被应用,可能的删除是链接ES2→NS1。 在这一系列移动中,删除不会被拒绝,因为ES2没有断开连接。经过这一操作,f4通过VL4为ES2→NS2→ES4重新路由,产生图5c)中的拓扑方案。

3.3 拓扑优化算法设计

基于3.1节的算法设计思想,给出具体算法步骤如下:

步骤1获取网络的初始拓扑结构、通信任务分配情况及网络节点和链路的约束条件,并将初始拓扑用图的邻接矩阵a(i,j)表示;

步骤2采用Floyd算法求给定通信任务的最短距离矩阵d(i,j)和最短路径矩阵p(i,j);

步骤2.1赋初值:对所有i和j,d(i,j)=a(i,j),当a(i,j)=无穷大,p(i,j)=0,否则为p(i,j)=j;k=1;

步骤2.2根据动态转移方程:

d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]),更新d(i,j)和p(i,j);

即对所有i和j,若d(i,k)+d(k,j)>=d(i,j),则转子步骤2.3，否则d(i,k)+d(k,j)=d(i,j),p(i,j)=p(i,k),k=k+l,转子步骤2.3；

步骤2.3重复执行子步骤2.2直到k=n+l。

步骤3设定模拟退火法的相关控制参数。如初始温度T0、控制降温速度的衰减因子α,以及同一T值下的迭代次数N。

步骤4使用模拟退火算法运用3种设计转换操作启发式地增删交换机和链路以确定最终拓扑。如图6所示,由初始解X和温度初值T0开始,根据Metropolis准则,以概率e接受新解X→XNEW,对当前解重复“产生新解→计算目标函数差→接受或丢弃”的迭代,并逐步衰减T0值,从而跳出局部最优解,算法终止时的当前解即为所得全局近似最优解。

图6 模拟退火算法流程

这种拓扑优化算法均衡地考虑了网络拓扑中路径和经过各节点的负载情况,较好地解决了两者之间的矛盾且算法的复杂程度较低,可以根据通信任务较快地得到相对距离近的通信路径,非常适合于在TTE网络拓扑中使用。

4 案例研究与仿真分析

为了验证上述拓扑优化算法的正确性,对实验仿真环境进行如下设置:对图3抽象得到如图7所示的拓扑图,其中包括10个节点(节点1至6为ES,节点7至10为NS),指定的通信任务分配情况如表1所示,共31个通信任务。表中的数字表示对应行节点到列节点之间的消息数目，如从节点1到节点4之间有5条消息帧(单向)传输。针对拓扑规模,设定合适的退火参数,T0=500,衰减因子α=0.99,及同一T值下的迭代次数N=20。由于时间触发消息实际帧长范围是[64 byte,1 518 byte][13],因此,在本次仿真中,每个消息帧长设为相同值Lk=256 byte,周期设为G=4 ms,设每个NS有16个端口、20个单位成本,每条物理链路是10个单位成本,暂不考虑网络拥塞及其所引起的时延问题。

图7 抽象出的TTE网络拓扑

节点标号123456 1002513 2000221 3000112 4213020 5101000 6141100

本次仿真基于Visual Studio2015的仿真平台,利用计算机编程仿真的方法对本文提出的TTE网络拓扑优化设计算法进行分析。通过详细比较直接连接方案和在此基础上采用优化算法所得的优化设计方案,得到了图8及表2中的数据。

图8 拓扑优化仿真结果对比图

方案交换机数/台链路数/条负载均值/帧负载方差/帧网络体系代价/单位 直接设计41218.5226.754×20+12×10=200 优化设计3923.6713.553×20+9×10=150

由上述数据可以看出，与直接设计方案相比较，本文提出的优化算法所得到的设计方案通过采用3种设计转换使得交换机数量和链路数量有所减少，网络体系代价相比直接连接方案有了明显降低，负载方差从26.75降至13.55，表明负载均衡度有了很大改善，网络中的流量分布更加均匀，避免了网络拥塞的出现。总之，本文的优化算法所得到的拓扑方案针对TTE网络可根据通信业务来调整节点与交换机的互连关系的特点进行设计使得最终的拓扑结构得到优化，更加有利于实际工程应用。

5 结 论

以时间触发以太网为互连基础设施的DIMA系统为研究背景，提出了一种将Floyd算法和模拟退火算法结合的拓扑优化算法，在进行通信任务的快速路径选择基础上，结合模拟退火算法较强的局部搜索能力，生成一个负载均衡兼顾低成本架构的网络拓扑结构。案例研究表明，该拓扑优化算法充分考虑了TTE网络通信本身具有的时间确定性和网络拓扑的任意性，可以使得整体网络拓扑架构成本更低，整个网络的结点以及链路上的负载分布更加均匀，更好地缓解在精确时间流情况下的网络拥塞问题，为DIMA系统提供了高性能且更可靠的通信环境。