动态网络环境中快速且负载均衡的服务功能链部署方法

摘要

本发明公开了一种动态网络环境中快速且负载均衡的服务功能链部署方法。传统的服务功能链部署算法大多是单独针对多服务器网络或数据中心网络提出的，没有普适性，本发明法既能使用在多服务器网络下，也可以使用在数据中心网络下，并且不受网络规模限制，因此与传统的部署算法相比，本发明的适用范围更广，利用强化学习模块学习了网络拓扑链路，再结合负载均衡模块可以得到接近最优解的最短路，并且可接受更多的SFC部署需求，找到的部署方案的总利润就会比传统部署算法更高，在得到有效训练的情况下，能够快速的输出SFC部署方案，相比于其他的高准确率部署算法，本发明的算法速度要快很多。

说明书

技术领域

本发明涉及动态网络服务功能链技术领域，具体涉及一种动态网络环境中快速且负载均衡的服务功能链部署方法。

背景技术

目前，大多数网络使用大量专用硬件设备，提供防火墙和网络地址转换(NAT)等功能。服务提供者提供的各种服务通常需要专门的硬件设备。随着网络规模的不断扩大，大数据、云计算等新兴行业的迅速扩张，开始一项新的服务需要部署各种专用硬件设备，使得设计私有协议和保护用户数据安全变得极为困难。由于用户在专用硬件设备上共享资源，黑客可以利用某些设备的某些安全漏洞，轻松获取大量用户的数据。随着服务需求的不断增加，服务提供者必须定期扩展其物理基础设施，从而导致较高的基础设施和运营成本。

基于网络服务需求，服务提供商开始关注网络功能虚拟化(NFV)技术。与以前的专用硬件设备不同，NFV技术将网络服务功能转换为软件，并通过通用服务器设备提供服务。虽然使用相同的服务器，但是NFV技术将计算机上的资源和功能隔离开来，然后将它们分配给用户，从而保证了用户数据的私密性和安全性。使用NFV技术，服务提供者可以通过管理软件来分发服务来快速响应服务需求和流量变化。此外，通过集中资源管理，服务提供者可以降低基础设施和运营成本。

使用NFV技术，我们可以使用虚拟网络函数(VNFs)来表示部署在连续网络拓扑节点上的网络服务，形成服务功能链(SFC)。这种方法降低了硬件成本和运营成本，但需要对IT资源和带宽资源具有健壮性要求。然而，NFV的发展也带来了挑战。例如，随着用户需求的增长，为用户提供服务的SFC可能需要经常进行调整，以确保服务的连续性。例如，当用户移动的情况下，保持连续性需要改变网络拓扑中的SFC，以适应用户的请求。所以，构建和调整SFC以降低各类成本的智能方法值得我们研究。

目前对于动态SFC部署的研究也有很多，比如CG算法。由于过程中加入了ILP方法，CG算法的部署成功率较高。其主要思想是把问题抽象成一个数学规划问题，在保证负载均衡的条件下，最大化服务提供商利润。CG算法即使经过了时间优化，但仍然需要相当长的时间来解ILP的解或得出列生成算法的解，最终才能输出合适的SFC。时间长的缺陷是它最大的问题。

对于动态SFC部署的研究还有其他算法，比如viterbi算法。这是一种启发式算法，所以在时间上具有优势。其主要思想是把支持需要部署功能的节点分层，在每一层之间寻找最短路，从而在使链路最短的情况下，最大化服务提供商利润。由于viterbi算法只考虑局部最优，所以对于动态SFC部署的全局问题，虽然运算时间短，但往往不能得到整个动态SFC部署问题的最优解决方案。

发明内容

针对现有技术中的上述不足，本发明提供的一种动态网络环境中快速且负载均衡的服务功能链部署方法解决了服务功能链部署缺陷的问题。

为了达到上述发明目的，本发明采用的技术方案为：一种动态网络环境中快速且负载均衡的服务功能链部署方法，包括以下步骤：

S1、通过强化学习算法输出网络拓扑的可选路径集合；

S2、通过负载均衡算法选择可选路径集合在中负载均衡条件下性价比最高的路径；

