一种面向航空集群机载网络的分布式更新方法

陈 坤, 吕 娜, 朱海峰, 方 宇

(空军工程大学信息与导航学院，西安，710077)

航空作战力量在现代战争中往往占据着一定战略地位，建设和发展航空网络的重要性不言而喻。现代军事思想不断衍生发展，未来航空集群作战的理念已被广泛认同[1-2]。为满足航空集群多平台多任务灵巧协同作战的需求，有研究人员将软件定义网络(Software-defined Networking, SDN)的思想运用在机载网络中，提出软件定义航空集群机载网络(Software-defined Airborne Network of Aviation Swarm, SDAN-AS)，赋予了机载网络灵活的网络控制和管理、自动化可编程的业务部署，从而提供与多任务灵活耦合的网络服务[3]。SDN的引入能够突破单个作战平台的效能瓶颈，多平台之间展开的灵活、高效协同能够弥补单一平台的弱点，从而形成优势互补的强大体系作战能力[1-3]。

在SDAN-AS中，也同样避免不了SDN固有的网络一致性更新问题，一致性更新是所有集中式控制的网络都面临的问题，即如何在改变网络配置期间保持网络的一致属性(如无路由黑洞、无转发循环和无链路拥塞)[4-6]。但由于控制器与交换机之间存在着固有延迟，即使同时发送更新指令，指令也难以同时到达所有的交换机。即使同时到达所有的交换机，完成更新的时间也难以同步。因此无法同时进行整个网络的更新，现有更新方法往往需要通过多个轮次来进行[7-8]。

网络的一致性更新近些年来受到广泛关注，研究人员针对更新期间的各种一致属性开展了各类研究。文献[9]首次提出两阶段更新方法，实现了更新过程中的数据包一致属性，保证转发路径不会是新旧两套转发规则的混合。文献[10]基于两阶段更新提出增量两阶段更新方法，牺牲更新时间来降低规则开销。文献[11]提出SWAN更新系统，采用预留链路带宽的方法实现无链路拥塞的更新。文献[12]提出Dionysus动态更新系统，通过构建更新依赖图减少网络更新时间，从而加快更新速度。以上几种现有更新方法在一定程度上能够较好地保持网络更新期间的各种一致属性，但都属于集中式更新方法，往往分为很多个轮次，通过控制器与数据平面的频繁交互来协调交换机的更新顺序。控制器下发更新指令到网络中的部分交换机，收到更新指令的交换机完成更新后向控制器发送确认消息，控制器在接收到所有的确认消息后完成更新的一个轮次，开始进入下一个轮次，下发新的更新指令到网络中的交换机。在集中式更新方法中，控制器与交换机之间的频繁交互将会大大增加更新的完成时间[13-14]。同时集中式更新方法在更新过程中全程依赖控制器的计算与调度，SDAN-AS中的控制器搭载于资源有限的空中平台，难以承载较高的负荷。

本文针对上述集中式更新方法的缺点，提出一种面向航空集群机载网络的分布式更新方法，设计改进的更新消息格式，将更新依赖关系编码到更新消息中，采用询问和通知2种消息实现数据平面的分布式交互，将控制器的更新顺序协调功能转移到数据平面上进行，从而实现快速一致的分布式更新，有效降低网络更新时间。对于追求高实时性、高动态组网的SDAN-AS而言，降低网络更新时间从而减少更新期间的网络性能下降具有重要意义。

1 问题描述

1.1 网络模型

为方便描述，首先引入本文的网络模型抽象。在SDAN-AS中，通常由大型空中平台担任网络控制器。由若干个小型空中平台担任网络交换机共同构成网络的数据平面。因此可以将SDAN-AS的数据平面抽象为由若干个节点和链路连接起来的无向图G=(V,E)。其中其中V={v1,v2,…,vm}表示网络中交换机的集合，E={e1,e2,…,en}表示链路集合。对于∀e∈E，Ce表示该链路的容量。μ={μe1,μe2,…,μen}表示网络链路利用率的集合。

本文采用标准的流模型，F={f1,f2,…,fm}表示网络中的业务流集合，其中每条业务流f表示在一个源节点和一个目的节点之间的一组数据包的集合，其流量需求表示为df。控制器可以通过定期收集数据平面信息或根据带宽资源分配计算出网络中业务流需求的估计值。业务流采用基于隧道的转发，对于每条业务流，采用VLAN标签建立多条从源节点到目的节点的隧道，隧道上的每个节点根据匹配VLAN标签的流表规则进行相应的转发。

1.2 网络更新问题

G表示网络状态，即决定网络中所有业务流的数据包转发规则的集合。网络控制器定期执行流量工程，根据业务需求变化和网络拓扑信息，执行路由算法或流量调度算法计算出新的路由转发规则，Po(f)表示流f在当前网络状态Go中的旧转发路径，Pn(f)表示流f在目标网络状态Gn中的新转发路径。执行网络更新将网络从状态Go转变为状态Gn，将流量从旧转发路径迁移到新转发路径上。

