杨培星,汤红波,游 伟,邱 航

1(郑州大学 网络空间安全学院,郑州 450002)

2(中国人民解放军战略支援部队信息工程大学 信息技术研究所,郑州 450002)

1 引 言

为了满足多样化的业务需求,5G网络的主要目标之一是支持各个垂直行业的技术和业务需求,这些垂直行业希望为其客户提供具有不同性能要求的多样化服务,而NFV已成为提供网络服务的关键支持技术[1].特别是近年来,随着用户数据流量的空前增长,用户访问的网络服务变得更加多样化和动态化,运营商利用网络服务技术通过部署多个专用的、定制化的、相互隔离的端到端逻辑网络为垂直行业提供多样化服务[2].

传统的关于网络服务的资源分配研究大都集中在云数据中心中,但大量物联网、智能驾驶、工业物联网等业务的引入,导致对带宽、时延、安全性等业务需求越来越严苛,传统云计算的集中部署方式已无法满足这些业务需求.因此需要将云中心的高性能计算能力及大规模存储能力拓展到网络边缘,用来提升网络质量,解决网络中的时延、安全和拥塞等问题.基于此,MEC[3]应运而生.然而,与核心云相比,边缘云的资源容量和计算能力有限,因此,在部署网络服务时要考虑云边协同下的资源分配问题.这种场景的一个例子是物联网企业中基于云的托管服务,在物联网企业中,物联网设备会产生大量流量,这些流量可以通过位于网络边缘的物联网网关路由到由多个数据中心或互连服务器组成的云环境.其中,一部分数据需要在用户侧处理来保证低时延、高并发、大流量等需求,同时,还有一些数据需要云端的强大计算能力支持数据存储、模型训练、大数据挖掘等操作[4].因此,根据物联网设备生成的数据量和正在交付的网络服务类型,网络服务可能跨越云端和边缘端,云边协同[5]下的网络服务部署模型如图1所示.

目前关于云边协同下的VNF部署研究已经成为学术界的热点问题,并被归类为NFV中的资源分配问题.如文献[6]研究如何在云边协同下部署VNF并在相邻VNF对之间进行流量路由,从而使在满足每个用户的时延约束下最小化最大链路负载率,减小网络阻塞.其中,服务功能链分为完全有序和部分有序两种,部分有序型服务功能链中相互独立的VNF可以并行处理流量数据包以减少传输时延.文献[7]提出根据不同的业务目标采取不同的策略来协调分配云边协同中的虚拟资源(网络、计算和存储资源),以满足垂直行业的网络切片要求.文献[8]提出一种针对边缘云资源有限问题的VNF动态资源分配方法.首先将时延敏感型流量请求转发到边缘节点中的原始 VNF,以最大限度地发挥边缘计算的优势,达到边缘节点的容量限制后,在核心云中部署一个新的VNF实例来分担流量负载,然后根据时延约束将时延敏感的流量转发到边缘云中,将时延不太敏感的流量转移到核心云.本文基于时延对流量进行分类并将其转发到不同的云数据中心以解决边缘云资源有限问题,但面对时延敏感型流量实际上仅能保证部分流量的时延约束.

上述工作都在研究云边协同下的VNF部署和流量调度问题,但是由于边缘云资源容量有限,不仅要考虑将不同类型的VNF类型部署在不同的资源域中,还要考虑多边缘云间的资源协调以及底层网络中的负载均衡,提高边缘云的资源利用率.鉴于此,在网络服务支持流量拆分的场景下,本文提出了一种基于流量拆分的VNF部署和流量调度方法.流量拆分是指将流量拆分为多条子流并通过多条链路传输至多个VNF实例中进行处理,每个VNF实例处理每条流量的一部分子流[9-11].通过将流量请求分配到多条路径和多个节点可以使全局流量分布的更加均衡,进而减少发生网络拥塞和流量请求超时的概率.其中,每条流量请求的拆分条数以及每条子流的拆分比例是根据底层网络的资源状态和流量的特性确定的.因此,整个过程包括有效的流量拆分策略、VNF部署策略和流量调度策略.将网络服务部署方法分为两个阶段,首先根据网络服务中包含的VNF的类型及其位置约束确定VNF在云边协同环境中的部署位置,然后在流量调度阶段引入动态的流量拆分思想,根据流量的时延等特性将其拆分成多条子流,并根据物理节点间的最短路径确定虚拟链路到物理链路的最佳映射.仿真结果显示,本文提出的云边协同下的VNF部署和流量调度方法既充分利用MEC减少传输时延的优势,提高网络中的流量请求接受率,又能保证网络中节点和链路的负载均衡,提高边缘云中的资源利用率.

