2.2.2 算法设计

本小节将介绍基于物理拓扑分层的SFC高效映射算法。首先解释分层子算法，然后阐述主体算法及分层子算法在其中的作用。

2.2.2.1　分层子算法

分层子算法的核心是对底层网络节点进行层次划分，利用分层信息辅助SFC部署算法进行节点探索和路径规划。该子算法是主体算法的关键部分，对最终SFC部署性能好坏有着举足轻重的作用。

分层子算法以SFC的发起用户为起始点，首先对拓扑进行整体分层，然后对每一层网络结构进行再分层，即整个底层网络拓扑将由一个一级分层结构和所有一级层内部的二级分层结构组成。定义为分层后的底层网络拓扑，记录着第x层的物理节点，记录着第x层的物理链路，则表示底层网络拓扑分层之后的最大层数。代表一级第x层内部的二级分层拓扑，代表以一级分层拓扑中第x层节点为起始点进行二级分层的第y层节点集合；代表以一级分层拓扑中第x层节点为起始点进行二级分层的第y层链路集合。为第x层的二级分层层数，、分别表示底层网络中物理节点总数和物理链路总数。分层结构的公式化描述如下：

式（2-3）表明整体分层拓扑结构由每层的节点集合与链路集合构成。式（2-4）表明分层子算法将建立一个以每个节点为起始点的二级分层拓扑结构，其中只包含一级层内部节点及链路。式（2-5）意味着每个节点可能同时存在于数层中，因而所有层的节点数目加起来可能大于节点总数。允许节点处于多个层中有利于寻路算法快速进行SFC部署。需要注意的是，SFC的起始点只能被分在一个层中，以避免SFC形成环路而折损性能。式（2-6）则表明：一条链路要么被划分在一级分层拓扑中，要么被划分在二级分层拓扑中，即分层拓扑中所有链路总数应等于实际网络拓扑的链路总数。两级分层拓扑涵盖了物理网络的所有节点和链路信息，是原拓扑的新形式，且相比于原拓扑，分层拓扑蕴含了更多信息，更有利于辅助完成SFC的高效部署。

图2-2为两级分层拓扑示例图，图2-2（a）为底层物理网络拓扑，节点A、B分别为SFC的起始物理节点和目标物理节点。分层子算法首先将SFC起始物理节点A放到一级分层拓扑的第1层中，则当后续从高层向低层寻找最佳路径来部署VNF时，一定能追溯到起始节点，从而完成服务功能链的部署；随后将与A相连的节点B、C、D放入第2层，保证相邻高层节点和低层节点间存在连通的链路。VNF部署在底层网络节点上，它们之间的通信直接依赖于底层网络链路，如果不同VNF所在的底层物理节点间存在直连链路，则它们之间的通信更便捷，消耗的带宽资源也更少；接下来将与B、C、D节点相连的节点E、F、I放到第3层中，由于节点A是服务功能链的起始节点，只能存在于第1层中，因此尽管A与第2层节点相连，也未将其放到第3层中；与第3层中节点E、F、I相连的底层物理节点有B、C、D、G、H，但由于B、C、D节点同时也存在于E、F、I所在层的上一层，即第2层，相同的底层物理节点不能存在于中间间隔一层的分层网络拓扑中，所以不能将其放在第4层中，最终第4层只包含节点G和H。依次类推，直至为所有一级层填入了节点。完成一级分层后，检查每个一级层内部是否有节点互连，如果有则进行内部分层：第2层中的C、D两个节点处于互连状态，因此对第2层进行二级分层，分层规则和一级分层的一致。

图2-2　两级分层拓扑示例图

网络拓扑分层根据SFC起始位置将底层物理节点合理划分在不同的层次中，用相应的网络链路关联相邻层次，从而形成一级分层；但部分链路信息未在一级分层中体现出来，因此需要在一级层内部进行二级分层，使隐藏的链路信息显露出来。两级分层机制没有对底层网络的节点或链路做任何改变，却以一种更契合SFC部署的方式对物理网络进行了全新呈现。给出了分层子算法伪码。

2.2.2.2　带宽资源开销优化算法

算法2-1完成了底层网络拓扑的两级分层，其返回的分层信息GL将使用以辅助带宽资源开销优化算法，即主算法，进行SFC部署。

带宽资源开销优化算法在网络拓扑分层子算法之上完善了应对SFC请求的处理逻辑。在收到SFC请求时，主算法会首先调用分层算法，以SFC起点为初始点将整个底层拓扑进行重编排，完成两级分层任务。基于分层信息GL，主算法对SFC请求和底层拓扑的契合度做出初步判断，如通过对比该SFC长度和分层后网络拓扑的层数判断其是否超出当前底层网络的承受范围。若SFC长度约等于分层网络的最大层数，则两者比较契合，大概率能在不浪费底层网络资源的情况下进行部署；若SFC长度远大于分层网络的最大层数，则部署将十分困难，大概率无法部署，即便是部署成功也会消耗过多底层网络资源，降低网络的承载能力；若SFC长度远小于分层网络的最大层数，则能轻松部署该项服务，但可能会出现带宽资源浪费。

若初步判断的结论是可尝试部署，则主算法由低到高在层数大于SFC长度的一级层中寻找SFC目标节点。若找到目标节点，则从目标节点开始，由高到低逆向延伸SFC部署路径，直至到达起始节点。主算法在向下搜索节点时，始终保持节点可用计算资源和链路可用带宽资源满足SFC资源需求，并择优选择。若成功找到一条路径，则返回作为部署方案，若无法找到，则拒绝该SFC。算法2-2给出了主算法伪码。

算法2-2依靠分层子算法返回的信息，将部署VNF节点的候选对象从所有物理节点约束至某层的节点，极大缩小了搜索范围；相邻层次间的直连链路也大大缩短了串联这些节点的物理路径，因此较易得出可以承载SFC请求的高效部署方案。