面向并发业务的卫星网络服务功能链优化算法

潘成胜，梁芷铭，石怀峰，3，孔志翔，3

（1.大连大学通信与网络重点实验室，辽宁大连 116622；2.大连大学信息工程学院，辽宁大连 116622；3.南京理工大学自动化学院，南京 210094）

0 概述

随着互联网的快速发展，我国网民数量截至2019年6 月已突破8 亿［1］。由于我国通信设施建设水平处于国际领先地位，且卫星发射数量逐年增多，目前卫星在轨数已超过200颗，而传统卫星网络设计完成投入使用后，其硬件升级更新迭代的成本巨大，难以满足提升卫星性能与降低升级难度与成本的网络需求。文献［2-3］通过将传统卫星网络与网络虚拟化技术相结合，从硬件中解耦出各种网络功能需求，以解决卫星上硬件模块更新困难的问题。为增强这种抽象虚拟化对卫星的改进，相关研究认为服务功能链（Service Function Chain，SFC）可以更好地提升空间信息网络性能，即卫星将接收到的服务请求中所用到的模块功能抽象为虚拟网络功能（Virtual Network Function，VNF），并将其串联起来编排为一个有序的链式集合构成服务功能链。

目前，针对SFC 的编排可分为构建与映射2 个步骤。在构建过程中将接收到的服务请求按照既定的策略进行处理，而在映射过程中则需要考虑以下3 种情况：从通信资源方面考虑，需要最小化传输链路与卫星间及层间的跳数；从内存及计算资源方面考虑，由于卫星负载及处理能力有限，需要合理利用卫星上的资源；从链路健壮性方面考虑，应有效解决卫星节点动态失效问题［4-5］。文献［6］提出一种禁忌搜索算法的SFC 部署算法，通过设置禁忌表在全网中搜索服务功能最优的部署位置，但该算法仅考虑了资源利用率情况。文献［7］采用一种面向VNF 环境的服务功能管理机制，主要通过维特比算法在候选节点中选择部署开销最小的服务功能，以降低部署成本，但该方法缺乏对通信资源消耗的考虑。

然而，以上研究未能对通信资源、计算资源消耗进行整体优化。针对该问题，本文构建一种适用于空间信息网络的抽象模型。该模型在空间信息网络中动态拓扑形成快照的基础上，利用流量缩放因子及VNF 间的相互依附关系对服务请求构建出合理的SFC。为解决SFC 映射过程中产生的随机失效、路由规划不合理以及资源实例碎片化等问题，本文提出一种最小资源消耗映射算法，以最小资源消耗为目标形成SFC 映射路径，最终得到SFC 构建与映射间的最优解决方案。

1 空间信息网络拓扑模型

本文提出一种基于服务功能链映射的空间信息网络抽象模型，具体如图1 所示。中地球轨道（Medium Earth Orbit，MEO）层具有工作寿命长与仰角度良好等特点，在空间信息网络的构成中发挥重要作用。将在MEO 层通信范围内的低轨卫星称为在足印以内，选择一颗在低地球轨道（Low Earth Orbit，LEO）层中覆盖时间最长的MEO 卫星成为控制者，起到控制与转发功能，一颗MEO 层卫星可与足印范围中的LEO 层卫星形成集群并加以管控［8-10］。但由于空间信息网络的高动态特性，MEO 层卫星所在的足印区域内LEO 卫星会发生变化，导致MEOLEO 间的集群关系发生改变。因为同步地球轨道（Geostationary Earth Orbit，GEO）层具有对地静止的特性，且模型中所有卫星节点均对其可见，所以其可作为制定决策的控制者对网络整体进行管控，并对链路中出现MEO-LEO 的集群改变进行调整，以保证服务请求质量。这种分布式管控模型可有效缓解频繁调用GEO 造成传输时延增大所带来的缺陷，同时也保证了整个通信环境的稳定性。

图1 空间信息网络抽象模型Fig.1 Abstract model of spatial information network

本文提出的空间信息网络抽象模型工作流程如下：

步骤1当GEO 层收到服务请求后，为降低卫星上资源碎片化的消耗对其进行拆分处理，抽象成一连串的有序SFC 并形成流表，准备下发到LEO/MEO 层卫星以响应服务请求。

