节点效用最大化的服务功能链构建方法

张传浩，周　桥

(1.铁道警察学院 公安技术系，郑州 450053；　2.国家数字交换系统工程技术研究中心，郑州 450002)(*通信作者电子邮箱zhangchuanhao@rpc.edu.cn)

0　引言

随着网络流量的急剧膨胀和网络业务的不断更新，当今的计算机网络越来越依赖于中间件盒子(middlebox)所提供的功能。文献[1]定义中间件盒子是工作在计算机网络4～7层的一种网络设备，用来对经过它的流量进行检测和修改。中间件盒子在网络中发挥着越来越重要的作用，如改善安全、提高性能、减小带宽以及提供其他新颖功能[2]等。但如何在网络中引导流量通过一定顺序的中间件盒子构成服务功能链来提供丰富的功能却是一个非常复杂的过程：首先需要在网络中的合适位置部署中间件盒子，然后需要手工配置转发规则来引导流量通过一定顺序的盒子。随着软件定义网络(Software Defined Networ, SDN)[3]和网络功能虚拟化(Network Function Virtualization, NFV)[4]技术的兴起，如何灵活高效地解决这些问题再次成为研究的热点。

SDN技术提供了逻辑集中式的管理控制，解耦了数据平面和转发平面，给中间件盒子提供了可编程的转发规则配置方式。StEERING方法[5]通过对OpenFlow多级流表进行改进来实现流量引导；SIMPLE方法[6]构建了基于SDN的策略执行层，能够使中间件的深度策略转化更加有效，并解决了流量引导中的环路问题；FlowTags方法[7]则通过对中间件以及交换机的改进，使之能够对进出的流进行标记来实现流量引导。但是基于SDN技术实现的服务功能链存在着一些共性的问题：首先，无法根据业务需求来实现中间件的动态部署；其次，当网络中部署着大量中间件盒子时，硬件成本及管理开销太大；最后，中间件盒子出现故障以及过载时，恢复速度过慢难以满足用户需求。

NFV技术克服了传统中间件盒子种类繁多、价格昂贵、结构封闭且十分不利于统一集中管理配置等缺点，由基于软件实现的虚拟功能代替基于硬件实现的硬件盒子，并部署于廉价的商用设备(例如x86服务器)上。Sekar等[8]提出了一种集成统一的中间件盒子结构CoMB(Consolidated MiddleBox)来解决传统中间件盒子所带来的弊端，每个CoMB运行多个基于软件的中间件，根据不同的业务启动相应的中间件。ClickOS[9]是基于Xen实现的软件平台，通过优化中间盒子处理能够创建快速启动的、低延迟的小型虚拟机。这些基于NFV的虚拟化中间件盒子主要侧重于提升数据平面以及软件上的实现，没有涉及虚拟功能实例的最优控制。基于SDN+NFV的方法能够很好地解决上面出现的问题：首先能实现虚拟中间件盒子间的流量引导；其次能根据业务需求动态部署虚拟的中间件盒子；最后还能对故障或者过载的中间件盒子实现迁移，从而实现虚拟功能实例的最优控制。OpenNF[10]和Slick[11-12]都是国外最新提出的基于SDN+NFV的服务功能部署架构。OpenNF利用SDN控制器设计了一个服务功能控制平面、一系列的API接口以及服务功能组合与转发机制；Slick设计了一个允许用户对某些指定流的服务功能进行编程处理的架构，通过用户自定义编程来完成虚拟中间件盒子的部署和流量引导。OpenNF和Slick的研究重点偏向于控制平面设计和控制软件的实现，且其服务功能链构建算法往往将流量引导和中间件盒子部署问题分开考虑，达不到节点资源效用最大化。

与当前主流方法不同，本文将虚拟化的中间件盒子部署问题和流量引导问题联合考虑，提出了一种节点效用最大化的服务功能链构建方法NUM(Node Utility Maximization)。实验结果表明，与主流方法相比，NUM在构建时间、构建成功率、网络拥塞率以及节点效用上均具有优越性。

1　服务功能链构建问题

SDN技术使得中间件盒子的流量引导更加灵活便利，NFV技术则可虚拟化中间件盒子且使其易于动态部署。在SDN+NFV环境下，为了实现用户订制的服务功能，需要利用NFV技术动态部署虚拟化的中间件盒子，再利用SDN技术从源节点引导流量通过特定顺序的中间件盒子到达目的节点构成服务功能链。本文将中间件盒子部署问题和流量引导问题联合起来，定义为服务功能链构建问题(Service Function Chain Construction Problem, SFCCP)。

