一种5G网络低时延资源调度算法

王琛, 汤红波, 游伟, 王晓雷, 袁泉

(1.国家数字交换系统工程技术研究中心, 450002, 郑州; 2.移动互联网安全技术国家工程实验室, 100876, 北京)

5G移动通信网将是一个全方位服务、多技术融合的网络,通过信息通信技术的演进和创新,来满足未来用户多样化的业务需求[1]。以软件定义网络(software defined network,SDN)和网络功能虚拟化(network function virtualization,NFV)为代表的网络新技术将成为5G网络的关键技术[2]。NFV技术使网络资源分配更加灵活,实现了异构的网络架构和服务的聚合[3]。在传统的网络架构中,网络功能通过昂贵的硬件中间件来实现,当移动网络运营商部署新业务时,需要大量的资本支出和运营支出。而在NFV环境下,网络功能通过实例化在商用服务器上的虚拟机(virtual machine,VM)中的软件化的虚拟网络功能(virtual network function,VNF)来实现,网络服务则是由多个虚拟网络功能以一定的依赖关系构成服务功能链(service function chaining,SFC)来完成。移动网络运营商通过NFV技术能够有效地减少资本支出和运营支出,为用户提供先进和灵活的网络服务[4],而SDN作为一种新型的网络架构,能够控制数据流通过相应的网络功能以执行相应的策略,实现灵活的网络管理[5]。SDN和NFV的结合为虚拟网络功能的协调控制和调度提供了有效的架构,促进了网络的创新[6]。在网络虚拟化下,资源分配分为服务功能链的构建、服务功能链的映射和虚拟网络功能调度这3个阶段。虚拟网络功能调度作为NFV环境下资源分配的第3个阶段,主要解决在给定相应的计算资源约束和虚拟网络功能执行顺序的基础上,为多个服务功能链中的每个虚拟网络功能在虚拟机中选择相应的实例化时间,从而达到最小化完成所有网络服务总时间的目的[7]。

IMT-2020将增强移动宽带、海量机器通信和高可靠低时延通信作为5G的主要应用场景[8]。为了使移动终端完美支持交互式游戏、3D虚拟现实等在线交互应用,5G提出了毫秒级时延和10 Gbit/s峰值速率的要求[9]。因此,设计高效的虚拟网络功能调度方法是将NFV应用在5G当中的关键问题之一。目前仅有少量的文献研究了虚拟网络功能调度问题。文献[10]将虚拟网络功能调度问题定义为柔性车间调度问题(flexible job shop problem,FJSP),然而未提出多项式时间内的解决方案,而且在其调度模型里仅考虑了虚拟网络功能的处理时延。文献[11]提出了NFV环境下具有较低复杂度的多资源数据包调度算法,该算法考虑了数据包队列的特性,然而未考虑服务功能链的特性。文献[12]对服务功能链的端到端时延进行了分析,然而其假定时延具有固定的值,这在实际中并不适用,不能应用在动态的网络服务中。文献[13]在FJSP模型的基础上引入数据流量在虚拟链路上的传输时延,建立了虚拟网络功能调度问题的混合整数线性规划模型,并设计了基于遗传算法的虚拟网络功能调度方法,但其提出的遗传算法容易早熟,陷入局部最优,无法获得更好的调度方案。虚拟化技术将物理服务器虚拟化为多个虚拟机节点,这些虚拟机节点之间由虚拟链路相互连接[14],流入服务功能链中的数据流量在具有有限带宽的虚拟链路中传输时会带来不可忽视的传输时延,而完成一个服务功能链需要利用多个虚拟机,这些虚拟机可以放置在位于一个数据中心或多个数据中心的物理实体上,瓶颈传输链路带来的时延将会降低整个网络服务的用户体验,因此虚拟网络功能调度问题需要考虑高效的带宽资源分配策略。文献[15]阐明了因为缺少对虚拟机的带宽保证,传统的传输层协议是不公平的,其将带宽分配建模为协作博弈模型,设计了相应带宽分配策略。文献[16]针对现有的带宽分配方案不能有效应对高动态的流量变化状况,通过考虑大量短流和突发流的影响,在控制论框架下基于符号逻辑模型设计了一种分布式速率分配算法。

