1、基于时变图聚合的虚拟化服务链负载均衡方法 1摘要：针对网络虚拟化背景下云数据中心服务功能链部署所引起局部资源负载不均衡问题，提出了基于时变图聚合的服务链负载均衡方法。通过将网络划分为一系列静态时变图，来描述时间窗内数据中心网络部署服务链的动态性，将静态时变图在时间序列上排列，并在相邻时变图上的同一节点之间建立链路，使之聚合为二维，从而将虚拟资源的分配问题转化为多商品流问题，并通过启发式算法高效地解决这一问题。实验结果表明，该方法与传统服务链部署方法相比，能有效降低最大链路利用率，并降低用户数据包的平均时延。关键词：网络功能虚拟化；云数据中心；服务链；负载均衡；Abstract：Concerni
2、ng 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 d
3、ata 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 alloc
4、ation 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
5、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.引言云数据中心针对不同租户的多样化的服务需求，提供相互隔离的租赁服务和弹性的云能力。目前主要通过将细粒度的网络功能组合为复杂的租赁服务以满足租户日益增长的应用需求，如
6、IETF 提出一种链式的服务组合方式来表示租户的业务需求服务功能链 1（Service Function Chain，SFC） ，即将服务抽象为租户流量经过一系列有序的，具有报文处理和转发功能的服务实体（Network Function, NF）的集合，服务实体可以包括防火墙（Firewall） 、网络地址转换（ Network Address Translation，NAT ）和深度包检测（deep packet inspection，DPI） 2等。但是，传统的 SFC 因服务实体与专用硬件的紧耦合，使得 SFC 的部署和变更尤为笨重，扩展性较差。软件定义网络 3（Software Def
7、ined Network, SDN）技术和网络功能虚拟化技术 4（Network Function Virtualization，NFV）的出现，将网络功能从通用的 x86 架构硬件上抽象出来，使得服务链的编排和部署脱离专用物理服务器的限制，租户所需求的 NF 通过软件和虚拟化的方式实现，称为虚拟服务功能实体（Virtualized Network Function, VNF） ，与传统方法相比更加灵活，同时通过将资源池化和虚拟化来进行资源调度成为可能 5。以数据中心的服务链使用状况为例，目前大型企业云数据中心在部署服务链过程中资源使用状况仍不容乐观，即在虚拟化背景下，多租户共享底层物理资源的
8、模式，普遍存在资源利用不均、利用效率普遍偏低和碎片化严重的情况：（1）数据中心要求 7*24h 不间断稳定运行，资源利用不均会导致部分物理服务器超载，从而引起宕机的情况，造成网络性能恶化；（2）拥塞会导致新服务链请求到来时，无法做出及时响应，用户体验质量（Quality of Experience，QOE）恶化；（3）资源负载不均衡，全网资源利用率低，造成资源浪费，即著名的“991 原则” 6，即 90%的物理设备，在 90%的在线时间内，只有 10%的资源利用率，不符合绿色计算的原则。因此，在 NFV 背景下研究服务链的资源负载均衡问题仍具有一定的必要性。网络的负载均衡问题通常指的是流量的负
9、载均衡，亦或是底层物理资源（计算、存储和带宽等）的负载均衡。在SFC的部署问题中，流量的大小和功能实体消耗资源的大小呈线性关系 7，因此我们假设流量的负载均衡问题和资源的负载均衡问题等同，目前Moens H等人对SFC 的部署问题进行了初步的探索 8，提出的VNE-P 方法将SFC 的部署问题看作是资源的映射问题，转化为ILP问题，并通过最优化算法求解，但是该算法未考虑虚拟资源可以灵活调度的特性，存在局部负载过大问题。Chua F C等人 9以减少物理服务器数目和降低租户使用延时为目标，在资源利用和用户体验之间权衡。本文主要针对 SFC 部署过程中异构资源的负载均衡目标，研究一种时变图聚合（T
10、ime-varying Graphs Integration , TGI）方法，在相邻静态时变图上的同一节点建立链路，将虚拟化 SFC 部署过程中的资源分配问题变成异构资源的权衡问题，最后以多商品流问题形式的求解，解决数据中心网络 SFC 资源利用不均问题。1 基于时变图聚合的服务链模型云数据中心网络中的资源主要分为三类：（1）通信资源，即服务器外接链路带宽等；（2）计算资源，表现为物理节点可以为服务功能实体提供的 CPU 和内存占用等；（3）存储资源，表现为节点硬盘阵列占用。由于在云数据中心网络中占用存储资源的主要是冗余备份数据 10，大小受备份机制的影响，为简化问题，我们在部署过程中不考虑
11、存储资源的使用，仅考虑计算和通信资源的这两种异构资源的权衡 11。由于多种异构资源联合优化的决策变量较多，且大多具有时变性，比如用户的 SFC 需求、网络的负载状况和服务器剩余计算能力等，难以实现多目标函数的全局优化。因此我们引入时变图聚合模型来描述网络的动态性能，由静态时变图构成一个有序的图序列，每个静态时变图表示该时间窗内的快照。在时变图理论 12中，底图表示一定序列中静态时变图全部路径的集合，在本文中其物理含义可以表征为全连通的、初始资源消耗为 0 的云数据中心网络，如下图 1 所示，根据理论对底图进行边和节点的演化 13，并且将前后相邻时变图中同一节点相连，演化为静态时变图依时间序列排
12、列的二维聚合图，另外根据领域知识，假设各个时间窗内网络中的状态不变，如拓扑通断、用户需求等状态不变。底 图演 化T1时 间 窗 T2时 间 窗 Tn时 间 窗用 户 需 求 1 用 户 需 求 2 用 户 需 求 n图 1 时变图聚合示意图Fig.1 Diagram of time-varying integration目前 SFC 部署主要分为串行和旁路并行两种，因为串行方式简单易部署，在工程中应用较广，因此本文主要讨论串形的 SFC，如下图 2 所示，源用户终端 和目的用户终端src间的流量通过三台物理服务器中的虚拟机（Virtual Machine，VM）部署的 SFC 进行处dst理，
13、该 SFC 部署次序为用户终端 -VNF11-VNF22-VNF2n-用户终端 ，由虚拟交src dt换机（Open vSwitch，OVS ）或核心 SDN 交换机根据控制器下发的流表进行报文转发 14。VNF11VNF12VNF1n.VNF21OVS2VNF22VNF2n.VNF31OVS3VNF32VNF3n.OVS1物 理 服 务 器 1 物 理 服 务 器 2 物 理 服 务 器 3用 户 终 端 dst云 数 据 中 心 网 络SDN控 制 器流 表 下 发图 2 串形 SFC 部署示意图Fig.2 Diagram of series SFC deployment 1.1 用户需求
14、模型通过用户需求模型将不同种类的业务（CDN、DPI 和负载均衡等）以功能需求和性能需求的形式进行表达。设 为网络服务链请求的集合， ，其中D12(,.)nDd，对于所有的 ， 表示从源节点 到目的节点 的服务链需1ind()h)src(std求。对于第 条服务链可分解为多个服务实体的有序组合，即 ，其中i 12,.iii mviv表示第 个功能实体，用户的功能需求由服务链的组成和编排控制，每个服务实体由CPUm和带宽性能需求组成，即 ，而服务链的性能需求可以看作是多个(,)iimimbandwvuthcp服务实体的性能需求的向量叠加 15，本文将性能需求的叠加看作是取最小值，必须满足用户的最
15、低的性能需求，即 ， 其中12i(,.i iidofgv。(,)ii iddconfgpubanwth1.2 服务链时变图聚合模型物 理 链 路 剩 余 带 宽物 理 服 务 器 剩 余 计 算 能 力 1T2nSrc n1n2 n3Dst虚 拟 拓 扑 聚 合 模 型用 户 的 SFC请 求 1资 源 负 载 均 衡 的SFC部 署 方 案用 户 的 SFC请 求 2用 户 的 SFC请 求 n图 3 服务链时变图聚合模型Fig .3 A time-varying integration for service function chain model 底层物理网络可以由单向无环图 来表示，
16、其中 表示网络节点的集合，(,)GNEN， 表示网络单向边的集合， 。本文的场景可以抽象为如上图 3 所示，源节nNEe点 流量经过中继物理服务器 、 和 ，到达目的节点 ，其中 NFV 技术将每个src1n23dst中继物理服务器的资源池化，供 SFC 分配使用。按照时变图的理论，将该场景按时间序列将其分为多个均匀时间窗大小的静态时变图，该集合为 ，表示在一段时12(,.)nMT间内的静态拓扑的集合，其中 ，且 ， 为固定值。1()iTitit利用 SFC 处理报文和转发报文的特性，将时变图（ ）依时间序列依次连接12,.n起来，使流量不仅可以在同一时间片内转发，而且可以在时间片之间“流动”
17、 ，同一节点在不同时间片之间建立链路，表示流量在同一节点停留，对报文进行处理，如图中虚线箭头所示，该链路可以表示为“计算链路” ，同通信链路一样，流量对计算资源的占用可以表示为对“计算链路”的占用，基于异构资源的负载均衡策略可以转化为基于流量的对链路的负载均衡策略。假设节点的剩余计算能力为 ，将其归一化为计算链路的带宽为cal。ecalut由于存在数据包压缩等服务，流量在计算链路上会出现减少的情况 16，不符合流量守恒的规律，此种业务在服务链中较少见，因此本文暂不考虑。因此本文假设节点的流量进出守恒，式（1）保证除源节点和目的节点以外的所有节点，流入节点的流量和流出节点的流量相等，对于每个节点
18、 ， 和 分别表示流出和流入该节点的流量。nN()n()()1,(),0,dedennsrcxtdDnNohwie（1）其中根据该聚合模型定义矩阵 为 的路径矩阵，该矩阵的二元变量 ，对于XDEdex每个 ， ，有式（2） ，即当某条链路 被用来传输流量 时， 为 1；链路dDeE不被用来传输流量 时， 为 0。该条件约束一条流始终流经一条路径，因为 TCP 流eddex的分流可能引起报文的乱序，容易造成流量吞吐量的下降 17，因此在目前云数据中心服务链的部署过程中较少见，本文暂不考虑分流这种情况。1,0deDeEx（2）定义 表示链路容量，其中 和 分别表示计算链路和 通信链路 的总带宽，e
19、uecub e表示链路占用容量，其中 和 分别表示计算链路和通信链路 的占用容量，下式eyy（3）和（4）约束所有的流量需求不能超过链路的容量，式（5）表示链路占用率。 ,dehxyE（3）0u（4）,ey（5）另外需要约束服务链的性能需求，使模型链路的流占用容量不小于其性能需求，如下式（6） （7）所示，针对任一服务链 ，式（6）表示流量流经路径中每一段计算链路占用id容量须大于用户最小 CPU 需求，同理式（7）表示每一段通信链路占用容量须大于用户最小的带宽需求。 min(),iecdytpuDeEA（6）ibawth（7）因为短流在数据中心的占比最高，而短流用户需求对于时延的敏感度最高，
20、因此本文将时延作为主要的用户需求指标。在云数据中心网络中，相比于排队时延，传输时延和发送时延大小基本不变，且大小可忽略不计，因此本文租户业务的端到端的时延仅考虑排队时延 18，式（8）约束服务链的最长时延不得超过用户的需求 。由于排队时延的评估maxT模型较为复杂，其中 为链路利用率，如式（ 8）所示， 为数据包的平均大小，假设流eL量为自相似流量， 为 Hurst 参数，当 时，表达式（ 8）可以与常见的 H0.5H队列模型相匹配 19。/1M1/2()max(/)eHLuT（8）为保障各租户的服务链需求，缓解网络中流量集中造成的局部资源负载过大问题，上文我们将资源的负载情况转化为二维聚合拓
21、扑的链路负载问题，因此将目标函数设置为最小化最大链路利用率 ，因为最大链路利用率该变量可以定性地表示网络的拥塞状况，max即 max()inze（9）通过该模型将服务实体的部署问题转化为多商品流问题 20，即不同时间窗产生的 SFC请求流量可以看作是“商品” ，通过多个 VNF 的转发，送达目的节点。利用路由算法在二维虚拟拓扑聚合模型上搜索符合负载均衡目标的路径，求解的路径即为服务实体的部署路径。2 求解算法由上述模型可以看出 SFC 的部署问题可以看作是一个多商品流问题，目前已经证明多商品流问题是一个 NP-hard 问题 21,如果采用线性求解方式的话，求解收敛速度较慢，造成服务的响应时间
22、过长，导致用户体验恶化。因此我们采用适用于该情况下的启发式算法求解该类问题，在保证求解速度的情况下搜索全局最优解，本文采用模拟退火算法 22来求解该问题。STEP 1：初始化阶段，设置模拟退火计划表：初始温度T（充分大） ，初始可行路径 （令它为当前解，是循环迭代P过程的起点） ，每个 T 值的循环次数 L；STEP 2：对 执行,.kSTEP3STEP6：STEP 3：执行邻域函数，得到新路径 ；*PSTEP4：计算增量 ，其中 为*maxax()()tmax()P评价函数；STEP5：执行 Metropolis 接受准则：若 ，则令 ，0t*接受 为新的当前解；否则，以概率 接受*Pep(
23、/)T作为新的当前解；STEP 6：如果满足终止条件，则输出当前解作为最优解，算法终止。终止条件通常设定为连续若干个新解都没有被接受时算法终止。STEP 7： 逐渐减小，且满足 时，转至 STEP2。T0T3 算法仿真及分析本章主要通过计算机仿真对 TGI 方法进行性能评估，并与传统方法进行比较。由于本文的主要关注点在于降低全网的最大资源利用率，以达负载均衡，所以本章主要讨论在不同请求数情况下 TGI 方法与传统的 VNF-P 方法在物理服务资源占用率和请求到达时延等方面的性能。同时也比较了不同算法在服务达成率上的性能。3.1 仿真环境本文搭建一个基于 NFV 和 SDN 架构的小型云数据中心
24、网络，底层拓扑由 5 个物理服务器节点组成，以线性关系相连接，可以在其上部署多条线性、不分流的虚拟化 SFC，物理节点的资源设置为计算资源，链路的资源设置为网络资源，以该场景为例，仿真分析TGI 方法与传统的 VNF-P 方法性能差别。通常情况下，租户的 SFC 请求根据用户的业务需求提出，每个 SFC 请求的流量单元为 1MB,链路大小设置为 20Mbps，每个物理节点的资源可容纳队列也设置为 20MB。设置每条 SFC 为（FW,NAT） ，业务的资源占比设置为1：1，为接近真实的网络状况，添加 1Mbps 的背景流量。用户无法感知底层物理服务器和链路的负载情况，因此可能出现用户的性能需求
25、远大于单个 VNF 可用资源容量的情况出现，本文不考虑此种情形。3.2 仿真结果及分析本文首先考虑在 SFC 请求数量递增的情况下传统 VNF-P 方法和提出的 TGI 方法对用户的需求的保障情况。0246810.0.51.52.0.53.0利msSFC利VNE-P利 TGI图 4 数据包到达时延对比Fig.4 Comparison of packet arrival delay如上图 4 所示，传统的 VNF-P 方法的用户数据包到达时延大于 TGI 方法，随着用户SFC 请求数的增加，差距变大，说明 TGI 方法在保障数据中心全网负载均衡的同时，可以空出有效的资源来保障用户的 QOE 的同
26、时，应对更多的用户请求；而传统 VNF-P 方法的时延主要包含发送时延和队列时延，发送时延基本相同，队列时延随着请求数增加而增大，因为传统 VNF-P 方法仅考虑单个请求的最优解，易引起流量在某些区域的集中，造成拥塞，无法及时应对之后到来的用户请求，流量队列较长，尤其对于时延敏感的业务，会引起用户 QOE 的恶化。024681012304506708利利%SFC利 VNE-P利TGI图 5 最大物理资源利用率对比Fig.5 Comparison of maximum physical resource utilization如上图 5 所示，在 SFC 请求数递增的情况下，最大物理资源利用率的
27、变化情况，传统的 VNF-P 方法的最大物理资源利用率大于基于资源权衡的 TGI 方法，且随着 SFC 请求的递增，差距变大，因为传统的 VNF-P 方法在部署服务链时仅考虑每条服务链的最小代价送达，并未考虑全网的资源负载均衡，因此流量在数据中心网络中转发时会集中于部分物理服务器上，造成负载过大。02468101203405607利利%SFC利VNE-P利 TGI图 6 平均物理资源利用率对比Fig.6 Comparison of average physical resource utilization如上图 6 所示，传统的 VNF-P 方法的平均物理资源利用率情况也大于 TGI 方法，且
28、差距越来越大，说明 TGI 方法利用异构资源的权衡，降低了资源池管理的粒度，减少了云数据中心资源“碎片化”的问题，降低网络整体的负载，因此可以容纳更多的用户请求。同时，利用时变图聚合模型进行资源权衡的方法，随着负载强度的增加，整体资源利用率始终较平缓，没有出现较大的波动，负载均衡状况稳定，适合云数据中心鲁棒性的需求。4 结论本文主要研究了在网络功能虚拟化环境下虚拟网络功能链的配置优化问题，针对传统 SFC 配置过程中的资源利用均衡度不足提出了基于时变图聚合的资源分配策略，结合NFV 和 SDN 将硬件资源虚拟化和池化的特点，将虚拟化资源分配问题转化为异构资源的权衡问题，提升了配置的灵活度，并通
29、过计算机仿真验证了 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 Dat
30、acentersJ.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 Hwan
31、g 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,
32、 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 Servic
33、e 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, Fl
34、occhini P, Quattrociocchi W, et al. Time-varying graphs and dynamic networksJ.International Journal of Parallel, Emergent and Distributed Systems,2012,27(5):387-408.13 Ferreira A. Building a reference combinatorial model for MANETsJ. Network, IEEE, 2004, 18(5):24-29.14 Jain R, Paul S. Network virtua
35、lization and software defined networking for cloud computing: a surveyJ.IEEE Communications Magazine,2013,51(11): 24-31.15 张晓红，黄继海网络功能虚拟化中的性能感知服务组合优化J电讯技术，2015，55(8):91992516 郑翠芳.几种常用无损数据压缩算法研究J.计算机技术与发展,2011,21(09):73-76.17 王富广.基于等价多路径的数据中心短流加速技术研究D.南京:南京大学,2015.18 温开源.数据中心负载均衡和流量控制技术研究D.南京:南京大学,2016.19 W. Stallings, High-Speed Networks and Internets: Performance and Quality of Service, Prentice Hall, 2002.20 Morabito R, Souza M C D, Vazquez M. Approximate decomposition methods for the analysis of