2 问题描述和模型建立

2.1 问题描述

本文旨在云边协同环境中部署多个网络服务,其中每个网络服务由多个按照一定顺序连接的VNF组成,其中每个VNF的实例个数由最大流量拆分数I确定.对于底层网络,无论是核心云还是边缘云,都由物理节点和物理链路组成,因此,不同的资源域都可以描述为网络拓扑图.本文将网络服务和底层网络描述为VNF转发图和底层网络图.因为涉及到云边协同,本文的资源分配问题比单一资源域要复杂的多,约束条件主要包括VNF的位置约束、资源约束和流量拆分约束.本文将云边协同下的虚拟网络功能部署问题表述为MILP问题,由于流量拆分策略增加了VNF实例的部署成本,且不同的流量调度策略会因链路成本的不同而产生不同的带宽成本,因此,本文的最优化目标是总资源开销.

其中需要注意的是,虽然流量拆分方法能够有效的提高的网络整体性能解决网络中的负载均衡问题,但是由于数据包遵循不同的路径,其到达的顺序可能有误,因此需要节点重新排序数据包.本文中,假设利用多路径传输技术Multipath QUIC[12]来处理流量拆分后的数据包,该传输协议可以确保来自多个路径的数据包被重新排序,以便按照它们发送的顺序到达应用层,从而保障网络通信的可靠性和稳定速率.

此外,不同类型的VNF在流量处理过程中可能改变用户的流量大小,例如,添加、删除和修改数据包头;屏蔽恶意流量;防火墙可以丢弃违反安全策略的传入数据包,从而导致更低的数据速率;视频渲染可以改变流量的编码,从而导致更高的数据速率[13]等操作.因此,在考虑流量调度的问题时,流量改变率也是应该考虑的因素.

2.2 系统模型

底层网络模型:底层基础设施用无向带权图Gp=(Cp,Lp)表示,其中Cp表示云节点集,Lp表示云链路集.其中,根据云节点所在的位置分为边缘云Ep⊂Cp和核心云Op⊂Cp,且Ep∪Op=Cp.每个云节点A,B∈Cp上包含多台服务器,每台服务器上可以部署多个虚拟机,每个虚拟机仅且运行一个VNF实例.对于任意物理节点i,ci表示服务器i的计算资源容量,物理节点之间的物理链路(i,j)∈Φ表示为物理节点i,j所属的云节点之间的物理链路.每个云节点包含一个路由器用于流量转发,云节点之间的物理链路表示为两个云上的路由器之间的物理链路.对于任意两个云节点之间的物理链路(A,B)∈Lp,b(A,B)表示云节点之间的物理链路带宽,d(A,B) 表示云节点之间物理链路的平均时延,c(A,B)表示云节点之间物理链路的部署成本.本文只考虑云间流量,因为云间链路比云内链路更容易拥塞且成本更高.

流量请求模型:每个流量请求t∈T可以由一个五元组表示,其中i(t)和o(t)分别为服务请求数据流量的源节点和目的节点,svn(t)为所需的网络服务类型,w(t)为初始流量速率,d(t)为流量请求的时延约束.此外,流量是可拆分的.

2.3 优化目标和约束条件