针对以上研究的不足,本文通过考虑虚拟网络功能实例化在虚拟机上的处理时延和数据流量在虚拟链路上的传输时延,建立了相应的虚拟网络功能调度模型,并设计了动态链路带宽分配策略,提出了基于联合遗传和禁忌搜索(GATS)的虚拟网络功能调度方法。该算法在带宽分配上具有更高的细粒度,充分利用了遗传算法的全局搜索能力和禁忌搜索的局部搜索能力,有效的避免了早熟问题,具有更快的收敛速度,可以得到更优的调度方案。

1　网络模型与问题建模

1.1　网络模型

定义服务功能链集合S,对于每个服务功能链si(i∈[1,S]),具有一组数据流量需要以固定顺序通过的虚拟网络功能;Fi(i∈[1,S])为服务功能链si中虚拟网络功能的集合;fij表示服务功能链si中的第j个虚拟网络功能;N为虚拟网络中虚拟机的集合;L为虚拟网络中虚拟链路的集合。假设每个虚拟机节点具有实例化不同虚拟网络功能的能力,且在同一时间段内至多实例化一个虚拟网络功能,Mfij(i∈[1,S],j∈[1,Fi])为具有实例化虚拟网络功能fij能力的虚拟机节点集合,即计算资源约束。本文考虑了2种类型的时延,即服务功能链的数据流通过虚拟机之间的虚拟链路的传输时延和虚拟网络功能实例化在虚拟机中的处理时延。假定每个服务功能链从流入端点到流出端点具有固定的流量需求,定义为Di(i∈[1,S]),2个虚拟机之间的虚拟链路的带宽为Bk1,k2(k1,k2∈[1,N]),因此,服务功能链si在虚拟机节点k1和k2之间虚拟链路的传输时延为Di/Bk1,k2。τk,fij(k∈[1,N])为虚拟网络功能fij实例化在虚拟机节点k上的处理时延。

1.2　问题建模

(1)

式(1)的约束条件为

(2)

(3)

(4)

式中:δ是所有服务功能链中最后一个虚拟网络功能的处理完成时间,即多个网络服务的完成时间。式(1)表示虚拟网络功能调度的目标,即最小化所有服务功能链请求的最大完成时间;式(2)确保了当服务功能链中的数据流量在虚拟网络功能处理完成后,相应的虚拟网络功能才能开始转发数据流;式(3)确保了只有从上行虚拟机中接收到数据流后,下行虚拟机才能开始处理相应的数据流;式(4)确保了有且仅有一个虚拟机实例化虚拟网络功能fij。

1.3　带宽分配策略

合理的带宽分配策略能够有效的降低数据流在虚拟链路上的传输时延。定义Cin(k)/Cout(k)为虚拟机节点k的流入/流出带宽。根据流经虚拟机的数据流量动态的分配带宽资源,将带宽分配建模为整数线性规划模型,其优化目标表示为

minη

(5)

式(5)的约束条件为

(6)

(7)

式中:η表示虚拟链路总的传输时延。式(5)表示带宽动态分配的目标,即最小化总传输时延;式(6)确保从一个虚拟机流出的所有链路带宽之和不大于该虚拟机的流出带宽;式(7)确保流入一个虚拟机的所有链路带宽之和不大于该虚拟机的流入带宽。

2　联合遗传和禁忌搜索算法(GATS)

根据上述虚拟网络功能调度模型,虚拟网络功能调度问题可看做是柔性车间调度问题的扩展,该问题是NP难问题,引入动态的链路带宽分配后,进一步增加了其复杂性,因此在多项式时间内无法利用传统方法求得精确解[7]。为了有效地解决虚拟网络功能调度问题,本文设计了一种联合遗传算法(genetic algorithm,GA)和禁忌搜索(tabu search,TS)的启发式算法(GATS),通过利用遗传算法的全局搜索能力和禁忌搜索的局部搜索能力,能够得到更优的调度方案。

2.1　染色体编码和解码

ci=[322131231231421324]

(8)

ci染色体中包含3条服务功能链,每条服务功能链由3个虚拟网络功能构成,共有4个虚拟机实例化所有虚拟网络功能。前9位基因表示虚拟网络功能的调度顺序,可被解码为f31→f21→f22→f11→f32→f12→f23→f33→f13,后9位基因表示实例化前9位虚拟网络功能的虚拟机序号,可解码为Mf31(2)→Mf21(3)→Mf22(1)→Mf11(4)→Mf22(2)→Mf12(1)→Mf23(3)→Mf33(2)→Mf13(4),其中Mf31(2)为可实例化虚拟网络功能f31的虚拟机节点集合Mf31中的第2个元素。当完成染色体编码后,需要将其解码,以生成可行的调度方案。下列伪代码表示相应的解码算法:

