2.3.3 算法设计

SFC部署算法的性能在很大程度上取决于部署路径的长度。因此，本小节设计了一个基于最短路径和SFC扩展的部署优化算法SFCDO。算法分为两个阶段。

（1）利用广度优先搜索（Breadth First Search，BFS）对物理网络拓扑进行预处理，找到源节点和目的节点之间的最短路径长度及不同跳数的节点分布。

（2）比较最短路径长度与SFC长度，根据对比结果采取相应的部署策略。

2.3.3.1　基于BFS的拓扑预处理

算法2-3给出了SFCDO算法的伪码：调用BFS算法，对源节点和目的节点之间的层序进行遍历，得到两个节点之间不同跳数的节点分布，以及两个节点之间最短路径长度。

算法2-3输入物理网络拓扑信息及SFC的源节点和目的节点，输出两个节点之间最短路径长度和不同跳数的节点分布。初始化过程创建一个队列queue并将其设置为空，初始化二维列表list1、一维列表list2和两个计数变量con1、con2，分别用于记录当前及下一跳中的节点数。length用于记录源节点和目的节点之间最短路径长度。

算法2-3第2行将源节点S加入queue。当queue不为空时，将迭代搜索下一个物理节点直到找到目的节点。第4行获取队首物理节点，将其标记为T，将T添加到list2中并将节点T标记为已访问，变量con1自减1。如果T是目的节点，则表示已经找到了源节点和目的节点之间满足资源约束条件的最短路径。于是，将list2添加到list1中，变量length自加1，算法2-3完成任务并返回length和list1；如果T不是目的节点，则需要遍历T的邻居节点。如果T的邻居节点V尚未被访问，则将V放入queue中，然后变量con2自加1。con1等于0表明已遍历当前跳数的所有节点，需要将list2加入到list1中并将list2重新置空用以记录下一跳节点。最后更新变量con1、con2及length的值。

图2-8展示了BFS算法示例。底层网络是由6个物理节点和7条物理链路组成的简单拓扑。图2-8（a）显示了初始化阶段，源节点s被添加到queue中，并且所有参数都被设置为它们的初始值；在图2-8（b）中，从队列中移除节点s标记为已访问并标记其跳数，然后访问节点s的邻居节点，发现新节点r和w并将它们加入到queue中。由于con1等于0，所以算法更新参数状态。

在图2-8（c）中，节点r被移除并添加到list2中，遍历节点r的邻居节点未发现新节点。在图2-8（d）中，遍历当前节点w的邻居节点得到节点t和x。此时con1等于0，算法更新参数状态。接下来，从queue中移除节点t并将其加入list2，遍历其邻居节点，发现d。节点d被添加到queue中，con2自加1，到达图2-8（e）所示的状态。在图2-8（f）中，算法从queue中取出x，由于con1等于0，所以算法更新这些参数状态。在图2-8（g）中，queue中弹出节点d，因为它是目的节点，所以算法达到终止条件，更新参数并返回length和list1。

在连通的网络拓扑中，算法2-3可以快速找到源节点、目的节点间最短路径的长度，以及不同跳数的节点分布。后续将基于算法返回的结果执行三种不同的SFC部署策略。

2.3.3.2　基于BFS的SFC部署算法

基于算法2-3返回的信息，比较最短路径和SFC长度，可得到3种结果：最短路径长度等于、小于或大于SFC长度。本小节的算法为每种结果提供了各自的部署方案。

式（2-30）定义了节点nk的最佳选择因子OSF(nk)，其中nc是当前选定的最后一个物理节点，其初始值为目的节点，λ为权重因子。OSF(nk)由链路时延和节点链路负载率加权而成，增加λ意味着更关注端到端时延，反之更重视负载率。后续实验观测了λ的变化对部署性能的影响。从式（2-31）中可以看出，delayrate(nk)的计算方法，SOCnode表示候选节点集合，其中的成员与上层或当前层节点相连。d(nc,nk)是连接节点nc和nk的链路的时延，分母是所有候选链路的最大时延。b(nk)是节点负载率，b(nc,nk)是相连链路的负载率。d(nc,nk)除以最大时延是为了让负载率在选择节点时具有更大的权重。算法将选择满足式（2-14）和式（2-21）约束且具有最小OSF的节点来部署当前VNF（VNL）。过程伪码见算法2-4。

