A Spatial and Temporal Optimal Method of Service Function Chain Orchestration Based on Overlay Network Structure
-
摘要: 网络功能虚拟化(NFV)的引入大幅降低了互联网业务的运营成本。针对现有的服务功能链(SFC)编排方法无法在优化底层资源的同时保证业务时延性能的问题,该文提出一种基于重叠网络结构的SFC时空优化编排策略。在将计算、网络资源与细粒度时延约束纳入考虑的基础上,该策略通过建立重叠网络模型实现了计算与网络资源的分离,将构建SFC所需的资源开销与相关时延共同抽象化为重叠网络链路权重,从而使SFC编排问题转化为易于求解的最短路径问题。对于需要批量处理的SFC集合设计了基于重叠网络的模拟退火迭代优化编排算法(ONSA)。通过对比实验证明了该策略下编排方案的平均端到端时延、链路资源占用率与运营开销相对其他方案分别降低29.5%, 12.4%与15.2%,请求接受率提高22.3%,虚拟网络功能(VNF)负载均衡性能得到显著提升。Abstract: With the introduction of Network Function Virtualization (NFV), the operating costs of operators can be greatly reduced. However, most existing Service Function Chain (SFC) orchestration researches can not optimize the resources utilization while guaranteeing the performance of service delay. A spatial and temporal optimal method of Service Function Chain (SFC) orchestration based on an overlay network structure is proposed. Based on the consideration of the restrictions such as computing resource, network resource and fine-grained end to end delay, this method separates the computing resource and network resource. The resources cost and related delay of SFC can be abstracted into the links weight of overlay network, which can help to convert the SFC orchestration problem into the shortest path problem that can be easily solved. As for the SFC requests set requiring batch processing, an Overlay Network based Simulated Annealing iterative optimal orchestration algorithm(ONSA) is designed. The simulation results demonstrate that the proposed orchestration scheme can reduce the end-to-end delay, the utilization ratio of link bandwidth resource and the operational expenditure by 29.5%, 12.4% and 15.2%, and the acceptance ratio of requests set can be improved by 22.3%. The performance of Virtual Network Function (VNF) load balancing can be significantly improved.
-
表 1 基于重叠网络的模拟退火迭代优化编排策略
输入: $G = (V,E)$, $I$,底层网络状态 SA参数$\{ {\tau _0},{\tau _{\min }},\rho ,L\} $ 输出: 集合$I$的时空优化编排方案${\rm{O}}{{\rm{S}}_{{\rm{opt}}}}$ (1) $\forall i \in I$,随机部署$\beta _i^k$生成${\rm{O}}{{\rm{S}}_{{\rm{init}}}}$ (2) 初始化参数,$\tau \leftarrow {\tau _0},{\rm{Objec}}{{\rm{t}}_{{\rm{now}}}} \leftarrow {\rm{Object}}({\rm{O}}{{\rm{S}}_{{\rm{init}}}})$ (3) while $\tau > {\tau _{\min }}$ do (4) for $l = 1:L$ do (5) if (rand<0.5) (6) 计算$\bar C_{{\rm{load}}}^{}$与${p_{{\rm{rem}}}}$并选择释放实例$m$ (7) 将经$m$处理的请求纳入${I_{{\rm{re}}}}$并释放$m$ (8) else (9) $\forall i \in I$,将${\delta _i} > \delta _i^{s,o}$的请求纳入${I_{{\rm{re}}}}$ (10) end for (11) for $i\;{\rm in}\;{I_{{\rm{re}}}}$ do (12) 依据$\beta _i^k$与底层网络状态构造${G_{{\rm{Overlay}}}}$ (13) 删除资源不足的节点与链路 (14) 计算链路权重$w_{{\rm{ver}}}^e$,$w_{{\rm{hor}}}^e$ (15) ${\rm{Path}}_{{\rm{Overlay}}}^i \leftarrow {\rm{Dijkstra}}(v_{{\rm{hor}}}^{1,{s_i}},v_{{\rm{hor}}}^{k + 1,{o_i}})$ (16) ${\rm{Pat}}{{\rm{h}}_i} \leftarrow {\rm{Path}}_{{\rm{Overlay}}}^i$ (17) end for (18) ${\rm{Object}}({\rm{O}}{{\rm{S}}_{{\rm{new}}}}) = \sum\nolimits_{i \in I} {[\varepsilon {\varphi _i} + (1 + \varepsilon ){\delta _i}]} $ (19) if ${\Delta _{{\rm{Obj}}}} < 0$ (20) ${\rm{O}}{{\rm{S}}_{{\rm{now}}}} \leftarrow {\rm{O}}{{\rm{S}}_{{\rm{new}}}}$ (21) else (22) ${P_{{\rm{acc}}}} = \exp ( - {\Delta _{{\rm{Obj}}}}/T)$ (23) $\tau \leftarrow \tau \rho $ (24) end while (25) ${\rm{O}}{{\rm{S}}_{{\rm{opt}}}} \leftarrow {\rm{O}}{{\rm{S}}_{{\rm{now}}}}$ 表 2 VNF参数
VNF 实例化开销(MIPS) 计算资源(MIPS) Packet处理时间(μs) Firewall 5 60 15 Encryption 5 60 15 IDS 8 40 20 NAT 4 60 15 -
邬江兴. 新型网络技术发展思考[J]. 中国科学: 信息科学, 2018, 48(8): 1102–1111. doi: 10.1360/N112018-00062WU Jiangxing. Thoughts on the development of novel network technology[J]. CIENTIA SINICA Informationis, 2018, 48(8): 1102–1111. doi: 10.1360/N112018-00062 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 E and NADEAU T. Problem statement for service function chaining[R]. IETF RFC-Informational, 2015. MOENS H and DE TURCK F. VNF-P: A model for efficient placement of virtualized network functions[C]. Proceedings of the 10th International Conference on Network and Service Management and Workshop, Rio de Janeiro, Brazil, 2014: 418–423. BARI F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725–739. doi: 10.1109/TNSM.2016.2569020 JANG I, SUH D, PACK S, et al. Joint optimization of service function placement and flow distribution for service function chaining[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2532–2541. doi: 10.1109/JSAC.2017.2760162 史久根, 张径, 徐皓, 等. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略[J]. 电子与信息学报, 2019, 41(4): 973–979. doi: 10.11999/JEIT180522SHI Jiugen, ZHANG Jing, XU Hao, et al. Joint optimization of virtualized network function placement and routing allocation for operational expenditure[J]. Journal of Electronics &Information Technology, 2019, 41(4): 973–979. doi: 10.11999/JEIT180522 陈卓, 冯钢, 刘蓓, 等. 运营商网络中面向资源碎片优化的网络服务链构建策略[J]. 电子与信息学报, 2018, 40(4): 763–769. doi: 10.11999/JEIT170641CHEN Zhuo, FENG Gang, LIU Bei, et al. Construction policy of network service chain oriented to resource fragmentation optimization in operator network[J]. Journal of Electronics &Information Technology, 2018, 40(4): 763–769. doi: 10.11999/JEIT170641 WEN Tao, YU Hongfang, SUN Gang, et al. Network function consolidation in service function chaining orchestration[C]. Proceedings of 2016 IEEE International Conference on Communications, Kuala Lumpur, Malaysia, 2016: 512–519. PEI Jianing, HONG Peilin, XUE Kaiping, et al. Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 11(8): 367–379. doi: 10.1109/TPDS.2018.2880992 陈卓, 冯钢, 刘蓓, 等. 运营商网络中面向时延优化的服务功能链迁移重配置策略[J]. 电子学报, 2018, 46(9): 2229–2237. doi: 10.3969/j.issn.0372-2112.2018.09.026CHEN Zhuo, FENG Gang, LIU Bei, et al. Delay optimization oriented service function chain migration and re-deployment in operator network[J]. Acta Electronica Sinica, 2018, 46(9): 2229–2237. doi: 10.3969/j.issn.0372-2112.2018.09.026 ARTEAGA C H T, RISSOI F, and RENDON O M C. An adaptive scaling mechanism for managing performance variations in network functions virtualization: A case study in an NFV-based EPC[C]. Proceedings of the 13th International Conference on Network and Service Management, Tokyo, Japan, 2017: 1–7. LI Tong, BAUMBERGER D, HAHN S, et al. Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin[C]. Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Raleigh, USA, 2009: 65–74. AGARWAL S, MALANDRINO F, CHIASSERINI C F, et al. VNF placement and resource allocation for the support of vertical services in 5G networks[J]. IEEE/ACM Transactions on Networking, 2019, 27(1): 433–446. doi: 10.1109/TNET.2018.2890631 LANGE S, GRIGORJEW A, ZINNER T, et al. A multi-objective heuristic for the optimization of virtual network function chain placement[C]. Proceedings of the 29th International Teletraffic Congress, Genoa, Italy, 2017: 152–161. WANG Xiaoke, WU Chuan, LE F, et al. Online VNF scaling in datacenters[C]. Proceedings of the IEEE 9th International Conference on Cloud Computing, San Francisco, USA, 2016: 140–147.