1输入:染色体c

4根据c计算每个虚拟机的路由

5根据动态链路带宽分配模型,执行整数规划算法进行链路带宽分配

6for从前往后选择c中的基因odo

7i=get_service(c(o))

8j=get_function(c(o))

9k=get_VM_node(c(o))

10xijk=1

11ifj=1 then

12tij=starting_time_VM(T,T′,Z,k)

13else

15tij=starting_time_VM(T,T′,Z,k)

16end if

17end for

2.2　适应度计算和选择

染色体的适应度值为所有服务功能链请求完成时间δ的倒数,如式(9)所示。

(9)

对于任意染色体,计算其适应度值,然后采用轮盘赌法进行排序,个体的选择概率如式(10)所示,其中NNIND表示种群个数。

(10)

2.3　交叉

图1　染色体交叉过程

2.4　变异

首先从种群中随机选择变异个体,然后在个体随机选择2个虚拟网络功能,最后交换这2个虚拟网络功能及实例化虚拟网络功能的虚拟机基因位置。染色体变异过程如图2所示,首先,随机选择第2和第3位基因,然后交换该位置基因和相应虚拟机分配基因(第11和第12位基因)的顺序,完成变异。

图2染色体变异过程

2.5　禁忌搜索

禁忌搜索的思想是标记已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象,从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域、禁忌表、禁忌长度、候选解、藐视准则等概念。禁忌搜索是解决调度问题的一种有效的局部搜索策略,本文采用了文献[17]提出的邻域结构,提出的禁忌搜索算法的流程如图3所示。

图3　禁忌搜索算法流程图

本文提出的GATS算法充分利用了遗传算法的全局搜索能力和禁忌搜索的局部搜索能力,其算法流程如图4所示。

图4　GATS算法流程图

在提出的GATS算法中,选择个体执行禁忌搜索时,首先需要将其解码为一个可行的调度解,然后将这个解作为禁忌搜索的初始解,算法执行完后,将输出的最优解编码为染色体,继续执行遗传操作,当达到最大进化代数Gmax时,终止GATS算法,当达到最大迭代次数Tmax时,终止禁忌搜索算法。设置Tmax=80×(G/Gmax)。在GATS算法的早期阶段,因为遗传算法不能为禁忌搜索提供较好的个体,禁忌搜索算法很难找到更优的解,所以禁忌搜索算法的最大迭代次数此时较小,可以节省GATS算法的计算时间。在GATS算法的后期阶段,遗传算法可以为禁忌搜索算法提供较好的个体,因此增大禁忌搜索算法的最大迭代次数可以帮助其找到更优的解。因此,将禁忌搜索算法的最大迭代次数随着GATS算法的进化过程动态调节,可以有效的降低算法时间复杂度。

3　实验验证与结果分析

未来5G系统将采用基于SDN/NFV的网络架构,可以实时的掌握全局网络视图,得到算法所需的输入数据。为了评估模型的可行性及算法有效性,本文将提出的联合算法(GATS)与文献[13]中均匀链路带宽分配的遗传算法(GA-NBA)和动态带宽分配的遗传算法(GA-BA)在统一的实验平台上进行了比较。

3.1　实验设置

5G系统将采用云数据中心架构,具有强大的并行处理能力。本文为了方便算法比较,使用了配置为Intel Core i7-4790 3.60 GHz CPU、8 GB内存的个人电脑,并利用CPLEX 12.4工具求解动态带宽分配整数规划模型,编写了算法的Matlab仿真程序。网络参数方面,设置最大服务功能链数量S=100,最大虚拟机数量N=20。虚拟网络功能在虚拟机中的处理时延在[2,10]ms内随机生成。虚拟网络为全连通网络,虚拟机之间的链路带宽初始化为2 Mb/s,虚拟机的流入/流出带宽可以由此得出。考虑移动核心网数据和控制平面服务功能链的数据流量需求,设置流经控制面服务功能链的数据流量在(0,2]kb之间随机取值,而针对数据平面服务功能链请求,流经数据平面服务功能链的数据流量则在[10,20]kb之间随机取值。可实例化虚拟网络功能的虚拟机节点集合随机生成,其中每个虚拟机节点实例化虚拟网络功能的数量不大于3,任意虚拟网络功能至少可由1个虚拟机节点实例化。3种算法参数统一设置为:种群数量NNIND=40,遗传代数maxGen=50,交叉概率为80%,变异概率为60%。

