ISSN 1000-1239 CN 11-1777/TP

• 网络技术 •

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

1. (解放军信息工程大学 郑州 450001) (河南省信息安全重点实验室 郑州 450001) (liuyi9582@126.com)
• 出版日期: 2018-04-01
• 基金资助:
国家“八六三”高技术研究发展计划基金项目（2012AA012704）；郑州市科技领军人才项目（131PLJRC644）

### A Hierarchical Method for Survivable Service Function Chain Embedding

Liu Yi, Zhang Hongqi, Yang Yingjie, Chang Dexian

1. (PLA Information Engineering University, Zhengzhou 450001) (Henan Key Laboratory of Information Security, Zhengzhou 450001)
• Online: 2018-04-01

Abstract: 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.