一种基于改进深度优先搜索算法的业务链编排方法

技术领域

本申请涉及业务链编排技术领域，尤其涉及一种基于改进深度优先搜索算法的业务链编排方法。

背景技术

通过网络功能虚拟化(Network function virtualization,NFV)，网络功能部署为商品硬件上的模块化软件组件，可进一步链接提供服务，为网络运营商提供更大的灵活性和更低的服务部署成本。同时，用软件模块代替用专用硬件实现的网络功能，对于运营商来说保持相同的性能水平是一个很大的挑战。对最终用户承诺的服务等级在通常包含QoS参数的服务级别协议(Service-Level Agreement,SLA)中进行了形式化，例如最小保证数据速率，最大端到端延迟D

因此，如何在满足服务QoS要求的前提下，以最小的成本完成业务链的编排成为一个亟待解决的问题。

发明内容

本申请实施例提供了一种基于改进深度优先搜索算法的业务链编排方法，实现了在满足服务QoS要求的前提下，以最小的成本完成业务链的编排。

有鉴于此，本申请第一方面提供了一种基于改进深度优先搜索算法的业务链编排方法，所述方法包括：

构建业务链编排模型，所述业务链编排模型中包括由第一数量的服务器节点以及第二数量的交换机节点组成的物理网络以及任意所述服务器节点之间形成的物理链路；

通过改进DFS算法，获得所述业务链编排模型中满足业务端到端时延要求的可行路径集；

以所述业务链编排模型的总成本为目标，在满足所述业务链编排模型的带宽以及端到端时延要求的限制下，计算确定所述可行路径集中成本效益最高的路径。

可选地，所述通过改进DFS算法，获得所述业务链编排模型中满足业务端到端时延要求的可行路径集具体包括：

