臺灣博碩士論文加值系統

虛擬網路功能(VNF)可以將傳統以硬體實作的網路功能或服務重新實作成可以動態啟動執行的軟體。透過網路功能虛擬化(NFV)的技術，VNF可以直接在泛用的硬體上執行，再結合滿足使用者位置限制的多連接邊緣計算系統(MEC)與資源容量充足的雲端系統(Cloud)，使VNF具有動態布建與撤除的彈性。服務鏈(SFC)有序地連接多個獨立VNF來提供特定網路服務。透過這個特性，我們設計動態調整SFC的機制，來應付網路狀態的可能動態變化以及伺服器或實體連結失效(failure)的可能性。我們利用賽局理論來設計多個SFC部署機制。每個SFC視為追求最小化延遲與成本的玩家，同時要滿足運算節點與網路連結的資源限制。我們證明多個SFC部署賽局為一個潛在賽局(potential game)，此賽局至少有一個納許均衡點(Nash Equilibrium)與有限改善性質(finite improve property)。透過這些特性，我們利用最佳回應(best response; BR)演算法與空間適應性策略(spatial adaptive play; SAP)演算法來求解上述賽局。最後我們的模擬結果顯示SAP 可以有效找到全域最佳解，而BR的收斂速度快，可以因應不同網路狀態的變化來做動態調整，並且只影響少部分的使用者。

Virtual Network Function (VNF) can turn network functions or services traditionally implemented in hardware into software that can be dynamically activated and executed. Through Network Function Virtualization (NFV) technology, VNF can directly execute on general-purpose hardware, combined with multi-access edge computing (MEC) that meets user location constraints and cloud with sufficient resource capacity, which enables VNFs to have the flexibility to dynamically deploy and remove. Service Function Chain (SFC) connects multiple independent VNFs in an orderly manner to provide specific network services. With this feature, we design a mechanism for dynamically adjusting the service function chain (SFC) to cope with dynamic changes in network status and failures of the server or entity link. We propose a game-theoretic approach to multiple SFC deployment. Each SFC is viewed as a player whose goal is to minimize latency and cost while meeting the resource constraints of computing nodes and network connections. We prove that the proposed SFC deployment game is a potential game with at least one Nash equilibrium and finite improve property. With these features, we use the best response (BR) algorithm and the spatial adaptive play (SAP) algorithm for game playing. Our simulation results show that SAP can effectively find the global optimal. On the other hand, BR has a fast convergence speed, adapts well to network dynamics, and only affects a small number of users.

摘要............................ ................. i
Abstract.......................... ................. ii
Table of Contents ..................................... iii
List of Figures ....................................... v
List of Tables........................................ vi
1 Introduction....................................... 1
2 Related Work...................................... 5
3 System Model...................................... 8
3.1 NFV Infrastructure ................................ 8
3.2 User........................................ 8
3.3 Service Function Chain Deployment Decisions . . . . . . . . . . . . . . . . . 9
4 Problem Formulation ................................. 11
4.1 User Latency ................................... 11
4.1.1 Processing Latency............................ 11
4.1.2 Context Switch Latency ......................... 12
4.1.3 Propagation Latency............................ 12
4.2 User Cost ..................................... 13
4.2.1 Operating Cost .............................. 13
4.2.2 Migration Cost .............................. 13
4.3 Overall Penalty Function and Constraint..................... 14
5 Game Formulation................................... 16
5.1 Constraint Relaxation............................... 16
5.2 Game Mechanism................................. 17
6 Proposed Approaches ................................. 20
6.1 Best Response Iterative Algorithm........................ 20
6.2 Spatial Adaptive Play Algorithm......................... 21
7 Numerical Results ................................... 23
7.1 Simulation Setting ................................ 24
7.2 Convergence of The Game ­Based Approaches. . . . . . . . . . . . . . . . . . 26
7.3 Incremental Addition of Users .......................... 28
7.4 Adaptation to Dynamic Participation....................... 30
7.5 Adaptation to Node Failures ........................... 31
7.6 Adaptation to Link Failures............................ 32
8 Conclusion ....................................... 34
References ......................................... 36
Appendix A Proof of Lemma 5.2.1 ........................... 40
Appendix B Proof of Lemma 5.2.2 ........................... 42
Appendix C Proof of Lemma 5.2.3 ........................... 44
Appendix D Proof of Lemma 5.2.4 ........................... 46 AppendixEProofofTheorem5.2.6........................... 47