S3、选取性价比最高的路径作为负载均衡的服务功能链部署方法。

进一步地：所述步骤S1的具体步骤为：

S11、通过QLFHM算法得到训练后的矩阵Q；

S12、通过训练后的Q矩阵得到可选路径集合。

进一步地：所述步骤S11的具体步骤为：

S111、初始化参数并随机生成起始节点v1和v2；

初始化参数包括：将矩阵Q初始化为全零矩阵，初始化奖励矩阵R，设置低阈值h_min和高阈值h_max，并初始化迭代参数h为0；

S112、在链路chain中加入起始节点v1；

S113、当h≤h_max时，将链路chain复制n份，并在每份链路chain中增加一个邻接节点v2，否则直接输出矩阵Q，结束该方法；

n为起始节点v1的集合V_v1中的元素数，邻接节点v2为起始节点v1所有路径相邻的节点；

S114、令h加1，更新当前状态，并令v1＝v2；

S115、当h＞h_min时，通过奖励矩阵R将链路chain信息写入矩阵Q中，返回步骤S113，否则直接返回步骤S113。

进一步地：所述步骤S111中矩阵Q和矩阵R均为五维矩阵，所述矩阵Q和R中的5个元素的下标分别为now_h，now_node，action_node，end_node，h，初始化奖励矩阵R具体为：设置奖励矩阵R中下标为now_node和end_node的元素值为1000，其余下标的元素值为0。

进一步地：所述步骤S115中通过奖励矩阵R将链路chain信息写入矩阵Q中的公式为：

上式中，s为状态集合，a为动作集合，s′为未来状态集合，a′为未来动作集合，r为奖励矩阵R中的元素，α为学习率，取值为[0，1]。

进一步地：所述步骤S12具体包括以下步骤：

S121、读取用户请求列表RE，根据用户请求列表RE中的每一条请求re从矩阵Q中获取备选路径集合PA；

S122、当备选路径集合PA中的路径pa可以部署用户请求列表的VNFs时，将路径pa加入到可选路径集合CA中，否则返回步骤S121；

S123、当可选路径集合CA为空时，用户请求部署失败，返回步骤S16，否则进入步骤S124；

S124、输出可选路径集合CA。

进一步地：所述步骤S2的具体步骤为：

S21、对可选路径集合CA中的每一条备选路径pa计算性价比得分；

S22、选取性价比得分最高的备选路径。

进一步地：所述步骤S21中性价比得分的计算公式为：

上式中，score为备选路径pa的性价比得分，weight_link为链路权重，weight_node为节点权重，SFC为可选路径集合，e为链路，v为节点，weight_{link>为链路e的权重，weightnode>为节点v的权重，Be为链路带宽资源，Iv为节点计算资源，其中，}

weight_node+weight_link＝1。

本发明的有益效果为：

(1)适用范围广。传统的服务功能链部署算法大多是单独针对多服务器网络或数据中心网络提出的，没有普适性。本发明法既能使用在多服务器网络下，也可以使用在数据中心网络下，并且不受网络规模限制，因此与传统的部署算法相比，本发明的适用范围更广。

(2)部署利润高。由于本发明提出的QLFHM算法，利用强化学习模块学习了网络拓扑链路，再结合负载均衡模块可以得到接近最优解的最短路，并且可接受更多的SFC部署需求。找到的部署方案的总利润就会比传统部署算法更高。

(3)决策时间短。由于本发明提出的算法中利用强化学习，在得到有效训练的情况下，能够快速的输出SFC部署方案，相比于其他的高准确率部署算法，本发明的算法速度要快很多。

附图说明

图1为本发明的流程图；

图2为本发明步骤S1的流程图；

图3为本发明步骤S11的流程图；

图4为本发明步骤S12的流程图。

具体实施方式

下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。

如图1所示，一种动态网络环境中快速且负载均衡的服务功能链部署方法，包括以下步骤：

S1、通过强化学习算法输出网络拓扑的可选路径集合，如图2所示，具体步骤为：

S11、通过QLFHM算法得到训练后的矩阵Q，如图3所示，具体步骤为：

S111、初始化参数并随机生成起始节点v1和v2；