将所述业务链编排模型中按照包括所述服务器节点的数量，将所有业务链分类为N(s

计算确定所述N(s

通过改进DFS算法将所述原始路径集拓展为主VNF，得到可行路径集。

可选地，所述通过改进DFS算法将所述原始路径集拓展为主VNF，得到可行路径集具体包括：

将所述原始路径集中的第i条路径的起始服务器节点入栈；

判断当前栈是否为空，若所述当前栈为空，则得到一条可行路径并加入可行路径集，若所述当前栈为非空，则取出所述当前栈中最上面的服务器节点，并判断所述最上面的服务器节点的累计延迟Ω是否为1，若所述最上面的服务器节点的累计延迟Ω为1则删除所述最上面的服务器节点，并返回重新判断所述当前栈是否为空，否则将所述最上面的服务器节点标记为已访问；

将与标记为已访问的所述最上面的服务器节点相邻的未被访问的服务器节点加入所述当前栈中，并返回重新判断所述当前栈是否为空，直至所述原始路径集中的所有路径的起始服务器节点均入栈。

可选地，所述计算确定所述N(s

计算确定所述N(s

可选地，所述以所述业务链编排模型的总成本为目标，在满足所述业务链编排模型的带宽以及端到端时延要求的限制下，计算确定所述可行路径集中成本效益最高的路径具体包括：

以所述业务链编排模型的总成本

其中，c

可选地，所述第一约束条件具体为：

其中，cap(·)为服务器节点n

可选地，所述第二约束条件具体为：

其中，b

可选地，所述第三约束条件具体为：

可选地，所述第四约束条件具体为：

可选地，所述第五约束条件具体为：

其中，x

从以上技术方案可以看出，本申请实施例具有以下优点：

本申请实施例中，提供了一种基于改进深度优先搜索算法的业务链编排方法，建立业务链编排模型，考虑到业务链的时延要求，利用改进DFS算法对已经超出时延的路径预先排除，降低业务链编排的复杂度，最后以业务链编排模型的总成本为目标，计算确定成本效益最高的路径，即成本最低的路径，得到最有成本效益的路径，实现了在满足服务QoS要求的前提下，以最小的成本完成业务链的编排。

附图说明

图1为本申请实施例中一种基于改进深度优先搜索算法的业务链编排方法的方法流程图；

图2为本申请实施例中改进DFS算法的方法流程图；

图3为本申请实施例中通过改进DFS算法将原始路径集拓展为主VNF，得到可行路径集的方法流程图；

图4为本申请实施例中节点和链路的剩余资源情况的示意图；

图5为本申请实施例中链路的链路负载情况的示意图；

图6为本申请实施例中编排的效费比的示意图。

具体实施方式

为了使本技术领域的人员更好地理解本申请方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

本申请设计了一种基于改进深度优先搜索算法的业务链编排方法，实现了在满足服务QoS要求的前提下，以最小的成本完成业务链的编排。

为了便于理解，请参阅图1，图1为本申请实施例中一种基于改进深度优先搜索算法的业务链编排方法的方法流程图，如图1所示，具体为：

101、构建业务链编排模型，业务链编排模型中包括由第一数量的服务器节点以及第二数量的交换机节点组成的物理网络以及任意服务器节点之间形成的物理链路；

需要说明的是，底层的物理网络用加权无向图G＝(V,L)表示，其中V和L分别为物理网络节点集和链路集。具体的，物理网络包括两种节点类型：用作承载VNF的服务器节点，其第一数量表示为N，以及用于VNF之间流量转发的交换机节点，其第二数量表示为M。

102、通过改进DFS算法，获得业务链编排模型中满足业务端到端时延要求的可行路径集；

需要说明的是，改进DFS算法将业务链编排模型中满足业务链端到端时延要求的可行路径搜索出来，并形成可行路径集。

103、以业务链编排模型的总成本为目标，在满足业务链编排模型的带宽以及端到端时延要求的限制下，计算确定可行路径集中成本效益最高的路径；

需要说明的是，业务链编排的目标是在满足QoS质量要求的基础上尽可能减少网络运营商的资本支出和运营支出，同时满足带宽以及端到端时延要求，因此在上述两个限制条件下，计算确定可行路径集中成本效益最高的路径，即总成本最低的路径。

本申请实施例中，提供了一种基于改进深度优先搜索算法的业务链编排方法，建立业务链编排模型，考虑到业务链的时延要求，利用改进DFS算法对已经超出时延的路径预先排除，降低业务链编排的复杂度，最后以业务链编排模型的总成本为目标，计算确定成本效益最高的路径，即成本最低的路径，得到最有成本效益的路径，实现了在满足服务QoS要求的前提下，以最小的成本完成业务链的编排。

具体地，本申请实施例中的改进DFS算法的方法流程图如图2所示，具体为：

201、将业务链编排模型中按照包括服务器节点的数量，将所有业务链分类为N(s

需要说明的是，根据包括服务器节点的数量，将所有业务链分类为N(s

202、计算确定N(s

需要说明的是，在对业务链进行分类以后，计算确定每一类中成本最低的业务链来形成原始路径集。

进一步地，本申请实施例中，计算N(s

利用负载平衡因子，可以保证网络始终处于均衡的状态。

203、通过改进DFS算法将原始路径集拓展为主VNF，得到可行路径集；

需要说明的是，利用改进DFS算法，将原始路径集中的路径统一拓展为主VNF，以满足业务需求，从而得到可行路径集。应该指出的是，此时的扩展只包括创建新的主要VNF，而不是找到共享的VNF。这是因为通过查找共享VNF获得的新路径的成本必然大于具有原始路径集合中具有相同数量的主VNF的路径。

具体地，本申请实施例中的通过改进DFS算法将原始路径集拓展为主VNF，得到可行路径集的方法流程图如图3所示，具体为：

301、将原始路径集中的第i条路径的起始服务器节点入栈；

需要说明的是，通过改进DFS算法来拓展链接，首先将原始路径集中的第i条路径的起始服务器节点入栈。

302、判断当前栈是否为空，若当前栈为空，则得到一条可行路径并加入可行路径集，若当前栈为非空，则取出当前栈中最上面的服务器节点，并判断最上面的服务器节点的累计延迟Ω是否为1，若最上面的服务器节点的累计延迟Ω为1则删除最上面的服务器节点，并返回重新判断当前栈是否为空，否则将最上面的服务器节点标记为已访问；

需要说明的是，

303、将与标记为已访问的最上面的服务器节点相邻的未被访问的服务器节点加入当前栈中，并返回重新判断当前栈是否为空，直至原始路径集中的所有路径的起始服务器节点均入栈；

需要说明的是，在将最上面的服务器节点标记为已访问后，即累计延迟Ω不为1的情况下，由于当前栈为非空，因此需要拓展链路，将标记为已访问的服务器节点相邻的未被访问的服务器节点加入到当前栈中，并返回重新判断当前栈是否为空，直到原始路径集中的所有路径的起始服务器节点均已经入栈。

进一步地，本申请实施例中所构建的业务链编排模型具体为：

底层的物理网络用加权无向图G＝(V,L)表示，其中V和L分别为物理网络节点集和链路集。具体的，物理网络包括两种节点类型：用作承载VNF的服务器节点，其第一数量表示为N，以及用于VNF之间流量转发的交换机节点，其第二数量表示为M；

对于任意服务器节点n

对任意连接节点n

每一个业务请求都包含一个有一系列VNF v组成的业务链s，V＝{v

VNFv

一个业务链具有最小带宽需求B

本申请还定义了如下的二进制辅助变量来描述业务链的编排：

y

z

业务链编排的目标是在满足服务链QoS要求的基础上尽可能减少网络运营商的资本支出和运营支出，同时满足带宽和端到端延迟要求。目标函数可以表示为：

其中的第一项表示网络功能的安装成本，第二项表示消耗链路带宽的成本。

在以业务链编排模型的总成本为目标，寻找成本效益最高的路径时，存在以下约束条件：

第一约束条件：服务器节点的可用容量不小于服务器节点承载的编排网络功能所消耗的容量，具体为：

其中，cap(·)为服务器节点n

第二约束条件：业务链的虚拟链路映射到的物理链路的可用带宽不小于物理链路承载的虚拟链路所消耗的带宽，具体为：

其中，b

第三约束条件：业务链的虚拟链路映射过程中，除了源服务器节点和目的服务器节点外的其他物理节点的有向流量之和为0，具体为：

第四约束条件：分配给线性业务链的服务器节点仅有一条输入边和输出边，具体为：

第五约束条件：业务链编排后的附加时延不大于业务链的最大附加容忍时延的限制下，计算确定可行路径集中成本效益最高的路径，具体为：

其中，x

基于本申请实施例提供的一种基于改进深度优先搜索算法的业务链编排方法，本申请结合仿真实验提供了一个应用例，具体为：

在仿真实验中选择100个节点的物理网络，其中包含30个服务器节点和70个交换机节点。服务器节点的容量和链路带宽被设定为固定值。每个服务链由2-6个VNF组成根据Google Apps中SLA的要求，时延要求从毫秒级到秒级变化。在实验中，初始化设置了1000个动态连续发生地服务链请求。

为了展示我们算法的优越性，选择以下两种冗余备份算法作为对比。(1)MinCost算法：在VNF的迭代备份中，每次选择资源消耗最小的VNF，不考虑共享性进行备份，直到服务链完成编排。(2)Single-path算法：该算法在原链路上进行备份，备份VNF放置在被备份VNF同一链路的下游，以避免产生附件的链路成本和时延。

我们选择一下三个指标评价：a.剩余网络资源：包括服务器节点和链路的剩余容量；b.链路的负载均衡程度：所有链路已用带宽的方差；c.备份的效费比：备份成本与编排数量的比率。

a.剩余资源：剩余资源的多少影响网络的持续承载能力。图4展示了三种算法完成同等数量服务链的编排后，节点和链路的剩余资源情况。随着业务数量要求的提高，Q-SCR相比于MinCost和Single-path保持着较高的剩余节点资源，同时Q-SCR在扩展链路时由于考虑了均衡网络的负载，所以链路也保持较高的利用率，剩余资源也多余另外两种算法。这对网络后续承载新的服务有较大帮助。

b.负载均衡程度：图5表示三种算法完成编排后的链路负载情况。Q-SCR在扩展链路时优先选择负载小的链路，以避免因为局部业务负载大而导致网络瘫痪。从图中可以看出，随着业务数量的提高，编排任务的增多，Q-SCR相较于MinCost和Single-path，使得网络始终保持较为均衡的状况。

c.编排的效费比：这个指标用来评估算法的成本效率。从图6中可以看出，随着需求的增加，每种算法的效费比都有所下降，Q-SCR得出的效费比始终高于MinCost和Single-path，表现出较好的成本效率。

本申请的说明书及上述附图中的术语“第一”、“第二”、“第三”、“第四”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本申请的实施例例如能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

应当理解，在本申请中，“至少一个(项)”是指一个或者多个，“多个”是指两个或两个以上。“和/或”，用于描述关联对象的关联关系，表示可以存在三种关系，例如，“A和/或B”可以表示：只存在A，只存在B以及同时存在A和B三种情况，其中A，B可以是单数或者复数。字符“/”一般表示前后关联对象是一种“或”的关系。“以下至少一项(个)”或其类似表达，是指这些项中的任意组合，包括单项(个)或复数项(个)的任意组合。例如，a，b或c中的至少一项(个)，可以表示：a，b，c，“a和b”，“a和c”，“b和c”，或“a和b和c”，其中a，b，c可以是单个，也可以是多个。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统，装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(英文全称：Read-OnlyMemory，英文缩写：ROM)、随机存取存储器(英文全称：Random Access Memory，英文缩写：RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，以上实施例仅用以说明本申请的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围。