基于重疊網(wǎng)絡(luò)結(jié)構(gòu)的服務(wù)功能鏈時空優(yōu)化編排策略
doi: 10.11999/JEIT190145
-
國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002
基金項目: 國家重點研發(fā)計劃(2017YFB0803204),國家自然科學(xué)基金(61521003, 61872382),廣東省重點領(lǐng)域研發(fā)計劃(2018B010113001)
A Spatial and Temporal Optimal Method of Service Function Chain Orchestration Based on Overlay Network Structure
-
National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China
Funds: The National Key Research and Development Project(2017YFB0803204), The National Natural Science Foundation of China (61521003, 61872382), The Research and Development Program in Key Areas of Guangdong Province (2018B010113001)
-
摘要: 網(wǎng)絡(luò)功能虛擬化(NFV)的引入大幅降低了互聯(lián)網(wǎng)業(yè)務(wù)的運營成本。針對現(xiàn)有的服務(wù)功能鏈(SFC)編排方法無法在優(yōu)化底層資源的同時保證業(yè)務(wù)時延性能的問題,該文提出一種基于重疊網(wǎng)絡(luò)結(jié)構(gòu)的SFC時空優(yōu)化編排策略。在將計算、網(wǎng)絡(luò)資源與細(xì)粒度時延約束納入考慮的基礎(chǔ)上,該策略通過建立重疊網(wǎng)絡(luò)模型實現(xiàn)了計算與網(wǎng)絡(luò)資源的分離,將構(gòu)建SFC所需的資源開銷與相關(guān)時延共同抽象化為重疊網(wǎng)絡(luò)鏈路權(quán)重,從而使SFC編排問題轉(zhuǎn)化為易于求解的最短路徑問題。對于需要批量處理的SFC集合設(shè)計了基于重疊網(wǎng)絡(luò)的模擬退火迭代優(yōu)化編排算法(ONSA)。通過對比實驗證明了該策略下編排方案的平均端到端時延、鏈路資源占用率與運營開銷相對其他方案分別降低29.5%, 12.4%與15.2%,請求接受率提高22.3%,虛擬網(wǎng)絡(luò)功能(VNF)負(fù)載均衡性能得到顯著提升。
-
關(guān)鍵詞:
- 網(wǎng)絡(luò)功能虛擬化 /
- 時空優(yōu)化 /
- 重疊網(wǎng)絡(luò) /
- 迭代優(yōu)化
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 基于重疊網(wǎng)絡(luò)的模擬退火迭代優(yōu)化編排策略
輸入: $G = (V,E)$, $I$,底層網(wǎng)絡(luò)狀態(tài) SA參數(shù)$\{ {\tau _0},{\tau _{\min }},\rho ,L\} $ 輸出: 集合$I$的時空優(yōu)化編排方案${\rm{O}}{{\rm{S}}_{{\rm{opt}}}}$ (1) $\forall i \in I$,隨機部署$\beta _i^k$生成${\rm{O}}{{\rm{S}}_{{\rm{init}}}}$ (2) 初始化參數(shù),$\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) 將經(jīng)$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) 依據(jù)$\beta _i^k$與底層網(wǎng)絡(luò)狀態(tài)構(gòu)造${G_{{\rm{Overlay}}}}$ (13) 刪除資源不足的節(jié)點與鏈路 (14) 計算鏈路權(quán)重$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}}}}$ 下載: 導(dǎo)出CSV
表 2 VNF參數(shù)
VNF 實例化開銷(MIPS) 計算資源(MIPS) Packet處理時間(μs) Firewall 5 60 15 Encryption 5 60 15 IDS 8 40 20 NAT 4 60 15 下載: 導(dǎo)出CSV
-
鄔江興. 新型網(wǎng)絡(luò)技術(shù)發(fā)展思考[J]. 中國科學(xué): 信息科學(xué), 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 史久根, 張徑, 徐皓, 等. 一種面向運營成本優(yōu)化的虛擬網(wǎng)絡(luò)功能部署和路由分配策略[J]. 電子與信息學(xué)報, 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 陳卓, 馮鋼, 劉蓓, 等. 運營商網(wǎng)絡(luò)中面向資源碎片優(yōu)化的網(wǎng)絡(luò)服務(wù)鏈構(gòu)建策略[J]. 電子與信息學(xué)報, 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 陳卓, 馮鋼, 劉蓓, 等. 運營商網(wǎng)絡(luò)中面向時延優(yōu)化的服務(wù)功能鏈遷移重配置策略[J]. 電子學(xué)報, 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. -