基于定时的航空集群机载网络更新方法

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

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

0 引 言

航空集群作战作为未来空中作战的主要样式,已被广泛研究和深入发展。受生物集群启发,在多航空平台间形成高效信息共享,实现平台间灵活协作,突破单一平台的弱势短板,继而涌现出远超个体的强大体系作战能力[1]。

机载网络是集群成员间信息交互的基础承载,机载网络的信息交互能力是保证航空集群作战效能发挥的关键[2]。当前的机载网络组网方式固定,网络设备与内部协议紧耦合,难以实现互操作,无法满足航空集群作战的信息交互需求,制约了平台的效能发挥和体系作战能力的全面提升。

为向机载网络提供与多任务灵活耦合的网络服务,实现简单高效的网络管控,软件定义航空集群机载网络[3](software-defined airborne network of aviation swarm,SDAN-AS)应运而生。SDAN-AS吸收了软件定义网络[4](software-defined networking,SDN)中的诸多好处,如控制与转发分离、逻辑集中的网络控制以及自动化业务部署等[5-6],为机载网络的发展带来新思路的同时也伴随着新的挑战[7]。

在SDAN-AS中,依然避免不了SDN固有的网络一致性更新问题。与传统网络不同,SDN将数据平面与控制平面解耦,通过逻辑集中的控制器提供集中统一的全局网络视图,从而实现更加灵活的网络控制,快速适应如路由更新、流量工程等变化。同时这也为快速的网络一致性更新带来了挑战。

研究人员针对网络一致性更新问题开展了大量研究。主要可划分为两阶段更新和次序更新两种方法[8]。文献[9]首先提出SDN的一致性更新问题,定义了数据包一致性,并提出两阶段更新协议(two-phase update protocol,TPP)。该方法采用不同的版本号标记新旧两套转发规则,在第1个阶段,将带有新版本号的新转发规则安装到所有的内部交换机;在第2个阶段,在入口交换机将数据包打上新版本号。从而实现网络转发规则的更改,并保证数据包一致性,即每个数据包只会按照新或旧转发规则进行处理,而不会是两者的混合。该方法需要同时保存新旧两套转发规则,流表规则开销较大[10]。

次序更新[11-15]将更新划分为一系列更新阶段,在每个阶段,控制器发送更新指令到一部分交换机,在控制器接收到该阶段所有的交换机完成更新的确认消息后,进入下一阶段。通过谨慎地计算更新顺序,实现网络的一致更新。

上述两种方法都属于异步网络更新。SDN采用的集中控制仅仅是在逻辑上集中,其物理上是分散的[16]。控制器与数据平面的网络设备之间存在着固有延迟,难以实现同步的更新,只能通过控制器与数据平面的交互来协调更新顺序,大大增加了更新时间。且对于流交换场景,无法解决流交换带来的更新死锁问题,难以实现网络的一致性更新。

过去十多年间,时钟同步技术在计算机网络中得到充分发展,如精准网络时间协议(precision time protocol,PTP)等时钟同步协议已成为商用网络设备的普遍特性,在实际应用中能够达到亚微秒级精度。随着SDN的发展和演进,用于SDN的时钟同步协议如ReversePTP等被提出,已被纳入Openflow协议,SDN的时钟同步机制逐步完善,基于时钟同步的网络更新被提出[17-18]。文献[17]证明了流交换场景的存在是不可避免的,并提出了一种定时更新系统——TIME4,利用精准到微秒级的时钟同步进行网络中更新操作的执行,但没有涉及到具体的更新调度。文献[18]进一步提出Chronus定时更新系统,针对最小化更新时间优化问题,采用时间拓展网络进行一致性的约束分析,但在时间拓展网络中只能假定链路时延为单位时间的整数倍,无法采用真实的链路时延。