由于更新的过程不是瞬态，而是异步分布式的过程。需要谨慎地协调交换机流表规则的更新顺序，否则交换机流表规则的不一致将会导致网络配置的不一致，从而产生如路由黑洞、循环转发、链路拥塞等问题[15-16]，严重影响更新期间的网络性能。为了避免网络配置的各种不一致，需要网络更新算法满足对应的一致属性。本文所设计的网络更新方法主要满足以下3种一致属性：

1)无路由黑洞一致性：更新期间网络中所有数据包都不会被丢弃。

2)无转发循环一致性：更新期间网络中所有数据包的转发不会产生环路[17]。

3)无链路拥塞一致性：更新期间网络中所有链路的负载都不会超过其容量[11-18]。

由于网络更新是异步的过程，可以将每一次网络更新U序列化为一系列的更新操作的集合，表示为U={o1,o2,…,on}，其中每一个更新操作o表示插入、修改或删除一条流表规则。为了保持更新期间的网络配置一致属性，最小化更新操作之间产生的冲突，需要安排更新操作以合适的顺序执行。由于更新操作之间具有相互依赖的关系，根据依赖关系可以建立起更新依赖图，从而根据更新依赖图计算出合适的更新顺序。

2 更新消息设计

为减缓控制器负载，直接在数据平面实现网络的分布式更新，本节设计了改进的更新消息格式，将更新依赖关系编码到更新消息中。

2.1 更新依赖图

为了更好地阐述改进的更新消息设计，首先引入更新依赖图的概念。更新依赖图是描述网络更新操作之间依赖关系的有向图。根据当前网络状态Go以及目标网络状态Gn，可以计算出从Go更新到Gn的过程中所需要执行的一系列更新操作。而后根据更新操作之间的相互依赖关系、网络链路带宽资源以及更新操作对链路带宽资源的需求等信息，可以为每一个给定当前网络状态Go和目标网络状态Gn的完整网络更新过程构建出满足其一致性要求的更新依赖图。

如图1所示，图1(a)中存在2条业务流，用不同的颜色表示，分别是源节点为1、目的节点为3的f1和源节点为2、目的节点为4的f2。每条业务流的需求都为10个单位，网络中的每条链路的链路容量为10个单位。其中实线部分表示当前网络状态Go，虚线部分表示目标网络状态Gn。

根据图1(a)的网络拓扑图生成的更新依赖图如图1(b)所示，其中圆形节点表示操作节点，操作节点与操作的对应关系如表1所示；矩形节点表示链路资源节点，表示链路e(2,3)上的可用链路带宽资源为0，指向性直线表示节点之间的依赖关系。操作C的执行将会在链路e(2,3)上释放10个单位的链路带宽资源，操作E的执行需要链路e(2,3)上具有10个单位的可用链路带宽资源。

图1 更新依赖图示例

表1 依赖图节点含义表示

2.2 改进型更新消息

为了实现分布式的快速一致网络更新，本小节设计了改进型更新消息格式，将操作之间的依赖关系编码到更新消息中。网络控制器采用改进型的更新消息来进行数据平面的网络配置，通过节点之间的分布式协调来执行网络更新。

改进型更新消息中包含以下3个字段的信息。

1)操作：表示一个任意的更新操作；

2)前置条件：表示执行该更新操作所需要预先执行的前置更新操作的组合，以逻辑布尔表达式呈现，更新操作之间采用逻辑关系式进行连接，只有前置条件满足之后才可执行该操作。

3)后置操作：表示依赖于该更新操作执行的一系列更新操作的集合。

控制器根据从数据平面收集到的网络状态信息为网络更新中的每一个更新操作计算出一个对应该操作的更新消息。控制器计算完更新消息后，同时下发所有的更新消息到对应的网络节点。节点接收到更新消息后按照以下规则进行执行。

对于一个收到更新消息的节点v：

1)只有当该更新消息中的前置条件被满足之后，才能够执行该更新消息中的操作；

2)在更新消息中的操作被执行之后，节点v向其后置操作中的所有更新操作所对应的节点发送通知消息。

前置条件中的逻辑布尔表达式由单个或多个更新操作通过&和||2种逻辑运算符连接起来。

定义1运算符&：对于任意的操作o1和o2，o1&o2表示o1与o2都被执行。

定义2运算符||：对于任意的操作o1和o2，o1||o2表示o1与o2至少存在一个被执行。

例如，若更新操作o1依赖于更新操作o2和o3的执行，则o1的前置条件为o2&o3，o2和o3的后置操作都为{o1}。前置条件和后置操作的计算在第3节中的算法2进行详细介绍。

