本发明公开了一种具有流量意识与能源感知的SFC动态部署方法，包括如下步骤：S1、检测当前的物理网络状态；S2：遍历SFC的VNF；S3、选出已开机部署集合；S4、执行BL‑BFS算法，得到最短路径并；S5、选出未开机部署集合；S6、执行BL‑BFS算法，得到最短路径；S7、选出已开机部署集合；S8、执行BL‑BFS算法，得到最短路径；S9、选出未开机部署集合；S10、执行BL‑BFS算法，得到最短路径；S11、输出最短路径组成的部署方案；S12、检查并释放到达在线工作时间的SR所占用的底层物理资源，实现SFC动态部署；本发明解决了现有技术存在的实用性低、网络资源利用率低以及部署效率低的问题。
1.一种具有流量意识与能源感知的SFC动态部署方法，其特征在于，包括以下步骤：S1：检测当前的物理网络状态，将已开机的节点加入到已开机集合中，未开机的加入到为未开机集合中；
S2：遍历服务功能链SFC的每一个虚拟化网络功能VNF，判断当前VNF是否为中间点，若是进入步骤S3，否则进入S7；
S3：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集，若是则进入步骤S5，否则进入步骤S4；
S4：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则进入步骤S5；
S5：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出用户服务请求SR的部署，否则进入步骤S6；
S6：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
S7：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集,若是则进入步骤S9，否则进入步骤S8；
S8：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点的跳数与距离SFC目的点的跳数之和最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则进入步骤S9；
S9：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出该条SR的部署，否则进入步骤S10；
S10：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个未开机节点跳数与距离SFC目的点跳数之和最小，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
S11：输出部署方案，根据部署方案，减去占用的底层物理资源，包括节点资源和带宽资源，并将部署成功的SR设置为工作状态的SR；
S12：定期检查每条处于工作状态的SR，判断其是否到达在线工作时间，若是则将其撤销，并释放其所占用的底层物理资源，实现SFC动态部署，否则重复步骤S12；
A-1：为除去部署SFC源、目节点的当前底层物理节点集合中每一个节点设置属性，包括访问痕迹visited、路径距离D以及父节点parents；
A-2：将上一个VNF的底层节点作为此次VNF的源节点，初始化每个节点的属性，初始化公式为：式中，visited＝flase为未被访问过；parents＝NULL为无父节点；
A-3：从初始化后的源节点开始搜索，设置源节点属性为：
式中，visited＝true为已被访问过；parents＝NULL为无父节点；
A-4：建立优先队列，进行初始化，并将源节点加入优先队列；
A-5：根据节点集合，得到满足带宽资源需求的优先队列及其对应的底层节点的路径距离；
A-6：将底层节点的路径距离与跳数约束进行比较，判断是否满足要求，若是则进入步骤A-7，否则该路径的目的点不可达，结束算法，并返回NULL，判断公式为：式中，Df为底层节点的路径距离； 为跳数约束；
A-7：根据优先队列和底层节点的路径距离，得到优先队列中源节点到底层节点间最少跳数的最短路径；
A-8：将底层节点的路径距离作为跳数，并输出最短路径和对应的跳数。
2.根据权利要求1所述的具有流量意识与能源感知的SFC动态部署方法，其特征在于，所述节点资源满足要求的判断公式为：式中， 为第j条到达SR的VNF fi资源需求；为物理节点vi的节点资源。
3.根据权利要求1所述的具有流量意识与能源感知的SFC动态部署方法，其特征在于，所述步骤A-5中，得到优先队列和底层节点的路径距离，包括如下步骤：A-5-1：遍历节点集合中与当前节点相邻的下一节点，并作为当前节点；
A-5-2：判断当前节点是否满足要求，若是则进入步骤A-5-3，否则进入步骤A-5-1，判断公式为：式中，visited＝flase为未被访问过； 为当前节点的带宽资源需求； 为上一节点u和当前节点v组成的链路luv的可用带宽资源；
A-5-3：更新当前节点的属性，并将当前节点加入到优选队列中，进入步骤A-5-4，更新公式为：式中，visited＝true为已被访问过；parents＝u为父节点为上一节点u；
A-5-4：判断当前节点是否为底层节点，若是则输出优选队列及其对应的路径距离，否则进入步骤A-5-1。
4.根据权利要求1所述的具有流量意识与能源感知的SFC动态部署方法，其特征在于，所述步骤A-7中，得到最短路径，包括如下步骤：A-7-1：建立点集，将优选队列中的源节点加入点集，并作为上一节点；
A-7-2：遍历优选队列中每个点，将父节点为上一节点的当前节点加入点集，并将当前节点作为上一节点；
A-7-3：判断当前节点是否为底层节点，若是将点集作为最短路径进行输出，否则进入步骤A-7-2。
5.根据权利要求1所述的具有流量意识与能源感知的SFC动态部署方法，其特征在于，同一条SFC请求的部署过程中，一个节点最多只能部署该条SFC上的一个VNF，公式为：式中， 为当前节点部署VNF的数量；f为当前VNF功能；SF为当前SFC请求中的VNF功能集合；sr为当前用户服务请求；SRs为SFC服务请求集合；v为当前节点；VG为物理网络节点集合。
一种具有流量意识与能源感知的SFC动态部署方法
技术领域
[0001] 本发明属于网络通讯技术领域，具体涉及一种具有流量意识与能源感知的SFC动态部署方法。
背景技术
[0002] 网络功能虚拟化(NFV)是一种转变以往依赖专业硬件来实现网络功能的新兴科技，它通过在虚拟化平台上运行软件模块，以降低成本和简化管理。其中虚拟网络功能(VNFs)可以被链接在一起来构成服务功能连SFC，以提供流量需要通过的网络服务。对于NFV的定义是：(1)NFV是定义、创造、管理网络的一种方式，这种方式是通过软件和自动化工具来代替专有网络设备来实现的；(2)NFV是解决基于专有硬件设施的网络元素日益增长的问题的一种解决方案，且其可以满足云计算、大数据以及互联网等的需求。
[0003] 现如今，关于NFV的研究成果就如雨后春笋般涌现出来了。关于资源利用率，网络安全，服务质量，响应时间，服务接受率以及能量开销等的研究慢慢变成了学术界和工业界竞相研究的对象。
[0004] 现有技术存在以下问题：
[0005] (1)为实现网络服务供应而高效部署VNFs是实现NFV目标的关键，而现有研究工作，大多是离线或是一次性的部署，忽略了VNFs的基本、动态(在线)部署和扩展需求，以及如何处理实际的时变交通量，实用性低；
[0006] (2)对于减少能源/资源开销方面的研究，现有研究仅仅是通过VNF的合并(尽可能把一条SFC的多个VNF部署在同一个物理节点)来达到节能效果，而忽略了大量服务器长时间的空载运行造成的能源浪费或频繁开启/关闭服务器而带来的能源消耗与机器磨损，网络资源利用率低；
[0007] (3)同一条SFC中的多个VNF共用相同物理节点将会受到资源方面的约束与性能方面的影响，导致部署效率低；
[0008] 综上所述，现有技术存在实用性低、网络资源利用率低以及部署效率低的问题。
发明内容
[0009] 针对现有技术中的上述不足，本发明提供的了一种实用性高、网络资源利用率高以及部署效率高的具有流量意识与能源感知的SFC动态部署方法，为网络运营商提供了高效率、低能耗的在线网络服务映射方案，最小化能源/资源开销，实现节能减排与资源的充分利用，同时部署效果高效、快速，提升用户的服务体验质量，解决了现有技术存在的实用性低、网络资源利用率低以及部署效率低的问题。
[0010] 为了达到上述发明目的，本发明采用的技术方案为：
[0011] 一种具有流量意识与能源感知的SFC动态部署方法，包括以下步骤：
[0012] S1：检测当前的物理网络状态，将已开机的节点加入到开机集合中，未开机的加入到为未开机集合中；
[0013] S2：遍历服务功能链SFC的每一个虚拟化网络功能VNF，判断当前VNF是否为中间点，若是进入步骤S3，否则进入S7；
[0014] S3：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集，若是则进入步骤S5，否则进入步骤S4；
[0015] S4：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则进入步骤S5；
[0016] S5：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出该条用户服务请求SR的部署，否则进入步骤S6；
[0017] S6：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
[0018] S7：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集,若是则进入步骤S9，否则进入步骤S8；
[0019] S8：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点的跳数与距离SFC目的点的跳数之和最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则进入步骤S9；
[0020] S9：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出该条SR的部署，否则进入步骤S10；
[0021] S10：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个未开机节点跳数与距离SFC目的点跳数之和最小，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
[0022] S11：输出部署方案，根据部署方案，减去占用的底层物理资源，包括节点资源和带宽资源，并将部署成功的SR设置为工作状态的SR；
[0023] S12：定期检查每条处于工作状态的SR，判断其是否到达在线工作时间，若是则将其撤销，并释放其所占用的底层物理资源，实现SFC动态部署，否则重复步骤S12。
[0024] 进一步地，节点资源满足要求的判断公式为：
[0025]
[0026] 式中， 为第j条到达SR的VNF fi资源需求；为物理节点vi的节点资源。
[0027] 进一步地，BL-BFS算法，包括如下步骤：
[0028] A-1：为除去部署SFC源、目节点的当前底层物理节点集合中每一个节点设置属性，包括访问痕迹visited、路径距离D以及父节点parents；
[0029] A-2：将上一个VNF的底层节点作为此次VNF的源节点，初始化每个节点的属性，初始化公式为：
[0030]
[0031] 式中，visited＝flase为未被访问过；parents＝NULL为无父节点；
[0032] A-3：从初始化后的源节点开始搜索，设置源节点属性为：
[0033]
[0034] 式中，visited＝true为已被访问过；parents＝NULL为无父节点；
[0035] A-4：建立优先队列，进行初始化，并将源节点加入优先队列；
[0036] A-5：根据节点集合，得到满足带宽资源需求的优先队列及其对应的底层节点的路径距离；
[0037] A-6：将底层节点的路径距离与跳数约束进行比较，判断是否满足要求，若是则进入步骤A-7，否则该路径的目的点不可达，结束算法，并返回NULL，判断公式为：
[0038]
[0039] 式中，Df为底层节点的路径距离； 为跳数约束；
[0040] A-7：根据优先队列和底层节点的路径距离，得到优先队列中源节点到底层节点间最少跳数的最短路径；
[0041] A-8：将底层节点的路径距离作为跳数，并输出最短路径和对应的跳数。
[0042] 进一步地，步骤A-5中，得到优先队列和底层节点的路径距离，包括如下步骤：
[0043] A-5-1：遍历节点集合中与当前节点相邻的下一节点，并作为当前节点；
[0044] A-5-2：判断当前节点是否满足要求，若是则进入步骤A-5-3，否则进入步骤A-5-1，判断公式为：
[0045]
[0046] 式中，visited＝flase为未被访问过； 为当前节点的带宽资源需求； 为上一节点u和当前节点v组成的链路luv的可用带宽资源；
[0047] A-5-3：更新当前节点的属性，并将当前节点加入到优选队列中，进入步骤A-5-4，更新公式为：
[0048]
[0049] 式中，visited＝true为已被访问过；parents＝u为父节点为上一节点u；
[0050] A-5-4：判断当前节点是否为底层节点，若是则输出优选队列及其对应的路径距离，否则进入步骤A-5-1。
[0051] 进一步地，步骤A-7中，得到最短路径，包括如下步骤：
[0052] A-7-1：建立点集，将优选队列中的源节点加入点集，并作为上一节点；
[0053] A-7-2：遍历优选队列中每个点，将父节点为上一节点的当前节点加入点集，并将当前节点作为上一节点；
[0054] A-7-3：判断当前节点是否为底层节点，若是将点集作为最短路径进行输出，否则进入步骤A-7-2。
[0055] 进一步地，同一条SFC请求的部署过程中，一个节点最多只能部署该条SFC上的一个VNF，公式为：
[0056]
[0057] 式中， 为当前节点部署VNF的数量；f为当前VNF功能；SF为当前SFC请求中的VNF功能集合；sr为当前用户服务请求；SRs为SFC服务请求集合；v为当前节点；VG为物理网络节点集合。
[0058] 本方案的有益效果为：
[0059] (1)本发明提出能源感知路由对能源的消耗与带宽资源使用进行优化，在路由选择时，在规定的链路跳数约定内尽可能重用已经开启的服务器，减少全网络中服务器的开启数量，实现了节能的效果；
[0060] (2)本发明实现了在线的SFC的动态部署，对不定时到达的SFCs的服务请求，都有各自的在线生存时间，当这个时间到达时，便会将其撤销，同时释放算所占用的资源，从而继续共后面的SFCs使用；并且本发明在部署过程中，优先考虑选择已经开启的服务器，使得当前开启节点的网络资源得到充分的利用，提高了网络资源利用率；
[0061] (3)本发明在每部署一个VNF以及一条虚拟链路时实现了全网的资源情况，对于每一个部署到底层网络中的服务请求的部署方案都是接近全局最优的，腾出更多的资源来承载后面到来的请求，降低了部署阻塞率；
[0062] (4)本发明在实现节能的同时，还实现了链路跳数的约束情况，每条虚拟路径在底层网络中的部署路径越长，意味着最后的响应时间也将越大，在寻找合适的节点部署VNF时尽可能靠近父节点部署位置，大大的节约了全网搜索合适节点的时间，从而降低了请求部署的时间，提高了部署效率。
附图说明
[0063] 图1为具有流量意识与能源感知的SFC动态部署方法步骤S1-6流程图；
[0064] 图2为具有流量意识与能源感知的SFC动态部署方法步骤S7-12流程图；
[0065] 图3为BL-BFS算法流程图；
[0066] 图4为得到优先队列和底层节点的路径距离的方法流程图；
[0067] 图5为得到最短路径的方法流程图。
具体实施方式
[0068] 下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。
[0069] 一种具有流量意识与能源感知的SFC动态部署方法，如图1和图2共同所示，包括以下步骤：
[0070] S1：检测当前的物理网络状态，将已开机的节点加入到开机集合中，未开机的加入到为未开机集合中；
[0071] S2：遍历服务功能链SFC的每一个虚拟化网络功能VNF，判断当前VNF是否为中间点，若是进入步骤S3，否则进入S7；
[0072] S3：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集，若是则进入步骤S5，否则进入步骤S4；
[0073] S4：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则进入步骤S5；
[0074] S5：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出该条用户服务请求SR的部署，否则进入步骤S6；
[0075] S6：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点跳数最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，进入步骤S2，取出下一个VNF，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
[0076] S7：从已开机集合中选出资源满足要求的节点放入已开机部署集合，判断已开机部署集合是否为空集,若是则进入步骤S9，否则进入步骤S8；
[0077] S8：遍历已开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个部署节点的跳数与距离SFC目的点的跳数之和最少，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则进入步骤S9；
[0078] S9：从未开机集合中选出资源满足要求的节点放入未开机部署集合，判断未开机部署集合是否为空集，若是则返回SFC部署失败，清空部署方案，退出该条SR的部署，否则进入步骤S10；
[0079] S10：遍历未开机部署集合中的每一个节点，执行BL-BFS算法，并判断是否存在距离上一个未开机节点跳数与距离SFC目的点跳数之和最小，且满足条件的底层节点及其对应的最短路径，若是则将当前VNF部署在该底层节点，并将该部署节点及对应的最短路径作为的部署路径加入部署方案，SFC部署成功，进入步骤S11，否则返回SFC部署失败，清空部署方案，退出该条SR的部署；
[0080] S11：输出部署方案，根据部署方案，减去占用的底层物理资源，包括节点资源和带宽资源，并将部署成功的SR设置为工作状态的SR；
[0081] S12：定期检查每条处于工作状态的SR，判断其是否到达在线工作时间，若是则将其撤销，并释放其所占用的底层物理资源，实现SFC动态部署，否则重复步骤S12。
[0082] 本实施例中，节点资源满足要求的判断公式为：
[0083]
[0084] 式中， 为第j条到达SR的VNF fi资源需求；为物理节点vi的节点资源。
[0085] 本实施例中，BL-BFS算法，如图3所示，包括如下步骤：
[0086] A-1：为除去部署SFC源、目节点的当前底层物理节点集合中每一个节点设置属性，包括访问痕迹visited、路径距离D以及父节点parents；
[0087] A-2：将上一个VNF的底层节点作为此次VNF的源节点，初始化每个节点的属性，初始化公式为：
[0088]
[0089] 式中，visited＝flase为未被访问过；parents＝NULL为无父节点；
[0090] A-3：从初始化后的源节点开始搜索，设置源节点属性为：
[0091]
[0092] 式中，visited＝true为已被访问过；parents＝NULL为无父节点；
[0093] A-4：建立优先队列，进行初始化，并将源节点加入优先队列；
[0094] A-5：根据节点集合，得到满足带宽资源需求的优先队列及其对应的底层节点的路径距离，如图4所示，包括如下步骤：
[0095] A-5-1：遍历节点集合中与当前节点相邻的下一节点，并作为当前节点；
[0096] A-5-2：判断当前节点是否满足要求，若是则进入步骤A-5-3，否则进入步骤A-5-1，判断公式为：
[0097]
[0098] 式中，visited＝flase为未被访问过； 为当前节点的带宽资源需求； 为上一节点u和当前节点v组成的链路luv的可用带宽资源；
[0099] A-5-3：更新当前节点的属性，并将当前节点加入到优选队列中，进入步骤A-5-4，更新公式为：
[0100]
[0101] 式中，visited＝true为已被访问过；parents＝u为父节点为上一节点u；
[0102] A-5-4：判断当前节点是否为底层节点，若是则输出优选队列及其对应的路径距离，否则进入步骤A-5-1；
[0103] A-6：将底层节点的路径距离与跳数约束进行比较，判断是否满足要求，若是则进入步骤A-7，否则该路径的目的点不可达，结束算法，并返回NULL，判断公式为：
[0104]
[0105] 式中，Df为底层节点的路径距离； 为跳数约束；
[0106] A-7：根据优先队列和底层节点的路径距离，得到优先队列中源节点到底层节点间最少跳数的最短路径，如图5所示，包括如下步骤：
[0107] A-7-1：建立点集，将优选队列中的源节点加入点集，并作为上一节点；
[0108] A-7-2：遍历优选队列中每个点，将父节点为上一节点的当前节点加入点集，并将当前节点作为上一节点；
[0109] A-7-3：判断当前节点是否为底层节点，若是将点集作为最短路径进行输出，否则进入步骤A-7-2；
[0110] A-8：将底层节点的路径距离作为跳数，并输出最短路径和对应的跳数。
[0111] 本实施例中，同一条SFC请求的部署过程中，一个节点最多只能部署该条SFC上的一个VNF，避免出现闭环，并且已使用为部署节点(转发节点)的节点，不能再作为同一条SFC的转发节点(部署节点)，公式为：
[0112]
[0113] 式中， 为当前节点部署VNF的数量；f为当前VNF功能；SF为当前SFC请求中的VNF功能集合；sr为当前用户服务请求；SRs为SFC服务请求集合；v为当前节点；VG为物理网络节点集合。
[0114] 本发明提供的了一种实用性高、网络资源利用率高以及部署效率高的具有流量意识与能源感知的SFC动态部署方法，为网络运营商提供了高效率、低能耗的在线网络服务映射方案，最小化能源/资源开销，实现节能减排与资源的充分利用，同时部署效果高效、快速，提升用户的服务体验质量，解决了现有技术存在的实用性低、网络资源利用率低以及部署效率低的问题。