本文针对上述异步分布式系统的问题,在航空集群背景下,提出一种基于定时的更新(time-based update,TBU)方法。将时间参数与更新依赖图相结合,设计基于时间的更新依赖关系图,并针对最小化更新时间的优化问题提出贪婪依赖图更新调度算法,根据真实链路时延为更新操作分配更新时间,从而按照预定计划进行定时网络更新。网络设备在预定的时间点执行相应更新操作,控制器下发更新指令后无需进行更新顺序的协调,避免了节点间的频繁交互。

1 问题描述

1.1 网络模型

1.2 定时更新问题

NS表示网络状态,是网络中的节点、链路以及业务流转发规则的合集。为优化网络传输,通常需要根据流量变化计算出当前最优路由转发规则,并更改网络的路由转发规则,该过程即为网络更新,要求在满足网络一致属性的同时,将网络从初始网络状态NSi转变至目标网络状态NSt。

一般的网络更新方法主要针对无路由黑洞、无转发循环和无链路拥塞3种一致属性进行研究。本文采用基于隧道的转发,业务流以整体的形式迁移,不会出现路由黑洞和循环转发问题。因此,只需关注无链路拥塞一致性,即更新期间任意时刻网络中任意链路上可能经过的流量总和都不能大于链路容量。

如图1所示,网络中每条链路的链路容量为10个单位,存在f1与f2两条业务流,分别用蓝色和红色标注,每条业务流的传输速率都为10个单位。NSi由图1中实线部分构成,NSt则由虚线部分构成。此时,两条业务流需要交换路径进行传输,在异步更新中,无法实现同时完成更新,无论哪一条流先完成更新,都会造成链路的拥塞。而在定时更新方法中,能够实现微秒级的时间同步,同时更新两条流,避免网络拥塞的产生。

图1 流交换更新场景示意图Fig.1 Flow exchange update scenario diagram

对于定时的一致更新,由于能够实现定时的多条流同时更新,因此可以将更新划分为k个阶段,对于第i个阶段(1≤i≤k),定义一个更新时间ti。在ti时刻,阶段i中所有的操作同时完成更新。在任意时间,都不会破坏网络的一致属性。

2 TBU方法

通过PTP能够实现精准到微秒级的时钟同步[19]。本节以TIME4系统为基础,提出TBU方法,将时间参数与依赖图相结合,设计基于定时的更新依赖图(time-based dependency graph,TBDG),并提出贪婪调度算法计算更新调度。

2.1 TBU方法流程描述

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

阶段 2控制器根据网络状态信息将一系列更新操作生成TBDG。再执行TBDG调度算法,为每个更新操作分配一个更新时间。将包含更新时间的更新消息下发到数据平面中对应的交换机。

阶段 3每个接收到更新消息的交换机提取出更新消息中的更新时间,并在其相应的更新时间点完成更新操作的执行,直至所有交换机完成更新,最终完成整个网络更新。

TBU方法流程如图2所示。

图2 TBU方法流程图Fig.2 TBU method flow chart

2.2 TBDG设计

TBDG采用有向线段将更新操作、链路资源、时间标记、资源标记等元素相互连接起来,用于展现更新操作执行之间复杂的相互依赖关系。

在TBDG中,存在更新操作和链路资源两种节点,分别以圆形和矩形表示。更新操作节点用集合O表示,链路资源节点用集合R表示。每一个更新操作节点o∈O表示添加、修改或删除流表规则。每一个链路资源节点r∈R表示该链路上的可用链路带宽资源。从一个更新操作节点o1指向另一个更新操作节点o2的有向边,表示o2依赖于o1,即o2必须在o1被执行后才能执行;从一个更新操作节点o指向一个链路资源节点r的有向边,附加时间标记tmark和链路资源标记rmark,表示r依赖于o,即o被执行tmark个时间单位后将会释放rmark个单位的链路资源到r上;从一个链路资源节点r指向一个更新操作节点o的有向边,附加时间标记tmark和链路资源标记rmark,表示o依赖于rmark,即o被执行tmark个时间单位后将会占用r上rmark个单位的链路资源。

