软件定义航空集群机载网络自适应更新策略
2021-05-29邹鑫清陈柯帆胡诗骏
邹鑫清， 吕 娜， 陈柯帆， 胡诗骏
(1. 空军工程大学信息与导航学院， 西安， 710077； 2.空军装备部上海局驻芜湖地区军代表室， 安徽芜湖， 241000)
近年来，随着现代战争逐步趋向信息化和网络化，航空作战平台的更新换代正向智能化快速发展。为了更好地协调、重组各类航空作战平台，以积极应对未来未知战场环境带来的挑战，衍生于生物集群的航空集群概念被提出[1]。航空集群是由规模一定、功能多样的有人/无人航空平台组成，集群成员间通过简单、智能和高效的协作完成复杂任务。
机载网络作为航空平台间信息交互的枢纽，是航空集群成员间进行灵巧协同配合的重要基础。但长期以来，机载网络从传统的“链”(航空数据链)发展到“网”(航空自组织网)，都是针对特定作战场景所设计，仅能满足特定作战任务的需求，且网络自身的灵活性、可扩展性及互操作性较差，难以满足未来网络中心战作战环境中不同系统间的信息交互需求[2]。
软件定义网络(software-defined networking, SDN)作为近几年发展迅猛的一种新型网络范式[3]，为当前机载网络面临的困境提供了全新的突破方法。SDN将网络的控制平面和数据平面分离，基于可编程的开放接口，通过逻辑集中的控制器实现对网络更灵活、细粒度地管理[4]。由于SDN的优势恰好可以弥补机载网络的缺陷，文献[5]将SDN的概念与技术应用于机载网络中，构建了新一代面向航空集群的网络——软件定义航空集群机载网络(software-defined airborne network of the aviation swarm, SDAN-AS)，为机载网络未来的发展方向提供了重要参考和借鉴，但却没有对SDAN-AS存在的具体关键技术问题进行深入挖掘与研究。
作为SDN网络运行的基础，网络更新问题一直受到相关研究者的广泛关注[6]。为保证业务传输的连续性，当网络链路、节点、拓扑等状态发生变化时(如节点故障、链路拥塞等)，需要对网络进行适应性调整，如改变传输路径、调整链路负载等，通常称为网络更新。网络更新问题是通信网络的基础性问题，更是SDN控制平面的核心问题，直接关系到网络运行效率和业务通信质量[7]。
目前SDN网络更新问题的研究普遍基于拓扑相对稳定、链路质量相对可靠的有线网络环境，针对多样性业务传输下的网络拥塞问题研究相应的网络更新策略。对于航空集群，由于其OODA的闭环作战需求，SDAN-AS的业务具有与SDN有线网络具有相同的多样性特点；但是航空集群成员移动速度较快、成员相对位置变化频繁，且存在敌方干扰的情况，导致SDAN-AS的链路状态高度不稳定，从而加剧了链路拥塞和业务传输的不连续，严重影响SDAN-AS的业务转发效率。
针对上述问题，从解决SDAN-AS链路拥塞、提升业务转发效率的角度，首先通过FLIP混合更新算法对各业务流的更新顺序进行规范，得到表示更新顺序的操作序列；在此基础上，设计链路拥塞的感知算法，并在混合更新算法中加入链路拥塞的感知，对操作序列加以约束条件，进一步改进混合更新算法提出基于拥塞避免的网络更新算法(congestion avoidance based algorithm of update, CA-AU)，以增加链路感知能力，减少链路拥塞的发生，从而提高SDAN-AS的业务转发效率及网络更新可靠性。
1 相关理论与模型构建
1.1 理论介绍
现有针对SDN网络的更新算法主要分为3类，分别为：次序更新[8]、两阶段提交更新[9]以及混合更新[10]。其中，次序更新通过计算交换机转发规则的替换顺序来保证网络更新的准确和可靠，当网络规模较小时该方法具有较高的可靠性且更新速度较快、效率较高；两阶段提交更新通过在交换机上同时保留业务流的新、旧转发规则，并在网络入口给业务流打标签，决定业务流的转发规则来保证网络更新的准确和可靠。但研究发现，当网络规模较大、交换机数量较多时，使用次序更新方法可能无法保证网络更新过程的准确和可靠；而当存在交换机的内存不足以额外存储一套新的转发规则时，无法使用两阶段提交更新方法。可以看出，当航空集群规模较大时，次序更新方法不适用；当集群成员存在内存不足的情况时，两阶段提交方法不适用。因此，本文后续基于混合更新方法，加入对链路拥塞的感知，提出适用于航空集群机载网络的更新策略。下面对混合更新算法——FLIP(fast lightweight policy)进行介绍。
算法首先将更新问题分解至每一条业务流，并对每条业务流独立计算各自的操作序列。算法以一个网络更新问题作为输入，具体内容包括：网络初始状态(拓扑、节点和链路的相关信息)、最终状态下的路由以及需要维护的给定策略。算法输出为所有业务流子操作序列混合所得的操作序列。其中，后一个子序列中的任何操作需在前一个子序列中的所有操作完成后执行。
算法首先提取各操作之间的顺序来保证更新过程中的转发正确性，不出现更新过程中的中间状态无可匹配的下一跳转发节点，或数据包在有限节点间相互转发的情况。其次，提取保留给定策略的约束条件，以保证更新过程中不违背给定的转发规则。当保留给定策略约束条件与部分转发正确性约束条件之间存在矛盾时，需要求解线性规划以确定一组更新开销最低的更新操作序列。
1.2 场景及架构描述
图1直观地展示了SDAN-AS的基本架构。与SDN相同，SDAN-AS将整个网络在逻辑上由南到北分割成3个平面，分别为数据平面、控制平面和应用平面[9]。其中，数据平面由负责数据存储与转发的网元设备组成(简称为数据转发设备)。这些数据转发设备的通信系统通常搭载于航空集群成员中的中小型空中平台(例如战斗机、侦察机、电子干扰机、无人机等)之上。控制平面由负责逻辑集中地掌控网络全局的网络控制器组成。这些网络控制器的通信系统通常搭载于航空集群成员中的大型空中平台(例如预警机和指通机)之上[11]。通过南向接口，网络控制器可以及时地掌握全局网络视图并向底层的数据转发设备下发相关指令消息。通过北向接口，网络控制器能够向上层实时地反馈底层网络状态信息，以便网络应用根据网络的实际情况进行动态调整，达到全网最优。应用平面由网络需要的、用户定义的各种业务与应用组成[12]。
图1 SDAN-AS网络架构
为了更加直观地对SDAN-AS网络更新问题进行描述，本文将SDAN-AS网络建模为一个无向图Ω=(V,E,C)，其中V={v1,v2,…,vM}表示网络拓扑内的全体节点的集合，M表示拓扑内节点的数量。E={(vs,vd)|vs,vd∈V}表示网络拓扑中链路的集合；C表示全体控制器集合，其构成SDAN-AS网络的控制平面。显然有C⊆V。接下来针对SDAN-AS网络更新中的相关变量进行定义：W={w1,w2,…,wm}表示当前网络更新过程中的待更新节点集合，显然有W⊆V，m表示待更新节点数量；Λ={f1,f2,…,fn}表示待更新业务流集合，n表示待更新业务流数量。
2 基于拥塞避免的SDAN-AS自适应更新策略
2.1 总体策略
图2为策略流程，包括更新问题收集阶段(上半部分)和更新操作约束求解阶段(下半部分)。
图2 基于拥塞避免的SDAN-AS自适应更新策略流程图
其中，更新问题收集阶段实现了SDAN-AS当前网络状态的采集以及更新问题的初步解析。具体包括①当前网络状态信息的采集。SDAN-AS网络控制器对当前网络状态信息进行采集，采集的信息包括：网络拓扑、节点和链路的相关信息(包括节点间链路的链路容量、网络中处于传输状态的业务流的优先级以及占用的链路容量等)。②业务流转发路径的采集。控制器通过北向接口，从应用平面获取高层次网络控制逻辑以及网络管控需求，包括网络更新完成后需实现的业务流的转发路径以及更新过程中需保留的给定策略。
更新操作序列求解阶段生成网络更新操作序列，实现SDAN-AS网络数据转发策略的更新，并保证更新过程中的一致性。该阶段包括：
1)网络更新问题的分解。根据更新问题收集阶段输入的网络初始转发策略、规划的转发策略、保留的给定策略以及预测的链路状态，提取出每条业务流需要保留的转发规则以及转发正确性需求，作为FLIP算法的输入。此外将链路状态信息作为基于拥塞避免的SDAN-AS更新算法的输入，具体算法细节将在2.2节阐述。
2)连接一致性与策略一致性约束条件计算。FLIP算法中的基本操作类型包括：①规则替换操作rep(s,f)，在节点s上对业务流f执行的以最终规则替换当前规则的操作；②标签操作tag(s,f,θ)，在节点s上对业务流f执行对其所有数据包打上标签θ的操作；③匹配操作match(s,f,θi,θf)。在节点s上执行安装初始和最终规则，并对业务流f中的新数据包打上标签θf、旧数据包打上标签θi的操作。当保证连接一致性与策略一致性的约束条件存在矛盾时，需迭代求解线性规划问题：
(1)
该线性规划问题的目标为寻找一组更新操作序列，使更新开销最低。其中，constrains onrep(i,f)表示全体替换操作的次序约束，当该线性规划问题无解时，通过标签-匹配操作取代更新序列中部分节点替换操作，从而化解约束矛盾，最终计算得到该线性规划问题最优解更新序列作为算法输出。
因此，根据网络更新的连接一致性与策略一致性需求，基于FLIP算法分别计算每条业务流的更新操作序列。首先通过线性函数求解该条业务流的规则切换操作序列rep(s,f)。若该线性函数无实解，则通过基于两阶段提交机制的标签-匹配操作tag(s,f,θ)-match(s,f,θi,θf)，代替部分节点的rep(s,f)操作，生成新的操作序列。
3)容量一致性约束条件计算：基于FLIP计算得到的业务流操作序列，根据网络更新的容量一致性需求，通过基于拥塞避免的自适应更新算法以及排队退避算法对网络更新的容量一致性约束进行计算，提取新的业务流更新操作次序约束。若现有更新操作无法避免更新过程中产生的拥塞，则进一步通过排队退避算法，将部分低优先级业务流加入拥塞链路前序节点的缓存队列中，待高优先级业务流完成更新后释放缓存恢复转发。
2.2 基于拥塞避免的SDAN-AS更新算法
2.2.1 SDAN-AS网络更新拥塞感知
算法1 链路拥塞感知算法
输入：F,VOL,CAP
输出：C，Ψ
1)C=∅
2)fori=1→ndo
4)endfor
5)forekinEdo
6)volek=0,Ψek=∅,i=1
7)whileek∈Traceido
8)volek=volek+voli
9)Ψek=Ψek∪fi
10)i=i+1
11)endwhile
12)ifvolek>capek
13)C=C∪ek
14)endif
15)endfor
设计SDAN-AS网络更新拥塞感知算法如下。算法输入包括全体待更新业务流路径集合F={Fi|1≤i≤n}、占用的链路容量VOL={voli|1≤i≤n}、当前网络中全体链路的容量CAP={capek|ek∈E}，其中E表示网络中全体链路集合。算法输出为潜在拥塞链路集合C以及各链路经过的业务流集合Ψ。此外，Tracei表示业务流在更新过程中所有转发路径遍历的链路集合。
算法1第1行对链路拥塞感知集合进行初始化；第2～4行计算得到全体业务流在更新过程中所遍历的链路；第5～15行计算链路拥塞状态，其中第7～11行计算每条链路上可能经过的业务流量，若超出该条链路的容量，该条链路在更新过程中可能出现拥塞情况，将被加入集合C，同时将该条链路上可能经过的业务流加入集合Ψ中。
2.2.2 基于拥塞避免的自适应更新算法
根据总体更新策略，在获取网络更新过程中的链路拥塞状态后，通过基于拥塞避免的自适应更新算法计算混合更新操作序列约束。
算法2 基于拥塞避免的自适应更新算法(CA-AU)
输入：网络更新流相关信息I=(PRI,SEQ,VOI,F)
拥塞状态信息L=(C,Ψ,CAP)
输出：混合更新操作序列约束集合Cons
1)Cons=∅
3)forfiinΨekdo
5)m=j
6)else
7)continue
8)endif
9)Ωi=∅,Γi={fx∈Ψek|prix 10)forfjinΓido 12)Ωi=Ωi∪fj 14)endif 16)break 17)endif 18)endfor 20)QueueRetreat() 21)endif 22)endfor 算法2第1行首先对混合更新操作序列约束集合Cons进行初始化，之后通过第2～24行，逐链路添加混合更新操作序列约束。其中，第4～9行判断流在更新后的转发路径是否经过当前潜在的拥塞链路，若经过则记录造成拥塞的更新操作序号，否则，继续分析更低一级优先级的业务流更新操作子序列。第10～19行依次在优先级低于fi的业务流更新操作子序列中搜索可释放链路容量的更新操作，并添加进混合更新操作序列约束集合Cons中。若在Ψek中搜索完毕后，ek的链路容量仍无法保证无拥塞更新，此时调用排队退避算法QueueRetreat()，对ek上的部分低处理优先级业务流添加排队退避以及恢复转发更新操作约束。本文对排队退避操作以及恢复转发操作定义如下： 定义1 排队等待操作queue(f,v,e)：在节点v上将业务流f中通过链路e转发的数据包加入缓存队列中，此时业务流f暂停在链路e上的传输，但不影响流f在该节点上的更新。 定义2 恢复转发操作recov(f,v,e)：在节点v的缓存队列中，将属于业务流f的数据包通过链路e转发。显然，对于一条业务流f，存在约束：queue(f,v,e) 算法3QuecueRetreat( ) 输入：网络更新流相关信息I=(PRI,SEQ,VOI,F) 拥塞状态信息L=(C,Ψ,CAP) fi的更新退避业务流集合Ω Ψek中优先级低于fi的业务流集合Γi 输出：排队退避约束集合Cons_QRi 1)Cons_QRi=∅,Φi=∅ 2)whileΓi≠∅ 6)endif 8)break 9)endif 10)endwhile 11)whileΦi≠∅ 12)l=1 16)l=l+1 17)endwhile 算法3输入包括待更新流相关信息I=(PRI,SEQ,VOI,F)；拥塞状态信息L=(C,Ψ,CAP)；流fi的更新退避业务流集合Ωi；Ψek中优先级低于fi的业务流集合Γi。输出为业务流fi的排队退避约束集合Cons_ORi。算法中Φi表示流fi的排队退避业务流集合，数组quei与reci分别保存了排队退避操作与恢复转发操作，若有j 图3给出一个基于拥塞避免的自适应更新算法示例。图中共有fi、f2与f33条待更新业务流,优先级pri1 同理，对于潜在拥塞链路[F,C]，为保证f1的无拥塞更新，在Ψ[F,C]={f1,f3}中搜索f3的更新操作子序列。不同的是，f3在更新前后均经过了链路[F,C]，无法通过更新退避约束实现f1的无拥塞更新。此时调用QueueRetreat()算法，并添加排队退避约束条件queue(f3,F,[F,C]) 经过链路拥塞感知算法可以计算得到潜在的拥塞链路为:C={[E,G],[F,C]},两条链路上经过的业务流集合分别为:Ψ[E,G]={f1,f2}和Ψ[F,C]={f1,f3},然后通过基于拥塞避免的自适应更新算法计算混合更新操作序列的约束'对于潜在拥塞链路[E,G],首先计算保证高优先级业务流f1的无拥塞更新的约束条件,在Ψ[E,G]={f1,f2}中搜索低优先级业务流f2的更新操作子序列。其中,操作可以在使f2的转发路径从链路[E,G]切 换为[E,H]从而释放链路[E,G]上的容量,且此时满足∑Ψ[E,G]vol-volf2≤capek，即在执行操作rep(E,f2)后链路上不再产生拥塞。因此，添加混合更新操作序列约束rep(E,f2) 同理，对于潜在拥塞链路[F,C]，为保证f1的无拥塞更新，在Ψ[F,C]={f1,f3}中搜索f3的更新操作子序列。不同的是，f3在更新前后均经过了链路[F,C]，无法通过更新退避约束实现f1的无拥塞更新。此时调用QueueRetreat()算法，并添加排队退避约束条件queue(f3,F,[F,C]) 本节将CA-AU更新策略与几种典型的SDN更新算法在SDAN-AS网络环境下进行仿真分析，并对几类关键性能指标进行比较，验证CA-AU的性能。选取的对比更新算法包括次序更新算法、FLIP混合更新算法以及zUpdate更新算法[13]。选取的性能评价指标为更新平均排队时延和平均更新成功率。仿真参数设置如表1所示，其中，网络中各业务流所占用的链路容量服从均值为5，方差为1的正态分布；各业务流优先级服从最小值为1，最大值为10的均匀分布。仿真实验参照Rocketfuel拓扑[14]，实验过程中可对网络中节点进行增减。当对指定自变量参数进行仿真分析时，其他自变量参数设置为平均值。 表1 仿真参数 图4为一次成功的网络更新过程中，各待更新业务流的平均排队时延随网络规模变化的趋势。 图4 排队时延与网络规模关系 参与对比的更新策略分别为CA-AU策略与FLIP混合更新算法，通过对比可以发现，随网络中节点数量的提升，FLIP与CA-AU的排队时延均呈现指数式上升的趋势。而FLIP的平均排队时延始终远高于CA-AU。在网络规模为20个节点时，平均时延已接近100s，其原因在于FLIP算法虽然充分考虑了单条业务流的转发正确性需求与给定策略需求，但没有考虑链路拥塞对网络更新的影响。拥塞现象易造成网络需要通过多次序列计算以及指令下发过程才能最终成功完成更新；相比之下，CA-AU的更新平均时延显著降低，随网络规模增至120个节点，其平均时延始终保持在10s以下。CA-AU的平均更新排队时延主要来源于低优先级业务流的主动排队退避。 图5为一次成功的网络更新过程中，各待更新业务流的平均排队时延随待更新业务流变化的趋势。在该组实验中，网络规模设置为70个节点。仿真结果表明，随业务流的增长，各流平均更新排队时延呈现更加急剧的指数增长，原因在于业务流数量的增长直接造成网络中链路拥塞现象的加剧，从而导致FLIP算法执行时，需要更多次的更新周期完成一次成功的网络更新；而对于CA-AU算法，拥塞链路的增加也造成低优先级业务流需要在更多的拥塞链路的前序节点上进行排队退避。但排队退避所引起的平均排队时延相较于FLIP算法仍显著降低。 图5 排队时延与业务流量关系 图6为一次成功的网络更新过程中，待更新业务流的平均排队时延随平均飞行速度之间的关系。为验证CA-AU在SDAN-AS高度动态的网络环境下的适应性，在该组实验中选取了zUpdate无拥塞更新策略作为对比。zUpdate是一种数据中心网络环境下的无拥塞更新方案，通过对比可以发现，随着飞行速度的提升，zUpdate与CA-AU的平均更新排队时延均明显上升，表明随着网络动态性的提升，zUpdate与CA-AU的适应性均有一定程度的下降。其中，zUpdate的平均排队时延在飞行速度较低时低于CA-AU，这是因为zUpdate可提供无拥塞的更新方案，而CA-AU则需要对部分低优先级的业务流进行主动的排队退避。然而随平均飞行速度的提升，zUpdate的平均排队时延急剧上升，并在飞行速度达到500km/h时开始高于CA-AU。这是因为CA-AU策略通过链路拥塞感知，对潜在的拥塞链路进行了更新约束的计算，相比于适用于静态网络环境的zUpdate，在动态网络环境下具有更高的容错与适应性能。 图6 排队时延与飞行速度关系 图7为网络更新成功率随网络规模的变化趋势，该组仿真实验选取次序更新作为对照，在不同规模下的网络中，采用相同的网络拓扑各执行100次重复实验。可以发现，随网络规模的提升，次序更新的更新成功率均呈指数式下降，随网络规模的提升，次序更新与CA-AU更新成功率的差距持续增大，当网络规模达到120个节点时，更新成功率降至20%以下。而CA-AU的更新成功率虽也随着网络规模的提升而下降，但在网络规模提升至120个节点的过程中始终保持在90%以上。该实验结果表明，在链路状态不稳定的机载网络环境下，基于混合更新的CA-AU相比于次序更新的可靠性有了大幅提升，同时也表明相比于次序更新，CA-AU具有更强的鲁棒性，可在更加复杂的网络环境下获取理想的更新效率。 图7 更新成功率与网络规模关系 本文面向软件定义航空集群机载网络的特殊复杂环境，研究适用于该网络的更新策略。首先，基于混合更新算法计算理想链路状态下业务流的更新操作序列，随后针对每条业务流做拥塞链路的感知，并根据链路拥塞情况提出拥塞避免算法，基于业务流优先级生成无拥塞的更新操作约束，以实现网络更新的准确、可靠性。仿真结果表明，本文提出的更新策略在更新过程中降低排队时延的同时，提高了更新的成功率。
3 仿真结果与分析
4 结语