如图1所示，本文所用的中间件盒子是建立在商用服务器中ClickOS平台上虚拟化的中间件盒子，控制器控制交换机根据业务需求动态地进行虚拟中间件盒子的实例化，在没有业务需求时关闭来节省资源。以图1为例简单说明服务功能链构建问题：根据业务需求，流量1需分别经过防火墙、入侵检测系统以及一个内容过滤器，流量2仅需经过防火墙和入侵检测系统，流量3则仅需经过防火墙和内容过滤器。为了满足用户的服务功能需求，首先需要选择出最优节点并求解出一条最优路径和资源分配，然后以业务需求和路径上的资源分配为条件来实现虚拟化中间件盒子的实例化，最后控制器引导流量在确定的路径上通过实例化的中间件盒子完成服务功能链构建。

图1　服务功能链构建示例Fig. 1　Example of service function chain construction

在SDN+NFV的网络环境中，主要有以下因素影响着SFCCP：

1)用户策略：用户制定策略的数量和复杂度直接决定了SFCCP的求解难度。本文对用户策略进行划分，每条策略划分成多个经过单一中间件盒子的流，以此来降低求解难度。

2)网络拓扑限制：主要是网络节点数量和网络节点的链接情况，以及链路带宽限制。

3)节点资源限制：交换机节点的转发处理能力主要被单个物理设备的三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)资源所限制，属于底层转发能力。

4)服务器资源限制：在服务器上的ClickOS平台上虚拟出中间件盒子需要耗费计算资源与存储和带宽资源，属于配置层计算能力。

5)虚拟网络功能相关性问题：本文讨论的虚拟网络功能模块均具备独立性特点，即均以用户需求为驱动进行部署，模块间交互接口网络数据流量；同时本文考虑的重点也是以模块为基本单元的服务链部署策略，所以模块之间的层级相同，可以不考虑其相关性。

2　服务功能链构建方法

2.1　服务功能链构建机制

各种因素互相影响、相互制约，使得虚拟中间件盒子的部署以及部署完成后的流量引导变成一个极为复杂的过程。为了解决SFCCP，本文设计如图2所示的服务功能链构建机制，通过扩展现有SDN控制器的南向接口实现对服务器上虚拟中间件的部署与管理。该机制核心的控制器主要由三部分组成：资源处理器、转发规则产生器以及服务器管理器。

1)资源处理器以网络拓扑结构、用户制定的服务功能需求以及交换机和服务器等的资源限制为输入，通过一定的算法实现对服务器的资源分配和网络节点及路径的选择；资源处理器计算的结果直接输出到转发规则产生器和服务器管理器。

2)服务器管理器根据资源处理器所计算的资源分配在对应的服务器上进行中间件盒子的实例化，并根据网络流量动态地进行开启和关闭处理。

3)转发规则产生器根据资源处理器所计算出的网络节点和路径下发转发规则。

在服务功能链构建机制中，规则产生器和服务器管理器是重要的组成部分，根据资源处理器所处理的结果，服务器管理器先进行虚拟中间件盒子的实例化，规则产生器再引导流量通过实例化的虚拟中间件盒子；而资源处理器是整个机制的核心，它负责对各种输入进行建模并计算，下一节将描述资源处理器建模的主要内容。

图2　服务功能链构建机制Fig. 2　Mechanism of service function chain construction

2.2　服务功能链构建模型

在SDN+NFV的环境下，虚拟中间件在网络节点的部署问题等同于节点资源对虚拟中间件的分配问题，而流量引导问题等同于对网络中最优节点的选择问题。因此服务功能链构建问题可简化成一种考虑链路带宽分配、节点资源分配以及服务器资源分配的新型路由问题。

模型描述如下：流量根据其不同的业务需求，可被划分成若干个从si到ti的流comi(si,ti,di)，di表示总的业务需求量；给定网络拓扑G=(V,E)，链路E的链路容量为B(E)，节点V的容量为C(V)，分配给V节点的服务器资源为S(V)，以及一系列的服务功能业务流量D={com1,com2，…,comk}。