2.3 分布式更新协调

在本文的分布式更新方法中，为数据平面上的分布式更新顺序协调定义了两种消息：询问消息、通知消息。取代了集中式更新方法中控制器的更新顺序协调功能，数据平面中的节点通过询问和通知两种消息进行分布式交互，协调更新顺序，从而减少控制器与数据平面之间的频繁交互所带来的延迟。

询问消息：当一个交换机接收到控制器发送的一条更新消息后，将会发送询问消息到其前置条件中的所有更新操作所对应的交换机，询问这些更新操作是否已执行。

通知消息：在一条更新消息中的操作被其对应的节点执行后，该节点将会发送通知消息到其后置条件中的所有更新操作所对应的交换机，从而通知这些交换机该更新操作已经执行。

询问和通知2种消息能够确保更新操作在数据平面被分布式地执行。操作之间的执行顺序完全由数据平面完成，从而取代控制器的更新顺序协调功能。网络控制器只需根据更新依赖图为所有的更新操作构造对应的更新消息并下发到数据平面，即使更新消息到达的时间不同，也能够保证更新操作按照更新依赖图中的依赖关系进行执行。

对于图1中的情况，控制器能够根据图1(b)中的更新依赖图构造出每一个更新操作所对应的更新消息，如第3节中图1的更新消息构造如表2所示。

表2 更新消息示例

当网络控制器将所有的更新消息下发到数据平面的各交换机后，由于更新操作A、B的前置条件均不存在，因此节点3接收到更新消息4后可直接执行更新操作B，向并其后置操作E所对应的节点2发送通知消息。同理，节点5在接收到更新消息5后可直接执行更新操作A，并向节点1发送通知消息。节点1接收到更新消息1后，不能立即执行更新操作C，只有在更新操作A执行之后才能更新，因此节点1需要向其前置条件(即操作C)对应的节点5发送询问消息，当节点1接收到节点5发送的通知消息后，即可执行更新操作C，并向其后置操作D、E所对应的节点2发送通知消息。

数据平面的交换机之间利用询问和通知两种消息进行分布式交互来协调更新顺序，最终完成整个网络的分布式更新。

3 分布式更新方法

3.1 更新方法流程描述

阶段1控制器根据从数据平面收集到的网络拓扑信息，将网络更新分解为一系列的更新操作。

阶段2根据网络状态信息将一系列更新操作生成更新依赖图。再根据更新依赖图计算出每一个更新操作所对应的前置条件和后置操作，构造更新消息并下发到该更新操作对应的交换机。

阶段3数据平面中的交换机接收到控制器发送的更新消息后，根据更新消息中的前置条件和后置操作开始执行分布式更新，采用询问、通知两种消息进行更新顺序的协调，从而完成数据平面的分布式网络更新。

3.2 算法描述

3.2.1 更新依赖图生成

对于更新依赖图的生成，首先根据网络所需要满足的一致属性，提取出约束条件，然后根据约束条件进行更新依赖图的生成。本文主要关注无路由黑洞、无循环转发和无拥塞3种一致属性。

无路由黑洞一致性约束：要确保添加隧道的操作在流量从入口交换机输入之前执行，删除隧道的操作要在流量迁移出该隧道之后执行。即修改入口交换机流量分配权重的操作依赖于添加隧道的操作，删除隧道的操作依赖于修改入口交换机流量分配权重的操作。

无循环转发一致性约束：由于网络采用基于隧道的转发，只有建立起一条新转发路径的隧道，才能够在其上进行数据包的转发，因此一定满足无循环转发的一致性。

无链路拥塞一致性约束：要确保更新操作的执行必须具有相应的可用链路带宽，即更新操作依赖于链路可用带宽资源，同时更新操作也会释放一些链路带宽资源。

生成更新依赖图算法如算法1所示。

算法1：更新依赖图生成算法

输入：流集合F；路径集合P；流需求集合df；

输出：更新依赖图

1.for eachf∈Fdo

2.寻找业务流f的入口交换机s

3.生成“修改s上的流量分配权重”操作节点，记为o*

4.for eachv∈Pn(f)-sdo

5.生成“在v中添加隧道Pn(f)”的操作节点，记为oadd

6.添加一条从oadd指向o*的边

7.end for

8.for eachv∈Po(f)-sdo

9.生成“在v中删除隧道Po(f)”的操作节点，记为odel

10.添加一条从o*指向odel的边

11.end for

12.for eache∈Pn(f)do

13.生成对应链路e的资源节点，记为r-

14.添加一条附加数值df，从r-指向o*的边

15.end for

16.for eache∈Po(f)do

17.生成对应链路e的资源节点，记为r+

18.添加一条附加数值df，从o*指向r+的边

19.end for

20.end for

