臺灣博碩士論文加值系統

網路功能虛擬化(Network Function Virtualization,NFV)在現今的網路技術已經成為不可或缺的一項技術，透過NFV技術可以更有效率的管理網路資源。網路服務供應商(Internet Service Provider,ISP)透過NFV技術部屬虛擬網路功能(Virtual Network Functions,VNF)來提供服務可以減少服務架設成本與管理成本。近年來研究中，透過安裝重複的VNF防止VNF故障並提高VNF的可靠度，由於實體設施中的計算資源量比起記憶體容量資源更為珍貴，因此有研究針對計算資源進行異地的備份保護，防止實體設施發生故障造成實體設施上的VNF無法正常運作。而實際上VNF將會被部署在不同的實體設施中，並透過鏈接的方式提供服務。因此在本篇論文中，我們會研究如何在網路中單一設施節點發生故障時，針對保護計算資源進行最小資源消耗的規劃，將VNF備份到延遲限制內的其他實體設施上且實體設施擁有足夠的計算資源可以啟用故障VNF。針對這個問題我們提出一種啟發式演算法(Extended Dominating-Set-Based Node Protection, EDSBNP)接著透過建立數學模型將問題轉化成整數線性規劃求解出最佳解並提出(Linear-Programming-Based Randomized-Rounding, LPBRR)來找出可行解。 最後會針對上述方法進行模擬與實驗。

Network Function Virtualization (NFV) has become an indispensable technology in current network technology. Through NFV technology, network resources can be managed more efficiently. Internet Service Providers (ISPs) can apply NFV technology to deploy Virtual Network Functions (VNFs) to provide network services while reducing the costs of service deployment and management.
Recently, installing duplicated VNFs to prevent from the failures of VNFs has received much attention and been widely studied to improve the reliability of the VNFs.Because the computing resource in a physical facility is often more limited and expensive compared to the storage resource, some research works study on how to efficiently back up computing resources for VNFs to prevent from the malfunction of physical facilities, where the computing resources required for the VNFs in one physical facility are assumed to be packaged and backed up to another physical facility. However, in reality, VNFs are often allowed to be deployed in different physical facilities. Therefore, in this thesis, we study how to schedule computing resources to back up VNFs to prevent from the failure of single facility node in networks such that the required resource is minimized when VNFs are able to be backed up to different physical facilities whose required latencies are allowed. For this problem, a heuristic, termed the Extended Dominating-Set-Based Node Protection (EDSBNP) algorithm, is first proposed. In addition, we also formulate the problem as an integer linear programming problem, which can be used to retrieve an optimal solution. Moreover, by relaxing the integrality constraints of the integer linear programming problem, a Linear-Programming-Based Randomized-Rounding (LPBRR) algorithm is proposed to find a feasible solution. Simulations are conducted to compare the proposed algorithms.

摘要.......................................................i
Abstract...................................................ii
誌謝.......................................................iii
目錄.......................................................iv
表目錄.....................................................vi
圖目錄.....................................................vii
第一章 緒論.................................................1
第二章 網路模型與問題定義...............................3
2.1 實體網路模型............................................3
2.2 虛擬網路模型............................................4
2.3 問題定義................................................5
第三章 資源備份規劃演算法....................................7
3.1 延遲限制關係圖..........................................7
3.2 節點啟用單一VNF.........................................9
3.3 節點啟用多個VNF........................................13
3.4 線性規劃...............................................14
3.4.1 整數線性規劃..........................................14
3.4.2 線性規劃.............................................18
3.4.3 基於線性規劃隨機進位..................................18
第四章 模擬實驗與結果分析....................................20
4.1 設施節點數量比較........................................20
4.2 設施節點最大資源量比較...................................22
4.3 鏈接最大延遲時間比較.....................................22
4.4 鏈接產生機率比較.........................................22
4.5 VNF最大計算資源量比較....................................23
4.6 啟用服務數量比較.........................................24
4.7 延遲限制大小比較.........................................24
第五章 結論..................................................26
5.1 研究結論.................................................26
5.2 未來展望.................................................26
參考文獻.....................................................27