模型整体目标是在尽可能多业务的同时，耗费最少的节点资源满足所有流量的业务功能需求，从而达到节点最优和效能最大化的目的。服务功能链构建问题核心在于选择最优的节点构建服务功能链来满足服务需求，根据模型整体目标，将该问题分为两部分：第一部分是最小化问题，即选择最小的节点集合来满足所有的服务需求；第二部分是最大化问题，即在已选节点的基础上满足最大的业务流量，从而达到节点资源和服务器资源最大效用。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

∀i∈[1,m],j∈{1,2},v∈V,∀u∈Vcomi

(8)

(9)

(10)

(11)

其中:式(1)是整体优化目标，选择最小的节点集合来满足业务需求；式(2)～(6)表示链路带宽限制、节点资源限制、服务器资源限制以及满足服务需求的约束；式(7)则要求节点资源处理能力大于业务需求，从而满足处理条件；式(8)～(11)表示在节点和链路上的流量守恒约束。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

其中：式(15)、(16)表示节点v的总流量守恒，式(17)、(18)分别是链路和节点资源限制；式(19)则是流量非负约束。

2.3　求解算法

该服务功能链部署问题是一个组合优化问题，同时也是NP难问题，此类问题求解方法通常采用模拟退火等启发式算法来寻找最优解。模拟退火(Simulated Annealing，SA)算法[13]能够有限度地接受劣解，可以跳出局部最优解，并且具有原理简单、使用方便、所求解全局最优或近似全局最优等特点，但是其求解时间过长，步长和温度T的初值较难设置，而且搜索过程中有概率遗失当前的最优解。而禁忌搜索算法(Tabu Search, TS)[14]模仿人类的记忆能力，在搜索过程采用设置禁忌表的方式来避免陷入局部最优以及迂回搜索，很好地克服了模拟退火算法的缺点。本文参考目前解决网络路径选择与节点资源分配问题常用的组合算法思路[15-16]，使用基于TS改进的组合模拟退火算法TS-CSA来解决服务功能链部署问题。

以下简单说明基于TS改进的组合模拟退火算法的主要步骤。TS-CSA算法共分为两层：其中内层算法是对节点选择决策进行优化，即对问题第一部分进行优化；外层算法则是在节点选择决策的基础上进行效用最大化，即对问题第二部分进行优化。设g为该问题的一个解，该解在SA算法中称为一个配置或状态。设Ω为状态空间，定义E(g)为状态g的能量。Metropolis策略[17]用于计算在温度t时从状态g到状态g′的转移概率，即：

(20)

其中温度T控制着SA算法的速度。

在外层优化算法中，利用禁忌搜索算法中的禁忌表思想对组合模拟退火算法进行改进，同时增加了升温操作，提高算法搜索效率。外层优化算法的具体步骤如下:

1)置空禁忌表H，设置模拟退火计划表，令初始温度为t，升温系数τ=1，降温系数ξ=0．9，随机生成问题的初始解X0，同时令当前记忆最优解Xbest=X0，Ω←Ω∪X0，且令禁忌长度λ(X0)=n，K=1。

2)执行外层邻域函数，同时更新禁忌表中各对象的禁忌长度。

3)执行内层优化算法。

4)若未满足同温度下的抽样稳定准则，返回步骤2)继续寻找新解，否则执行降温操作。

5)若未满足升温条件，则返回步骤2)继续寻找新解，否则执行升温操作。

6)检验收敛性。

算法伪代码如下所示：

1)

while not stop

2)

Xbest=X0;tk=t;

3)

fori=1 toL

4)

ifλ(X0)>0

5)

getXnew,calculateE(Xnew)

6)

λ(X0)=λ(X0)-1;

7)

ifλ(X0)=0;

8)

goto procedure TS-CSA partⅡ

9)

end if

10)

Update the tabu listH;

11)

end if

12)

ifE(Xnew′)

13)

Xbest=Xnew′;

14)

ifE(Xnew)

15)

X0=Xnew;

16)

else CalculateP(tk)=

exp[-(E(Xnew)-E(Xk))/τt];

17)

end if

18)

if random(0,1)

19)

X0=Xnew;

20)

end if

21)

end if

22)

end for

23)

K=K+1;t=ζt;

24)

end while

25)

printXbest

内层优化算法的步骤为:

1)以Xnew为当前初始解和最优解，构造内层邻域解，得到新解Xnew′。

2)判断新解的优劣性。

3)若未达到同温度下的抽样稳定准则，则返回步骤2);否则算法终止，返回外层优化算法。

内层算法(TS-CSA partⅡ)伪代码如下所示：

1)

while not stop

2)

