一种区分等级的可生存服务功能链映射方法  

A Hierarchical Method for Survivable Service Function Chain Embedding

作　　者：刘艺[1,2] 张红旗 杨英杰[1,2] 常德显 Liu Yi;Zhang Hongqi;Yang Yingjie;Chang Dexian(PLA Information Engineering University,Zhengzhou 450001;Henan Key Laboratory of Information Security,Zhengzhou 450001)

机构地区：[1]解放军信息工程大学,郑州450001 [2]河南省信息安全重点实验室,郑州450001

出　　处：《计算机研究与发展》2018年第4期748-767,共20页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2012AA012704);郑州市科技领军人才项目(131PLJRC644)~~

摘　　要：针对在底层网络可能发生单点和单链路故障情况下的服务功能链(service function chain,SFC)映射问题,提出一种区分等级的可生存SFC映射方法,为提供重要服务的关键SFC预先分配备用资源,为提供普通服务的普通SFC快速重映射失效部分,从而兼顾提高SFC可生存能力和降低底层网络资源开销的需求.首先,在考虑最小化SFC服务时延的条件下,分别为关键SFC和普通SFC的可生存映射问题建立混合整数线性规划模型.其次,提出2种启发式的模型求解算法,其中,面向关键SFC的主备服务路径构建算法采用贪心思想交替进行节点和链路映射,以减小SFC服务时延,并在主备服务路径之间建立桥接路径,以提高路径切换速度和降低路径切换过程的丢包率;面向普通SFC的失效服务路径重建算法引入最大流问题求解失效节点的最佳重映射位置,以提高成功恢复的失效普通SFC数目,并利用改进的Dijkstra最短路径算法选择时延低的重映射路径.最后,在不同网络条件下实验验证了启发式算法的性能,并且在模拟网络环境中所提可生存SFC映射方法能保证SFC的成功运行率在59.2%以上.Aiming at embedding the service function chain(SFC)in substrate network under the condition of single-node or single-link failure,this paper proposes a hierarchical method for survivable SFC embedding.The method takes into account both improving the survivability of SFC and reducing the resource consumption of substrate network.For the key service function chain(KSFC)delivering essential services,it pre-allocates backup resources for possible failures in the future.Meanwhile,for the normal service function chain(NSFC)delivering common services,it quickly re-embeds the failed nodes and links after a failure has occurred.Firstly,taking into account minimizing the service latency of SFC,we provide two mixed integer linear programming(MILP)formulations for the survivable embedding problem of KSFC and NSFC.Secondly,we propose two heuristic algorithms to solve the formulations quickly,namely,the primary-backup service path building algorithm(PBSP-Bld)for the KSFC and the failed service path restoring algorithm(FSP-Res)for the NSFC.The PBSP-Bld not only embeds nodes and links alternately based on greedy strategy to reduce the service latency of SFC,but also establishes bridging path between the primary and the backup service paths,which improves the speed of path switching and reduces the packet loss rate during path switching.Additionally,the FSP-Res finds the best re-embedding positions for failed nodes by means of the max-flow problem,which increases the number of recovered NSFCs.It also uses the modified version of Dijkstra s shortest path algorithm to select re-embedding paths with low latency.Experimental results demonstrate the good performance of the heuristic algorithms under different network conditions.Moreover,the proposed method keeps the success ratio of running SFC above 59.2%under the simulated network environment.

关 键 词：服务功能链 可生存服务功能链映射 混合整数线性规划 最大流问题 服务时延 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]