初始化参数包括：将矩阵Q初始化为全零矩阵，初始化奖励矩阵R，设置低阈值h_min和高阈值h_max，并初始化迭代参数h为0，矩阵Q和矩阵R均为五维矩阵，所述矩阵Q和R中的5个元素的下标分别为now_h，now_node，action_node，end_node，h；now_h指在访问当前状态已过节点的数量，now_node代表当前状态的所在节点，action_node是下一步动作可用的节点集，end_node指SFC最终将达到的节点，h是能够满足部署需求的最少节点数，初始化奖励矩阵R具体为：设置奖励矩阵R中下标为now_node和end_node的元素值为1000，其余下标的元素值为0。

S112、在链路chain中加入起始节点v1；

S113、当h≤h_max时，将链路chain复制n份，并在每份链路chain中增加一个邻接节点v2，否则直接输出矩阵Q，结束该方法；

n为起始节点v1的集合V_v1中的元素数，邻接节点v2为起始节点v1所有路径相邻的节点；

S114、令h加1，更新当前状态，并令v1＝v2；

S115、当h＞h_min时，通过奖励矩阵R将链路chain信息写入矩阵Q中，公式为：

上式中，s为状态集合，a为动作集合，s′为未来状态集合，a′为未来动作集合，r为奖励矩阵R中的元素，α为学习率，取值为[0，1]。并输出矩阵Q，返回步骤S113，否则直接返回步骤S113。

S12、通过训练后的矩阵Q得到可选路径集合。如图4所示，包括以下步骤：

S121、读取用户请求列表RE，根据用户请求列表RE中的每一条请求re从矩阵Q中获取备选路径集合PA；

S122、当备选路径集合PA中的路径pa可以部署用户请求列表的VNFs时，将路径pa加入到可选路径集合CA中，否则返回步骤S121；

S123、当可选路径集合CA为空时，用户请求部署失败，返回步骤S16，否则进入步骤S124；

S124、输出可选路径集合CA。

即使在决策阶段，矩阵Q也不一定是永久不变的。可根据实际情况进行调整，系统支持对新路径或节点进行补充学习，或删除失效路径和节点。

S2、通过负载均衡算法选择可选路径集合在中负载均衡条件下性价比最高的路径，具体步骤为：

S21、对可选路径集合CA中的每一条备选路径pa计算性价比得分，性价比得分的计算公式为：

上式中，score为备选路径pa的性价比得分，weight_link为链路权重，weight_node为节点权重，SFC为可选路径集合，e为链路，v为节点，weight_{link>为链路e的权重，weightnode>为节点v的权重，Be为链路带宽资源，Iv为节点计算资源，其中，}

weight_node+weight_link＝1。

S22、选取性价比得分最高的备选路径。

S3、将性价比最高的路径作为负载均衡的服务功能链部署。

记录该条服务的起始时间t_start-re和截止时间t_end-re，将re加入在线服务SFC集合ONL中，改变各资源剩余情况，检查ONL中是否有SFC到达服务截止时间，有则将该re撤出ONL并返还各资源占用。

网络可以看成是图G＝(V，E)，其中V表示节点集合，E表示节点之间的链路集合。每个e∈E代表两个网络节点之间的物理链路；B_e∈N显示链接的带宽承载能力。每个v∈V是一个网络服务器，作为两个用户的访问点和交换机；每个服务器还具有IT资源容量；I_v∈N表示v的IT资源。T代表了VNFs的集合。T_v∈T来表示节点v支持的集合。所有服务器都可以提供NFV服务，然而可能有些服务器只支持部分VNFs。假设带宽资源和节点IT资源是有限的。

RE用来代表所有传入的请求的集合。每个请求i∈RE由以下变量组成：s_i，d_i，P_i，r_i。这里s_i指的是客户的访问节点，d_i是用户的所需数据提供者的节点，P_i是一个向量，其中包含在SFC中要求必须存在的VNFs的序列，而r_i指的是薪酬支付。请求的SFC成功部署后，r_i与要求的VNFs的数量有关。ω代表单位值。为了方便起见，令ω＝1。