根据文献[14]提出的VNF映射资源开销计算方法,推导出网络服务映射的计算资源开销.在VNF映射过程中,若网络服务中的VNFμ有a=1,…,m个VNF实例并行处理,则其占用的物理资源开销如公式(1)所示.其中δμ表示VNFμ部署产生的总物理资源开销,δμo表示管理和维护VNFμ所需的物理资源开销,只要服务器节点部署了VNFμ就会生成该部分开销,与流经该服务器的流量大小无关.δμa表示每个VNF实例μa处理流量请求所需的物理资源开销.

(1)

(2)

(3)

(4)

约束条件:

资源容量约束:公式(5)和公式(6)表示请求资源与底层物理网络之间的资源约束关系.其中,公式(5)表示虚拟链路和物理链路之间的带宽约束,即对于任何一条云间链路,其传输的流量请求所占用的带宽资源之和不能超过该云间链路的带宽容量.公式(6)表示VNF和物理节点之间的资源约束,对于任何一个物理节点,其承载的VNF所占用的总计算资源不能超过该节点的计算资源容量.其中公式右侧第1项表示在物理节点上部署VNF实例所需的计算资源,第2项表示所有VNF实例处理流量请求所需的计算资源开销.

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

3 算法设计

根据上述的网络服务部署模型,云边协同环境下的网络服务部署可以被认为是一种特殊类型的虚拟网络映射(VNE)问题,该问题是NP难问题[16],引入流量拆分后,进一步增加了其复杂性.因此,本文设计了一种基于禁忌搜索算法(TS)和遗传算法(GA)相结合的联合优化(TSGA)算法,通过利用禁忌搜索的局部搜索能力和遗传算法的全局搜索能,得到网络服务的部署方案.

禁忌搜索算法和遗传算法各有优缺点,虽然两种算法都可以解决本文研究的在云边协同环境下的网络服务部署问题,但是仅某一种算法存在依赖于初始解[17]或陷入早熟收敛的问题,因此,两种算法相结合可以获得更好的优化效果和更优的部署方案.

算法 1 中概述了TSGA算法的伪代码.引入双层编码方法同时实现网络服务的构建与部署,从初始解nss0开始,将初始解设置为最佳部署方案和当前部署方案nowns.然后通过VNF个体变异和调整流量拆分比例生成邻域结构,再通过迭代来探索邻域空间.并根据适应度函数公式计算出所有邻域结构的适应度函数值生成点序列,然后将最小适应度值所对应的部署方案设为最佳候选集nextns.若最佳候选解nextns的适应度值小于全局最优解bestns的适应度值,则将nowns和bestns全部替换为nextns,并将其对应的部署方案nextns作为禁忌对象替换最早进入禁忌表的禁忌对象.否则,判断候选解中各部署方案的禁忌属性,即是否在禁忌表中.将候选解集中非禁忌对象对应的最佳候选解设为新的nowns,并用nowns替换最早进入禁忌表的禁忌对象元素,以帮助局部搜索过程摆脱局部最优.但是最佳部署方案bestns保持不变.为了避免陷入局部最优并再次循环到之前已经选择过的部署方案,将已经选择过的部署方案储存在禁忌列表中,阻止在一定的迭代次数内移动到之前已经选择过的部署方案.但是,如果这些移动产生的部署方案得到的适应度值比迄今为止所有的适应度值都要小,那么仍然可以选择此适应度值所对应的部署方案,这种情况称为特赦准则.重复以上过程,直到满足迭代次数时终止算法循环.接下来将详细介绍TSGA算法的组成部分.

算法1.基于禁忌搜索算法和遗传算法的网络服务部署算法

输入：底层网络参数:底层网络拓扑图Gp=(Cp,Lp);网络服务参数:网络服务拓扑图Sv=(Nv,Ev);流量请求参数:五元组.

输出：最优部署方案bestns,适应度函数值fitnessvalue

1. 设置禁忌列表tabu,迭代次数num,邻域结构长度length,适应度函数fitness;

2. 初始解:根据输入参数随机生成网络服务初始部署方案nss0;

3. 将nss0设置为当前部署方案nowns和最佳部署方案bestns;

4. for q=1:sq_num //计算适应度函数值fitnessvalue

5. 根据流量的服务类型计相对应网络服务的部署位置确定流量所经过的节点顺序,并计算每条子流的总时延delayns1,delayns2

