基于最长有效功能序列的服务功能链部署算法

李丹; 兰巨龙; 王鹏; 胡宇翔

doi:10.11999/JEIT180402

基于最长有效功能序列的服务功能链部署算法

doi: 10.11999/JEIT180402

国家数字交换系统工程技术研究中心郑州 450000

基金项目: 国家863计划(2015AA016102)，国家自然科学基金(61521003, 61702547)

详细信息

作者简介:
李丹：男，1989年生，博士生，研究方向为新型网络体系结构

兰巨龙：男，1962 年生，教授，博士生导师，主要研究方向为网络体系结构、信息安全

王鹏：男，1985年生，博士，主要研究方向为新型网络体系结构、路由技术

胡宇翔：男，1982年生，博士，主要研究方向为新型网络体系结构、网络安全

通讯作者:
李丹　pkulidan@foxmail.com

中图分类号: TP393
计量
- 文章访问数: 1829
- HTML全文浏览量: 742
- PDF下载量: 57
- 被引次数: 0
出版历程
- 收稿日期: 2018-04-28
- 修回日期: 2018-10-10
- 网络出版日期: 2018-10-30
- 刊出日期: 2019-03-01

Service Function Chain Deployment Algorithm Based on Longest Effective Function Sequence

National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450000, China

Funds: The National 863 Program of China (2015AA016102), The National Natural Science Foundation of China (61521003, 61702547)

摘要

摘要:
服务功能链的服务性能取决于功能的部署位置和数据传输路径的选择。针对资源有限的网络中的服务功能链部署问题，该文设计了一种基于最长有效功能序列(LEFS)的服务功能链部署算法，以功能复用和带宽需求联合优化为目标，在控制路径长度的同时根据LEFS逐步搜索中继节点，直至满足服务请求。仿真结果表明，该算法能够均衡网络资源，同时优化网络的功能部署率和带宽利用率，与其他算法相比，网络资源利用率降低了10%，可以支持更多的服务请求，且算法计算复杂度低，可以实现对服务请求的快速响应。
- 服务功能链 /
- 最长有效功能序列 /
- 功能复用 /
- 带宽需求
Abstract:
The efficiency of Service Function Chain (SFC) depends closely on where functions are deployed and how to select paths for data transmission. For the problem of SFC deployment in a resource-constrained network, this paper proposes an optimization algorithm for SFC deployment based on the Longest Effective Function Sequence (LEFS). To optimize function deployment and bandwidth requirement jointly, the upper bound of path length is set and relay nodes are searched incrementally on the basis of LEFS until the service request is satisfied. Simulation results show that, the proposed algorithm can balance network resource and optimize the function deploymen rate and bandwidth utilization. Compared with other algorithms, the utilization of network resource decreases 10%, so that more service requests can be supported. What is more, the algorithm has a lower computation complexity and can response to service requests quickly.
- Service Function Chain (SFC) /
- Longest Effective Function Sequence (LEFS) /
- Function reuse /
- Bandwidth requirement

HTML全文

图 1 服务功能链部署示意图

下载: 全尺寸图片幻灯片

图 2 最长有效功能序列示意图

下载: 全尺寸图片幻灯片

图 3 各算法功能部署率

下载: 全尺寸图片幻灯片

图 4 各算法带宽利用率

下载: 全尺寸图片幻灯片

图 5 各算法网络资源综合利用率

下载: 全尺寸图片幻灯片

图 6 各算法可支持的服务请求数

下载: 全尺寸图片幻灯片

图 7 各算法平均响应时间

下载: 全尺寸图片幻灯片

表 1 算法1：最长有效功能序列函数

