Service Function Chain Deployment Algorithm Based on Longest Effective Function Sequence
-
摘要:
服务功能链的服务性能取决于功能的部署位置和数据传输路径的选择。针对资源有限的网络中的服务功能链部署问题，该文设计了一种基于最长有效功能序列(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.
-
表 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
-
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/JEIT170600LI 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.001LIANG 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. -
下载:
图(7) / 表(2)
计量
- 文章访问数: 1761
- HTML全文浏览量: 682
- PDF下载量: 57
- 被引次数: 0