如图3所示,图3(a)中每条链路的容量都为10个单位,存在f1与f2两条业务流,分别用蓝色和红色标注,每条业务流的传输速率都为10个单位。NSi由图1中实线部分构成,NSt由虚线部分构成。根据NSi和NSt可生成TBDG如图3(b)所示,图中节点含义在表1中进行详细描述。

图3 TBDG构建示意图Fig.3 Schematic of TBDG construction

表1 TBDG中的节点含义Table 1 Node meaning in TBDG

3 算法描述

本节对本文所提定时更新方法中的相关算法进行详细描述。

3.1 TBDG生成算法

在定时更新的阶段2,控制器执行TBDG生成算法,根据当前和目标网络状态生成TBDG。TBDG生成算法针对每一条业务流依次进行计算。首先生成添加、删除和修改规则的更新操作节点,并添加操作节点之间的依赖关系。然后生成修改规则的更新操作所需要占用和释放的链路资源节点。最后添加资源节点与操作节点之间的依赖关系,并添加相应的时间标记和资源标记。TBDG生成算法如算法1所示。

算法1 TBDG生成算法输入:初始网络状态NSi;目标网络状态NSt输出:TBDG1foreachf∈Fdo2 foreachv∈Pnf-sdo3 生成添加隧道的操作节点oadd4 endfor5 foreachv∈Pof-sdo6 生成删除隧道的操作节点odel7 endfor8 生成修改流量分配权重的操作节点omod9 添加从oadd指向omod的边10 添加从omod指向odel的边11 foreache∈Pnfdo12 生成对应链路e的资源节点,记为r-13 计算从源节点s到该链路的时延tc14 添加从r-指向o*的边,附加rmark=df,tmark=tc15 endfor16 foreache∈Pofdo17 生成对应链路e的资源节点,记为r+18 计算从源节点s到该链路的时延tc19 添加从o*指向r+的边,附加rmark=df,tmark=tc20 endfor21endfor

算法第2～8行根据NSi和NSt生成要添加、删除和修改的操作节点;算法第9～10行添加操作节点之间的依赖关系,由于添加和删除隧道只与交换机内存有关,因此不会与链路资源节点产生依赖关系;第11～20行生成链路资源节点,并添加链路资源节点与更新操作节点之间的依赖关系,将业务流的需求作为带宽资源标记,将链路的时延作为时间标记附加到有向边上,表示更新操作的执行对链路资源的需求和释放以及相对应的时间。

3.2 贪婪调度算法

在生成TBDG之后,控制器需要为每个更新操作oi分配一个更新时间ti。但最小化总更新时间是NP难问题。因此，本节设计了一种贪婪调度算法。将时间划分为时间步,根据TBDG中包含的节点之间的依赖关系,在每个时间步调度尽可能多的更新操作,同时不违背网络的一致属性,即在任意的时间点任意的链路上的负载不能超过其链路容量。

首先,将时间划分为离散的时间步,即T={0,1,…}。文献[18]假设网络中的链路时延相同并设为单位时间。本文考虑了真实的链路时延,将链路时延的平均值设为单位时间。

然后,按照时间步进行迭代,在每一个时间步i,计算出可以同时执行的最多数目的更新操作集合Si;更新TBDG后进入下一个时间步,直至所有的更新操作都被更新。从而将计算出合适的更新调度S={S1,S2,…,Sk}。贪婪调度算法每次贪婪地寻找最多数目的更新操作,从而减少执行更新占用的总时间步数目,即可减少网络更新时间。贪婪调度算法如算法2所示。

算法2 贪婪调度算法输入:TBDG输出:更新调度S1i=0;S0=Φ;变量初始化2whilei≥03 Si=Φ4 foreacho∈Oadddo5 Si=Si∪o;Oadd=Oadd-o6 endfor7 foreacho∈Odeldo8 ifo不存在父节点then9 Si=Si∪o;Odel=Odel-o10 endif11 endfor12 foreacho∈Omoddo13 ifCanSchedule(i,Si,o)then14 Si=Si∪o;Omod=Omod-o15 endif16 endfor17 TBDG=TBDG_ITERATE(TBDG,tmark);执行TBDG迭代算法18 i=i+119 ifTBDG中不存在更新操作then20 终止算法21 endif22endwhile