步骤2在GEO 层上生成的流表下发到各MEO-LEO 集群中并利用MEO 进行调配，按照流表策略在相应卫星上虚拟出所需功能，以完成映射任务。其中：MEO 卫星负责转发与LEO 的调配工作，针对卫星间的高动态性，若在某一时刻下的快照中卫星的生命周期不满足服务需求（LEO 即将脱离MEO 的足印区域），则需要MEO 关注并调配当前LEO 周围的其他LEO 对服务功能角色进行补充；若当前MEO 卫星足印中没有可以满足服务的LEO 卫星，则向GEO 卫星发出申请，并查找其他可部署的MEO-LEO 集群以满足服务请求。

步骤3LEO 接收到指令后按照流表要求完成SFC 映射以响应服务请求。流表需要安全、稳定以及可靠的约束条件，先保证链路的稳定性，再考虑资源消耗以及传输效率的情况。

2 服务功能链的编排

服务功能链的提出是为了提供一个灵活、功能配置可拓展、面向对象与可重构的一种网络服务［11］。本文提出的SFC 编排设计思路如下：首先以流量缩放因子与VNF 之间的相互依附关系为约束原则，以降低卫星上以及卫星间通信资源开销为目标对SFC进行构建，为SFC 映射找到最小资源开销路由策略奠定基础；其次考虑到星上拓扑的高动态性，采用基于A*算法的本文算法进行SFC 映射，匹配出可得到最小资源开销的路由策略。

2.1 虚拟网络功能的流量缩放因子及依附关系

随着VNF 技术的逐渐成熟，一些功能从硬件实现中解放出来以节约迭代升级成本，实现通过软件定义的方式处理业务需求逐渐成为一种发展趋势［7］。在执行网络请求处理的过程中，一条服务请求对应一条SFC，而每条SFC 由源节点、有序的VNF以及目的节点组合而成。若要处理一条SFC 请求，则需通过相应网络资源构建出这些虚拟功能模块，再按照一定的策略映射到网络当中，才能保证提供可靠而稳定的服务［12-14］。

虚拟网络功能基于其特性按照一定的比率放大或缩小经过的数据流，本文称其为流量缩放因子ω。在此假设一个前提：为了避免流性能的退化，不可将流拆分成多条进行传输。

图2 说明了流量缩放因子对构建SFC 的影响。其中：S与D分别为源节点与目的节点，M1、M2、M3均为空间信息网络中的卫星节点；N1与N2为抽象出的VNF，N1的流量缩放因子为2，即由其功能属性会导致经过的数据流放大2 倍，N2的流量缩放因子为0.5，则会使经过的数据流缩小1/2，空心圆圈表示该卫星节点仅作为跳转节点未使用虚拟功能；服务请求为a个单位的数据流大小，横向箭头表示链路，纵向箭头表示生成抽象，链路上数字表示当前链路中的数据流大小。从图2 可以看出，通过分别将流量缩放因子较大的VNF 与缩放因子较小的VNF 放在构建的服务功能链末尾与链首，可降低传输过程中带宽资源的压力。与此同时，还需考虑到在SFC 构建时VNF 间的相互依附关系，需将有上下文联系的VNF放在一起考虑，比如加密与解密是不可调换顺序的功能，不能为降低通信资源压力而破坏这种相互依附关系。因此，整体关注SFC 的构建可达到降低链路通信资源开销的目的。

图2 流量缩放因子对带宽的影响Fig.2 Effect of traffic scaling factor on bandwidth

2.2 建模分析

本文将空间信息网络抽象为无向图P(U，E)的形式，其中，V表示网络中所有提供处理能力的卫星节点集合，对于每个卫星节点u∈U，E表示所有卫星间的物理链路集合，每条链路e∈E。B(u1，u2)表示带宽，ζ=(γ1，γ2，…，γn)表示VNF 资源集合，γu，m表示卫星上节点u存在网络虚拟功能为m的虚拟资源类型，单颗卫星可抽象出多类资源，用C(v)表示卫星节点的计算资源容量。

当系统接收到服务请求f进入到网络中时，用E表示经过空间网络中物理节点u1，u2的服务请求路径：

若卫星上节点针对接收的服务请求f进行处理时产生一条多跳路径，其中跳转可能在卫星节点间发生，也可能在一颗卫星抽象出的不同虚拟功能间发生。用f(i，u′)表示服务请求f经过i次跳转后在物理节点u′的位置上，假设共有N跳，i∈[1，N]，则有：