ifE(Xnew′)

3)

Xnew=Xnew′;

4)

else CalculateP(t)=exp[-(E(Xnew′)-E(Xnew))/τt];

5)

if random(0,1)

6)

Xnew=Xnew′;

7)

end if

8)

end while

3　实验仿真与性能评估

3.1　实验平台

为了验证模型与算法的可靠性与有效性，本实验算法仿真部分在配置Intel Core i7 CPU 3.40 GHz、4 GB内存的计算机上运行。实验网络模型如图3所示，底层网络拓扑和服务功能请求的拓扑由GT-ITM[18]工具生成，通过仿真来验证算法的性能。本文设计的服务功能链构建原型模型采用ClickOS模拟网络中的大量元服务实例，ClickOS是一款高性能的虚拟化平台，当单个物理CPU核运行100个实例时，ClickOS虚拟机(Virtual Machine, VM)能实现整体10 Gb/s的速率。实验平台由NetFPGA 10G实现的OpenFlow交换机的全连接网络组成：每台交换机连接一台服务器，运行ClickOS平台；每台服务器配置3.4 GHz Intel Core i7处理器、4 GB内存和1 Gb/s网络接口。

3.2　实验仿真

3.2.1服务功能链构建时间

分别用GT-ITM模拟节点数k=5，连接度d=2，以及按照网络复杂度越来越高的原则分别设计：k=15,d=4;k=25,d=6;k=50,d=8;k=100,d=8等网络拓扑结构，服务功能链数M=10保持不变。通过Matlab实验分别仿真StEERING、SIMPLE和本文NUM方法的服务功能链的构建时间随节点数的变化，结果如图4所示；再用GT-ITM模拟节点数k=10，连接度d=3的网络拓扑，使服务功能链数逐渐增加，分别为M=5,10,20,50,100，通过Matlab实验分别仿真模拟退火算法、禁忌搜索算法和改进的组合模拟退火算法计算服务功能链的构建时间随服务功能链数的变化，结果如图5所示。构建时间越短，说明算法效率越高。

图3　实验网络拓扑Fig. 3　Experimental network topology

图4　服务功能链构建时间随节点数变化情况Fig. 4　Service function chain construction time changes with the number of nodes

图5　服务功能链构建时间随服务功能链数变化情况Fig. 5　Service function chain construction time changes with the number of service function chains

3.2.2服务功能链构建成功率

定义服务功能链构建成功率SR=m/M,其中:M为需求服务功能链数量，m为实际成功构建的服务功能链数量。按照3.2.1节的数据设定通过Matlab仿真以下情况：随着拓扑节点数增多不同算法的构建成功率，结果如图6所示；随着服务功能链增多不同算法的构建成功率，结果如图7所示。成功率越高说明算法越有效。

3.2.3网络拥塞率

图6　服务功能链构建成功率随节点数变化情况Fig. 6　Success rate of service function chain construction changes with the number of nodes

图7　服务功能链构建成功率随服务功能链数变化情况Fig. 7　Success rate of service function chain construction changes with the number of service function chains

图8　构建拥塞率随服务功能链数变化情况Fig. 8　Congestion rate of construction changes with the number of service function chains

3.2.4节点平均效用

图9　节点平均效用随服务功能链数变化情况Fig. 9　Mean utility of nodes changes with the number of service function chains

3.3　性能分析

图4和图5反映了随着网络节点数和网络中服务功能链数增多时不同算法的服务功能链构建时间变化情况，可以看到，NUM在构建时间上明显少于其他两种方法，其算法采用分层式的结构降低了模型求解的复杂度，更利于最优解的寻找；图6和图7反映了网络节点数和网络中服务功能链数与服务功能链构建成功率之间的关系，可以看到，随着节点数和服务功能链数的增多，构建成功率呈下降趋势，但是NUM方法构建成功率仍高于其他两种算法，这是因为构建成功率取决于解的优异性，而本文TS-CSA算法寻找到的最优解优于其他方法；图8反映了网络中服务功能链数与网络拥塞率之间的关系，可以看出服务功能链数和拥塞率成正比，但采用NUM拥塞率较低，负载均衡性能优于其他两种方法，因为该方法在网络中所选的节点优于其他方法，能够避免节点拥塞；而图9反映了网络中服务功能链数与节点平均效用之间的关系，可以看出本文方法明显提升了节点的效用(约20%)，因为该方法可以在全网范围内找到最优节点并进行资源最大化利用，能达到节点效用最优。