6. if delayns1<=delayns2

7. delayns=delayns2;

8. else

9. delayns=delayns1;

10. end //计算流量总时延delayns

11. if delayns>latency(q) OR 节点资源容量和链路带宽容量不能满足所需资源

12. 流量请求处理失败;

13. else

14. 计算次流量请求所需总资源开销,更新节点和链路的剩余资源;

15. end

16. 计算所有流量请求所需的总资源开销与适应度函数值;

17. end

18. fork=1:num//迭代寻优

19. 根据nowns利用遗传算法的交叉和变异操作生成邻域结构linyu;

20. 根据邻域结构linyu和禁忌列表tabu生成当前邻域linyu的点序列函数select;

21. 计算当前点序列select的适应度函数值,得到适应度序列;

22. 找出适应度最小值以及其所对应的部署方案nextns;

23. if fitness(nextns)≤fitness(bestns) //满足特赦准则

24. 将nextns设置为nowns和bestns,并更新禁忌列表tabu;

25. else

26. 从邻域的非禁忌对象中找出适应度最小值以及其所对应的部署方案nextns;

27. 将nextns设置为nowns,并更新禁忌列表tabu;

28. end;

29.k=k+1;

30.end

31.获得最优部署方案bestns及其适应度函数值;

3.1 初始解

本文根据每条流量中可以拆分的最大子流数来生成初始解,且将该初始解设置为TSGS算法的起点.下面只介绍无流量拆分时的初始解nss1,nss1可以很容易的扩展到最大子流数为2或3时的初始解nss2和nss3.

首先采用十进制整数编码方式同时对网络服务的构建与部署进行双层编码,长度为网络服务中所包含VNF类型的两倍.如图2所示的一个网络服务编码,前5位为网络服务的构建编码,不同的数字代表不同的VNF类型,从左至右的顺序代表VNF之间流量转发的方向;后5位为网络服务的部署编码,分别对应前5位VNF类型部署的节点位置,VNF的部署位置需要满足VNF类型的位置约束和所部属节点的资源约束,例如本网络服务中VNF类型1部署于底层物理网络中7号物理节点.解码时,首先根据网络服务的构建编码计算每个VNF实例所需的部署资源开销和VNF之间所需的带宽资源开销,然后根据部署编码在底层基础设施中的最短路径集合Link查找物理节点之间的流量转发路径,并判断物理链路上的剩余带宽是否满足带宽资源需求,如果不能满足,则删除该物理链路,接着在最短路径集合Link中重新计算这两个物理节点之间的物理链路.这种计算物理链路的方式能够减少部署节点之间转发路径的计算次数,提高解码效率.然后将此初始解nss1设置为最佳部署方案bestns和当前部署方案nowns.

3.2 邻域结构

TSGA算法基于遗传算法中的交叉和变异操作用两种种方法生成邻域结构:第1个是VNF个体变异,旨在扩大算法的搜索范围,避免陷入局部最优解;第2个是流量拆分比例调整,旨在重新调整流量请求中每条子流的拆分比例.

VNF个体变异:由于网络服务中流量转发路径是定向的,因此网络服务的构建编码部分是固定的,因此VNF个体变异指的是网络服务的部署编码部分的变异策略.且变异策略只考虑节点,不考虑链路,在网络服务中随机选择一个VNF,然后根据其资源约束和位置约束随机分配给另一个候选物理节点,然后在最短路径集合Link查找满足带宽约束的流量转发路径.

动态流量拆分:动态流量拆分指各个子流的拆分比例是根据可用资源和时延约束动态调整的,而不是固定值.从需要流量拆分的流量请求中随机选择一条流量请求t∈T,然后从该流量请求的多个子流中随机选择其中两条子流,然后调整这两条子流之间的流量拆分比例,使这两条子流的流量总和保持不变.为了处理分流比变量的连续性,假设流量被拆分为m个离散单元.例如,假设选择了第I条子流,并且其最大子流数为3,每条子流I1、I2、I3处理的流量单元分别为m1、m2和m3,其中m1+m2+m3=m.首先随机从3条子流中选择2个,假设是I1和I3.然后选择一个介于 1 和(m2+m3)之间的随机数,假设是n.最后,将I1和I3处理的流量分别调整为n和(m1+m3-n).