算法1：最长有效功能序列函数( ${\rm LEFS}\left( {z,S} \right)$ )
(1) $\varphi = {\text{functions along }}z$
(2) for $i = 1{\text{ to }}\left\| S \right\|$
(3) 　 for $j = 1{\text{ to }}\left\| \varphi \right\|$
(4) 　　　if ${S_i} = {\varphi _j}$
(5) 　　　　 ${\theta _{ij}} = {\theta _{i - 1j - 1}} + 1$ , ${\omega _{ij}} = {\omega _{i - 1j - 1}} + 1$
(6) 　　else if ${\varphi _j} = {\text{0}}$
(7) 　　　 ${\theta _{ij}} = {\theta _{i - 1j - 1}} + 1$ , ${\omega _{ij}} = {\omega _{ij - 1}}$
(8) 　　　else ${\theta _{ij}} = {\theta _{ij - 1}}$ , ${\omega _{ij}} = {\omega _{ij - 1}}$
(9) 　　　end if
(10) 　　end for
(11) 　　if ${\theta _{i\left\| \varphi \right\|}} < i$
(12) 　　　 $i = i - 1$ , break
(13) 　　end if
(14) end for
(15) ${\rm le} = {\theta _{i\left\| \varphi \right\|}}$ , ${\rm re} = {\omega _{i\left\| \varphi \right\|}}$ // $\rm le$ ：最长有效功能序列长度； $\rm re$ ：功能复用度
(16) ${\rm flag} = \left\| \varphi \right\|$
(17) for $k = i{\text{ to }}1$
(18) 　　for $j = {\rm flag}{\text{ to }}1$
(19) 　　　if ${S_k} = {\varphi _j}$ and ${\theta _{kj}} = k$ then
(20) 　　　　 ${\rm flag} = j$ , break
(21) 　　end if
(22) 　end for
(23) 　if $j < k$
(24) 　　for $j = {\rm flag}{\text{ to }}1$
(25) 　　　if ${\varphi _{2j}} = {\text{0}}$
(26) 　　　　break
(27) 　　　end if
(28) 　　end for
(29) 　　 ${\rm flag} = j$ , ${\rm de}\left( {{S_k}} \right) = {\varphi _j}$ // $\rm de$ ：剩余功能部署位置
(30) 　end if
(31) end for
(32) return $\rm le$ , $\rm re$ and $\rm de$

下载: 导出CSV

表 2 算法2：基于最长有效功能序列的服务功能链部署

算法2　基于最长有效功能序列的服务功能链部署
(1) for each service request ${r_i}$
(2) 　 ${v_0} = {o_i}$ , ${z_0} = \varnothing$ , $k = 0$
(3) 　while ${\rm LEFS}\left( {{z_k},{S_i}} \right).{\rm le} < \left\| {{S_i}} \right\|$
(4) 　　 $k = k + 1$ , ${h_k} = \varnothing$ // ${h_k}$ ：备选路径集合
(5) 　　for ${v_k} \in V$ and ${v_k} \notin {z_{k - 1}}$
(6) 　　　 ${z_k} = {z_{k - 1}} + {P_{{v_{k - 1}},{v_k}}}$
(7) 　　　calculate ${\rm LEFS}\left( {{z_k},{S_i}} \right)$ according to algorithm 1
(8) 　　　calculate ${u_i}$ according to Eq. (5)
(9) 　　　if $\left\| {{z_k}} \right\| + \left\| {{P_{{v_k},{t_i}}}} \right\| {\rm \le} {u_i}$ and ${\rm LEFS}\left( {{z_k},{S_i}} \right).{\rm le} > {\rm LEFS}\left( {{z_{k - 1}},{S_i}} \right).{\rm le}$
(10) 　　　　put ${z_k}$ into ${h_k}$
(11) 　　　end if
(12) 　　end for
(13) 　　select ${z_k}$ with the maximum ${g_{ik}}$ in ${h_k}$ according to Eq. 　　　　　(8)
(14) 　　update ${v_k}$ and ${z_k}$
(15) 　end while
(16) 　 $z \!=\! {z_k} \!+\! {P_{{v_k},{t_i}}}$ , deploy functions according to ${\rm LEFS}\left( {{z_k},{S_i}} \right).{ }$ de, and update ${C_E}$ and ${C_V}$
(17) end for

下载: 导出CSV

参考文献(19)

HAN Bo, GOPALAKRISHNAN V, JI Lusheng, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90–97. doi: 10.1109/MCOM.2015.7045396

QUINN P and GUICHARD J. Service function chaining: Creating a service plane via network service headers[J]. Computer, 2014, 47(11): 38–44. doi: 10.1109/MC.2014.328

