基于时变图聚合的虚拟化服务链负载均衡方法

基于时变图聚合的虚拟化服务链负载均衡方法摘要：针对网络虚拟化背景下云数据中心服务功能链部署所引起局部资源负载不均衡问题，提出了基于时变图聚合的服务链负载均衡方法。通过将网络划分为一系列静态时变图，来描述时间窗内数据中心网络部署服务链的动态性，将静态时变图在时间序列上排列，并在相邻时变图上的同一节点之间建立链路，使之聚合为二维，从而将虚拟资源的分配问题转化为多商品流问题，并通过启发式算法高效地解决这一问题。实验结果表明，该方法与传统服务链部署方法相比，能有效降低最大链路利用率，并降低用户数据包的平均时延。关键词：网络功能虚拟化；云数据中心；服务链；负载均衡；Abstract：Concerning load unbalanced caused by service function chain deployment in cloud data center by network function virtualization, a load balancing method of service chain based on time-varying graphs integration were proposed. In order to represent the dynamic network of service function chain deployment in data center within time span by dividing dynamic network into a series of static time-varying graphs , integrating static time-varying graphs into multi-dimensional along time series, establishing link between the same node in adjoined time-varying graphs, finally transform the virtual resource allocation problem into multi-commodity network flow model. This paper also developed an efficient heuristic algorithm to effectively solve the problem. Compared to the previous generally used service function chain deploying method, the simulation results show that the proposed method can substantially not only lower the performance of max physical link utilization, but also lower the average latency of tenant packets.Key words：network function virtualization；cloud data center；service function chain；load balancing.引言云数据中心针对不同租户的多样化的服务需求，提供相互隔离的租赁服务和弹性的云能力。目前主要通过将细粒度的网络功能组合为复杂的租赁服务以满足租户日益增长的应用需求，如IETF提出一种链式的服务组合方式来表示租户的业务需求服务功能链1（Service Function Chain，SFC），即将服务抽象为租户流量经过一系列有序的，具有报文处理和转发功能的服务实体（Network Function, NF）的集合，服务实体可以包括防火墙（Firewall）、网络地址转换（Network Address Translation，NAT）和深度包检测（deep packet inspection，DPI）2等。但是，传统的SFC因服务实体与专用硬件的紧耦合，使得SFC的部署和变更尤为笨重，扩展性较差。软件定义网络3（Software Defined Network, SDN）技术和网络功能虚拟化技术4（Network Function Virtualization，NFV）的出现，将网络功能从通用的x86架构硬件上抽象出来，使得服务链的编排和部署脱离专用物理服务器的限制，租户所需求的NF通过软件和虚拟化的方式实现，称为虚拟服务功能实体（Virtualized Network Function, VNF），与传统方法相比更加灵活，同时通过将资源池化和虚拟化来进行资源调度成为可能5。以数据中心的服务链使用状况为例，目前大型企业云数据中心在部署服务链过程中资源使用状况仍不容乐观，即在虚拟化背景下，多租户共享底层物理资源的模式，普遍存在资源利用不均、利用效率普遍偏低和碎片化严重的情况：（1）数据中心要求7*24h不间断稳定运行，资源利用不均会导致部分物理服务器超载，从而引起宕机的情况，造成网络性能恶化；（2）拥塞会导致新服务链请求到来时，无法做出及时响应，用户体验质量（Quality of Experience，QOE）恶化；（3）资源负载不均衡，全网资源利用率低，造成资源浪费，即著名的“991原则”6，即90%的物理设备，在90%的在线时间内，只有10%的资源利用率，不符合绿色计算的原则。因此，在NFV背景下研究服务链的资源负载均衡问题仍具有一定的必要性。网络的负载均衡问题通常指的是流量的负载均衡，亦或是底层物理资源（计算、存储和带宽等）的负载均衡。在SFC的部署问题中，流量的大小和功能实体消耗资源的大小呈线性关系7，因此我们假设流量的负载均衡问题和资源的负载均衡问题等同，目前Moens H等人对SFC的部署问题进行了初步的探索8，提出的VNE-P方法将SFC的部署问题看作是资源的映射问题，转化为ILP问题，并通过最优化算法求解，但是该算法未考虑虚拟资源可以灵活调度的特性，存在局部负载过大问题。Chua F C等人9以减少物理服务器数目和降低租户使用延时为目标，在资源利用和用户体验之间权衡。本文主要针对SFC部署过程中异构资源的负载均衡目标，研究一种时变图聚合（Time-varying Graphs Integration , TGI）方法，在相邻静态时变图上的同一节点建立链路，将虚拟化SFC部署过程中的资源分配问题变成异构资源的权衡问题，最后以多商品流问题形式的求解，解决数据中心网络SFC资源利用不均问题。1 基于时变图聚合的服务链模型云数据中心网络中的资源主要分为三类：（1）通信资源，即服务器外接链路带宽等；（2）计算资源，表现为物理节点可以为服务功能实体提供的CPU和内存占用等；（3）存储资源，表现为节点硬盘阵列占用。由于在云数据中心网络中占用存储资源的主要是冗余备份数据10，大小受备份机制的影响，为简化问题，我们在部署过程中不考虑存储资源的使用，仅考虑计算和通信资源的这两种异构资源的权衡11。由于多种异构资源联合优化的决策变量较多，且大多具有时变性，比如用户的SFC需求、网络的负载状况和服务器剩余计算能力等，难以实现多目标函数的全局优化。因此我们引入时变图聚合模型来描述网络的动态性能，由静态时变图构成一个有序的图序列，每个静态时变图表示该时间窗内的快照。在时变图理论12中，底图表示一定序列中静态时变图全部路径的集合，在本文中其物理含义可以表征为全连通的、初始资源消耗为0的云数据中心网络，如下图1所示，根据理论对底图进行边和节点的演化13，并且将前后相邻时变图中同一节点相连，演化为静态时变图依时间序列排列的二维聚合图，另外根据领域知识，假设各个时间窗内网络中的状态不变，如拓扑通断、用户需求等状态不变。图 1 时变图聚合示意图Fig.1 Diagram of time-varying integration目前SFC部署主要分为串行和旁路并行两种，因为串行方式简单易部署，在工程中应用较广，因此本文主要讨论串形的SFC，如下图2所示，源用户终端和目的用户终端间的流量通过三台物理服务器中的虚拟机（Virtual Machine，VM）部署的SFC进行处理，该SFC部署次序为用户终端-VNF11-VNF22-VNF2n-用户终端，由虚拟交换机（Open vSwitch，OVS）或核心SDN交换机根据控制器下发的流表进行报文转发14。图 2 串形SFC部署示意图Fig.2 Diagram of series SFC deployment 1.1用户需求模型通过用户需求模型将不同种类的业务（CDN、DPI和负载均衡等）以功能需求和性能需求的形式进行表达。设为网络服务链请求的集合，其中，对于所有的， 表示从源节点到目的节点的服务链需求。对于第条服务链可分解为多个服务实体的有序组合，即，其中表示第个功能实体，用户的功能需求由服务链的组成和编排控制，每个服务实体由CPU和带宽性能需求组成，即，而服务链的性能需求可以看作是多个服务实体的性能需求的向量叠加15，本文将性能需求的叠加看作是取最小值，必须满足用户的最低的性能需求，即，其中。1.2 服务链时变图聚合模型图 3 服务链时变图聚合模型Fig .3 A time-varying integration for service function chain model 底层物理网络可以由单向无环图来表示，其中表示网络节点的集合，表示网络单向边的集合，。本文的场景可以抽象为如上图3所示，源节点流量经过中继物理服务器、和，到达目的节点，其中NFV技术将每个中继物理服务器的资源池化，供SFC分配使用。按照时变图的理论，将该场景按时间序列将其分为多个均匀时间窗大小的静态时变图，该集合为，表示在一段时间内的静态拓扑的集合，其中，且，为固定值。利用SFC处理报文和转发报文的特性，将时变图（）依时间序列依次连接起来，使流量不仅可以在同一时间片内转发，而且可以在时间片之间“流动”，同一节点在不同时间片之间建立链路，表示流量在同一节点停留，对报文进行处理，如图中虚线箭头所示，该链路可以表示为“计算链路”，同通信链路一样，流量对计算资源的占用可以表示为对“计算链路”的占用，基于异构资源的负载均衡策略可以转化为基于流量的对链路的负载均衡策略。假设节点的剩余计算能力为，将其归一化为计算链路的带宽为。由于存在数据包压缩等服务，流量在计算链路上会出现减少的情况16，不符合流量守恒的规律，此种业务在服务链中较少见，因此本文暂不考虑。因此本文假设节点的流量进出守恒，式（1）保证除源节点和目的节点以外的所有节点，流入节点的流量和流出节点的流量相等，对于每个节点，和分别表示流出和流入该节点的流量。（1）其中根据该聚合模型定义矩阵为的路径矩阵，该矩阵的二元变量，对于每个，有式（2），即当某条链路被用来传输流量时，为1；链路不被用来传输流量时，为0。该条件约束一条流始终流经一条路径，因为TCP流的分流可能引起报文的乱序，容易造成流量吞吐量的下降17，因此在目前云数据中心服务链的部署过程中较少见，本文暂不考虑分流这种情况。（2）定义表示链路容量，其中和分别表示计算链路和通信链路的总带宽，表示链路占用容量，其中和分别表示计算链路和通信链路的占用容量，下式（3）和（4）约束所有的流量需求不能超过链路的容量，式（5）表示链路占用率。（3）（4）（5）另外需要约束服务链的性能需求，使模型链路的流占用容量不小于其性能需求，如下式（6）（7）所示，针对任一服务链，式（6）表示流量流经路径中每一段计算链路占用容量须大于用户最小CPU需求，同理式（7）表示每一段通信链路占用容量须大于用户最小的带宽需求。（6）（7）因为短流在数据中心的占比最高，而短流用户需求对于时延的敏感度最高，因此本文将时延作为主要的用户需求指标。在云数据中心网络中，相比于排队时延，传输时延和发送时延大小基本不变，且大小可忽略不计，因此本文租户业务的端到端的时延仅考虑排队时延18，式（8）约束服务链的最长时延不得超过用户的需求。由于排队时延的评估模型较为复杂，其中为链路利用率，如式（8）所示，为数据包的平均大小，假设流量为自相似流量，为Hurst参数，当时，表达式（8）可以与常见的 队列模型相匹配19。（8）为保障各租户的服务链需求，缓解网络中流量集中造成的局部资源负载过大问题，上文我们将资源的负载情况转化为二维聚合拓扑的链路负载问题，因此将目标函数设置为最小化最大链路利用率，因为最大链路利用率该变量可以定性地表示网络的拥塞状况，即（9）通过该模型将服务实体的部署问题转化为多商品流问题20，即不同时间窗产生的SFC请求流量可以看作是“商品”，通过多个VNF的转发，送达目的节点。利用路由算法在二维虚拟拓扑聚合模型上搜索符合负载均衡目标的路径，求解的路径即为服务实体的部署路径。2 求解算法由上述模型可以看出SFC的部署问题可以看作是一个多商品流问题，目前已经证明多商品流问题是一个NP-hard问题21,如果采用线性求解方式的话，求解收敛速度较慢，造成服务的响应时间过长，导致用户体验恶化。因此我们采用适用于该情况下的启发式算法求解该类问题，在保证求解速度的情况下搜索全局最优解，本文采用模拟退火算法22来求解该问题。STEP 1：初始化阶段，设置模拟退火计划表：初始温度T（充分大），初始可行路径（令它为当前解，是循环迭代过程的起点），每个T值的循环次数L；STEP 2：对执行STEP3STEP6：STEP 3：执行邻域函数，得到新路径；STEP4：计算增量，其中为评价函数；STEP5：执行Metropolis接受准则：若，则令，接受为新的当前解；否则，以概率接受作为新的当前解；STEP 6：如果满足终止条件，则输出当前解作为最优解，算法终止。终止条件通常设定为连续若干个新解都没有被接受时算法终止。STEP 7：逐渐减小，且满足时，转至STEP2。3 算法仿真及分析本章主要通过计算机仿真对TGI方法进行性能评估，并与传统方法进行比较。由于本文的主要关注点在于降低全网的最大资源利用率，以达负载均衡，所以本章主要讨论在不同请求数情况下TGI方法与传统的VNF-P方法在物理服务资源占用率和请求到达时延等方面的性能。同时也比较了不同算法在服务达成率上的性能。3.1 仿真环境本文搭建一个基于NFV和SDN架构的小型云数据中心网络，底层拓扑由5个物理服务器节点组成，以线性关系相连接，可以在其上部署多条线性、不分流的虚拟化SFC，物理节点的资源设置为计算资源，链路的资源设置为网络资源，以该场景为例，仿真分析TGI方法与传统的VNF-P方法性能差别。通常情况下，租户的SFC请求根据用户的业务需求提出，每个SFC请求的流量单元为1MB,链路大小设置为20Mbps，每个物理节点的资源可容纳队列也设置为20MB。设置每条SFC为（FW,NAT），业务的资源占比设置为1：1，为接近真实的网络状况，添加1Mbps的背景流量。用户无法感知底层物理服务器和链路的负载情况，因此可能出现用户的性能需求远大于单个VNF可用资源容量的情况出现，本文不考虑此种情形。3.2 仿真结果及分析本文首先考虑在SFC请求数量递增的情况下传统VNF-P方法和提出的TGI方法对用户的需求的保障情况。图 4 数据包到达时延对比Fig.4 Comparison of packet arrival delay如上图4所示，传统的VNF-P方法的用户数据包到达时延大于TGI方法，随着用户SFC请求数的增加，差距变大，说明TGI方法在保障数据中心全网负载均衡的同时，可以空出有效的资源来保障用户的QOE的同时，应对更多的用户请求；而传统VNF-P方法的时延主要包含发送时延和队列时延，发送时延基本相同，队列时延随着请求数增加而增大，因为传统VNF-P方法仅考虑单个请求的最优解，易引起流量在某些区域的集中，造成拥塞，无法及时应对之后到来的用户请求，流量队列较长，尤其对于时延敏感的业务，会引起用户QOE的恶化。图 5 最大物理资源利用率对比Fig.5 Comparison of maximum physical resource utilization如上图5所示，在SFC请求数递增的情况下，最大物理资源利用率的变化情况，传统的VNF-P方法的最大物理资源利用率大于基于资源权衡的TGI方法，且随着SFC请求的递增，差距变大，因为传统的VNF-P方法在部署服务链时仅考虑每条服务链的最小代价送达，并未考虑全网的资源负载均衡，因此流量在数据中心网络中转发时会集中于部分物理服务器上，造成负载过大。图 6 平均物理资源利用率对比Fig.6 Comparison of average physical resource utilization如上图6所示，传统的VNF-P方法的平均物理资源利用率情况也大于TGI方法，且差距越来越大，说明TGI方法利用异构资源的权衡，降低了资源池管理的粒度，减少了云数据中心资源“碎片化”的问题，降低网络整体的负载，因此可以容纳更多的用户请求。同时，利用时变图聚合模型进行资源权衡的方法，随着负载强度的增加，整体资源利用率始终较平缓，没有出现较大的波动，负载均衡状况稳定，适合云数据中心鲁棒性的需求。4 结论本文主要研究了在网络功能虚拟化环境下虚拟网络功能链的配置优化问题，针对传统SFC配置过程中的资源利用均衡度不足提出了基于时变图聚合的资源分配策略，结合NFV和SDN将硬件资源虚拟化和池化的特点，将虚拟化资源分配问题转化为异构资源的权衡问题，提升了配置的灵活度，并通过计算机仿真验证了TGI方法的有效性，仿真结果表明，基于资源主动权衡的TGI方法可以有效提高物理资源的负载均衡率及用户请求的接收率。参考文献1 P.Quinn, T.Nadeau. “Problem statement for service function chaining, IETF, Fremont,” CA, USA Tech. Rep. RFC 7498, 2015.2 Xia M, Shirazipour M, Zhang Y, et al. Network Function Placement for NFV Chaining in Packet/Optical DatacentersJ.Journal of Lightwave Technology,2015,33(8):1565-1570.3 Kreutz D, Ramos F M, Verissimo P E. Software-defined comprehensive surveyJ. Proceedings of the IEEE, 2015, 103(1): 14-76.4 Li Y, Chen M. Software-Defined Network Function Virtualization: A Survey. IEEE Access, 2015; 3: 2542-2553.5 Hwang J，Ramakrishnan K K, Wood T. NetVM: high performance and flexible networking using virtualization on commodity platformsC/Proc of the 11th USENIX Conference on Networked Systems Design and Implementation. Seattle: USENIX, 2014: 445-4586 李小庆.银行私有云的构建和实现J.金融科技时代,2017,(01):15-19.7 Wang L, Lu Z, Wen X, et al. Joint Optimization of Service Function Chaining and Resource Allocation in Network Function VirtualizationJ.Shanxi Science&Technology,2014,PP(99):1-1.8 Moens H, Turck F D. VNF-P: A model for efficient placement of virtualized network functionsC/ International Conference on Network and Service Management. IEEE, 2014:418-423.9 Chua F C, Ward J, Zhang Y, et al. Stringer: Balancing Latency and Resource Usage in Service Function Chain ProvisioningJ. IEEE Internet Computing, 2016, 20(6):22-31.10 周斌.面向大数据的高效存储容量缩减技术研究D.武汉:华中科技大学,2015.11 吕博.网络虚拟化资源管理架构与映射算法研究D.北京:北京邮电大学,2011.12 Casteigts A, Flocchini P, Quattrociocchi W, et