3.3 禁忌列表

为避免重复选择同一种部署方案以及避免局部最优解,TSGA算法将接受的候选解的移动声明为“禁忌”并在一定次数的迭代内将其存储在禁忌列表中.此外,该算法禁止选择存在于禁忌列表中的部署方案,除非该移动产生的部署方案的适应度函数值优于最优部署方案(bestns)的适应度函数值.

3.4 邻域评估和特赦准则

在每次迭代中,TSGA算法评估整组邻域结构的部署方案,然后选择其中一个设置为当前部署方案.TSGA算法使用公式(17)中的适应度函数,在评估邻域结构中的候选部署方案时,适应度函数是部署成本和流量请求接收数的加权和,适应度函数值越小越好.其中,cost(ε)是网络服务的总资源开销,包括网络服务部署所需的资源开销以及用于流量处理所需的资源开销;amod是流量请求未接受数量n(t)的权重,n(t)定义为有多少流量请求未被成功处理,本部分是为了奖励满足所有流量请求的邻域选择,尤其是时延约束.

fitness=cost(ε)+amodn(t)

(17)

在每次迭代中,在计算完生成的邻域结构中的所有部署方案的适应度函数值后,对所有的邻域评估结果进行序列排序.如果其最小适应度值优于当前部署方案的适应度值且没有存储于禁忌列表中,则将此部署方案替换为当前部署方案;如果此部署方案存储于禁忌列表中,但是其适应度值小于最小适应度值,则依然将此部署方案替换为当前部署方案,因为满足了特赦准则.

3.5 停止准则

TSGA算法在达到最大迭代次数后终止.在仿真实验过程中,不断调整迭代次数,以便在部署方案质量和代码执行时间之间找到一个平衡.

4 仿真结果与分析

本节通过仿真实验验证了本文所提出的联合算法的有效性,并将本文提出的TSGA算法与文献[4]中采用的TS算法和文献[18]中采用的轮询算法(Round Robin,RB)进行对比,验证多个流量请求到达情况下算法求解出的网络服务部署方案的有效性.每种对比算法运行10次,实验结果取平均值.文献[4]的最优化目标是部署成本与总时延的加权之和,并用TS算法解决网络服务的部署问题.选择这个算法的原因是因为它的物理场景与本文相似,都是在云边环境中部署多种类型的网络服务.文献[18]利用RB算法和最短路径算法联合实现VNF的部署,通过在互相靠近的物理节点上部署VNF从而最小化端到端时延.选择这个算法的原因是因为它的目标函数是最小化整体时延,与本文降低通信时延的目标相似.

4.1 实验环境与参数设置

为了验证TSGA算法的性能,本文在配置为Intel Core i7-6700 CPU、16GB内存、1T硬盘的台式机算上使用MATLAB R2021A进行仿真试验.仿真环境中使用的云边协同的网络拓扑由GT-ITM工具生成,底层物理基础设施由3个核心云与17个边缘云组成,其中每个核心云的计算容量为8Gbps,每个边缘云的计算容量为2Gbps,且每个云都有一个路由器仅用于本云内所有流量的转发.边缘云之间两个方向的链路带宽设置为2Gbps,边缘云与核心云之间的链路带宽设置为8Gbps,每条链路的单位流量成本在0.1～0.4/Mbps之间.关于链路传输时延,本文采用与文献[18]类似的方法,根据VNF的部署约束选择部署位置,假设边缘云之间的传输时延为1ms,边缘云和核心云之间的传输时延为3ms,两个核心云之间的传输时延为5ms.