LI Yong, ZHENG Feng, CHEN Min, et al. A unified control and optimization framework for dynamical service chaining in software-defined NFV system[J]. IEEE Wireless Communications, 2015, 22(6): 15–23. doi: 10.1109/MWC.2015.7368820

COHEN R, LEWIN-EYTAN L, NAOR J S, et al. Near optimal placement of virtual network functions[C]. 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2015: 1346–1354.

李丹, 兰巨龙, 王鹏, 等. 一种集中调控的分布式服务路径选择算法[J]. 电子与信息学报, 2018, 40(4): 785–793. doi: 10.11999/JEIT170600

LI Dan, LAN Julong, WANG Peng, et al. Distributed service path selection algorithm under central control[J]. Journal of Electronics &Information Technology, 2018, 40(4): 785–793. doi: 10.11999/JEIT170600

梁宁宁, 兰巨龙, 张岩. 基于分布式选择探测算法的服务路由机制[J]. 电子学报, 2017, 45(7): 1545–1552. doi: 10.3969/j.issn.0372-2112.2017.07.001

LIANG Ningning, LAN Julong, and ZHANG Yan. A service routing mechanism based on the distributed selection probing algorithm[J]. Acta Electronica Sinica, 2017, 45(7): 1545–1552. doi: 10.3969/j.issn.0372-2112.2017.07.001

XIA Ming, SHIRAZIPOUR M, ZHANG Ying, et al. Network function placement for NFV chaining in packet/optical datacenters[J]. Journal of Lightwave Technology, 2015, 33(8): 1565–1570. doi: 10.1109/JLT.2015.2388585

BARI M F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network & Service Management, 2016, 13(4): 725–739. doi: 10.1109/TNSM.2016.2569020

BARI M F, CHOWDHURY S R, AHMED R, et al. On orchestrating virtual network functions[C]. 2015 11th International Conference on Network and Service Management (CNSM), Barcelona, Spain, 2015: 50–56. doi: 10.1109/CNSM.2015.7367338.

KLINKOWSKI M A and WALKOWIAK K. On the advantages of elastic optical networks for provisioning of cloud computing traffic[J]. IEEE Network, 2013, 27(6): 44–51. doi: 10.1109/MNET.2013.6678926

ZHANG Liang and ZHU Zuqing. Spectrum-efficient anycast in elastic optical inter-datacenter networks[J]. Optical Switching & Networking, 2014, 14(4): 250–259. doi: 10.1016/j.osn.2014.05.018

XIE Lijun, JIANG Yiming, WANG Binqiang, et al. An approach for network function combination based on least busy placement algorithm[J]. China Communications, 2016, 13(Sup): 167–176. doi: 10.1109/CC.0.7560888

MEHRAGHDAM S, KELLER M, and KARL H. Specifying and placing chains of virtual network functions[C]. 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet), Luxembourg, 2014: 7–13.

LONG Qu, ASSI C, SHABAN K, et al. A reliability-aware network service chain provisioning with delay guarantees in NFV-enabled enterprise datacenter networks[J]. IEEE Transactions on Network & Service Management, 2017, 14(3): 554–568. doi: 10.1109/TNSM.2017.2723090

MECHTRI M, GHRIBI C, and ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 533–546. doi: 10.1109/TNSM.2016.2598068

YANG Ke, ZHANG Hong, and HONG Peilin. Energy-aware service function placement for service function chaining in data centers[C]. 2016 IEEE Global Communications Conference (GLOBECOM), Washington, D.C., USA, 2016: 1–6.

FANG Wenjian, ZENG Menglu, LIU Xiahe, et al. Joint spectrum and IT resource allocation for efficient vNF service chaining in inter-datacenter elastic optical networks[J]. IEEE Communications Letters, 2016, 20(8): 1539–1542. doi: 10.1109/LCOMM.2016.2580151

KUO Tungwei, LIOU Bangheng, LIN Kate Chingju, et al. Deploying chains of virtual network functions: On the relation between link and server usage[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1562–1576. doi: 10.1109/TNET.2018.2842798

SALAMA H F. Multicast Routing for Real-time Communication of High-speed Networks[M]. Raleigh, USA, North Carolina State University, 1996: 198.

施引文献

资源附件(0)

访问统计