算法2-4以物理拓扑、包含源节点和目的节点的SFC请求及算法2-3的返回信息为输入，在不断迭代中寻找物理节点来承载VNF，最终返回SFC的部署方案（如果能成功部署的话）。

算法2-4通过比较Lpath和LSFC的大小来决定部署方案。如果Lpath等于LSFC，则在前一跳节点分布中寻找物理节点以部署当前VNF，节点必须满足节点和链路资源约束，并且具有最小的OSF。如果Lpath大于LSFC，即两节点间最短路径长度大于SFC长度，在这种情况下，最短路径中存在冗余节点和链路，于是算法对SFC进行扩展：添加新的VNF和VNL，使Lpath等于LSFC。新增的VNL需要消耗带宽资源，因此需选择SFC中带宽资源需求最小的VNL进行扩展，但添加的VNF不消耗额外的计算资源。如果Lpath小于LSFC，则当前SFC不能部署在两节点之间的最短路上，则算法将在最短路径中的节点之间寻找其他节点扩展物理路径以匹配SFC长度。每次迭代首先尝试在当前跳节点集合中寻找物理节点，然后在上一跳节点集合中寻找物理节点。DS用于记录部署方案，算法结束时，通过比较SFC和部署方案DS来判断是否成功，并且计算部署SFC所产生的资源开销。

图2-9演示了基于BFS的SFC部署示例。图2-9（a）展示了算法2-3的输出，包括底层物理网络拓扑、两个节点之间最短路径的长度及不同跳数的节点分布信息。图2-9（b）展示了一条包含两个VNF和三条VNL的SFC请求示例。图2-9（c）展示了所有物理链路的端到端时延和负载率。图2-9（d）给出了所有节点的实时负载率。

示例中假设网络节点计算资源和链路带宽资源都满足资源需求。为了找到节点s和d之间的一条物理路径来部署SFC，算法2-4从目的节点开始搜索。由于SFC长度等于两个节点间最短路径长度，因此从d的上层开始搜索节点，如list1中所示，有两个候选节点t和x。两个节点的OSF如图2-9（e）所示。由于节点x的最优选择因子OSF小于节点t的OSF，所以选择节点x来部署vnf2，同时部署相应的VNL。然后从节点x开始，寻找承载下一个VNF的物理节点，候选节点是r和w。由于节点r不是节点x的邻居节点，所以只能选择w来部署vnf1。最后，找到了源节点s，成功部署该SFC，部署路径是s→w→x→d。图2-9（f）显示了SFC部署方案。

算法2-4是基于BFS和SFC扩展的部署方案。它优先选择源节点和目的节点间跳数较少的路径来部署SFC。由于部署路径的长度与端到端时延和带宽资源开销密切相关，因此算法可以同时优化这两项性能指标。此外，该算法引入最优选择因子OSF对平衡物理设备负载有积极影响。

2.3.3.3　算法复杂度分析

本小节提出的SFCDO算法由算法2-3和算法2-4组成。假设物理网络拓扑中存在|NP|个节点和|EP|条链路，则SFCDO算法的时间复杂度分析如下。

（1）算法2-3在源节点和目的节点间调用BFS搜索。过程中每个节点最多入队、出队一次，即队列操作的总时间为O(|NP|)。网络拓扑信息存储于邻接链表，算法只在节点出队时扫描出队节点的邻接链表，换言之，每个邻接链表最多扫描一次，即扫描相邻列表的总时间上界为O(|EP|)。因此，算法2-3的时间复杂度为O(|NP|+|EP|)。

（2）对于算法2-4，当Lpath≥LSFC时，每个节点和链路最多扫描一次，算法复杂度为O(|NP|+|EP|)。当Lpath<LSFC时，算法复杂度为O(2·(|NP|+|EP|))。因此，算法2-4的时间复杂度为O(|NP|+|EP|)。

综上，SFCDO算法部署一条SFC的时间复杂度是O(|NP|+|EP|)。