算法第1行对时间步和更新调度进行初始化;第2～22行对时间步进行迭代,计算出在每个时间步i能够执行的最多数目的更新操作集合Si。其中第4～6行表示计算能够执行的添加规则操作;第7～11行表示计算能够执行的删除规则操作;第12～16行表示计算能够执行的添加修改规则操作,通过第13行的CanSchedule算法检测该操作是否能够执行,能够执行则该算法返回结果为true,否则返回false;第17～21行表示计算完每个时间步的更新调度后,需要执行TBDG迭代算法对TBDG进行迭代,并进入下一个时间步,直至TBDG中所有的更新操作都被执行。

3.2.1 CanSchedule算法

在计算能够执行的添加修改规则操作时,需要执行CanSchedule算法遍历Omod中的所有更新操作节点。首先假设该节点o能够在时间步i时执行,将o加入更新调度Si中,而后执行TBDG迭代算法,若存在其父节点r的可用链路资源不足,则说明该操作无法执行,返回False值,否则返回True值。CanSchedule算法如算法3所示。

算法3 CanSchedule算法输入:TBDG;时间步i;更新调度Si;更新操作o输出:True或False1Si=Si∪o2foreachr∈o的父节点3 TBDG=TBDG_ITERATE(TBDG,tmark);执行TBDG迭代算法4 ifrmark<0then5 returnFalse6 终止算法7 endif8endfor9returnTure

3.2.2 TBDG迭代算法

在计算完每个时间步的更新调度后,进入下一个时间步,需要执行TBDG迭代算法对TBDG进行迭代。

TBDG迭代算法对更新操作集合Si中的每一个更新操作进行遍历。由于Oadd中的添加规则操作和Odel中的删除规则操作只与Omod中的修改规则操作存在依赖关系,与链路资源节点无关,因此执行操作后只需在TBDG中删除该操作及与其连接的边。对于Omod中的修改规则操作,执行操作后需要修改与其具有依赖关系的链路资源节点的可用链路资源和时间标记tmark。TBDG迭代算法如算法4所示。

算法4 TBDG_ITERATE算法输入:TBDG;更新操作集合Si,时间间隔Δt输出:TBDG1Δt=1;更新时间步初始化为12foreacho∈Sido3 ifo∈Oadd∪Odel4 在TBDG中删除o及连接o的边5 else6 foreachr属于o的父节点7 ifr指向o的边的tmark≤Δtthen8 r=r-rmark9 在TBDG中删除该条边10 else11 tmark=tmark-Δt12 endif13 endfor14 foreachr∈o的子节点15 ifo指向r的边的tmark≤Δtthen16 r=r+rmark17 在TBDG中删除该条边18 else19 tmark=tmark-Δt20 endif21 endfor22 endif23endfor

4 仿真实验及分析

本文基于Exata 5.1网络仿真软件搭建航空集群机载网络。本节对本文所提基于定时的更新方法TBU进行仿真分析,将Dionysus和TPP两种SDN更新方法作为基线算法进行对比,从而分析所提更新方法的效能。

4.1 仿真参数设置

表2为本节仿真实验中的相关参数设定。为模拟航空集群机载网络,按照作战半径,在1 000 km×1 000 km的矩形范围中随机生成20～100个网络节点。节点通信半径设定为200 km,根据通信半径生成网络拓扑连通图。节点在200～1 200 km/h的速度范围内随机运动。随机选择源节点和目的节点生成40～200条业务流,每条业务流的流量需求服从正态分布N(1,1)。业务流采用基于隧道的转发,在源节点和目的节点之间建立起一条隧道,其上的每个节点根据隧道进行相应的转发。控制器定期执行流量工程和路由算法,根据初始网络状态NSi计算出目标网络状态NSt,而后开始进行网络更新。共完成了1 000次从NSi到NSt的连续网络更新过程,并对每一次更新的数据进行统计、处理和分析。