将服务请求中所需的虚拟网络功能γ部署到空间信息网中的物理节点u上，则有：

针对服务请求f中考虑到的网络虚拟功能之间的依附关系，用“＞”表示VNF 间调用的先后顺序，γa＞γb表示虚拟网络功能γb依附γa，需要先处理γa后再处理γb，则有：

这种依附关系具有传递性，例如γa＞γb且γb＞γc，则γa＞γc。

用ratio(γ)表示网络虚拟功能类型为γ的流量缩放因子，定义分别代表服务请求f流入和流出节点u时对流量大小影响的比率：

若存在依附关系γa＞γb，需将a放在b后进行部署，且有如下约束条件：

costi表示VNF 的通信资源开销，当仅存在一个VNF 时，costi=ωi=ratio(γ)。若处理式（6）这种相互依附关系的VNF 后，对于后续没有与自身存在依附关系的虚拟网络功能个体或集群，则需要将γa放在γb前，且存在以下约束：

其中，(1-ratioa)/costa＜(1-ratiob)/costb，将(1-ratioa)/costa看作γa的属性，其值越小则在SFC 中的摆放位置越靠前。

考虑到减小卫星上VNF 部署实例的碎片化，针对SFC 中的待映射VNF，有且仅有一次被部署到卫星节点上：

考虑到实际传输时负载均衡且符合物理实际，对于任意一颗卫星，待处理所需的计算资源总和需小于该卫星节点实际最大值：

同理，所有服务请求f部署到卫星节点所需的通信资源总和应小于该物理节点所能提供的最大带宽传输能力，应满足：

为了能够更细粒度地利用卫星上资源，卫星节点u上的虚拟网络功能可被多条服务请求申请使用：

为了最小化空间信息网络中卫星节点的计算资源与通信资源，并提高服务请求接收率，将目标函数设置为：

2.3 SFC 映射的问题描述

A*寻路是在Dijskra 算法的基础上增加预测函数演变而来，通过对其选择合理的搜索方向逐渐向目标节点靠近，从而找到最短路径。

其中，f(s，e)表示从起始点s经过当前节点x到目的节点e所需的总开销，g(s，x)表示从起始点s到当前节点x产生的实际通信开销，h(x，e)表示从当前节点x到目的节点e的开销评价。

为了使源节点s找到目的节点e的路径最短，以μ(x)作为约束h(x，e)的权值，使其小于等于实际开销可控制算法搜索目标节点范围，当其值大于1 时可使算法增大预测函数权重以有效增大搜索范围，且在周围节点不具备部署能力时可快速跳出局部最优限制。

卫星间通信开销g(s，x)包括链路丢包率、通信资源占用比率以及链路间时延，本文将通过综合这些数据加权对后继节点进行计算。

其中：l(s，x)表示链路丢包率，链路丢包率增加表示当前链路段拥塞，若达到阈值表示该段链路不具备映射条件，需要重新进行路由分配；b(s，x)表示通信资源占用比率，其反映链路通信资源使用情况；d(s，x)表示时延，其包括排队时延、处理时延以及传播时延；α、β、τ（赋权参数）在算法中以1∶1∶1 进行调配，实际可根据服务需求特点适当调节，且α+β+τ=1。

开销预测函数h(x，t)是由待选卫星x与其相邻卫星t的星间通信开销平均值，以及经过加权处理后的卫星间欧几里得距离得出，具体如式（15）所示：

其中：开销预测函数若要达到效果必须小于实际开销结果；λ为卫星间链路带宽占用率，表示卫星间链路传输拥塞情况；考虑传输距离也是传播时延产生的条件，用des(x，t)表示卫星间欧几里得距离，且其值越小传输距离越短，通信所用延迟时间越短，即可得到开销预测函数h(x，t)。

2.4 服务功能链的映射算法

本文提出一种空间信息网络服务功能链映射算法，选择映射路径时可通过预测函数对卫星节点的选取进行评价分析，并根据服务需求通过减小预测函数的权值来加快搜索范围收敛速度，或为了获得全局最优解，增大权值范围跳出局部最优，算法的具体步骤如下：

本文统计针对当前快照中卫星上资源抽象出的虚拟功能种类，判断此卫星能否满足服务请求，open表中存放的都是待处理的卫星节点，通过对当前节点以及周围相邻节点F 值的计算与比较，将当前开销最小的点q标记为父节点，再计算父节点q周围的节点开销并进行比较，经过迭代计算持续更新在搜索中找到更优秀开销的节点作为父节点，并最终得到SFC 映射路径输出。