3.2　实验结果分析

图6　控制面流量GATS算法(GA-BA算法)调度结果

图7　控制面流量GA-NBA算法调度结果

首先,设置网络为全连通的具有5个虚拟机的底层网络和2条控制面服务功能链(VNF4→VNF2→VNF1→VNF3→VNF5)和(VNF3→VNF2→VNF4→VNF5→VNF1),对3种算法进行了仿真实验。图6和图7分别给出了在控制面流量下GATS算法(本例中GA-BA的仿真结果与其相同)和GA-NBA算法的仿真结果。图中,Y轴表示不同的虚拟机,X轴表示时间。不同颜色表示不同的服务功能链,色块中上方的数字表示虚拟网络功能所在的服务功能链的序号和在服务功能链中的位置,下方的文字表示虚拟网络功能的类型。可以看出,2种具有带宽分配策略的方法获得了相同的仿真结果,这是因为控制面流量较小,传输时延对调度结果的影响较小。表1给出了3种算法在算法时间复杂度和服务完成时间上的对比。GA-NBA算法的服务完成时间最长为17 s。引入带宽分配策略后其他2种算法将服务完成时间减少了7%。对比GA-BA算法和GATS算法的时间复杂度,由于GATS算法在遗传算法中加入了禁忌搜索算法,增加了算法的时间复杂度。

表1　控制平面流量结果比较

图8　数据面流量GA-NBA算法调度结果

图9　数据面流量GABA算法调度结果

图10　数据面流量GATS算法调度结果

使用相同的虚拟机网络拓扑,针对2条数据平面服务功能链请求运行3种算法,运行结果如图8～图10所示。从图8～图10可见,由于数据流量较大,传输时延对服务完成时间的影响更加显著。表2给出了3种算法在算法时间复杂度和服务完成时间上的对比。实验结果表明,引入链路带宽分配后,服务完成时间明显减少,GA-BA算法和GATS算法分别在带宽平均分配的GA-NBA方法的基础上将服务完成时间降低了24.3%和37.1%。因为本文GATS算法对带宽分配的细粒度更小,能够获得更好地带宽分配策略,因此,GATS算法比GA-BA算法获得了更小的服务完成时间。通过比较表1和表2可以看出,算法的时间复杂度仅与虚拟网络的拓扑和服务功能链的数量有关。

表2　数据平面流量结果比较

图11表示了在数据平面流量下,不同进化代数下服务完成时间的收敛过程。由图11可以看出,GATS算法具有更优的收敛效率,而GA-BA算法则经常陷入局部最优解,这是因为,GATS算法采用了禁忌搜索对染色体的解进行了进一步优化,具有较好的局部搜索能力,表现出较快的收敛速度,避免了早熟问题,同时采用了细粒度更高的带宽分配策略能够获得更短的服务完成时间。

图11　2种算法的收敛过程

图12　不同服务功能链请求强度下的服务完成时间

图12表示不同的服务功能链请求强度下的2种算法的服务完成时间,其中,网络参数设置为具有20节点的全联通网络,设置种群数量NNIND设置为40,最大遗传代数maxGen为50,服务功能链数据流量在0～20 kb均匀生成。可以看出,GATS算法获得的服务完成时间更少,而且随着流量的上升,本文方法的优势更加明显,这是因为由于流量的增加,传输时延将成为影响服务完成时间的关键因素,GATS算法在链路带宽分配上具有更高的细粒度,而且GATS算法将遗传算法和禁忌搜索算法有效的结合,能够搜索到更优的调度方案,在更短的时间内完成网络服务。

4　结　论

本文基于柔性车间调度问题提出了结合虚拟链路动态带宽分配的虚拟网络功能调度模型,并设计了联合遗传和禁忌搜索的启发式算法(GATS)进行求解。GATS算法通过混合整数规划的方法准确求出链路带宽分配的闭式最优解,提高了带宽分配的细粒度,同时利用禁忌搜索算法的局部搜索能力,有效避免了遗传算法的早熟问题。实验结果表明,GATS算法在收敛速度上具有较高优势,而且获得了更好的调度方案,能够满足5G低时延场景的需求,增加了用户的服务体验和运营商的收益。但是,本文提出的算法由于融合了2种算法,增加了算法的时间复杂度。下一步,将在保证求得更优调度方案的前提下,研究算法时间复杂度更低的算法。

参考文献:

[1]张平, 陶运铮, 张治. 5G若干关键技术评述 [J]. 通信学报, 2016, 37(7): 15-29.

ZHANG Ping, TAO Yunzheng, ZHANG Zhi. Survey of several key technologies for 5G [J]. Journal on Communications, 2016, 37(7): 15-29.

[2]MARTINI B, PAGANELLI F, CAPPANERA P, et al. Latency-aware composition of virtual functions in 5G [C]∥IEEE Conference on Network Softwarization: Software-Defined Infrastructures for Networks, Clouds, IoT and Services, NETSOFT 2015. Piscataway, NJ, USA: IEEE, 2015: 1-6.

[3]ABDELWAHAB S, HAMDAOUI B, GUIZANI M, et al. Network function virtualization in 5G [J]. IEEE Communications Magazine, 2016, 54(4): 84-91.

[4]刘彩霞, 卢干强, 汤红波, 等. 一种基于Viterbi算法的虚拟网络功能自适应部署方法 [J]. 电子与信息学报, 2016, 38(11): 2922-2930.

LIU Caixia, LU Ganqiang, TANG Hongbo, et al. Adaptive deployment method for virtualized network function based on Viterbi algorithm [J]. Journal of Electronics & Information Technology, 2016, 38(11): 2922-2930.

[5]KREUTZ D, RAMOS F M V, ESTEVES P, et al. Software-defined networking: A comprehensive survey [J]. Proceedings of the IEEE, 2014, 103(1): 10-13.

[6]CHENG G, CHEN H, HU H, et al. Enabling network function combination via service chain instantiation [J]. Computer Networks, 2015, 92: 396-407.

[7]HERRERA J G, BOTERO J F. Resource allocation in NFV: A comprehensive survey [J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 518-532.

[8]OSSEIRAN A, BOCCARDI F, BRAUN V, et al. Scenarios for 5G mobile and wireless communications: the vision of the METIS project [J]. IEEE Communications Magazine, 2014, 52(5): 26-35.

[9]袁泉, 汤红波, 黄开枝, 等. 基于Q-learning算法的vEPC虚拟网络功能部署方法 [J]. 通信学报, 2017, 38(8): 172-182

YUAN Quan, TANG Hongbo, HUANG Kaizhi, et al. Deployment method for vEPC virtualized network function via Q-learning [J]. Journal on Communications, 2017, 38(8): 172-182.

[10] RIERA J F, ESCALONA E, BATALLE J, et al. Virtual network function scheduling: Concept and challenges [C]∥2014 International Conference on Smart Communications in Network Technologies. Piscataway, NJ, USA: IEEE, 2014: 6867768.

[11] LI X, QIAN C. Low-complexity multi-resource packet scheduling for network function virtualization [C]∥Proceedings of 2015 IEEE Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2015: 1400-1408.

[12] LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions [C]∥Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway, NJ, USA: IEEE, 2015: 98-106.

[13] QU L, ASSI C, SHABAN K. Delay-aware scheduling and resource optimization with network function virtualization [J]. IEEE Transactions on Communications, 2016, 64(9): 3746-3758.

[14] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: State-of-the-art and research challenges [J]. IEEE Communications on Surveys & Tutorials, 2016, 18(1): 236-262.

[15] GUO J, LIU F, LUI J, et al. Fair network bandwidth allocation in IaaS datacenters via a cooperative game approach [J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 873-886.

[16] GUO J, LIU F, HUANG X, et al. On efficient bandwidth allocation for traffic variability in datacenters [C]∥ Proceedings of IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2014: 1572-1580.

[17] GAMBARDELLA L M, MASTROLILLI M. Effective neighborhood functions for the flexible job shop problem [J]. Journal of Scheduling, 1996, 3(3): 3-20.

[本刊相关文献链接]

王琳,钱德沛,王锐,等.高效支持负载聚合的程序资源敏感度获取及分析方法.2017,51(4):79-84.[doi:10.7652/xjtuxb201704012]

朱正仓,赵季红,唐睿,等.移动中继协助下终端直通中的模式选择和资源分配方案.2016,50(10):111-117.[doi:10.7652/xjtuxb201610017]

赵辉,郑庆华,张未展,等.多版本视频点播流媒体服务器集群资源分配方法.2016,50(6):30-35.[doi:10.7652/xjtuxb 201606005]

周墨颂,朱正东,董小社,等.采用资源划分的云环境下Hadoop资源许可调度方法.2015,49(8):69-74.[doi:10.7652/xjtuxb201508012]