表2 仿真参数设置Table 2 Simulation parameter setting

仿真选择对比的更新方法描述如下。

(1)Dionysus:该算法为动态次序更新方法,首先根据网络状态生成更新依赖图,而后按照依赖图进行动态的异步更新。

(2)TPP:该算法为两阶段更新协议,采用版本号对新旧两套流表规则进行标记和区分,第1个阶段在内部交换机上添加新流表规则,第2个阶段在入口交换机上修改数据包版本号。

4.2 仿真结果分析

(1)更新时间比较

图4为网络更新时间的比较,更新时间为从初始网络状态转变到目标网络状态的一次完整的网络更新所需要的时间。

从仿真结果可以看出,与Dionysus和TPP相比,TBU方法在更新时间上降低了约50%～60%,业务流数目越多效果越明显。由于Dionysus基于依赖图进行动态的更新,因此更新时间要短于TPP。在Dionysus和TPP中,更新顺序协调占据了大量的更新时间[20],而TBU采用定时的更新,为每个更新操作预先分配时间点,避免了异步更新方法中的复杂更新顺序协调,减少了节点频繁交互带来的高延迟;并且能够通过多业务流同时更新解决流交换场景中的死锁问题,因此能够显著降低网络更新完成时间。

图4 更新时间比较Fig.4 Update time comparison

(2)更新死锁率比较

图5为网络更新期间更新死锁率的比较。由于更新操作与链路资源之间存在依赖关系。当更新操作与链路资源相互依赖形成环路,将会导致更新死锁。从仿真结果可以看出,更新死锁率随着业务流数目增加而增加。Dionysus和TPP两种方法的更新死锁率较高,约为10%～18%,而TBU方法始终保持较低的更新死锁率,约为1%～2%。TBU方法能够通过多业务流同时更新解决更死锁问题。有效降低了更新死锁率。

图5 更新死锁率比较Fig.5 Update deadlock rate comparisons

(3)拥塞流数目比较

图6为网络更新期间拥塞流数目的比较。拥塞流数目即在更新期间产生网络拥塞的流的数目。

从仿真结果可以看出,Dionysus和TPP始终存在约20%的业务流拥塞,两者在拥塞流数目上相近。而在TBU中,在业务流数目较小时,拥塞流数目始终为零。在业务流数目较大时,存在极小程度的拥塞,约占总业务流的2%。这是由于TPP方法无法解决拥塞问题,只能保持更新期间的数据包一致性,无法保持无拥塞一致性;Dionysus方法无法避免依赖图中的死锁问题,只能用过降低业务流速率来缓解死锁。而TBU方法通过实现多业务流的精准定时更新,能够较好的解决更新死锁问题,从而显著降低更新期间的网络拥塞。

图6 拥塞流数目比较Fig.6 Comparison of congested flows numbers

(4)规则开销比较

图7为网络更新期间规则开销的比较。规则开销即在更新期间添加、删除和修改的流表规则的数目。

图7 规则开销比较Fig.7 Comparison of overhead of rules

从仿真结果可以看出,3种方法的流表规则数目均随业务流数目的增加呈线性增长。但TBU与Dionysus在规则开销上相近,而TPP的规则开销约为前两者的2倍。这是由于TBU与Dionysus都基于依赖图进行调度,TBU方法中将时间参数与依赖图相结合,不会对规则开销产生影响。而在TPP方法中,由于在更新期间需要同时存在新旧两套流表规则,因此产生较高的规则开销。

5 结 论

本文针对异步网络更新方法更新时间长、难以解决更新死锁的问题,为软件定义航空集群机载网络设计了一种定时更新方法:① 提出的定时更新方法与异步更新方法相比,更新时间降低了约50%～60%,显著提升更新速度。② 提出的定时更新方法利用多条流同时更新解决更新死锁问题,与异步更新相比,更新死锁率和拥塞流数目均有显著降低。③ 所提定时更新方法能够满足软件航空集群场景下的快速一致网络更新需求。