用户i请求的SFC成功部署后获得的利润由profit_i表示，而l_i代表成功部署的SFC链长，即SFC的节点数目。

profit_i＝r_i-l_i*ω

一条成功布署的SFC应该满足用户需求中的起止节点，合适的长度，以及SFC上按序排列的VNFs。由于要考虑运营商利润，链长l_i受制于r_i的限制。

我们使用一个布尔变量P_j，v来表示第j个VNF(表示为vnf_j)被部署在节点v上的状态。p_j，v的值为1表示可以部署，值为0则表示不可以部署。

布尔变量x_i表示用户i请求的SFC是否可以部署成功。如果该SFC可以部署，则x_i值为1，否则为0。Node_SFC_i表示用户i的SFC中的所有节点集合。Node_vNFs_i表示用户i的SFC中的用于部署VNF的节点集合。Link_SFC_i表示用户i的SFC中的所有路径。另外SFC的首尾节点不部署VNF。

Node_vNFs_i＝Node_SFC_i-(s_i+d_i)

z_i，j，π是一个布尔变量，用于表示用户i的SFC中的VNFs是按序排列的。当SFC由起点出发，每个部署VNF的节点经过路径π到达的是需要部署的下一个VNF的节点，直到尾节点时，z_i，j，π为1，否则为0。

假设在动态SFC请求场景里，用户请求到达期间，服务提供者将为新请求提供服务，并在某些服务请求时间结束时，取消该SFC的服务功能。请求到达时间会有一定时间间隔。因此，在任何时候，服务提供者都有可能会处理两种类型的用户请求。这主要会影响服务提供商的运营费用，包括检查是否有新的请求可用以及是否存在需要取消的在线SFC。

动态部署的目标是最大化服务提供者的利润。假定IT资源和带宽容量作为部署约束条件存在，但它们只影响部署能力，而不影响操作成本。

Node_vNFs_put_i表示用户i的SFC中部署VNFs的节点的集合。I_max_v表示节点v的IT资源的最大承载量。I_use_j表示第j个VNF所需的IT资源量。Link_vNFs_put_i表示用户i的SFC中所有路径的集合。B_max_e表示路径e的带宽资源的最大承载量，而B_use_i表示用户i的SFC所需要的带宽资源量。对于网络全局来说：

对于网络中每个节点v：

对于网络中每个路径e：

确保用户在任何服务时间内使用的带宽和IT资源不会超过可用的总容量。

布尔变量表示用户i的请求是否被成功部署。所以这个问题的目标是最大化服务提供者的总利润K，描述如下：

在为一个请求生成SFC之后，当有足够的资源可用时，SFC将被部署到相应的路径上。路径的带宽资源将被消耗，假设消耗了一个单元。

部署vNF的服务器的IT资源也将被消耗，假设消耗了一个单元，但是用户访问节点和数据提供者节点不会消耗IT资源。

当SFC的服务时间届满后，SFC将退出网络。部署VNF的服务器的IT资源和途径路径的带宽资源也将被恢复。

该发明可以部署在基于多服务器的支持NFV的运营商网络中，以实现服务功能链的部署。NFV技术将控制功能从网络交换设备中分离出来，将其以软件的形式实现放置在通用的服务器上运行，运营者可随时直接进行控制功能编程。

NFV技术有助于实现网络的灵活化，避免专用设备造成的网络复杂僵化，从而实现了网络的简单控制以及SFC的灵活部署，最终使得只要通过一些简单的控制工具，就能实现对整个网络的控制和管理。这是支持NFV技术的网络的优势之一。

网络运营商可以将本专利所提出的在基于多服务器的支持NFV的运营商网络部署服务功能链的方法部署在运营商网络中支持NFV技术的通用的服务器上，每个通用的服务器上的节点软件可以调度自身带有的查询功能更新全网信息，获取网络中所有节点、链路的活性及其资源情况等信息。当网络中有节点或者链路损坏时，可以快速反映在用于决策的Q矩阵中，避免部署失败，并且及时提醒运营商去检查失效节点或链路。

通过这种集中式的控制方式来决策下一次需求到来时的部署方案，计算出链路选择，部署成本等关键参数，并反馈给运营商决定部署与否。