本文采用一种可以避免出现重路由情况发生的策略［15-17］，每当算法搜索过程中出现候选节点与下一跳卫星链路通信断开的情况时，为避免发生重路由会立刻反馈至MEO/GEO 卫星，并同时生成新的服务功能链映射路径。针对节点失效计算时原路径上局部节点失效的问题，本文可从链路通信断开处的节点进行填补以更新出新的路径策略。

3 实验结果与分析

3.1 仿真实验参数设置

本文仿真实验配置环境如下：使用配置为64 位Ubuntu操作系统，Intel®CoreTMi7-3770 CPU@3.40 GHz处理器，16 GB 内存的PC 机上运行，使用编程语言Python3.6 在JetBrains PyCharm 2018.1.4 x64 平台编写。

OPNET 软件可模拟空间信息网络中卫星拓扑以及卫星对于VNF 的抽象，其中三颗GEO 位于对地静止轨道，经度为0°，东经120°，西经120°。MEO、LEO 分别参照Odyssey 与Iridium 分布，卫星仿真参数如表1所示。

表1 卫星仿真参数Table 1 Satellite simulation parameters

为尽可能还原空间信息网络中的运行情况，本文模拟出以下3 种情况：

1）使用OpenStack 模拟服务请求需求生成卫星上VNF 并管理，VNF 仿真参数如表2 所示。

表2 VNF 仿真参数Table 2 VNF simulation parameters

2）使用OpenDaylight 控制器对卫星拓扑进行控制管理，采用Openflow 生成模拟服务请求的流，从而实现流量经由虚拟机生成VNF。

3）预设每条服务请求包含的VNF 数量不确定，并服从［3，10］的均匀分布，接收的服务请求服从［100，300］的泊松分布［18-19］。

3.2 算法对比分析

实验将本文算法与随机映射RAND 算法以及离线布局OMD［20］算法在统一网络环境中进行仿真分析比较。由于映射的开销主要源自于满足服务需求时达成功能实现的计算资源和内存资源的消耗，以及在通过算法构建链路时路径中产生的通信资源消耗。为最小化映射开销，本文通过流量缩放因子及VNF 间相互依附关系构建出一条合理的SFC，利用SFC 的构建来降低在卫星间和层间通信时通信资源的消耗，再通过本文算法找到SFC 映射的最佳路径，以减少卫星上资源碎片化与计算内存资源的开销。

总资源消耗表示在某一快照中满足服务请求下，各个节点计算资源、通信资源以及内存资源的使用情况。由于卫星的处理能力主要由CPU 计算资源体现，因此在综合考虑消耗多种资源的情况下，统一将CPU 占用50%，其他资源平均分配。如图3 所示，随着任务请求数增加，本文算法可在预测函数中进行快速择优，以满足高并发情况下的服务支持，且本文算法的总资源消耗率较RAND 算法、OMD 算法分别平均降低27%和6%。

图3 3 种算法的总资源消耗率对比Fig.3 Comparison of total resource consumption rate of three algorithms

在处理请求时延方面，本文算法同样有稳定的收敛趋势，随着SFC 任务请求数的不断增加，并发业务量提高依旧可以表现出良好的处理能力。图4 指标反映了本文算法对于服务请求、构建链路的路由选择效率以及拥塞情况的处理能力，且所得结果显示在高并发环境下，本文算法具有最小的处理请求时延结果，较OMD 算法处理时延平均降低了19%。因此，随着并发业务量增多，本文算法可更快找到SFC 映射解决方案。

图4 3 种算法的处理请求时延对比Fig.4 Comparison of processing request delay of three algorithms

4 结束语

本文提出一种适用于SFC 快速构建与映射的空间信息网络抽象模型。该模型根据流量缩放因子及VNF 间的相互依附关系构建出合理的SFC，并针对SFC 映射过程中的随机失效等问题，提出一种服务功能链优化算法。仿真结果表明，该算法可在较高的并发服务请求下，有效减小请求处理时延、降低映射时的总资源消耗，满足网络功能服务需求。下一步将采用神经网络算法对本文空间信息网络模型进行优化，通过调整各层空间中GEO、MEO、LEO 的数量得到最优部署方案，在降低空间部署成本的同时显著提高空间网络服务请求速率。