[1] I.Benkacem,T.Taleb,M.Bagaa,andH.Flinck.OptimalVNFsplacementinCDNslicing over multi­cloud environment. IEEE Journal on Selected Areas in Communications, 36 (3):616–627, 2018.
[2] Y.Bi,M.Bunyakitanon,N.Uniyal,A.Bravalheri,A.Muqaddas,R.Nejabati,andD.Sime­ onidou. Distributed online resource allocation using congestion game for 5g virtual net­ work services. In 2019 IEEE Global Communications Conference (GLOBECOM), pages 1–7, 2019.
[3] S.Bian,X.Huang,Z.Shao,X.Gao,andY.Yang.Servicechaincompositionwithresource failures in NFV systems: A game­theoretic perspective. IEEE Transactions on Network and Service Management, 18(1):224–239, 2020.
[4] H. Cao, J. Du, H. Zhao, D. X. Luo, N. Kumar, L. Yang, and F. R. Yu. Resource­ability assisted service function chain embedding and scheduling for 6G networks with virtual­ ization. IEEE Transactions on Vehicular Technology, 70(4):3846–3859, 2021.
[5] D. Dietrich, A. Abujoda, A. Rizk, and P. Papadimitriou. Multi­provider service chain embedding with nestor. IEEE Transactions on Network and Service Management, 14(1): 91–105, 2017.
[6] S. D’Oro, L. Galluccio, S. Palazzo, and G. Schembra. Exploiting congestion games to achieve distributed service chaining in NFV networks. IEEE Journal on Selected Areas in Communications, 35(2):407–420, 2017.
[7] J. Jia, L. Yang, and J. Cao. Reliability­aware dynamic service chain scheduling in 5G networks based on reinforcement learning. In IEEE INFOCOM 2021­IEEE Conference on Computer Communications, pages 1–10, 2021.
[8] S.Knight,H.X.Nguyen,N.Falkner,R.Bowden,andM.Roughan.TheInternetTopology Zoo. IEEE Journal on Selected Areas in Communications, 29(9):1765–1775, 2011.
[9] S.Le,Y.Wu,andM.Toyoda.Acongestiongameframeworkforservicechaincomposition in NFV with function benefit. Information Sciences, 514:512–522, 2020.
[10] S. Le, Y. Wu, Y. Guo, and C. Del Vecchio. Game theoretic approach for a service function chain routing in NFV with coupled constraints. IEEE Transactions on Circuits and Systems II: Express Briefs, 68(12):3557–3561, 2021.
[11] S.­T. Le, Y. Wu, and X.­M. Sun. Congestion games with player­specific utility functions and its application to NFV networks. IEEE Transactions on Automation Science and En­ gineering, 16(4):1870–1881, 2019.
[12] A. Leivadeas, G. Kesidis, M. Ibnkahla, and I. Lambadaris. VNF placement optimization at the edge and cloud. Future Internet, 11(3):69, 2019.
[13] D.Li,P.Hong,K.Xue,andJ.Pei.Virtualnetworkfunctionplacementconsideringresource optimization and SFC requests in cloud datacenter. IEEE Transactions on Parallel and Distributed Systems, 29(7):1664–1677, 2018.
[14] J. Li, W. Shi, H. Wu, S. Zhang, and X. Shen. Cost­aware dynamic SFC mapping and scheduling in SDN/NFV­enabled space–air–ground­integrated networks for internet of ve­ hicles. IEEE Internet of Things Journal, 9(8):5824–5838, 2021.
[15] J. Li, W. Shi, Q. Ye, N. Zhang, W. Zhuang, and X. Shen. Multiservice function chain embedding with delay guarantee: A game­theoretical approach. IEEE Internet of Things Journal, 8(14):11219–11232, 2021.
[16] 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, 18(1):236–262, 2015.
[17] D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14(1): 124–143, 1996.
[18] J. Pei, P. Hong, K. Xue, and D. Li. Efficiently embedding service function chains with dynamic virtual network function placement in geo­distributed cloud system. IEEE Trans­ actions on Parallel and Distributed Systems, 30(10):2179–2192, 2018.
[19] A. Pentelas, G. Papathanail, I. Fotoglou, and P. Papadimitriou. Network service embed­ ding across multiple resource dimensions. IEEE Transactions on Network and Service Management, 18(1):209–223, 2020.
[20] C. Pham, N. H. Tran, S. Ren, W. Saad, and C. S. Hong. Traffic­aware and energy­efficient vNF placement for service chaining: Joint sampling and matching approach. IEEE Trans­ actions on Services Computing, 13(1):172–185, 2017.
[21] W. Rankothge, H. Ramalhinho, and J. Lobo. On the scaling of virtualized network func­ tions. In 2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM), pages 125–133, 2019.
[22] L. Ruiz, R. J. Durán, I. De Miguel, P. S. Khodashenas, J.­J. Pedreno­Manresa, N. Merayo, J. C. Aguado, P. Pavon­Marino, S. Siddiqui, J. Mata, P. Fernández, R. M. Lorenzo, and E. J. Abril. A genetic algorithm for VNF provisioning in NFV­enabled Cloud/MEC RAN architectures. Applied Sciences, 8(12):2614, 2018.
[23] I. Sarrigiannis, K. Ramantas, E. Kartsakli, P.­V. Mekikis, A. Antonopoulos, and C. Verik­ oukis. Online VNF lifecycle management in an MEC­enabled 5G IoT architecture. IEEE Internet of Things Journal, 7(5):4183–4194, 2019.
[24] M. Savi, M. Tornatore, and G. Verticale. Impact of processing­resource sharing on the placement of chained virtual network functions. IEEE Transactions on Cloud Computing, 9(4):1479–1492, 2019.
[25] X. Shang, Z. Liu, and Y. Yang. Network congestion­aware online service function chain placement and load balancing. In Proceedings of the 48th International Conference on Parallel Processing, pages 1–10, 2019.
[26] Y.­C. Tai and L.­H. Yen. Network service embedding in multiple edge systems: Profit maximization by federation. In ICC 2021­IEEE International Conference on Communi­ cations, pages 1–6, 2021.
[27] B. Yi, X. Wang, K. Li, S. k.Das, and M. Huang. A comprehensive survey of network function virtualization. Computer Networks, 133:212–262, 2018.
[28] H. P. Young. Individual strategy and social structure. Princeton University Press, 2020.
[29] Z.Zhou,Q.Wu,andX.Chen.Onlineorchestrationofcross­edgeservicefunctionchaining for cost­efficient edge computing. IEEE Journal on Selected Areas in Communications, 37(8):1866–1880, 2019.
[30] J. Zu, G. Hu, D. Peng, S. Xie, and W. Gao. Fair scheduling and rate control for service function chain in NFV enabled data center. IEEE Transactions on Network and Service Management, 18(3):2975–2986, 2021.