4　结语

本文主要解决了SDN+NFV环境下的服务功能链构建问题。首先，对SDN+NFV环境下的服务功能链构建问题进行详细描述，分析了影响SFCCP的主要因素；然后介绍了本文所设计的服务功能链构建机制，分别建立了最优化节点选择模型和最大效能模型，并利用禁忌搜索改进模拟退火算法对模型进行求解；最后，对比测试了在网络节点和服务功能链数增多的情况下，不同算法的服务功能链构建时间、构建成功率和网络拥塞率的变化以及采用本文方法在节点效用上的提升，结果表明本文方法具有明显优势。下一步的研究主要集中在节点数及服务功能链数增多时如何进一步提高构建服务功能链的成功率，以及如何对过载的服务器虚拟机进行迁移来达到网络中负载均衡的目的。

参考文献:

[1]GEMBER A, PRABHU P, GHADIYALI Z, et al. Toward software-defined middlebox networking [C]// HotNets-XI: Proceedings of the 2012 11th ACM Workshop on Hot Topics in Networks. New York: ACM, 2012: 7-12.

[2]SHERRY J, HASAN S, SCOTT C, et al. Making middleboxes someone else’s problem: network processing as a cloud service [J]. ACM SIGCOMM Computer Communication Review — Special October issue SIGCOMM ’12, 2012, 42(4): 13-24.

[3]McKEOWN N. Software-defined networking [J]. INFOCOM Keynote Talk, 2009, 17(2): 30-32.

[4]CARAPINHA J, JIMÉNEZ J. Network virtualization: a view from the bottom [C]// VISA ’09: Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 73-80.

[5]ZHANG Y, BEHESHTI N, BELIVEAU L, et al. StEERING: a software-defined networking for inline service chaining [C]// ICNP 2013: Proceedings of the 2013 21st IEEE International Conference on Network Protocols. Piscataway, NJ: IEEE, 2013: 1-10.

[6]QAZI Z A, TU C-C, CHIANG L, et al. SIMPLE-fying middlebox policy enforcement using SDN [C]// SIGCOMM ’13: Proceedings of the ACM SIGCOMM 2013 Computer Communication. New York: ACM, 2013: 27-38.

[7]FAYAZBAKHSH S K, SEKAR V, YU M, et al. FlowTags: enforcing network-wide policies in the presence of dynamic middlebox actions [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 19-24.

[8]SEKAR V, EGI N, RATNASAMY S, et al. Design and implementation of a consolidated middlebox architecture [C]// NSDI’12: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 24.

[9]MARTINS J, AHMED M, RAICIU C, et al. ClickOS and the art of network function virtualization [C]// NSDI’14: Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 459-473.

[10]GEMBER-JACOBSON A, VISWANATHAN R, PRAKASH C, et al. OpenNF: Enabling innovation in network function control [C]// SIGCOMM ’14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM, 2014: 163-174.

[11]ANWER B, BENSON T, FEAMSTER N, et al. A slick control plane for network middleboxes [C]// HotSDN ’13: Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 147-148.

[12]ANWER B, BENSON T, FEAMSTER N, et al. Programming slick network functions [C]// SOSR ’15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research. New York: ACM, 2015: Article No. 14.

[13]KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671-680.

[14]GLOVER F, LAGUNA M. Tabu search [M]// Metaheuristic Procedures for Training Neutral Networks. Boston: Springer, 1993: 53-69.

[15]秦进,倪玲霖,缪立新.多级多商品流物流网络设计的优化模型与组合模拟退火算法[J].计算机应用研究,2010,27(9):3348-3351. (QIN J, NI L L, MIU L X. Optimization model and combined simulated annealing algorithm for multi-level multi-commodity logistics network design [J]. Application Research of Computers, 2010, 27(9): 3348-3351.)

[16]LIN Y, BIAN Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing Tabu search algorithm to solve the symmetrical traveling salesman problem [J]. Applied Soft Computing, 2016, 49(C): 937-952.

[17]METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines [J]. The Journal of Chemical Physics, 1953, 21(6): 1087-1092.

[18]ZEGURA E W, CALVERT K L, ACHARJEE S B. How to model an internetwork [C]// INFOCOM’96: Proceedings of the Fifteenth Annual Joint Conference of the IEEE Computer Societies on Networking the Next Generation. Washington, DC: IEEE Computer Society, 1996, 2: 594-602.