[1] R. Szabo, M. Kind, F.-J. Westphal, H. Woesner, D. Jocha, and A. Csaszar,“Elastic network functions: Opportunities and challenges”, IEEE Network,vol. 29, no. 3, pp. 15–21, 2015. doi: 10.1109/MNET.2015.7113220.
[2] A. H. M. Jakaria, M. A. Rahman, and C. Fung, “A requirement-oriented design of nfv topology by formal synthesis”, IEEE Transactions on Network and Service Management, vol. 16, no. 4, pp. 1739–1753, 2019. doi: 10.1109/TNSM.2019.2920824.
[3] A. M. Alwakeel, A. K. Alnaim, and E. B. Fernandez, “A pattern for a virtual network function (vnf)”, in Proceedings of the 14th International Conference on Availability, Reliability and Security, ser. ARES ’19, Canterbury,CA, United Kingdom: Association for Computing Machinery, 2019, isbn:9781450371643.
[4] S. Sun, M. Kadoch, L. Gong, and B. Rong, “Integrating network function virtualization with sdr and sdn for 4g/5g networks”, IEEE Network, vol. 29,no. 3, pp. 54–59, 2015. doi: 10.1109/MNET.2015.7113226.
[5] S. Abdelwahab, B. Hamdaoui, M. Guizani, and T. Znati, “Network function virtualization in 5g”, IEEE Communications Magazine, vol. 54, no. 4,pp. 84–91, 2016. doi: 10.1109/MCOM.2016.7452271.
[6] M. A. Abdelaal, G. A. Ebrahim, and W. R. Anis, “High availability deployment of virtual network function forwarding graph in cloud computing environments”, IEEE Access, vol. 9, pp. 53 861–53 884, 2021. doi: 10.1109/ACCESS.2021.3068342.
[7] O. Houidi, O. Soualah, W. Louati, and D. Zeghlache, “Dynamic vnf forwarding graph extension algorithms”, IEEE Transactions on Network and Service Management, vol. 17, no. 3, pp. 1389–1402, 2020. doi: 10.1109/TNSM.2020.2990815.
[8] G. Sallam, G. R. Gupta, B. Li, and B. Ji, “Shortest path and maximum flow problems under service function chaining constraints”, in IEEE INFOCOM 2018 -IEEE Conference on Computer Communications, 2018, pp. 2132–2140. doi:10.1109/INFOCOM.2018.8485996.
[9] D. Zheng, C. Peng, X. Liao, L. Tian, G. Luo, and X. Cao, “Towards latency optimization in hybrid service function chain composition and embedding”,in IEEE INFOCOM 2020 - IEEE Conference on Computer Communications,2020, pp. 1539–1548.doi: 10.1109/INFOCOM41043.2020.9155529.
[10] A. Muhammad, I. Sorkhoh, L. Qu, and C. Assi, “Delay-sensitive multi-source multicast resource optimization in nfv-enabled networks: A column generation approach”, IEEE Transactions on Network and Service Management,vol. 18, no. 1, pp. 286–300, 2021. doi: 10.1109/TNSM.2021.3049718.
[11] Y. Xue and Z. Zhu, “On the upgrade of service function chains with heterogeneous nfv platforms”, IEEE Transactions on Network and Service Management, vol. 18, no. 4, pp. 4311–4323, 2021. doi: 10.1109/TNSM.2021.3103175.
[12] O. Alhussein and W. Zhuang, “Robust online composition, routing and nf placement for nfv-enabled services”, IEEE Journal on Selected Areas in Communications, vol. 38, no. 6, pp. 1089–1101, 2020. doi: 10.1109/JSAC.2020.2986612.
[13] F. Malandrino, C. F. Chiasserini, G. Einziger, and G. Scalosub, “Reducing service deployment cost through vnf sharing”, IEEE/ACM Trans. Netw.,vol. 27, no. 6, pp. 2363–2376, Dec. 2019. doi: 10.1109/TNET.2019.2945127.
[14] F. He, T. Sato, B. C. Chatterjee, T. Kurimoto, S. Urushidani, and E.Oki, “Robust optimization model for backup resource allocation in cloud provider”, in 2018 IEEE International Conference on Communications (ICC),2018, pp. 1–6. doi: 10.1109/ICC.2018.8422840.
[15] M. Karimzadeh-Farshbafan, V. Shah-Mansouri, and D. Niyato, “A dynamic reliability-aware service placement for network function virtualization(nfv)”,IEEE Journal on Selected Areas in Communications, vol. 38, no. 2, pp.318–333, 2020. doi: 10.1109/JSAC.2019.2959196.
[16] M. Huang, W. Liang, Y. Ma, and S. Guo, “Maximizing throughput of delaysensitive nfv-enabled request admissions via virtualized network function placement”, IEEE Transactions on Cloud Computing, vol. 9, no. 4, pp. 1535–1548, 2021. doi: 10.1109/TCC.2019.2915835.
[17] Y. T. Woldeyohannes, B. Tola, Y. Jiang, and K. K. Ramakrishnan, “Coshare:An efficient approach for redundancy allocation in nfv”, IEEE/ACM Transactions on Networking, vol. 30, no. 3, pp. 1014–1028, 2022. doi: 10.1109/TNET.2021.3132279.
[18] D. Zhai, X. Meng, Z. Yu, and X. Han, “Reliability-aware service function chain backup protection method”, IEEE Access, vol. 9, pp. 14 660–14 676,2021. doi: 10.1109/ACCESS.2021.3051045.
[19] F. Ben Jemaa, G. Pujolle, and M. Pariente, “Analytical models for qosdriven vnf placement and provisioning in wireless carrier cloud”, in Proceedings of the 19th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, ser. MSWiM ’16, 2016, pp. 148–155.doi:10.1145/2988287.2989154.
[20] J. Zhang, Z. Wang, C. Peng, L. Zhang, T. Huang, and Y. Liu, “Raba:Resource-aware backup allocation for a chain of virtual network functions”,in IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, 2019, pp. 1918–1926.doi: 10.1109/INFOCOM.2019.8737565.
[21] F. He, T. Sato, and E. Oki, “Backup resource allocation model for virtual networks with probabilistic protection against multiple facility node failures”, in 2019 15th International Conference on the Design of Reliable Communication Networks (DRCN), 2019, pp. 37–42. doi: 10.1109/DRCN.2019.8713736.
[22] C. Shelbourne, L. Linguaglossa, T. Zhang, and A. Lipani, “Inference of virtual network functions state via analysis of the cpu behavior”, in 2021 33th International Teletraffic Congress (ITC-33), 2021, pp. 1–9.
[23] C. Peng, D. Zheng, and X. Cao, “Minimum cost hybrid node protection in nfv”, in 2021 7th International Conference on Computer and Communications(ICCC), 2021, pp. 345–349. doi: 10.1109/ICCC54389.2021.9674656.
[24] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, and R.Boutaba, “Network function virtualization: State-of-the-art and research challenges”, IEEE Communications Surveys & Tutorials, vol. 18, no. 1,pp. 236–262, 2016. doi: 10.1109/COMST.2015.2477041.
[25] B. Martini, F. Paganelli, P. Cappanera, S. Turchi, and P.Castoldi,Latencyaware composition of virtual functions in 5g”, in Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft), 2015, pp. 1–6. doi:10.1109/NETSOFT.2015.7116188.
[26] S. Agarwal, F. Malandrino, C. F. Chiasserini, and S. De, “Vnf placement and resource allocation for the support of vertical services in 5g networks”,IEEE/ACM Trans. Netw., vol. 27, no. 1, pp. 433–446, Feb. 2019, issn:1063-6692. doi: 10.1109/TNET.2018.2890631.
[27] G. Lin, W. Zhu, and M. M. Ali, “An effective hybrid memetic algorithm for the minimum weight dominating set problem”, IEEE Transactions on Evolutionary Computation, vol. 20, no. 6, pp. 892–907, 2016. doi: 10.1109/TEVC.2016.2538819.
[28] V. V. Vazirani, Approximation algorithms. Springer, 2001, pp. I–IXI, 1–378,isbn: 978-3-540-65367-7.
[29] C. Peng, D. Zheng, S. Philip, and X. Cao, “Latency-bounded off-site virtual node protection in nfv”, IEEE Transactions on Network and Service Management,vol. 18, no. 3, pp. 2545–2556, 2021. doi: 10.1109/TNSM.2021.3096477.
[30] P. Erdos, A. Rényi, et al., “On the evolution of random graphs”, Publ.Math.
Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960.
[31] E. N. Gilbert, “Random graphs”, The Annals of Mathematical Statistics,vol. 30, no. 4, pp. 1141–1144, 1959.