参考文献[4]中的仿真参数,设定底层物理网络可接受的最大流量请求数为100,平台中可实例化的VNF类型数量为10(其中4种VNF必须部署于边缘云中,2种必须部署于核心云中,剩余4种可以根据部署于任何一类云中),每个网络服务包含的VNF数量不超过5.实验中所需的VNF类型及其相关参数如表1所示,其中规定了不同类型VNF的流量改变率raf,每Mbps带宽所需的计算资源uf和位置约束(p(μ)=1表示该VNF必须部署在核心云中;p(μ)=-1表示该 VNF必须部署在边缘云上;p(μ)=0表示“不关心”情况,可以部署在任何一个云中).

表1 VNF类型及参数Table 1 VNF types and parameters

本实验中共部署6种类型的网络服务,每个网络服务的网络拓扑已提前确定,包括所需的VNF类型以及它们之间的顺序,且每个网络服务根据其服务类型处理一定数量的流量请求.假设每条流量请求根据其所需服务类型选择接入特定的网络服务,每条流量请求是一组数据包,每个流量请求的源节点和目的节点在边缘云节点上的路由器之中随机选择.实验结果的每个数据为运行10次取平均值,接下来讨论仿真结果并进行分析.

4.2 算法性能与评估

首先,验证TSGA算法的收敛性和有效性,设置流量请求数为100,禁忌列表长度为200,迭代次数为200.

图3为最大子流数对流量请求接受数量的影响.从图中可以看出,当I=1,I=2,I=3时,最大流量请求接受数量分别为81.6,94.1和96.7.采用动态的流量拆分方法,流量请求完成率提高了12.5%.这是因为将流量请求拆分成多条独立的子流,不仅可以解决底层网络中链路的负载均衡问题减少网络拥塞的概率,还可以利用VNF并行处理方法让多个节点共同分担流量数据包避免因物理节点过载而造成流量请求超时.通过流量拆分来降低节点的资源利用率来降低节点处理时延,从而满足流量请求严格的时延约束.但是,对于I=2和I=3,流量拆分数增加,流量成功率提升了2.6%,即增大流量拆分数对流量请求接受数量的影响力有限.这是因为I的值并不意味着流量总是被分成I条独立的子流,只要满足流量请求的时延约束流量就不会被进一步拆分,因此一味的增大最大子流数不一定就会得到更好的部署效果.从图中还可以看出,将流量拆分数设置为2就可以满足场景中大多数流量请求的时延约束.

图3 最大子流数对流量请求接受数量的影响Fig.3 Effect of the maximum number of substreams on the number of traffic requests accepted

图4为最大子流数对流量请求平均资源开销的影响.从图中可以看出,I值越大,流量请求的平均资源开销越高.主要原因为,为了满足更多流量请求的时延要求,就要增加子流数以降低总通信时延,然而增加子流数也意味着增加VNF实例数以及不同的链路带宽开销.与图3类似,I=1和I=2时最优解的性能之间有比较大的差距,I=2和I=3时最优解的性能近似相同.从图3,图4中可以看出I=2时即可接收场景中94%的流量请求,且继续增加流量拆分数对流量请求接受率的提升空间较小,同时I值越大,算法的执行时间越长,已接受的流量请求的平均资源开销也越大.因此下文中将TSGA算法与TS算法和RB算法进行对比时,选取I=2.

接下来验证同时处理多个流量请求时3种算法求解出的网络部署方案的有效性,为了增强对比效果,设置流量请求数为200.图5为不同流量请求数量下的适应度值对比,可以看出,TSGA算法的解决方案更好,RB算法的解决方案最差,TS算法居中,较接近于RB算法.主要原因为:RB算法没有考虑到物理节点和物理链路的可用资源和性能的差异性,虽然更为简洁,但是容易导致节点间的负载不平衡和网络阻塞.与TS算法相比,在邻域结构的构建上,TSGA算法在邻域结构的构建上加入遗传算法的交叉因子和变异因子,增加邻域结构的随机性和多样性,且流量拆分策略克充分利用底层网络中的碎片化资源处理和传输流量请求,因此在相同的场景中可以找到更优的部署方案.

图5 不同流量请求数量下的适应度值Fig.5 Fitness values under different traffic request numbers