3.2.2 构造更新消息

在生成更新依赖图之后，控制器需要为每一个更新操作构造出一条更新消息，下发到数据平面中相对应的交换机。

更新消息构造的关键是计算前置条件和后置操作，前置条件为一系列更新操作的组合，表现为逻辑布尔表达式的形式；后置操作为一系列更新操作的集合。更新消息构造算法如算法2所示。

算法2：更新消息构造算法

输入：更新依赖图

输出：更新消息

1.初始化所有操作的前置条件和后置操作

2.for eachoido

3.if ∃oj∈oi的父节点且oj∈U then

4.oi的前置条件=oi的前置条件&oj

5.end if

6.end for

7.for eachrdo

8.ifr的可用资源

9.计算r子节点优先级

10.将r子节点按照优先级从高到低排列

11.for eacho∈r子节点do

12.r的可用资源=r的可用资源-o的链路需求

13.ifr的可用资源<0 then

14.根据r的父节点计算合适的调度S

15.o的前置条件=o的前置条件&S

16.end if

17.end for

18.end if

19.end for

20.for eachoido

21.if ∃oj∈oi的前置条件 then

22.oj的后置操作=oj的后置操作∪oi

23.end if

24.end for

4 仿真实验及分析

本文的仿真实验搭建在CPU为Intel Xeon，主频为3.2 GHz，内存16 GB的商用服务器上。软件定义航空集群机载网络的场景采用Exata 5.1网络仿真平台进行搭建。本节与现有集中式网络更新方法的典型代表Dionysus更新系统进行对比，从而验证分析所提方法的性能。

4.1 仿真参数设置

仿真参数设置如表3所示。节点按照控制器计算并下发的流表规则进行数据包转发和处理。控制器在每个流量工程周期内根据当前网络拓扑重新计算新的路由转发，执行网络更新。共进行1 000次完整的网络更新过程，对每一次完整网络更新数据进行统计、处理和分析。

表3 仿真参数设置

4.1.1 更新完成时间

图2为网络更新完成时间的比较。从仿真结果可以看出，计算时间只在更新完成时间中占据了很小的比例，更新完成时间主要表现在更新顺序协调所消耗的协调时间。由于分布式更新方法采用询问与通知2种消息直接在数据平面的交换机之间进行分布式交互，避免了集中式更新中依赖控制器进行更新调度的“控制器-交换机-控制器”模式所带来的频繁交互产生的高延迟，因此能够显著降低更新协调时间。与Dionysus更新系统相比，本文提出的分布式更新方法在更新计算时间上表现近似，但在更新协调时间上降低了约40%，从而显著降低了整个更新完成时间。

图2 更新完成时间比较

4.1.2 更新协调距离

图3为本文分布式更新方法在仿真实验中更新协调距离的累积密度函数。更新协调距离表示一个更新操作执行之后向被其依赖的更新操作所对应的节点发送通知消息所需要的跳数，其累计密度函数表示不大于该更新协调距离的操作在操作总数目中所占比例。从仿真结果可以看出，在分布式更新中约20%的更新协调距离为0，即相互依赖的更新操作在相同的交换机上执行；约36%的更新协调距离为1，即相互依赖的更新操作在相邻的交换机上执行。而在集中式更新中，需要控制器与数据平面之间反复交互，每个操作的更新协调距离都至少为2。分布式更新方法利用相邻交换机之间的直接交互，大大降低了消息交互所带来的更新时间，从侧面验证了分布式更新方法在降低更新时间上的优势。

图3 更新协调距离比较

4.1.3 业务流更新时间

图4为业务流更新时间的累计密度函数对比。业务流更新时间表示单条业务流更新完成所需要的时间，其累计密度函数表示不大于该更新时间的业务流数目在业务流总数目中所占比例。从仿真结果中可以看出，在集中式更新方法中，最长的业务流更新时间约为800 ms，90%的业务流在400 ms内完成更新；而分布式更新方法中最长的业务流更新时间约为600 ms，90%的业务流在250 ms内完成更新。在同等累计密度函数下，分布式更新方法的业务更新时间比集中式更新方法更短；在同等业务流更新时间的限制下，分布式更新方法完成了更多的业务流更新。可以看出分布式更新方法在提高业务流更新速度方面表现较好。

图4 业务流更新时间

5 结语

本文针对集中式网络更新方法更新时间长、过于依赖控制器的问题，提出一种应用于软件定义航空集群机载网络的分布式更新方法。

与集中式更新方法相比，本文所提方法通过实现数据平面的分布式交互有效降低更新协调距离，减少了更新协调所需的交互次数，从而降低更新协调时间。仿真实验表明，本文所提方法与集中式更新方法相比，更新计算时间大致保持相同，更新协调时间降低了约40%，从而显著减少整个网络的更新完成时间。