图6为不同流量请求数量下的流量请求接受率,初始资源充足,流量请求接受率都为1,随着流量请求接收数量的增大,曲线出现不同趋势的下降.其中,TSGA算法在流量请求为60时开始出现接受率下降的情况,即此时出现流量请求拒绝的现象,比TS算法和RB算法开始下降分别多了20和40个流量请求数.且TSGA算法的流量请求接受率一直高于其他两种算法,当流量请求数量为200时,TSGA,TS和RB算法的流量请求接受率分别为42.6%,34.9%和29.7%,相比之下,TSGA算法的流量请求接受率高于TS算法7.7%左右,高于RB算法12.9%左右.主要原因为:TS算法和RB算法都是采用静态的流量拆分策略和相对僵化的邻域结构选择方法,在大流量场景中,静态的流量拆分策略降低了对底层网络中资源分配的灵活性,同时僵化的邻域结构方法容易使算法陷入局部最优解.相比之下,TSGA算法在邻域结构的构建上,加入遗传算法的交叉因子和变异因子,增加邻域结构的随机性和多样性,从而跳出局部最优解找到更优的部署方案.且动态的流量拆分策略保证了网络中的负载均衡,通过均衡每个节点的资源利用率减小节点处理时延,从而满足更多流量请求的时延约束,进而增加了流量请求接受率.

图6 不同流量请求数量下的流量请求接受率Fig.6 Traffic request acceptance rate under different traffic request numbers

图7为不同数量流量请求下处理完成的流量请求的平均资源开销,从图中可以看出,TS算法和RB算法的平均资源开销分别收敛于2.14和2.19,而TSGA算法的平均资源开销收敛于2.03,相比于TS算法和RB算法降低了近似5.4%和7.8%.其中,流量请求数量较小时,其平均资源开销较大,随着流量请求数量的增加,平均资源开销逐渐降低,后期流量请求接受数量逐渐趋于饱和,平均资源开销也无下降空间.主要原因为:初始无资源竞争,平均资源开销对流量请求接受率影响有限,但是,流量请求较大时,要想在有限资源下接受尽可能多的流量请求,需要每条流量请求都以最小的资源开销满足流量请求的位置约束,资源约束和时延约束,因此需要寻找更优的网络服务部署和流量路由方法以减小平均资源开销,从而接受更多的流量请求.

图7 不同流量请求数量下的平均资源开销Fig.7 Average resource overhead under different traffic request numbers

5 结 论

传统的关于网络服务的资源分配研究大都集中在云数据中心中,但物联网、智能驾驶、工业物联网等业务的大量引入,导致对带宽、时延、安全性等业务需求越来越严苛.传统云计算的集中部署方式已无法满足这些业务需求,因此需要将部分VNF下沉至网络边缘以降低网络时延,减少网络阻塞的压力.然而,与核心云相比,边缘云的资源容量收到很大限制,因此,不仅要考虑将不同类型的VNF部署在不同的资源域中,还要考虑多边缘云间的资源协调以及底层网络中的负载均衡,避免边缘云节点过载造成流量超时或链路过载出现网络拥塞等问题.所以,在云边协同场景下部署网络服务,如何有效地利用核心云和边缘云各自的优势实现VNF的部署和流量调度是本文要解决的问题.本文提出了一种动态的流量拆分策略进行灵活的流量调度,根据流量的时延约束将其拆分成多条子流,并利用网络中的碎片化资源提高流量请求接受率.本文将云边协同下的虚拟网络功能部署和流量路由问题描述为混合整数线性规划(Mixed Integer Linear Programming,MILP)问题,并提出了一种基于禁忌搜索算法和遗传算法的联合优化(TSGA)算法,仿真结果表明,动态的流量拆分策略可以灵活优化全局网络,利用网络中的碎片化资源提高流量请求接受率,但当流量请求接受率达到一定值时,继续增加流量拆分数对流量请求接受率的提升空间较小.而且,本文提出的TSGA算法与TS算法和RB算法相比可以分别提高7.7%和12.9%的流量请求接受率,并分别减少5.4%和7.8%的流量平均开销.